JP7493405B2 - Test method and computing device - Google Patents

Description

The present invention relates to a test method and a computing device.

Complex programs are generally difficult to verify. In fields with high software requirements, it is necessary to obtain 100% test coverage at the unit test level. In sequential programs, where the order of operations within a program is always constant, interdependencies rarely become an issue during testing, and the difficulty of testing is limited. On the other hand, testing is difficult for non-sequential programs, where the order of operations within a program is not constant.

Systems with large programs or high-speed processing, such as real-time systems such as advanced driver assistance systems (ADAS) and autonomous driving systems (ADS), use multiple processors. When conventional single-core systems are built on multi-core hardware, multiple systems can be integrated using automatic parallelization. In both cases, the number of possible execution orders within a program is huge, making safe integration difficult. When applying an automatic parallelizing compiler to conventional single-core software, another problem arises: can we actually verify that the parallelized code has the same functionality and behavior as the original code?

The idea of checking correct execution by the compiler was developed especially at the level of translation from a programming language to assembly code, where the use of directed acyclic graphs, known as program dependence graphs, has contributed greatly to improving the efficiency of binary code and automatic parallelization.

Patent Document 1 discloses a test support device that includes a scenario information storage means for storing information about a test scenario that defines a plurality of test nodes and processes between the test nodes, a test node information storage means for storing, for each test node, information about the test node including information identifying the test node to which the next transition should be made, and information about whether or not the process includes a branch path that branches off, a first judgment means for judging whether or not the branch path exists for each test node, a predicted execution time calculation means for calculating a predicted execution time required to complete a test when a snapshot is taken in a test node where the first judgment means judges that the branch path exists, an execution time calculation means for calculating an execution time required to complete a test without taking a snapshot, a time reduction calculation means for calculating, for each test node where a snapshot is taken, the difference between the execution time and the predicted execution time as a reduction time, a selection means for selecting a test node with the largest reduction time, and an output means for outputting information identifying the selected test node.

JP 2011-129028 A

The invention described in Patent Document 1 does not allow efficient testing of a specific macrotask when testing a program that includes multiple macrotasks that can be executed in multiple different orders.

A testing method according to a first aspect of the present invention is a testing method in which a computer tests a program including a plurality of macrotasks that can have a plurality of execution orders, and includes the steps of setting one of the plurality of macrotasks as a focus task, identifying an ancestor list which is a collection of the macrotasks that affect the focus task, classifying the macrotasks included in the ancestor list into a non-parallel group that does not contribute to parallelization and a parallel contribution group that contributes to parallelization, generating a plurality of test patterns for the parallel contribution group, and executing the plurality of test patterns using results obtained by executing the macrotasks belonging to the non-parallel group.
A calculation device according to a first aspect of the present invention includes a memory unit that stores a program including a plurality of macrotasks that can have a plurality of execution orders; a test calculation unit that sets one of the plurality of macrotasks as a focus task, identifies an ancestor list that is a collection of the macrotasks that affect the focus task, separates the macrotasks included in the ancestor list into a non-parallel group that does not contribute to parallelization and a parallel contribution group that contributes to parallelization, and generates a plurality of test patterns for the parallel contribution group; and a program execution unit that executes the plurality of test patterns using results obtained by executing the macrotasks belonging to the non-parallel group.

According to the present invention, when testing a program that includes multiple macrotasks that can be executed in multiple different orders, testing of specific macrotasks can be efficiently performed.

Hardware configuration diagram of the computing device Functional configuration diagram of the computing device A directed graph showing the program FIG. 13 is a diagram showing an example of an area table. A diagram showing test cases for each area in a program Flowchart showing the structural analysis process performed by the test calculation unit Flowchart showing the structural analysis process performed by the test calculation unit Flowchart showing the structural analysis process performed by the test calculation unit Flowchart showing table creation processing by the test calculation unit Flowchart showing memory dump processing by the test calculation unit Flowchart showing program testing by the test calculation unit Flowchart showing program testing by the test calculation unit Flowchart showing program testing by the test calculation unit

-First embodiment-
A first embodiment of a test method executed by a computing device will be described below with reference to FIGS.

(Hardware configuration)
1 is a hardware configuration diagram of a computing device 1 that executes a test method according to the present invention. The computing device 1 includes a CPU 2 that is a central processing unit, a ROM 3 that is a read-only storage device, a RAM 4 that is a readable and writable storage device, a storage unit 5 that is a non-volatile storage device, and an external interface 6. The CPU 2 realizes a plurality of functions described below by expanding a program stored in the ROM 3 into the RAM 4 and executing it. The storage unit 5 is, for example, a hard disk drive or a flash memory. However, it is not an essential component that the storage unit 5 is stored inside the computing device 1, and the computing device 1 may access the storage unit 5 installed outside the computing device 1 via the external interface 6.

The external interface 6 is an interface with the outside of the computing device 1, and may be targeted at either humans or computers. For example, it may be devices such as a mouse, keyboard, display, and printer targeted at humans, or the connection interfaces for these devices. It may also be a communications interface targeted at other computers, and a removable media read/write device. In the following, a human who operates the computing device 1 is referred to as an "operator."

(Functional configuration)
Fig. 2 is a functional configuration diagram showing the functions of the arithmetic device 1 as functional blocks. Fig. 2 also shows information stored in the memory unit 5. The arithmetic device 1 includes, as its functions, an input/output unit 21, a test arithmetic unit 22, and a program execution unit 23. The memory unit 5 stores a queue Q, a first stack S1, a second stack S2, a confirmed list CL, a processed list PL, an area table T100, and test target program information TP.

The queue Q, the first stack S1, the second stack S2, the confirmed list CL, and the processed list PL are targets that the test calculation unit 22 reads and writes, and are storage locations for data that the test calculation unit 22 uses during the processing. In this embodiment, this information is not output to the outside of the calculation device 1. The queue Q is a general queue used in the field of programming, and has the property that the first data input is the first data to be output. The first stack S1 and the second stack S2 are general stacks used in the field of programming, and have the property that the first data input is the last data to be output. The confirmed list CL and the processed list PL are collections of elements, and there is no order between the elements.

In this embodiment, the queue Q, the first stack S1, and the second stack S2 list their elements in the order they were input. For example, when the first stack S1 is empty, i.e., an empty set, and first "A", then "B", and finally "C" are input, i.e., pushed, into the first stack S1, the data in the first stack S1 is listed as "A, B, C".

The test target program information TP is information about a program that is to be tested by the arithmetic device 1. Hereinafter, the program that is to be tested by the arithmetic device 1 will be referred to as "program P1". The test target program information TP includes at least information that allows the program P1 to be created, such as source code and object files. As will be described later, the operation of the program P1 can be expressed using a directed acyclic graph. The directed acyclic graph showing the operation of the program P1 may be included in the test target program information TP, or may be created by the arithmetic device 1 using a known technique such as disassembly. The area table T100 stores information obtained by the test calculation unit 22 analyzing the program P1. This will be described in more detail later.

The input/output unit 21 acquires information necessary for the calculation, such as information related to the program P1 and instructions from an operator, from outside the calculation device 1, and outputs the calculation results to the outside of the calculation device 1 as necessary. The input/output unit 21 is realized by using the external interface 6 in addition to the calculation by the CPU 2.

The test calculation unit 22 performs various calculations required to test the program P1. The operation of the test calculation unit 22 will be mainly described below. The test calculation unit 22 first executes a structural analysis process to analyze the structure of the program P1 to be processed. In the structural analysis process, the program P1 is separated into a non-parallel group that does not contribute to parallelization and a parallel contribution group that contributes to parallelization. However, strictly speaking, in the structural analysis process, a second stack S2 is created that identifies the parallel contribution group among the macrotasks that make up the program P1. In other words, the macrotasks that make up the program P1 that are not identified by the second stack S2 are the non-parallel group.

