JP2008158759A - Programming method, program processing method, processing program, and information processing device - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To solve a problem that in order to process programs to be processed in parallel while keeping execution orders properly, it is necessary to decide dependency relations between programs or between threads in a fixed manner in advance. <P>SOLUTION: In this processing method, based on graph data configuration generation information including previous information and following information extracting portions associated with respective program modules from a parallel operation control description describing a parallel processing relation between program modules, a predetermined program module is extracted to be added to the graph data configuration according to the dependency relation, and operation is carried out from a node, before which all the nodes are already processed. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

  The present invention relates to program processing, and more particularly to program processing for parallel processing.

  A conventional multi-thread parallel processing program generates a plurality of threads, each of which is forced to perform programming in consideration of synchronous processing. For example, in order to keep the execution order appropriate, it is necessary to add processing that guarantees synchronization to various places in the program, which increases the maintenance cost because it becomes difficult to debug the program.

Patent Document 1 discloses a method for realizing parallel processing based on execution results of threads and dependency relationships between threads when a plurality of threads are generated. In this method, it is necessary to quantitatively specify the redundantly executed threads in advance, which causes a problem that the flexibility of program change is lacking.
JP 2005-258920 A

  In order for programs to be processed in parallel to perform processing while maintaining an appropriate execution order, it is necessary to fix the dependency relationship between programs or threads in advance.

  The present invention has been made in view of the above problems, and provides a program method, a generation program, and an information processing apparatus that can flexibly cope with multi-thread parallel processing.

According to the programming method of the present invention,
Regardless of the execution status of other programs, use multiple program modules that can be executed on condition that input data is first given, and a parallel execution control description that describes the parallel processing relationship between the program modules. A graph data structure generation information including at least preceding information and subsequent information of the program module obtained by extracting a portion related to each of the program modules from the parallel execution control description for each program module. When the input data is created and given, the program module that receives the input data is extracted based on the preceding information included in the graph data structure generation information, and the extracted graph data structure generation information No representing the execution unit of the program module In order to automatically add the generated node to the current graph data structure configured based on the preceding information and subsequent information defined in the graph data structure generation information. Programming characterized by using an execution control description becomes possible.

According to the program processing method of the present invention,
A program processing method for processing in parallel a plurality of program modules that can be executed on condition that input data is first given regardless of the execution status of other programs, wherein the program modules are connected in parallel. For each program module, graph data structure generation information including at least preceding information and subsequent information of the program module obtained by extracting a part related to each of the program modules from a parallel execution control description describing a processing relationship is created for each program module. When certain input data is given, a program module that receives the input data is extracted based on the preceding information included in the graph data structure generation information, and the extracted graph data structure generation information Generate a node representing the execution unit of the program module This generated node is automatically added to the graph data structure configured based on the preceding information and subsequent information defined in the graph data structure generation information of the previously generated node, and exists at that time For a certain node included in the graph data structure, when all nodes representing program modules defined by the preceding information included in the parallel execution control description corresponding to the node have been processed, execution of the node is started. Can do.

Furthermore, with the processing program of the present invention,
A processing program for processing in parallel a plurality of program modules that can be executed on condition that input data is first given regardless of the execution status of other programs, and parallel processing between the program modules For each program module, graph data structure generation information including at least preceding information and succeeding information of the program module obtained by extracting a portion related to each of the program modules from a parallel execution control description describing the relationship of When certain input data is given, a program module that receives the input data is extracted based on the preceding information included in the graph data structure generation information, and the program is generated for the extracted graph data structure generation information. Create a node representing the module execution unit Is automatically added to the graph data structure configured based on the preceding information and the succeeding information defined in the graph data structure generation information of the previously generated node, and exists at that time For a node included in the graph data structure, if all nodes representing program modules defined by the preceding information included in the parallel execution control description corresponding to the node have been processed, the node can be executed. It becomes.

  An information processing apparatus that provides the above functions is also provided.

  It is possible to provide a programming environment that can flexibly cope with multi-thread parallel processing.

