Minimizing program execution time for parallel processing

Abstract

According to one embodiment, an information processing apparatus comprises a storage storing program modules and parallel execution control description describing relationships of the program modules, a conversion module extracting a part relating to the program module from the parallel execution control description, and creating graph data structure creation information including preceding and succeeding information of the program module, an adding module extracting graph data structure creation information to which the input data is given, creating a node, and adding the created node to a formerly created graph data structure, and an execution module subjecting the graph data structure to at least one of first search and second search with a restricted breadth, selecting one node from nodes stored in the node memory, and executing a program module corresponding to the selected node.

1 . An information processing apparatus comprising:
 a storage configured to store program modules executable on condition that input data has been given irrespectively of execution states of other programs, and a parallel execution control description for describing relationships of the program modules at a time of parallel processing;   a conversion module configured to extract a part relating to each of the program modules from the parallel execution control description stored in the storage, and to create graph data structure creation information including at least preceding information and succeeding information for each of the program modules;   an adding module configured to extract graph data structure creation information to which the input data is given, to create a node based on the extracted graph data structure creation information, the created node comprising an executable node of which all preceding nodes in the graph data structure are execution-completed and a non-executable node, and to add the created node to a formerly created graph data structure based on the preceding information and the succeeding information;   a storing module configured to store the created node into a node memory when all nodes precedent to the created node in the graph data structure are execution-completed; and   an execution module configured to   execute one of a first search and a second search to determine a node to be executed next;   the first search for a node being made in the graph data structure from an executed node to a node having a non-executed child node through an upper layer node, the first search being turned back at the node having the non-executed child node, and the first search being made to the non-executed child node through a lower layer node, the non-executed child node being determined as the node to be executed next, and   the second search for a node being made in the graph data structure to a predetermined upper limit layer node through an upper layer node, the second search being turned back at the predetermined upper limit layer node, and the second search being made to a non-executed node through a lower layer node, the non-executed node being determined as the node to be executed next;   select the determined node to be executed next from nodes stored in the node memory; and   execute a program module corresponding to the selected node,   wherein the execution module is configured to measure a processing time of a program module for determining the node to be executed next in the second search while changing the predetermined upper limit layer and to determine a layer with a minimum processing time as the predetermined upper limit layer.   
     
     
         2 . The apparatus of  claim 1 , wherein the execution module is configured to execute the first search when certain nodes including preceding nodes are all execution-completed. 
     
     
         3 . The apparatus of  claim 1 , wherein the execution module is configured to measure a processing load of a program module when search patterns constituted of a combination of the first search and the second search with changing the predetermined upper limit layer are executed, and to execute one of the search patterns which minimizes the processing load. 
     
     
         4 . The apparatus of  claim 1 , further comprising an updating module configured to detect a manner how a node group is assigned to a real processor in the graph data structure, and to update the graph data structure by regarding the node group as one node if there is a node group to be assigned to the same processor. 
     
     
         5 . A program execution method executed by an information processing apparatus and using program modules executable on condition that input data has been given irrespectively of execution states of other programs and a parallel execution control description for describing relationships of the program modules at a time of parallel processing, the method comprising:
 a conversion step executed by the information processing apparatus, extracting a part relating to each of the program modules from the parallel execution control description stored in a storage, and creating graph data structure creation information including at least preceding information and succeeding information of the program module for each of the program modules;   an adding step executed by the information processing apparatus, extracting graph data structure creation information to which the input data is given, creating a node based on the extracted graph data structure creation information, the created node comprising an executable node of which all preceding nodes in the graph data structure are execution-completed and a non-executable node, and adding the created node to a formerly created graph data structure based on the preceding information and the succeeding information;   a storing step executed by the information processing apparatus, storing the created node into a node memory when all nodes precedent to the created node in the graph data structure are execution-completed; and   an execution step executed by the information processing apparatus, executing one of a first search and a second search to determine a node to be executed next;   the first search for a node being made in the graph data structure from an executed node to a node having a non-executed child node through an upper layer node, the first search being turned back at the node having the non-executed child node, and the first search being made to the non-executed child node through a lower layer node, the non-executed child node being determined as the node to be executed next;   the second search for a node being made in the graph data structure to a predetermined upper limit layer node through an upper layer node, the second search being turned back at the predetermined upper limit layer node, and the second search being made to a non-executed node through a lower layer node, the non-executed node being determined as the node to be executed next; and   executing a program module corresponding to the node to be executed next.   
     
     
         6 . The method of  claim 5 , wherein the execution step comprises executing the first search when certain nodes including preceding nodes are all execution-completed. 
     
     
         7 . The method of  claim 5 , wherein the execution step comprises measuring a processing load of a program module when search patterns constituted of a combination of the first search and the second search with changing the predetermined upper limit layer are executed, and executing one of the search patterns which minimizes the processing load. 
     
     
         8 . The method of  claim 5 , further comprising an updating step of detecting a manner how a node group is assigned to a real processor in the graph data structure, and updating the graph data structure by regarding the node group as one node if there is a node group to be assigned to the same processor. 
     
     
         9 . A non-transitory computer readable medium storing a computer program making processors perform a parallel processing, the computer program controlling a computer to perform steps of:
 storing program modules executable on condition that input data has been given irrespectively of execution states of other programs, and a parallel execution control description for describing relationships of the program modules at a time of parallel processing;   extracting a part relating to each of the program modules from the parallel execution control description stored in the storage, and to create graph data structure creation information including at least preceding information and succeeding information for each of the program modules;   extracting graph data structure creation information to which the input data is given, to create a node based on the extracted graph data structure creation information, the created node comprising an executable node of which all preceding nodes in the graph data structure are execution-completed and a non-executable node, and to add the created node to a formerly created graph data structure based on the preceding information and the succeeding information;   storing the created node into a node memory when all nodes precedent to the created node in the graph data structure are execution-completed; and   executing one of a first search and a second search to determine a node to be executed next;   the first search for a node being made in the graph data structure from an executed node to a node having a non-executed child node through an upper layer node, the first search being turned back at the node having the non-executed child node, and the first search being made to the non-executed child node through a lower layer node, the non-executed child node being determined as the node to be executed next;   the second search for a node being made in the graph data structure to a predetermined upper limit layer node through an upper layer node, the second search being turned back at the predetermined upper limit layer node, and the second search being made to a non-executed node through a lower layer node, the non-executed node being determined as the node to be executed next;   executing a program module corresponding to the node to be executed next.   
     
     
         10 . The non-transitory computer readable medium of  claim 9 , wherein the computer program controlling the computer performs further step of executing the first search when certain nodes including preceding nodes are all execution-completed. 
     
     
         11 . The non-transitory computer readable medium of  claim 9 , wherein the computer program controlling the computer performs further steps of measuring a processing load of a program module when search patterns constituted of a combination of the first search and the second search with changing the predetermined upper limit layer are executed, and executing one of the search patterns which minimizes the processing load. 
     
     
         12 . The non-transitory computer readable medium  claim 9 , wherein the computer program controlling the computer performs further steps of:
 detecting a manner how a node group is assigned to a real processor in the graph data structure, and updating the graph data structure by regarding the node group as one node if there is a node group to be assigned to the same processor.