After the structural analysis process, the test calculation unit 22 performs a table creation process that uses the results of the structural analysis process to compile information about each area included in the program P1 into an area table T100. Furthermore, the test calculation unit 22 performs a memory dump process to acquire a memory dump for efficient testing. Finally, the test calculation unit 22 executes a program test targeting a specified area. Note that the order in which the table creation process and the memory dump process are executed does not matter.

The program execution unit 23 executes the program P1 according to the operation command of the test calculation unit 22. However, the program execution unit 23 may execute the entire program P1 or may execute only a part of the program P1. Furthermore, the program execution unit 23 has a function to stop the execution of the program at a position specified by the test calculation unit 22. The program execution unit 23 may also emulate, by software, a processor built into the computer that executes the program P1, or the calculation device 1 may have a processor different from the CPU 2 and the program execution unit 23 may use that processor.

(Example of a program)
Program P1 can be decomposed into multiple processing units, and its operation is represented by an acyclic directed graph. In other words, the arithmetic device 1 can analyze any program as long as the operation can be represented using an acyclic directed graph. Hereinafter, each processing unit will be referred to as a "macrotask." A macrotask is one or more processes that do not include branching processes.

Figure 3 is a directed graph showing program P1, which is the processing target in this embodiment. Program P1 is composed of a total of 10 macrotasks: MT6, MT9, MT14, MT16, MT17, MT18, MT19, MT21, MT22, and MT23. The positional relationship of the macrotasks shown in Figure 3 is also related to the direction of the arrows, and all of the arrows point from the top to the bottom of the illustration, and are also said to point from ancestor to descendant. In other words, the higher up the illustration is, the more ancestor it is, and the lower down the illustration is, the more descendant it is.

When processing of program P1 begins, execution of MT14, the first ancestor, begins, and when execution of MT23, the last descendant, is completed, program P1 ends. Figure 3 shows that when MT14 is completed, MT16 to MT19 are each executed in no particular order. Below, the first ancestor in a given range is also referred to as the "root node," and the last descendant in a given range is referred to as the "terminal node." For example, in the entire range shown in Figure 3, the root node is MT6, and the terminal node is MT23.

In Figure 3, area A11 surrounded by a rectangle includes MT6, MT9, and MT14. Area A12 surrounded by a dashed line includes MT14, MT18, MT19, and MT21. Area A13 surrounded by a dashed line includes MT14, MT17 to MT19, MT21, and MT22. In area A11, the root node is MT6, and the terminal node is MT14. In area A12, the root node is MT14, and the terminal node is MT21.

(Area table T100)
Fig. 4 is a diagram showing an example of the area table T100. The area table T100 describes information on the parallel contribution group calculated by the test calculation unit 22. As will be described in detail later, the parallel contribution group calculated in the area table T100 differs depending on the set attention task. The example shown in Fig. 4 is an example in which the program P1 shown in Fig. 3 is targeted and the attention task is T22. Note that Fig. 4 merely conceptually represents the area table T100 in a table format, and it is not necessary to record in the table format, and a link to the actual data may be described in each cell of the table.

The area table T100 has one or more records, and each record has fields for program T101, area ID T102, parallelized binary T103, start task T104, end task T105, start point dump T106, end point dump T107, and directed graph T108. The program T101 stores an identifier for the program to be analyzed, such as the name of the program. The area ID T102 stores an identifier for the area, such as the name of the area.

Parallelized binary T103 stores a binary file that executes the process included in the area of that record, and that has been parallelized as much as possible. In other words, if parallelization is possible in that area, a binary file that has been parallelized is stored, and if parallelization is not possible in that area, a non-parallelized binary file is stored.

The start task T104 stores the name of the most ancestor macrotask contained in the area of that record. The end task T105 stores the name of the most descendant macrotask contained in the area of that record. The start point dump T106 stores memory dump information from the last processing of the start task T104. Note that memory dump information is also called a "memory snapshot."

The end point dump T107 stores memory dump information for the first processing of the end task T105. The directed graph T108 stores information on the directed graph of the macrotask included in the area of that record, for example, the directed graph shown in FIG. 3.

(test case)
FIG. 5 is a diagram showing test cases corresponding to each area shown in FIG. 3. The test cases are created by the test calculation unit 22. The test cases are a list of all macrotasks included in an area in the order of execution, and in the example shown in FIG. 5, all possible execution orders are listed. In this embodiment, a test case for area A11 is not created, but is shown in FIG. 5 for reference. Area A11 includes three macrotasks, which are connected in series in a straight line. In other words, there is no choice of execution order for the macrotasks in area A11, and only one case, case "A11-1", exists. Each task in area A11 must be executed in order, so it is a non-parallel group that does not contribute to parallelization.

Area A12 contains four macrotasks, with MT18 and MT19 existing in parallel. As a result, either MT18 or MT19 may be executed first, so area A12 has two cases, "A12-1" and "A12-2." Specifically, the first macrotask to be executed is fixed to be MT14, the last to be executed is fixed to be MT21, and the second and third macrotasks to be executed are either MT18 or MT19.

Area A13 contains six macrotasks, broadly speaking, the first group consisting of MT18, MT19, and MT21, and the second group consisting of only MT17, which exist in parallel. Furthermore, within the first group, MT18 and MT19 exist in parallel. The order of execution of the parallel macrotasks does not matter, and they may be executed at any time. Therefore, there are eight cases in area A13, "A13-1" to "A13-8".

(Flowchart of structure analysis process)
6 to 8 are flowcharts showing the structural analysis process by the test calculation unit 22. First, in step S100, the test calculation unit 22 initializes the queue Q, the first stack S1, the second stack S2, and the confirmed list CL. Specifically, the initialization process in this step sets the queue Q, the first stack S1, the second stack S2, and the confirmed list CL to be empty, that is, to an empty set.

In the next step S101, the test calculation unit 22 reads various information related to the program P1. In the next step S102, the test calculation unit 22 extracts a directed graph D1 from the information read in step S101. In the explanation of the operation example in this flowchart, the directed graph D1 extracted in this step is the directed graph illustrated in FIG. 3.

In the next step S103, the test calculation unit 22 determines a focus point X, which is one of the macrotasks MT included in the program P1. The focus point X may be automatically selected by machine processing, for example, a location where an error was found in the previous execution, or may be manually set by an operator. In the explanation of the operation example in this flowchart, the focus point X is "MT22". In the next step S104, the test calculation unit 22 creates an ancestor list C1 of the focus point X. When the directed graph D1 is as shown in FIG. 3 and the focus point X is "MT22", the ancestor list C1 is "MT6, MT9, MT14, MT17, MT18, MT19, MT21".

In the following step S105, the test calculation unit 22 sets the attention point X as the processing object Xi. In the following step S106, the test calculation unit 22 sets the processing object Xi as confirmed. Specifically, the test calculation unit 22 adds "MT22", which is the processing object Xi, to the confirmed list CL. When the processing of step S106 is completed, the test calculation unit 22 proceeds to step S106A.

In step S106A, the test calculation unit 22 determines whether there is an adjacent node of the unconfirmed processing target Xi in the ancestor list C1. An adjacent node is a node that is one node away, regardless of whether it is a descendant or ancestor, in other words, regardless of its position in the vertical direction. For example, in the example shown in Figure 3, the adjacent nodes of "MT22" are "MT17, MT21, and MT23."