(First embodiment)
FIG. 1 is a diagram illustrating an example of a system configuration diagram according to the present embodiment. In FIG. 1, a plurality of processors 100, a memory 101, an HDD 102, and an internal bus 103 are shown.

  The processor 100 has a function of interpreting program codes stored in various storage devices and executing processing described in advance as a program. In FIG. 1, three processors 100 that are equivalent to each other are shown. However, the processors need not necessarily be equivalent to each other, and may include processors having different processing capabilities or processors that process different types of codes. .

  The memory 101 indicates a storage device made of, for example, a semiconductor. A program processed by the processor 100 is read into the memory 101 accessible at a relatively high speed before the processing, and is accessed from the processor 100 according to the program processing.

  The HDD 102 indicates a magnetic disk device, for example. The HDD 102 can store a larger amount of data than the memory 101, but is often disadvantageous in terms of access speed. The program code processed by the processor 100 is stored in the HDD 102, and only the part to be processed is read out on the memory 101.

  The internal bus 103 is a common bus configured such that the processor 100, the memory 101, and the HDD 102 are connected to each other and can exchange data with each other.

  Although not shown, an image display device for outputting processing results or an input / output device such as a keyboard for inputting processing data may be provided.

  FIG. 2 is a diagram showing an example of program translation according to the present embodiment.

  The basic module 200 is a program executed by the system according to the present embodiment, and the parallel execution control description 201 is data referred to when executing. The parallel execution control description 201 indicates the dependency of each basic module 200 during parallel processing, and is converted into graph data structure generation information 204 by the translator 202 before being executed by the information processing apparatus 203.

  In addition to the case where the translator 202 converts the basic module 200 in advance before processing, a method of performing the translation while sequentially translating by a runtime task or the like during execution of the basic module 200 is also conceivable.

  Software at the time of execution on the information processing apparatus 203 includes a basic module 200, graph data structure generation information 204, a runtime library 205, and an OS 206. The runtime library 205 includes an API (Application Interface) when the basic module 200 is executed on the information processing apparatus 203, and has a function for realizing exclusive control required when the basic module 200 is processed in parallel. Have. On the other hand, the function of the translator 202 may be called from the runtime library 205, and when called during the process of the basic module 200, the parallel execution control description 201 of the part to be processed next may be converted each time. This configuration eliminates the need for a resident task for translation and allows parallel processing to be configured more compactly.

The OS 206 manages the entire system such as hardware of the information processing apparatus 203 and task scheduling. By introducing the OS 206, when the basic module 200 is executed, the programmer is freed from miscellaneous management of the system and can concentrate on programming, and generally can easily describe software that can be operated on many models. There are benefits.

  FIG. 3 is a diagram illustrating an example of a processing flow of a conventional parallel processing program. FIG. 3 shows a schematic diagram in which a plurality of programs A300, B301 and C302 are processed in parallel.

  The programs are not processed independently of each other. When the processing results of other programs are used for their own processing, or because the data consistency is ensured, the processing of a specific part of the other program ends. Sometimes you have to wait. When a program having such characteristics is processed in parallel, a mechanism for knowing the execution status of another program must be embedded in each part of the program. By embedding this mechanism, data guarantees and exclusive control are realized between programs to perform cooperative operation.

  For example, when a predetermined event occurs during the processing of the program A300, the program B301 is requested to perform some processing (event 303). The program B301 receives the event 303, executes a predetermined process, and further issues an event 304 to the program C302 when a predetermined condition is satisfied. The program B301 responds to the program A300 as an event 305 with the processing result received from the program A300 by the event 303.

  However, if a description for realizing synchronous processing in parallel processing is written in the program itself, consideration different from the original logic is required and the program becomes complicated. Further, resources are wasted while waiting for the end of processing of other programs. Furthermore, it is often difficult to modify the program later, for example, processing efficiency fluctuates greatly due to a slight timing shift.

  In the information processing apparatus according to the present embodiment, it is divided into parts that require synchronous processing and data exchange, and the relationship between them is defined as a parallel execution control description, thereby facilitating the componentization of the basic module, and the parallel processing definition. We propose a method that can be managed in a compact manner.

  FIG. 4 is a diagram for explaining an example of a program dividing method according to this embodiment. FIG. 4 shows programs A400 and B401 that perform synchronization processing with each other.

  First, it is assumed that the program A 400 is executing the thread 402 and the program B 401 is executing the thread 407. When the program A400 is executed up to the point 406, the processing result needs to be transferred to the program B401. Therefore, when the program A 400 terminates the thread 402, the program A 400 notifies the program B 401 of the processing result as an event 404. The program B 401 is a process that can be executed by the thread 405 for the first time when both the event 404 and the processing result of the thread 407 are obtained. On the other hand, the program A 400 receives the end of the thread 402 and executes the program after the point 406 as the thread 403.

  A portion where processing can proceed unconditionally like the above thread 402, and a point where a certain processing result to be notified to other threads can be obtained while processing a program, such as point 406, or another thread There is a point where obtaining a processing result from the above is a condition for starting the processing.

  Therefore, as shown in FIG. 4, the program is divided at a point such as point 406, and the processing units of the program after the division are defined as basic modules a1 to a3 and basic modules b1 to b3, respectively. Although two mutually related programs are shown in FIG. 4, even if there are more programs that are related to each other, they can be divided in the same way.

  FIG. 5 is a diagram for explaining an example of the dependency relationship of the basic modules according to the present embodiment. The basic module 500 represents the basic module described with reference to FIG. 4, and modularized programs that can be unconditionally advanced regardless of other threads are assigned to the respective modules. This modularized program corresponds to the basic module 200. Further, these basic modules are associated based on a link 501 indicating a dependency relationship with other basic modules. Each basic module receives an event such as a calculation result output from a preceding basic module whose relation is defined by a link 501 and simultaneously generates an event to a subsequent basic module whose relation is defined by a link. In addition, a basic module containing a plurality of links indicates that a plurality of event conditions are necessary for its own processing.

  FIG. 6 is a diagram illustrating an example of the node 600 according to the present embodiment. The node here corresponds to each basic module. After the parallel execution control description 201 is converted into the graph data structure generation information 204 by the translator 202, the basic module is converted into the graph data structure based on this information. It is a thing.

