Data updating method using overlap area and program converting device for converting update program in distributed-memory parallel processor

Abstract

In a parallel processor, a local area and an overlap area are assigned to the memory of each processing element (PE), and each PE makes calculations to update the data in both areas at the runtime. If the data in the overlap area is updated in processes closed in the PEs, the data transfer between adjacent PEs can be reduced and the parallel processes can be performed at a high speed.

What is claimed is:  
     
       1. A program converting device for use in an information processing device for converting an input program into a program to be executed in a parallel processor comprising a plurality of processing elements and a communications network, comprising: 
       a detecting means for detectingunit to detect in the input program a loop portion in which optimization can be realized using an overlap area; and  
       a setting means for convertingunit to convert the input program by assigning an overlap area to a processing element processing the loop portion and generating a code based on which data in the overlap area is calculatedupdated through calculations in multiple iterations using only the data in the processing element, and for outputting a converted program.  
     
     
       2. The program converting device according to  claim 1 , wherein said detecting means  unit detects as said loop portion a parallel loop encompassed by a serial loop, said parallel loop being able to be optimized using the overlap area. 
     
     
       3. The program converting device according to  claim 1 , wherein said setting means  unit generates a code such that data can be processed twice consecutively without communications after the processing element processing said loop portion updates the overlap area through communications with an adjacent processing element. 
     
     
       4. The program converting device according to  claim 1   
       further comprising:  a size determining means for   unit determining an optimum size of the overlap area after estimating process time for said loop portion, and  
       wherein said setting means  unit assigns the overlap area of a size determined by said size determining means  unit to the processing element processing said loop portion.  
     
     
       5. The program converting device according to  claim 4 , wherein said size determining means  unit determines the optimum size such that the process time for said loop portion becomes short. 
     
     
       6. A program converting device for use in an information processing device for converting an input program into a program to be executed in a parallel processor comprising a plurality of processing elements and a communications network, comprising: 
       a detecting means for detectingunit to detect in the input program a loop portion in which optimization can be realized using an overlap area; and  
       a setting means for convertingunit to convert the input program by assigning an overlap area to a processing element processing the loop portion and generating a code based on which data is updated in the overlap area through single direction data transfer and data in the processing element is shifted in a direction of the data transfer, and for outputting a converted program.  
     
     
       7. The program converting device according to  claim 6 , 
       further comprising:  a communications change means for changing  unit to change data dependency in processing said loop portion from bi-directional transfer to single direction transfer and for generating a subscript of an array in which the single direction data transfer can be performed, and 
       wherein said setting means  unit generates a code for use in updating the data using the subscript in said array generated by said communications change means  unit.  
     
     
       8. The program converting device according to  claim 7 , wherein said communications change means  unit changes a direction of a distance vector representing the data dependency into single direction among processing elements and generates the subscript of the array using a changed distance vector. 
     
     
       9. The program converting device according to  claim 7 , wherein said communications change means  unit generates the subscript of the array such that a data layout of the processing element processing said loop portion can be shifted in a particular  the direction of the data transfer each time data is processed, shifted data layout covering two processing elements. 
     
     
       10. The program converting device according to  claim 9 , wherein said setting means  unit generates a code to return the shifted data layout after processing said loop portion to an original data layout. 
     
     
       11. A program converting device for use in an information processing device for converting an input program into a program to be executed in a parallel processor comprising a plurality of processing elements and a communications network, comprising: 
       a detecting means forunit detecting in the input program a loop portion in which optimization can be realized using an overlap area; and  
       a setting means forunit converting the input program by assigning an overlap area to a processing element processing the loop portion and generating a code based on which data in the overlap area is calculatedupdated through calculations in multiple iterations using only the data in the processing element and a code passed on which the data in the overlap area is updated through single direction data transfer, and for outputting a converted program.