If the test calculation unit 22 determines that there is an unconfirmed adjacent node of the processing target Xi in the ancestor list C1, it proceeds to step S107, and if it determines that all adjacent nodes of the processing target Xi included in the ancestor list C1 have been confirmed, it proceeds to step S107A. Specifically, the test calculation unit 22 first lists all adjacent nodes of the processing target Xi included in the ancestor list C1, and can make the judgment of this step based on whether or not they are listed in the confirmed list CL.

In step S107, the test calculation unit 22 determines whether the in-degree of the processing object Xi is greater than 1. If the test calculation unit 22 determines that the in-degree of the processing object Xi is greater than 1, the process proceeds to step S110, and if the test calculation unit 22 determines that the in-degree of the processing object Xi is not greater than 1, i.e., is equal to or less than 1, the process proceeds to step S107A.

In step S107A, the test calculation unit 22 judges whether or not there is an adjacent node of the confirmed processing target Xi in the ancestor list C1. Comparing the judgment in this step with step S106A, the difference is whether it is unconfirmed or confirmed. If the test calculation unit 22 judges that there is an adjacent node of the confirmed processing target Xi in the ancestor list C1, it proceeds to step S108, and if it judges that all adjacent nodes of the processing target Xi included in the ancestor list C1 are unconfirmed, it proceeds to step S109.

In step S108, the test calculation unit 22 determines whether the out-degree of the processing object Xi is greater than 1. If the test calculation unit 22 determines that the out-degree of the processing object Xi is greater than 1, the process proceeds to step S110, and if the test calculation unit 22 determines that the out-degree of the processing object Xi is 1 or less, the process proceeds to step S109. As a specific example of the in-degree and out-degree, in the example shown in FIG. 3, the in-degree of TM14 is "1" and the out-degree is "4".

In step S109, the test calculation unit 22 judges whether the processing object Xi corresponds to the source node XN in the ancestor list C1. If the test calculation unit 22 judges that the processing object Xi corresponds to the source node XN in the ancestor list C1, the process proceeds to step S110. If the test calculation unit 22 judges that the processing object Xi does not correspond to the source node XN in the ancestor list C1, the process proceeds to step S111. In step S111, the test calculation unit 22 extracts neighboring nodes of the processing object Xi and defines an adjacent group N. For example, in the example shown in FIG. 3, if the processing object Xi is "MT22", the adjacent group N is "MT17, MT21, MT23". When the process of step S111 is completed, the test calculation unit 22 proceeds to step S111A in FIG. 7 via the circled A. This concludes the explanation of FIG. 6.

In step S111A of FIG. 7, the test calculation unit 22 initializes the processed list PL. In the following step S119, the test calculation unit 22 judges whether all elements of the adjacent group N have been processed, and proceeds to step S120 if it judges that all elements have been processed, and proceeds to step S112 if it judges that unprocessed elements exist. In step S119, the test calculation unit 22 can make the judgment of step S119 by comparing the elements of the adjacent group N with the macrotasks listed in the processed list PL.

In step S112, the test calculation unit 22 extracts any unprocessed macrotask from the adjacent group N as element Ni. In the following step S112A, the test calculation unit 22 adds the element Ni extracted in step S112 to the processed list PL. In other words, the test calculation unit 22 adds the name of the macrotask extracted as element Ni in step S112 to the processed list PL. In the following step S113, the test calculation unit 22 judges whether or not the element Ni is included in the ancestor list C1. If the test calculation unit 22 judges that the element Ni is included in the ancestor list C1, the process proceeds to step S114, and if the test calculation unit 22 judges that the element Ni is not included in the ancestor list C1, the process returns to step S119.

In step S114, the test calculation unit 22 judges whether or not the element Ni has been confirmed, in other words, whether or not the element Ni is listed in the confirmed list CL. If the test calculation unit 22 judges that the element Ni has been confirmed, the process proceeds to step S115, and if the test calculation unit 22 judges that the element Ni has not been confirmed, the process proceeds to step S117. In step S115, the test calculation unit 22 judges whether or not the element Ni is included in the queue Q. If the test calculation unit 22 judges that the element Ni is included in the queue Q, the process proceeds to step S116, and if the test calculation unit 22 judges that the element Ni is not included in the queue Q, the process returns to step S119.

In step S117, the test calculation unit 22 adds element Ni to the end of the queue Q. In the following step S118, the test calculation unit 22 changes element Ni to confirmed. Specifically, the test calculation unit 22 adds the name of the macrotask extracted as element Ni to the confirmed list CL.

In step S120, which is executed if a positive judgment is made in step S119, the test calculation unit 22 judges whether or not queue Q is an empty set. If the test calculation unit 22 judges that queue Q is an empty set, it proceeds to step S601 in FIG. 8 via circled C, and if it judges that queue Q is not an empty set, it proceeds to step S121. Note that a positive judgment is made in step S120 when step S117 is not executed even once before step S120 is executed. In step S121, the test calculation unit 22 extracts the head of queue Q and sets it as the processing target Xi, and returns to step S106A in FIG. 6 via circled B. This concludes the explanation of FIG. 7.

In step S601, which is the first process shown in FIG. 8, the test calculation unit 22 assigns zero to the variable i and proceeds to step S602. In step S602, the test calculation unit 22 determines whether the length of the first stack S1 is longer than the value of "i+1". Note that the length of the first stack S1 is the number of macrotasks added to the first stack S1. If the test calculation unit 22 determines that the length of the first stack S1 is longer than the value of "i+1", the test calculation unit 22 proceeds to step S603, and if the test calculation unit 22 determines that the length of the first stack S1 is equal to or less than the value of "i+1", the test calculation unit 22 ends the process shown in FIG. 8.

In step S603, the test calculation unit 22 extracts the i+1th element in the first stack S1 from the directed graph D1, and creates an ancestor list of the extracted macrotask as a temporary ancestor list A00. As described above, in this embodiment, the element number of the first stack S1 is defined as the last added element as "0". If elements are added to the first stack S1 in the order of "MT22, MT21, MT14" and the value of the variable i is zero, the "i+1"th element of the first stack S1 is "MT21". <Ask a comment if this is correct> The ancestor list of this "MT21" is created as the temporary ancestor list A00. In this case, the temporary ancestor list A00 is "MT14, MT18, M19". The validity period of the temporary ancestor list A00 created in step S603 is the next time step S603 is executed or the end of the processing in FIG. 8, whichever is earlier.

In the following step S604, the test calculation unit 22 assigns the value of the variable i to the variable j and proceeds to step S605. In step S605, the test calculation unit 22 judges whether the value of the variable j is greater than "-1", and proceeds to step S606 if it judges that the variable j is greater than "-1", and proceeds to step S614 if it judges that the variable j is less than or equal to "-1". In step S606, the test calculation unit 22 identifies the macrotask that is the jth element in the first stack S1, and extracts the descendants of the macrotask from the ancestor list C1 to create a temporary descendant list D00. For example, if the jth element in the first stack S1 is "MT14" and the ancestor list C1 is "MT14, MT17, MT18, M19, MT21", the temporary descendant list D00 will be "MT17, MT18, MT19, MT21".

In the following step S607, the test calculation unit 22 extracts elements common to the temporary descendant list D00 created in step S606 and the temporary ancestor list A00 created in step S603 to create a duplicate list IS00. For example, if the temporary descendant list D00 is "MT17, MT18, MT19, MT21" and the temporary ancestor list A00 is "MT14, MT18, M19", the duplicate list IS00 is "MT18, M19". In the following step S608, the test calculation unit 22 calculates the value obtained by subtracting the outdegree from the indegree for each element of the duplicate list IS00, and calculates the sum of these values as SD00.