As described above, the node 600 obtained by structuring the basic module in the graph data structure has a dependency relationship with other nodes through links. When viewed as a node as shown in FIG. 6A, there are two types of links, a link 601 to the preceding node and a connector 602 to the succeeding node.

  The link 601 is a link coupled to an output terminal of another node necessary for obtaining data necessary for the node 600 to execute a predetermined process. Each link 601 has definition information such as what kind of output end a link is necessary with.

  The connector 602 includes identification information indicating what kind of data is output after the processing of the node 600. Subsequent nodes can determine whether or not the conditions under which they can be executed are complete based on the identification information of the connector 602 and the parallel execution control description 201.

  When it is considered that the conditions executable by the system are satisfied, the node 600 is queued in the executable queue 603 in units of nodes as shown in FIG. 6B, and should be executed next from the queued nodes. The node is retrieved and processed.

  FIG. 7 is a diagram showing an example of the node graph data structure generation information 204 according to the present embodiment. FIG. 7 shows graph data structure generation information 700 translated from the parallel execution control description 201. The information includes the basic module ID, a plurality of pieces of link information to the preceding node, the output buffer type of the node, and the processing cost of the node. The cost information here indicates a cost related to processing of the basic module 200 corresponding to the node. This information is considered when selecting the next node to be extracted from among the nodes queued in the executable queue 603.

  In the link information to the preceding node, a condition for a node to be the preceding node of the node is defined. For example, the definition of a node that outputs a predetermined data type, a node having a specific ID, and the like can be considered.

  The graph data structure generation information 700 represents the corresponding basic module 200 as a node, and is used as information for adding the basic module to an existing graph data structure as shown in FIG. 5 based on link information or the like. .

  FIG. 8 is a diagram showing an example of a processing flow for adding a graph data structure according to this embodiment. When this flow is executed, an executable node is generated based on the graph data structure generation information 700 and is queued in the executable queue 603.

First, a runtime task that manages multithread processing receives input data to be processed (step S01). The presence or absence of input data is determined (step S02). If there is no input data (No), the input data is accepted again.

If there is input data in step S02 (Yes), the graph data structure generation information 204 that receives the input data is extracted and acquired (step S03). The output data of the basic module 200 is classified in advance into a plurality of types to be described in the output buffer type of the graph data structure generation information 700. When extracting the graph data structure generation information 204 with input data as an input, this data type is determined based on the data type to be input data included in the link information to the preceding node described in the graph data structure generation information 700. It is sufficient to extract data that matches the input data.

  Next, the node 600 corresponding to the graph data structure generation information 700 acquired in step S03 is generated (step S04). When a plurality of graph data structure generation information 700 is extracted here, a plurality of nodes 600 corresponding to the plurality of graph data structure generation information 700 are generated.

  The generated node 600 is then added to the existing graph data structure (step S05). The existing graph data structure here refers to the dependency relationship before and after the generated node based on the link information to the preceding node of the node 600 generated from the graph data structure generation information 700 and the output buffer type. This is structured as shown in FIG.

  Next, for each node included in the existing graph data structure, it is determined whether or not each preceding node has completed processing (step S06). If all the preceding nodes have been completed for a certain node (Yes), it is considered that this node has a condition for starting execution, and this node is queued in the executable queue 603 (step S07). On the other hand, if there is a preceding node that has not yet completed processing (No), the processing cannot be started, and the flow ends. Even if the node 600 is generated in this way, the basic module 200 corresponding to the node is not immediately executed, and the processing is not performed until the dependency relationship with the other nodes of the added graph data structure is satisfied. Deferred.

  FIG. 9 is a diagram illustrating an example of basic module processing according to the present embodiment. This flow shows an example in which each basic module 200 is executed by reading a node queued in the executable queue 603.

  First, a node to be executed next is selected based on a predetermined condition from among the executable nodes queued in the executable queue 603 (step S11). The predetermined condition can be selected based on criteria such as the oldest queued node, the node with many subsequent nodes, or the node with high cost.

  The cost of each node may be calculated and calculated as follows.

