Program processing device, parallel processing program, program processing method, parallel processing compiler, recording medium containing the parallel processing compiler, and multi-processor system

A non-transitory recording medium encoded with a parallel processing program inputted in the storage unit of a program processing device,

• wherein the parallel processing program causes a processing unit of the program processing device to:
• identify a starting point and an end point of each thread in the parallel processing program which is inputted in the storage unit and to which a thread description is added, using a reserved keyword or a symbol;
• and generate an intermediate language, in which a thread attribute of the each thread is added to each operation instruction included in a thread area specified by the starting point and the end point;
• input therein the intermediate language;
• extract an instruction block input/output data from the intermediate language;
• and generate, based on the instruction block input/output data, single data dependency edge information including information on a single data dependency, which is a dependency of a data generated or referenced by a single operation instruction, information on a data structure dependency, which is a dependency of a data between instructions acting on the data structure, and information on a pointer alias data dependency, which is a dependency of a data between instructions acting on a pointer reference data;
• input therein the intermediate language and the data dependency edge information;
• extract, from the intermediate language, a data dependency edge for connecting a thread with another thread, and a thread output data generation instruction and a thread input reference instruction each corresponding to the data dependency edge, based on the data dependency edge information;
• and generate inter-thread data dependent instruction pair information;
• input therein the intermediate language;
• extract a pointer data from the data dependency edge for connecting between different threads;
• insert a pointer alias ID computing instruction just prior to an instruction for defining the pointer data of the intermediate language;
• and generate a first program;
• input therein the first program and the inter-thread data dependent instruction pair information;
• insert an inter-thread data transfer instruction just subsequent to the thread output data generation instruction in the first program, based on the inter-thread data dependent instruction pair information;
• insert an inter-thread data reception synchronization instruction just prior to the thread input data reference instruction in the first program, based on the inter-thread data dependent instruction pair information;
• insert a thread start-up instruction at a branch instruction, on which a thread of interest is control-dependent, or at a function entrance;
• and generate a second program;
• and
• input therein the second program;
• partition the second program into threads, based on the thread attribute of each instruction;
• and convert the each thread into an execution code.

A program processing method performed by a program processing device for inputting therein a parallel processing program with a thread description added thereto;

• partitioning the program into threads;
• and generating execution codes for a multi-processor system having a plurality of processors, using the threads, the program processing device comprising:
• a storage unit;
• and
• a processing unit,
• the program processing method performed by the processing unit comprising the steps of:
• identifying a starting point and an end point of each thread in the parallel processing program inputted in the storage unit, using a reserved keyword or a symbol;
• and generating an intermediate language, in which a thread attribute of the each thread is added to each operation instruction included in a thread area specified by the starting point and the end point;
• inputting the intermediate language;
• extracting an instruction block input/output data from the intermediate language;
• and generating, based on the instruction block input/output data, data dependency edge information including information on a single data dependency, which is a dependency of a data generated or referenced by a single operation instruction, information on a data structure dependency, which is a dependency of a data between instructions acting on the data structure, and information on a pointer alias data dependency, which is a dependency of a data between instructions acting on a pointer reference data;
• inputting the intermediate language and the data dependency edge information;
• extracting, from the intermediate language, an data dependency edge for connecting a thread with another thread, and a thread output data generation instruction and a thread input reference instruction each corresponding to the data dependency edge, based on the data dependency edge information;
• and generating inter-thread data dependent instruction pair information;
• inputting the intermediate language;
• extracting a pointer data from the data dependency edge for connecting between different threads;
• inserting a pointer alias ID computing instruction just prior to an instruction for defining the pointer data of the intermediate language;
• and generating a first program;
• inputting the first program and the inter-thread data dependent instruction pair information;
• inserting an inter-thread data transfer instruction just subsequent to the thread output data generation instruction in the first program, based on the inter-thread data dependent instruction pair information;
• inserting an inter-thread data reception synchronization instruction just prior to the thread input data reference instruction in the first program, based on the inter-thread data dependent instruction pair information;
• inserting a thread start-up instruction at a branch instruction, on which a thread of interest is control-dependent, or at a function entrance;
• and generating a second program;
• and
• inputting the second program;
• partitioning the second program into threads, based on the thread attribute of each instruction;
• and converting the each thread into an execution code.

A multi-processor system having a plurality of processors, the multi-processor system performing a processing based on execution codes generated by a program processing device, in which the program processing device inputs therein a parallel processing program with a thread description added thereto, partitions the program into threads, and generates the execution codes for the multi-processor system, the multi-processor system comprising, for each of a plurality of the processors:

• a storage unit;
• and
• a processing unit,
• the processing unit comprising:
• an inter-processor communication processing unit for performing control between the processors in a data flow machine-type data-driven control method;
• and
• an in-processor processing unit for performing control between the processors in a Neumann-type program-driven control method,
• the inter-processor communication processing unit performing a communication between the processors in synchronization with the in-processor processing unit, and detecting a communication data hazard between the processors, and
• the in-processor processing unit performing a processing based on the execution codes stored in the storage unit, and executing or suspending the execution codes according to a result of detecting the data hazard,
• wherein the storage unit stores therein a data communication port table for holding port information,
• the port information includes a data size, a data storage address, a transfer port ID each for performing an inter-processor communication of a direct access-type data, a pointer reference data, and a pointer data, and, additionally, port alias information for performing an inter-processor communication of the pointer reference data and the pointer data,
• the port alias information includes information on a pointer alias including a data size, a data storage address, and an alias ID for each of all data objects to be referenced by a pointer,
• if an inter-processor communication of a direct access-type data is performed,
• the inter-processor communication processing unit of a first processor on a transfer side obtaining the port information of the direct access-type data;
• identifying, using the data storage address in the port information, a data storage address of the direct access-type data stored in the storage unit of the first processor on the transfer side;
• and transferring a data having the identified data storage address and the transfer port ID to a second processor on a receive side, and
• the inter-processor communication processing unit of the second processor on the receive side identifying a data storage address of the received data, which is stored in the storage unit of the second processor on the receive side, using the received transfer port ID;
• and storing the received data into the identified data storage address,
• if an inter-processor communication of a pointer reference data is performed,
• the inter-processor communication processing unit of the first processor on the transfer side obtaining the port alias information of the pointer reference data;
• identifying a data storage address of a data object referenced by a pointer of the pointer reference data, stored in the storage unit of the first processor on the transfer side, using the port alias information;
• and transferring the transfer port ID, an alias ID of the pointer reference data, and all data objects referenced by the pointer, to the second processor on the receive side, and
• the inter-processor communication processing unit of the second processor on the receive side identifying a data storage address of each of the data objects, stored in the storage unit of the second processor on the receive side, using the received transfer port ID and the alias ID;
• and storing the received data objects into respective identified data storage addresses, and
• if an inter-processor communication of a pointer data is performed,
• the inter-processor communication processing unit of the first processor on the transfer side obtaining the port alias information of a pointer of interest;
• identifying a data storage address of a data object referenced by a pointer of the pointer data, and stored in the storage unit of the first processor on the transfer side, using the port alias information;
• and computing a pointer offset value by subtracting the data storage address from a value of the pointer;
• and transferring the transfer port ID, the alias ID of the pointer, and the pointer offset value to the second processor on the receive side, and
• the inter-processor communication processing unit of the second processor on the receive side identifying a data storage address of a data object stored in the storage unit of the second processor on the receive side, using the received transfer port ID and the alias ID;
• computing a pointer value, which is valid in the storage unit of the second processor on the receive side, by adding the data storage address to the received pointer offset value;
• and storing the pointer value into the storage unit of the second processor on the receive side.