In the following step S609, the test calculation unit 22 calculates the out-degree in the macrotask of the j-th element in the first stack S1 as OD00. In the following step S610, the test calculation unit 22 calculates the in-degree in the macrotask of the j-th element in the first stack S1 as ID00. In the following step S610, the test calculation unit 22 uses the calculation results of steps S608 to S610 to determine whether the value obtained by subtracting ID00 from the sum of OD00 and SD00 is equal to or greater than zero. If the test calculation unit 22 judges step S610 as positive, the process proceeds to step S611, and if the test calculation unit 22 judges step S610 as negative, the process proceeds to step S613.

In step S611, the test calculation unit 22 inserts the i+1th element of the first stack S1 into the second stack S2. In the following step S612, the test calculation unit 22 inserts the jth element of the first stack S1 into the second stack S2 and proceeds to step S614. Note that steps S611 and S612 are so-called push operations on the second stack S2. In step S613, the test calculation unit 22 decreases the value of the variable j by "1" and returns to step S605. In step S614, the test calculation unit 22 increases the value of the variable i by "1" and returns to step S602. Step S613 is so-called decrement processing, and step S614 is so-called increment processing. This concludes the explanation of FIG. 8.

The first stack S1 generated by the processing of Figures 6 to 8 includes information indicating an area that includes a branch. The second stack S2 includes information indicating an area that includes a branch within the area included in the first stack S1.

(Example of structural analysis processing)
An example of the operation of the structural analysis process will be described. In the example of the operation described below, the description of the subject of the operation will be omitted, but all the subjects of the operation are the test calculation unit 22. An example will be described in which the directed graph D1 extracted in step S102 is that shown in FIG. 3, and the attention point X is "MT22". In this case, the ancestor list C1 generated in step S104 is "MT6, MT9, MT14, MT17, MT18, MT19, MT21". In step S106A, the test calculation unit 22 judges in the affirmative because the adjacent node of "MT22", which is the processing target Xi, exists in the ancestor list C1 and is not included in the confirmed list CL. Then, in step S107, the incoming degree of "MT22" is 2, so the test calculation unit 22 judges in the affirmative and proceeds to step S110, where the first stack S1 is updated to "MT22".

In step S111, the test calculation unit 22 defines adjacent group N as "MT17, MT21, MT23." In FIG. 7, the loop of S112 to S118 continues until all elements in adjacent group N are processed, so that the processes of S113 to S118 are performed on all elements included in adjacent group N in order as element Ni.

If element Ni is "MT17", step S113 is judged as positive, step S114 is judged as negative, steps S117 and S118 are executed, and the process returns to step S119. If element Ni is "MT21", step S113 is judged as positive, step S114 is judged as negative, steps S117 and S118 are executed, and the process returns to step S119. If element Ni is "MT23", step S113 is judged as negative, and the process returns to step S119.

Therefore, when a positive judgment is made the first time in step S119, queue Q is "MT17, MT21", confirmed list CL is "MT17, MT21, MT22", and first stack S1 is "MT22". In the following step S120, the test calculation unit 22 makes a negative judgment and proceeds to step S121, where it takes out the top "MT17" from queue Q and sets it as processing target Xi, and returns to step S106A in FIG. 6 via circled B. In other words, at the point of returning to S106A, the only element in queue Q is "MT21".

(Example of structural analysis process | After passing through B for the first time)
For "MT17", which is the processing target Xi, steps S106A and S107A are judged to be positive, but since the in-degree and out-degree of "MT17" are "1", steps S107 and S108 are judged to be negative. Furthermore, since "MT17" is not a source node in the ancestor list C1, the process proceeds to step S111. Here, "MT14, MT22", which are neighbors of "MT17", are defined as a new adjacent group N, and the process proceeds to FIG. 7.

In FIG. 7, first, the processes of S113 to S118 are performed on the elements of adjacent group N, "MT14, MT22," in order as element Ni. If element Ni is "MT14," step S113 is judged as positive, step S114 is judged as negative, steps S117 and S118 are executed, and the process returns to step S119. If element Ni is "MT22," step S113 is judged as positive, and step S114 is judged as positive due to the process in step S106. As "MT22" is not included in queue Q, a negative judgment is made and the process returns to step S119.

That is, when step S119 makes a positive determination for the second time, queue Q is "MT21, MT14", confirmed list CL is "MT17, MT21, MT22, MT14", and first stack S1 is "MT22". Here again, queue Q is not an empty set, so the process proceeds from step S120 to step S121, where the top element "MT21" is extracted from queue Q and set as processing target Xi, and the process returns to step S106A in FIG. 6. That is, at the point of returning to S106A, the only element in queue Q is "MT14".

(Example of structural analysis process | After passing through B for the second time)
For "MT21" which is the processing target Xi, a positive judgment is made in step S106A, and since the in-degree of "MT21" is "2", a positive judgment is made in step S107, and the process proceeds to S110, where "MT21" is added to the first stack S1. That is, the first stack S1 becomes "MT22, MT21". In the following step S111, "MT18, MT19, MT22", which are neighbors of "MT21", are defined as a new adjacent group N, and the process proceeds to FIG. 7.

In FIG. 7, first, the processes of S113 to S118 are performed for each of the elements of adjacent group N, "MT18, MT19, MT22," as element Ni. If element Ni is "MT18," step S113 is judged as positive, step S114 is judged as negative, steps S117 and S118 are executed, and the process returns to step S119.

If element Ni is "MT19", step S113 is judged as "YES", step S114 is judged as "NO", steps S117 and S118 are executed, and the process returns to step S119. If element Ni is "MT22", step S113 is judged as "YES", step S114 is judged as "YES", and since "MT22" is not included in queue Q, a negative judgment is made, and the process returns to step S119.

That is, when step S119 makes a positive determination for the third time, queue Q is "MT14, MT18, MT19", confirmed list CL is "MT17, MT18, MT19, MT21, MT22, MT14", and first stack S1 is "MT22, MT21". Here again, queue Q is not an empty set, so the process proceeds from step S120 to step S121, where the top element "MT14" is extracted from queue Q and set as processing target Xi, and the process returns to step S106A in FIG. 6. That is, at the point of returning to S106A, the elements of queue Q become "MT18, MT19".

(Example of structural analysis process | After passing through B for the third time)
For "MT14", which is the processing target Xi, all of the adjacent nodes "MT17, MT18, MT19" included in the ancestor list C1 are included in the confirmed list CL, so a negative judgment is made in step S106A, and a positive judgment is made in step S107A. And since the out-degree of "MT14" is greater than 1, a positive judgment is made in step S108, and the process proceeds to S110, where "MT14" is added to the first stack S1. That is, the first stack S1 becomes "MT22, MT21, MT14". In the following step S111, "MT9, MT16, MT17, MT18, MT19", which are neighbors of "MT14", are defined as a new adjacent group N, and the process proceeds to FIG. 7.

In FIG. 7, steps S113 to S118 are first performed on each of the elements of adjacent group N, "MT9, MT16, MT17, MT18, MT19," as element Ni. If element Ni is "MT9, MT16," it is not included in ancestor list C1, so a negative judgment is made in step S113 and the process returns to step S119. If element Ni is "MT17," it is a positive judgment in step S113, "MT17" has been confirmed so a positive judgment is made in step S114, and "MT17" is not included in queue Q so a negative judgment is made and the process returns to step S119.

When element Ni is "MT18, M19", steps S113, S114, and S119 are all judged as positive, and element Ni is added to the end of queue Q in step S116. That is, at this point, queue Q is "MT18, MT19", and first stack S1 is "MT22, MT21, MT14". Here too, queue Q is not an empty set, so the process proceeds from step S120 to step S121, where the top element "MT18" is extracted from queue Q and set as processing target Xi, returning to step S106A in FIG. 6. That is, at the point of returning to S106A, the element of queue Q becomes "MT19".