Cost of additional node = (α × past average execution time)
+ (Β x Output buffer usage)
+ (Γ x number of subsequent nodes)
+ (Δ x execution frequency when not scheduled)
In general, it is considered that the throughput of parallel processing increases when processing is performed from a node with high cost. Here, the non-scheduled execution frequency refers to a frequency at which a situation in which no node is queued in the executable queue 603 appears while the basic module is being executed. If this situation occurs, an underflow of the executable queue 603 occurs, and the parallel processing degree of the basic module 200 decreases, which is not preferable. Since such a basic module 200 is calculated at a higher cost, it can be processed early and expected to avoid bottlenecks.

  Predetermined values may be used for the coefficients α to δ of the linear expression of the cost calculation formula, or the coefficients α to δ may be dynamically changed while observing the processing status.

  When the node to be executed next is acquired, an output buffer for storing the processing result of this node is secured before execution (step S12). The output buffer is secured based on the definition of the output buffer type defined in the graph data structure generation information 700.

  When the output buffer can be secured, the execution of the basic module 200 corresponding to this node is started (step S13). When the basic module 200 ends the processing, the executed flag of the node in the graph data structure is set to processed (step S14).

  Next, it is determined whether all subsequent nodes included in the graph data structure of the node have been processed (step S15). If all the subsequent nodes have been processed (Yes), the node can be deleted from the graph data structure (step S16). At this time, since the output data of the node is not used, the output buffer secured in step S12 is also released. Conversely, if there is a subsequent node that has not been processed yet, the output data of that node may be used in the basic module of the subsequent node, and therefore it should not be deleted from the graph data structure.

  Next, for each of all nodes included in the graph data structure, it is determined whether all preceding nodes of the node have been processed (step S17). If there is a node for which all of the preceding nodes have been processed (Yes), the node is considered to have been executed and the queue is queued in the executable queue 603 (step S18). A node that has not been processed even at one of the preceding nodes (No) cannot be executed without waiting for the end of the processing of the preceding node.

  With this configuration, since the parallel processing is performed by selecting the basic module 200 that can be independently executed by the runtime task and simultaneously updating the graph data structure, the series of processing is considered as an application. There is no need. In addition, since the basic module 200 does not include a part that branches from another task, it is not necessary to consider arbitration with another task being executed.

  Therefore, it is possible to provide a programming environment that can flexibly cope with multi-thread parallel processing.

  Note that the present invention is not limited to the above-described embodiment as it is, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. In addition, various inventions can be formed by appropriately combining a plurality of constituent elements disclosed in the embodiment. For example, some components may be deleted from all the components shown in the embodiment. Furthermore, constituent elements over different embodiments may be appropriately combined.

It is a figure which shows an example of the system block diagram concerning this embodiment. It is a figure which shows an example of the translation of the program which concerns on this embodiment. It is a figure which shows an example of the processing flow of the conventional parallel processing program. It is a figure explaining an example of the division method of the program concerning this embodiment. It is a figure explaining an example of the dependency relation of the node concerning this embodiment. It is a figure explaining an example of the node concerning this embodiment. It is a figure which shows an example of the graph data structure production | generation information of the node which concerns on this embodiment. It is a figure which shows an example of the addition process flow of the graph data structure which concerns on this embodiment. It is a figure which shows an example of the basic module process which concerns on this embodiment.

Explanation of symbols

DESCRIPTION OF SYMBOLS 100 ... Processor, 101 ... Memory, 102 ... HDD, 103 ... Internal bus, 200 ... Basic module, 201 ... Parallel execution control description, 202 ... Translator, 203 ... Information processing device 204: Graph data structure generation information 205: Runtime library 206: OS, 300: Program A 301: Program B 302: Program C 303 ... Event, 402 ... Thread, 500 ... Basic module, 501 ... Link, 601 ... Link, 602 ... Connector, 603 ... Executable queue, 700 ... Graph Data structure generation information