(Example of structural analysis process | After passing through B for the fourth time)
For "MT18" which is the processing target Xi, all of the adjacent nodes "MT14, MT21" are included in the confirmed list CL, so step S106A is judged as negative, and step S107A is judged as positive. In step S108, the outdegree of "MT14" is "1", so a negative judgment is made and the process proceeds to S109, and since "MT14" is not a source node, a negative judgment is made and the process proceeds to step S111. In step S111, "MT14, MT21", which are neighbors of "MT19", are defined as a new adjacent group N, and the process proceeds to FIG. 7.

In FIG. 7, steps S113 to S118 are first performed with each of the elements "MT14, MT21" of adjacent group N as element Ni. When element Ni is "MT14, MT21", both are included in ancestor list C1, so step S113 is judged as positive, and they are included in confirmed list CL, so step S114 is judged as positive, and they are not included in queue Q, so a negative judgment is made and the process returns to step S119. Then, a positive judgment is made in step S119.

In this case, nothing is added to queue Q, and queue Q contains only "MT19", which is the state immediately after passing through B for the fourth time. Also, the first stack S1 is "MT22, MT21, MT14". In step S120, queue Q is not an empty set, so the process proceeds to step S121, where the top "MT19" is removed from queue Q and set as processing target Xi, and the process returns to step S106A in Figure 6. In other words, the elements of queue Q become an empty set when returning to S106A.

(Example of structural analysis process | After passing through B for the fifth time)
For "MT19" which is the processing target Xi, all of the adjacent nodes "MT14, MT21" are included in the confirmed list CL, so step S106A is judged as negative, and step S107A is judged as positive. In step S108, the outdegree of "MT14" is "1", so a negative judgment is made and the process proceeds to S109, and since "MT19" is not a source node, a negative judgment is made and the process proceeds to step S111. In step S111, "MT14, MT21", which are neighbors of "MT19", are defined as a new adjacent group N, and the process proceeds to FIG. 7.

In FIG. 7, steps S113 to S118 are first performed with each of the elements "MT14, MT21" of adjacent group N as element Ni. When element Ni is "MT14, MT21", both are included in ancestor list C1, so step S113 is judged as positive, and they are included in confirmed list CL, so step S114 is judged as positive, and they are not included in queue Q, so a negative judgment is made and the process returns to step S119. Then, a positive judgment is made in step S119.

In the process after passing through B for the fifth time, nothing is added to queue Q, so queue Q is an empty set, just like the state immediately after passing through B for the fifth time. In step S120, since queue Q is an empty set, a positive judgment is made for the first time, and the process proceeds to step S601 in Figure 8 via circled C. At this point, the first stack S1 is "MT22, MT21, MT14".

(Example of structural analysis process | initial process in FIG. 8)
Since no operations have been performed on the second stack S2 since it was initialized at the beginning of Fig. 6, it remains an empty set at the start of the processing in Fig. 8. Some elements have been added to the first stack in the processing in Fig. 6 and Fig. 7 as described above. Note that in this embodiment, no pop operation is performed on the first stack S1, and the length of the first stack S1 does not become shorter.

In step S601, zero is assigned to the variable i. In step S602, the length of the first stack S1 is "3", which is greater than "i+1", or "1", and so a positive judgment is made. The "i+1", or "1st", element in the first stack S1 is "MT21", and so in step S603, "MT14, MT18, MT19", which is the ancestor list of "MT21", is set as temporary ancestor list A00. In the following step S604, zero, which is the value of variable i, is assigned to variable j, and in the following step S605, variable j is greater than "-1", so a positive judgment is made and the process proceeds to step S606.

In step S606, the descendants of "MT14", which is the "j"th element, i.e. the "0"th element, of the first stack S1, are extracted from the ancestor list C1, and "MT18, MT19, MT21" are set as temporary descendant list D00. In the following step S607, "MT18, MT19", which are common to the temporary descendant list D00 and the temporary ancestor list A00, are set as duplicate list IS00. In the following step S608, zero, which is the sum of the differences between the indegrees and outdegrees of MT18 and MT19, is set as SD00.

In the following step S609, the outdegree "4" of "MT14", the "j"th, i.e., "0"th element of the first stack S1, is set to OD00. In the following step S610, the indegree "2" of "MT21", the "i+1"th, i.e., "1"th element of the first stack S1, is set to ID00. In the following step S610A, the value of OD00 + SD00 - ID00 is calculated as "2", and since this is greater than or equal to zero, an affirmative judgment is made and the process proceeds to step S611.

In step S611, "MT21", which is the "i+1"th element of the first stack S1, i.e. the "1st" element, is inserted into the second stack S2. In the following step S612, "MT14", which is the "j"th element of the first stack S1, i.e. the "0th" element, is inserted into the second stack S2. In the following step S614, the variable i is incremented to "1" and the process returns to step S602. By the above-described processing for the first week in FIG. 8, the second stack S2 has been updated to "MT21, MT14".

(Example of structural analysis process | second week in Figure 8)
In step S602, which is executed the second time, the length "3" of the first stack S1 is longer than "i+1", i.e., "2", so an affirmative determination is made and the process proceeds to step S603. In step S603, "MT14, MT17, MT18, MT19, MT21", which is the ancestor list of "MT22", the "i+1"th, i.e., the "2nd", element of the first stack S1, is set as temporary ancestor list A00. In the following step S604, the value of variable i, "1", is substituted for variable j, and in the following step S605, variable j is greater than "-1", so an affirmative determination is made and the process proceeds to step S606.

In step S606, the descendants of "MT21", the "j"th element of the first stack S1, i.e. the "1st" element, do not exist in the ancestor list C1, so the temporary descendant list D00 becomes an empty set. Therefore, the duplicate list IS00 in step S607 also becomes an empty set, and SD00 is zero.

In the next step S609, the outdegree "1" of "MT21", the "j"th element, i.e. the "1st" element, of the first stack S1, is set to OD00. In the next step S610, the indegree "2" of "MT22", the "i+1"th element, i.e. the "2nd" element, of the first stack S1 is set to ID00. In the next step S610A, the value of OD00 + SD00 - ID00 is calculated as "-1", which is less than zero, so a negative judgment is made and the process proceeds to step S613. In step S613, the variable j is decremented from "1" to "0". Then the process returns to step S605. In the above-described second week processing of FIG. 8, there is no change in the second stack S2.

(Example of structural analysis process | Week 3 in Figure 8)
In step S605, which is the third execution, the value of the variable j is zero and is greater than "-1", so an affirmative determination is made and the process proceeds to step S606.

In step S606, the descendants of "MT14", which is the "j"th element, i.e. the "0"th element, of the first stack S1, are extracted from the ancestor list C1, and "MT18, MT19, MT21" are set as temporary descendant list D00. In the following step S607, "MT18, MT19", which are common to the temporary descendant list D00 and the temporary ancestor list A00, are set as duplicate list IS00. In the following step S608, zero, which is the sum of the differences between the indegrees and outdegrees of MT18 and MT19, is set as SD00.

In the following step S609, the outdegree "4" of "MT14", the "j"th, i.e., "0"th element of the first stack S1, is set to OD00. In the following step S610, the indegree "2" of "MT22", the "i+1"th, i.e., "2"th element of the first stack S1, is set to ID00. In the following step S610A, the value of OD00 + SD00 - ID00 is calculated as "2", and since this is greater than or equal to zero, an affirmative judgment is made and the process proceeds to step S611.

In step S611, "MT22", which is the "i+1"th element of the first stack S1, i.e. the "2nd" element, is inserted into the second stack S2. In the following step S612, "MT14", which is the "j"th element of the first stack S1, i.e. the "0th" element, is inserted into the second stack S2. In the following step S614, the variable i is incremented to "2" and the process returns to step S602. As a result of the processing for the third week in Figure 8 described above, the second stack S2 has been updated to "MT21, MT14, MT22, MT14".

In step S602, since the length of the first stack S1, "3", is not longer than "i+1", i.e., "3", a negative judgment is made and the structural analysis process is terminated. Through the process described above, "MT21, MT14, MT22, MT14" are obtained as the second stack S2.

(Flowchart of table creation process)
9 is a flowchart showing the table creation process by the test calculation unit 22. The table creation process can be executed as long as the structural analysis process is completed, regardless of whether it is executed before or after the memory dump process. However, the table creation process must be completed before the program test.

In FIG. 9, first, in step S200, the test calculation unit 22 copies the second stack S2 created by the structural analysis process shown in FIGS. 6 to 8. As described below, in the table creation process, a pop operation is performed on the second stack S2, causing the second stack S2 to change. Therefore, to prevent this from affecting other processes such as the memory dump process, the copied second stack S2 is used in the following processes. After completing the process of step S200, the test calculation unit 22 processes steps S201 to S203 in parallel. However, it is not essential that steps S201 to S203 be processed in parallel, and the three may be processed in order.

In step S201, the test calculation unit 22 reads the program P1. In step S202, the test calculation unit 22 acquires the directed graph D1 of the program P1. In step S203, the test calculation unit 22 creates an ancestor list C1 of the focus point X. Note that the focus point X in step S203 is the focus point X determined in step S103 of the structural analysis process.

When the execution of all steps S201 to S203 is completed, the test calculation unit 22 proceeds to step S204. In step S204, the test calculation unit 22 determines whether the length of the second stack S2 is greater than 2. If the test calculation unit 22 determines that the length of the second stack S2 is greater than or equal to 2, the test calculation unit 22 proceeds to step S205, and if the test calculation unit 22 determines that the length of the second stack S2 is less than 2, the process shown in FIG. 9 is terminated.

In step S205, the test calculation unit 22 performs a pop process on the second stack S2 and names the acquired TM as the first element G. In the following step S205, the test calculation unit 22 performs a pop process on the second stack S2 again and names the acquired TM as the second element H. That is, two elements are deleted from the second stack S2 by the processes of steps S205 and S206. In the following step S207, the test calculation unit 22 applies a parallelization algorithm to the first element G to the second element H of the program P1. There is no restriction on the parallelization algorithm applied in this step, and various known algorithms can be applied.

In the following step S208, the test calculation unit 22 creates a partial ancestor list PDi from the first element G to the second element H based on the ancestor list C1. That is, the range from the first element G to the second element H in the ancestor list C1 is named the partial ancestor list PDi. In the following step S209, the test calculation unit 22 generates a parallelized binary Bi from the first element G to the second element H of the program P1.

In the following step S210, the test calculation unit 22 stores the partial ancestor list PDi created in step S208 in the T108 column of the area table T100, and stores the binary Bi created in step S209 in the T103 column of the area table T100. In the following step S210A, the test calculation unit 22 stores the first element G to the second element H as the area Ai in the T102 column of the area table T100.

In the next step S211, the test calculation unit 22 records the first command of the second element H in the T105 column of the area table T100. In the next step S212, the test calculation unit 22 records the last command of the first element G in the T104 column of the area table T100, and returns to step S204. Between the two commands recorded here, the execution order of the macrotasks changes depending on the situation, so repeated execution is performed in the subsequent test. For this reason, steps S211 to S212 are performed to record the start and end points of the repeated execution. The second stack S2 decreases by two elements each time the processing of steps S205 to S212 is performed, and when the length of the second stack S2 becomes less than two, the processing of FIG. 9 ends.

Note that the last command of the second element H may be recorded in step S211, and the first command of the first element G may be recorded in step S212. However, since the order of processing within the first element G and the second element H is fixed, repeatedly executing the processing up to the point where the order is fixed will reduce the efficiency of the test. Therefore, as shown in the flowchart, it is desirable to record the last command of the first element G and the first command of the second element H.

(Example of table creation process)
An example of the operation of the table creation process using the second stack S2 created in the above-mentioned example of the structure analysis process will be described. In the example of the operation described below, the subject of the operation will be omitted, but the subject of the operation is the test calculation unit 22 in all cases. In step S200, the second stack S2 in which four items "MT21, MT14, MT22, MT14" are stored in order from the top is copied. Explanations of steps S201 to S202 will be omitted. In step S203, the focus point X is "MT22" as in the above-mentioned example of the operation, so the ancestor list C1 created is "MT6, MT9, MT14, MT17, MT18, MT19, MT21" as in the above-mentioned example of the operation.

In the first step S204 that is executed next, the length of second stack S2 is "4", which is greater than or equal to 2, so a positive judgment is made. Then in step S205, the last input "MT14" is popped and becomes the first element G, and in step S206, "MT22" is popped and becomes the second element H. As a result of the processing of steps S205 to S206 for the first time, the length of second stack S2 becomes "2" from "4".

In the next step S207, a parallelization algorithm is applied to MT14 to MT22, and in step S208, a partial ancestor list PDi is created for MT14 to MT22. The partial ancestor list PDi may contain information on a directed graph that is diagrammed so that it is easy for humans to understand, or it may contain information on a directed graph that is written logically so that it is easy for a computer to process.

In the following step S209, a parallelized binary Bi of MT14 to MT22 is created. In step S210, the partial ancestor list PDi and the binary Bi are saved in the area table T100. In step S210A, new area IDs are assigned to MT14 to MT22 and saved in the first record of the area table T100. In the following step S211, the first command of MT22, and in the following step S212, the last command of MT14, are saved in the first record of the area table T100.

In the second iteration of step S204, the length of the second stack S2 is "2", so an affirmative judgment is made and the process proceeds to step S205. In step S205, "MT14" is set as the first element G, and in step S206, "MT21" is set as the second element H. The processing of steps S205 to S206 for the first iteration changes the length of the second stack S2 from "2" to "0". In the following steps S207 to S212, writing is performed on the second row of the area table T100 for "MT14" to "MT21". Individual explanations will be omitted.

In the third iteration of step S204, the length of the second stack S2 is "0", so a negative judgment is made and the table creation process ends. This concludes the explanation of an example of the operation of the table creation process.

(Flowchart of memory dump process)
10 is a flowchart showing the memory dump process by the test calculation unit 22. The memory dump process can be executed as long as the structural analysis process is completed, regardless of whether it is executed before or after the table creation process. However, the memory dump process must be completed before the program test.

In FIG. 10, first, in step S300, the test calculation unit 22 copies the second stack S2 created by the structural analysis process. As described later, in the process shown in FIG. 10, a pop operation is performed on the second stack S2, causing the second stack S2 to change. Therefore, in order to prevent this from affecting other processes such as the table creation process, the copied second stack S2 is used in the following process. In the following step S301, the test calculation unit 22 loads the program P1 and proceeds to step S302.

In step S302, the test calculation unit 22 judges whether the length of the second stack S2 is longer than 2. If the test calculation unit 22 judges that the length of the second stack S2 is 2 or more, the process proceeds to step S303. If the test calculation unit 22 judges that the length of the second stack S2 is less than 2, the process proceeds to step S307. In step S303, the test calculation unit 22 performs a pop process on the second stack S2 and names the acquired macrotask as the third element M. In the following step S304, the test calculation unit 22 sets the end of the third element M as the signal position for memory dump. In the following step S305, the test calculation unit 22 performs a pop process on the second stack S2 again and names the acquired TM as the fourth element N. In the following step S306, the test calculation unit 22 sets the start of the TM of the fourth element N as the signal position for memory dump, and returns to step S302. That is, two elements are deleted from the second stack S2 by the processes of steps S303 and S305.