Claims (10)

Regardless of the execution status of other programs, a plurality of program modules that can be executed on condition that input data is given first,
A programming method using a parallel execution control description describing a parallel processing relationship between the program modules,
Graph data structure generation information including at least preceding information and subsequent information of the program module obtained by extracting a part related to each program module from the parallel execution control description is created for each program module,
When certain input data is given, a program module that receives the input data is extracted based on the preceding information included in the graph data structure generation information,
Generate a node representing the execution unit of the program module for the extracted graph data structure generation information,
In order to automatically add the generated node to the graph data structure existing at that time, which is configured based on the preceding information and the succeeding information defined in the graph data structure generation information, the parallel execution control description is added. A programming method characterized by using.   For a node included in the graph data structure existing at that time, when all nodes representing program modules defined in the preceding information included in the parallel execution control description corresponding to the node have been processed, the node The programming method according to claim 1, wherein the parallel execution control description is used to start execution of a program.   If all the nodes extracted based on the subsequent information of the graph data structure generation information corresponding to a certain node included in the graph data structure existing at that time have been processed, the node is automatically extracted from the graph data structure. The programming method according to claim 1, wherein the parallel execution control description is used in order to be deleted. A program processing method for processing in parallel a plurality of program modules that can be executed on condition that input data is first given regardless of the execution status of other programs,
Graph data structure generation information including at least preceding information and succeeding information of the program module obtained by extracting a portion related to each of the program modules from a parallel execution control description that describes a parallel processing relationship between the program modules, Create for each program module,
When certain input data is given, a program module that receives the input data is extracted based on the preceding information included in the graph data structure generation information,
Generate a node representing the execution unit of the program module for the extracted graph data structure generation information,
The generated node is automatically added to the graph data structure configured based on the preceding information and the subsequent information defined in the graph data structure generation information of the previously generated node,
For a node included in the graph data structure existing at that time, when all the nodes representing the program modules defined in the preceding information included in the parallel execution control description corresponding to the node have been processed, A program processing method characterized by starting execution.   If all the nodes extracted based on the subsequent information of the graph data structure generation information corresponding to a certain node included in the graph data structure existing at that time have been processed, the node is automatically extracted from the graph data structure. The program processing method according to claim 4, wherein the program processing method is deleted.   5. The program processing method according to claim 4, wherein the creation of the graph data structure generation information is automatically performed for a portion related to a program module executed in the program processing in the parallel execution control description. . A processing program for processing in parallel a plurality of program modules that can be executed on condition that input data is first given regardless of the execution status of other programs,
Graph data structure generation information including at least preceding information and subsequent information of the program module obtained by extracting a portion related to each of the program modules from a parallel execution control description describing a parallel processing relationship between the program modules, Create for each program module,
When certain input data is given, a program module that receives the input data is extracted based on the preceding information included in the graph data structure generation information,
Generate a node representing the execution unit of the program module for the extracted graph data structure generation information,
The generated node is automatically added to the graph data structure configured based on the preceding information and the subsequent information defined in the graph data structure generation information of the previously generated node,
For a certain node included in the graph data structure existing at that time, when all the nodes representing the program modules defined in the preceding information included in the parallel execution control description corresponding to the node have been processed, A processing program characterized by being executed.   If all the nodes extracted based on the subsequent information of the graph data structure generation information corresponding to a certain node included in the graph data structure existing at that time have been processed, the node is automatically extracted from the graph data structure. The processing program according to claim 7, wherein the processing program is deleted.   8. The processing program according to claim 7, wherein the graph data structure generation information is automatically created for a portion related to a program module executed in the program processing in the parallel execution control description. Storage means for storing a plurality of program modules that can be executed on condition that input data is first given regardless of the execution status of other programs;
Graph data structure generation information including at least preceding information and succeeding information of the program module obtained by extracting a part related to each of the program modules from a parallel execution control description describing a parallel processing relationship of the program module. Processing means to create for each,
The processing means further includes
When certain input data is obtained as a result of executing the program module, the program module having the input data as an input is extracted based on the preceding information included in the graph data structure generation information,
Generate a node representing the execution unit of the program module for the extracted graph data structure generation information,
The generated node is automatically added to the graph data structure configured based on the preceding information and the subsequent information defined in the graph data structure generation information of the previously generated node,
For a node included in the graph data structure existing at that time, when all the nodes representing the program modules defined in the preceding information included in the parallel execution control description corresponding to the node have been processed, An information processing apparatus that executes a corresponding program module.

Images