In step S307, the test calculation unit 22 executes the program P1. Then, in step S308, the test calculation unit 22 acquires a memory dump every time the program P1 reaches the signal position set in steps S304 and S306. In the following step S309, the test calculation unit 22 stores the memory dump acquired in step S308 in the T106 and T107 columns of the area table, and ends the process shown in FIG. 10. Specifically, the memory dump acquired at the signal position corresponding to step S304 is recorded in T106, and the memory dump acquired at the signal position corresponding to step S306 is recorded in T107.

(Example of memory dump processing)
An example of the operation of memory dump processing using the second stack S2 created in the above-mentioned example of the operation of the structural analysis processing will be described. In the example of the operation described below, the subject of the operation will be omitted, but the subject of the operation is the test calculation unit 22. In step S300, the second stack S2 in which four items "MT21, MT14, MT22, MT14" are stored in order from the top is copied. In step S301, the program P1 is read.

In the first iteration of step S302, the length of second stack S2 is "4", which is greater than or equal to 2, so a positive judgment is made. Then in step S303, the last input "MT14" is popped and made the third element M, and in step S304 the last command of "MT14" is set as the signal position. In step S305, "MT22" is popped and made the fourth element N, and in step S306 the first command of "MT22" is set as the signal position. As a result of the processing of steps S303 and S305 for the first iteration, the length of second stack S2 becomes "2" from "4".

In step S302 the second time, the length of second stack S2 is "2", which is greater than or equal to 2, so a positive judgment is made. Then in step S303, "MT14" is popped and made the third element M, and in step S304 the last command of "MT14" is set as the signal position. In step S305, "MT21" is popped and made the fourth element N, and in step S306 the first command of "MT21" is set as the signal position. As a result of the processing of steps S303 and S305 the first time, the length of second stack S2 becomes "0" from "2".

In step S302 for the third time, the length of the second stack S2 is "0", which is not 2 or more, so a negative judgment is made and the process proceeds to step S307. In step S307, program P1 is executed, and in step S308, a memory dump, in other words a snapshot of the memory, is acquired each time a traffic light position is reached. Then, in step S309, the acquired memory dump is saved in the area table T100, and the memory dump process ends.

(Program test flow chart)
Fig. 11 is a flowchart showing a program test by the test calculation unit 22. In Fig. 11, the test calculation unit 22 first selects a target area Ai from the area table T100 in step S401. This selection may be performed based on a manual operation by an operator, or may be selected by automatic processing according to a predetermined rule. The automatic processing according to a predetermined rule is, for example, selecting the areas Ai listed in the area table T100 one by one in order from the top.

In the following step S402, the test calculation unit 22 decides whether or not to perform a heat run on the area Ai selected in step S401. If the test calculation unit 22 decides to perform a heat run, the process proceeds to step S403, and if the test calculation unit 22 decides not to perform a heat run, the process proceeds to S501 in FIG. 12 via circled D. Note that the decision in step S402 is made, for example, based on a setting made in advance by an operator. In step S403, the test calculation unit 22 decides whether or not to use a memory dump. If the test calculation unit 22 decides not to use a memory dump, the process proceeds to step S404, and if the test calculation unit 22 decides not to use a memory dump, the process proceeds to step S410. Note that the decision in step S403 is made, for example, based on a setting made in advance by an operator.

In step S404, the test calculation unit 22 reads the T106 column of the area table T100 and proceeds to step S405. In step S405, the test calculation unit 22 obtains the parallelized binary Bi from the T103 column of the area table T100 and proceeds to step S406. In step S406, the test calculation unit 22 initializes the parallelized binary Bi using a memory dump. In the following step S407, the test calculation unit 22 makes necessary modifications to the state of the parallelized binary Bi, in other words, the information stored in the memory. This modification is for making the execution result of the binary Bi reach a predetermined threshold value, for example, by rewriting the value of a specific variable. For example, when S407 is executed for the first time, the value is changed to a value that is only "1" larger, and when S407 is executed for the second time, the value is changed to a value that is only "2" larger, and the value of the variable is updated according to the number of times S407 is executed thereafter.

In the next step S408, the test calculation unit 22 executes the parallelized binary Bi, and in the next step S409, the test calculation unit 22 acquires the execution result of the parallelized binary Bi. In the next step S410, the test calculation unit 22 judges whether or not the execution result of the parallelized binary Bi has reached a predetermined threshold. If the test calculation unit 22 judges that the predetermined threshold has been reached, it ends the processing shown in FIG. 11, and if it judges that the predetermined threshold has not been reached, it returns to step S406.

In step S410, which is executed if a negative judgment is made in step S403, the test calculation unit 22 reads the program P1. In the following step S411, the test calculation unit 22 reads the column T104 corresponding to the selected area Ai from the area table T100, and hereinafter, the macro task written in this column is referred to as the loop start element F.

In the following step S412, the test calculation unit 22 sets the program P1 to stop at the loop start element F. In the following step S413, the test calculation unit 22 executes the program P1. In the following step S414, the test calculation unit 22 acquires a memory dump of the program P1 that has stopped at the loop start element F, and proceeds to step S405. This concludes the explanation of FIG. 11.

Figure 12 is a flowchart showing the processing executed when a negative judgment is made in step S402 in Figure 11. In step S501, which is executed when a negative judgment is made in step S402, the test calculation unit 22 reads information in the T108 column of the area table T100. In the following step S502, the test calculation unit 22 reads an addition request for the directed graph made by the operator. In the following step S503, the test calculation unit 22 processes the directed graph in accordance with the addition request read in step S502.

The first specific example in steps S502 and S503 is to specify the execution order of the macrotasks, more specifically, to limit the execution order to only one in which "MT17" is executed third. The second specific example is to add a macrotask specified by the operator to a specified position.

In the next step S504, the test calculation unit 22 extracts all paths from the directed graph D1 processed in step S503. In the next step S505, the test calculation unit 22 creates binary PBi corresponding to each path, and proceeds to FIG. 13 via the circled E.

Figure 13 is a flowchart showing the process executed after step S505 in Figure 12. In step S506 executed next to step S505, the test calculation unit 22 determines whether or not to use a memory dump. If the test calculation unit 22 determines that a memory dump will be used, the process proceeds to step S507, and if the test calculation unit 22 determines that a memory dump will not be used, the process proceeds to step S513.

In step S507, the test calculation unit 22 acquires a memory dump from the T106 column of the area table T100, and proceeds to step S508. In step S508, the test calculation unit 22 initializes the binary PBi using the memory dump acquired in step S507. In the following step S509, the test calculation unit 22 manipulates the input as necessary. This manipulation is, for example, rewriting a value in the memory. In the following step S510, the test calculation unit 22 executes the binary PBI. In the following step S511, the test calculation unit 22 checks the execution result of the binary PBI executed in step S510.

In the next step S512, the test calculation unit 22 determines whether or not there is still a binary PBI to be executed. If the test calculation unit 22 determines that there is still a binary PBI to be executed, the process returns to step S508. If the test calculation unit 22 determines that there is no binary PBI to be executed, the process ends as shown in FIG. 13.

In step S513, which is executed if a negative judgment is made in step S506, the test calculation unit 22 reads the macrotask written in the T104 column in the area table T100 and sets it as element E. In the following step S514, the test calculation unit 22 sets program P1 to stop in element E. In the following step S515, the test calculation unit 22 executes program P1. In the following step S516, the test calculation unit 22 acquires a memory dump of program P1 stopped in element E and proceeds to step S508. This completes the process in FIG. 13.

(Program test operation example)
A number of operation examples of the program test will be described below. However, the following will only provide an overview of the operation, and detailed explanations will be omitted. In addition, the operator has instructed in advance for each operation example whether or not to perform a heat run and whether or not to use a memory dump. In the operation examples described below, the subject of the operation will be omitted, but the subject of the operation is the test calculation unit 22 in all cases.

(Program test operation example 1)
An operation example 1 of the program test will be described. In this operation example 1, a heat run is not performed and a memory dump is not used. In operation example 1, a negative determination is made in step S402 since a heat run is not performed, and the process proceeds to step S501 in Fig. 12 via circled D. Then, steps S501 to S505 are executed, and the process proceeds to step S506 in Fig. 13 via circled E. In step S506, a negative determination is made and the process proceeds to step S513 since a memory dump is not used.

In steps S513 to S516, the column for start task T104 in area table T100 is read as element F, and a memory dump is obtained when program P1 reaches element F. In steps S508 to S511, the memory dump obtained in S516 is used to initialize and execute binary PBi. The binary PBi to be executed is created in steps S504 to S505 corresponding to all paths in the directed graph, and the processing of steps S508 to S511 is repeated until all of them have been executed.

(Program test operation example 2)
An operation example 2 of the program test will be described. In this operation example 2, a memory dump is used without performing a heat run. Since operation example 2 is similar to operation example 1 until reaching FIG. 13, an explanation of the process up to step S506 will be omitted. Since a memory dump is used in step S506, an affirmative determination is made, and in step S507, a memory dump is obtained from the start point dump T106 column of the area table T100. Since the process from step S508 onwards is similar to operation example 1, an explanation will be omitted.

(Program test operation example 3)
A third operation example of the program test will be described. In this third operation example, a heat run is performed, and a memory dump is not used. In operation example 3, a heat run is performed, so a positive determination is made in step S402, and a memory dump is not used, so a negative determination is made in step S403, and the process proceeds to step S410.
In steps S410 to S414, program P1 is read, the start task T104 column in the area table T100 is read as element F, and a memory dump is obtained when program P1 reaches element F. In subsequent steps S405 to S06, the parallelized binary Bi is obtained from the area table T100, and the memory dump is used to initialize the binary Bi. In step S407, necessary modifications are made and then the binary Bi is executed, and the execution is repeated while changing the modifications made in S407 until the execution result reaches the desired threshold. When the desired threshold is reached, the test ends.

(Program Test Operation Example 4)
A fourth operation example of the program test will be described. In this fourth operation example, a heat run is performed and a memory dump is used. In operation example 4, a heat run is performed, so an affirmative determination is made in step S402, and a memory dump is used, so an affirmative determination is made in step S403 and the process proceeds to step S404. In step S404, the memory dump is read from the area table T100 and the process proceeds to step S405. The process from step S405 onwards is the same as in operation example 3, so a description thereof will be omitted.

According to the above-described first embodiment, the following advantageous effects can be obtained.
(1) The test method executed by the arithmetic device 1 is a test method in which the arithmetic device 1, which is a computer, tests a program including a plurality of macrotasks that can have a plurality of execution orders. This method includes setting one of the plurality of macrotasks as a focus point (S103 in FIG. 6), identifying an ancestor list C1 that is a set of macrotasks that affect the focus point X (S104 in FIG. 6), classifying the macrotasks included in the ancestor list C1 into a non-parallel group that does not contribute to parallelization and a parallel contribution group that contributes to parallelization (structural analysis processing), generating a plurality of test patterns for the parallel contribution group (S501 to S504 in FIG. 12), and executing the plurality of test patterns using results obtained by executing the macrotasks belonging to the non-parallel group (S406 to S408 in FIG. 11, S508 to S510 in FIG. 13). Therefore, in a test of a program P1 including a plurality of macrotasks that can have a plurality of execution orders, a test targeting the specific macrotask set as the focus point X can be efficiently executed.

(2) The result obtained by executing a macrotask belonging to a non-parallel group is a dump of the memory of the computer executing the macrotask, and one dump is used to execute multiple test patterns (loop S410: NO in FIG. 11, loop S512: YES in FIG. 13). Therefore, since a memory dump is used instead of executing the same process multiple times, the time required to execute multiple test patterns can be reduced.

(3) The test method executed by the computing device 1 includes modifying the generated test pattern based on the operator's instructions (S502 to S503 in FIG. 12). Therefore, in addition to the automatically generated test pattern, the operator can make any modifications that interest him or her.

(4) The test method executed by the computing device 1 sets the macrotask in which an error has occurred when executing the program as the attention point X (S103 in FIG. 6). Therefore, the entire test can be executed automatically without the need for an operator to specify it.

In each of the above-described embodiments and variations, the functional block configurations are merely examples. Several functional configurations shown as separate functional blocks may be configured together, or a configuration shown in a single functional block diagram may be divided into two or more functions. In addition, some of the functions of each functional block may be provided by other functional blocks.

In each of the above-mentioned embodiments and modifications, the program executed by the arithmetic device 1 is stored in the ROM 3, but the program may be stored in the storage unit 5. Furthermore, the arithmetic device may load a program from another device via a medium available to the external interface 6 when necessary. Here, the medium refers to, for example, a storage medium that is detachable from the input/output interface, or a communication medium, i.e., a network such as a wired, wireless, or optical network, or a carrier wave or digital signal that propagates through the network. Furthermore, some or all of the functions realized by the program may be realized by a hardware circuit or an FPGA.

The above-mentioned embodiments and modifications may be combined with each other. Although various embodiments and modifications have been described above, the present invention is not limited to these. Other aspects that are conceivable within the scope of the technical concept of the present invention are also included within the scope of the present invention.

1... Calculation device 5... Storage unit 21... Input/output unit 22... Test calculation unit 23... Program execution unit D1... Directed graph Q... Queue S1... First stack S2... Second stack T100... Area table

Claims (5)

1. A method for testing a program including a plurality of macrotasks that can be executed in a plurality of different orders by a computer, comprising:
setting one of the plurality of macrotasks as a focus task;
identifying an ancestor list, which is a set of the macrotasks that affect the focus task;
classifying the macrotasks included in the ancestor list into a non-parallel group that does not contribute to parallelization and a parallel contributing group that contributes to parallelization;
generating a plurality of test patterns for the parallel contributions;
executing the plurality of test patterns using results obtained by executing the macrotasks belonging to the non-parallel group. 2. The test method according to claim 1,
the result obtained by executing the macrotask belonging to the non-parallel group is a dump of the memory of the computer executing the macrotask,
A testing method comprising: executing the plurality of test patterns using one of the dumps. 2. The test method according to claim 1,
The testing method further includes modifying the generated test pattern based on an operator's instruction. 2. The test method according to claim 1,
a macrotask in which an error occurs when the program is executed, the macrotask being set as the target task. a storage unit for storing a program including a plurality of macrotasks that can be executed in a plurality of different orders;
a test calculation unit that sets one of the plurality of macrotasks as a focus task, identifies an ancestor list that is a set of the macrotasks that affect the focus task, classifies the macrotasks included in the ancestor list into a non-parallel group that does not contribute to parallelization and a parallel contribution group that contributes to parallelization, and generates a plurality of test patterns for the parallel contribution group;
a program execution unit that executes the plurality of test patterns using a result obtained by executing the macro task that belongs to the non-parallel group.

Images