Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-07-27
2001-06-26
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C712S011000, C709S241000
Reexamination Certificate
active
06253372
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method of generating a communication schedule for transmitting and receiving data between processors constituting a parallel computer or a distributed multiprocessor system. In particular, the invention, in addition to being realized as one of the functions that a parallel compiler itself has, can also be employed in a communication library which is called out when an object program compiled by a parallel compiler is executed.
BACKGROUND ART
An important component for enhancing the performance of a parallel computer or a distributed multiprocessor system is the communication procedure in which communication is performed when transmitting and receiving data between processors. The communication speed between processors is considerably slower compared with the operating speed of a processor. Therefore, if communication is inefficiently performed, an enhancement in the system performance cannot be expected.
Thus, the conventional method performs inter-processor communication by using a relatively simple communication pattern of an asynchronous communication library. For this reason, there is the possibility that the communication waiting state will frequently occur. Consequently there are cases where a parallel computer which communicates data by a method such as this cannot exhibit sufficiently high performance.
Accordingly, it is an objective of the present invention to generate an optimum communication schedule in the communication between processors constituting a parallel computer or a distributed multiprocessor system.
Another objective of the present invention is to prevent a reduction in the efficiency of a system by preventing a reduction in the efficiency of a memory or a virtual memory system.
SUMMARY OF THE INVENTION
To achieve the aforementioned objectives, a first aspect of the invention provides a method of determining a communication schedule in the case where data communication is performed between a plurality of processors of a system. The method comprises the steps of (1) sorting processors, which transmit and receive data through the inter-processor communications, into a plurality of groups, (2) generating communication graphs each of which has nodes respectively corresponding to said groups and edges respectively corresponding to said inter-processor communications, for distances of said nodes, and (3) determining said communication schedule of said inter-processor communications so that the generated communication graphs correspond to communication steps of the inter-processor communication.
A second aspect of the invention provides a method of determining a communication schedule in the case where data communication is performed between a plurality of processors of a system. The method comprises the steps of (1) sorting processors, which transmit and receive data through the inter-processor communications, into N groups, (2) generating N−1 communication graphs each of which has N nodes respectively corresponding to said groups and edges respectively corresponding to said inter-processor communications, for distances
1
through N−1 of said nodes, and (3) determining said communication schedule of said inter-processor communications so that the generated N−1 communication graphs correspond to communication steps of the inter-processor communication.
A third aspect of the invention provides a recording medium whereupon there is recorded a computer program for determining a communication schedule in the case where data communication is performed between a plurality of processors of a system. The recording medium comprises (1) first instruction means for sorting processors, which transmit and receive data through the inter-processor communications, into a plurality of groups, (2) second instruction means for generating communication graphs each of which has nodes respectively corresponding to said groups and edges respectively corresponding to said inter-processor communications, for distances of said nodes, and (3) third instruction means for determining said communication schedule of said inter-processor communications so that the generated communication graphs correspond to communication steps of the inter-processor communication.
A fourth aspect of the invention provides a recording medium whereupon there is recorded a computer program for determining a communication schedule in the case where data communication is performed between a plurality of processors of a system. The recording medium comprises (1) first instruction means for sorting processors, which transmit and receive data through the inter-processor communications, into N groups, (2) second instruction means for generating N−1 communication graphs each of which has N nodes respectively corresponding to said groups and edges respectively corresponding to said inter-processor communications, for distances
1
through N−1 of said nodes, and (3) third instruction means for determining said communication schedule of said inter-processor communications so that the generated N−1 communication graphs correspond to communication steps of the inter-processor communication.
A fifth aspect of the invention provides a system which has a plurality of processor modules each comprising a processor, memory means, and communication means and where said communication means is able to input and output data at the same time. The system includes a parallel compiler which, when compiling a source program, executes an object program which includes a communication schedule for processors generated by executing the aforementioned methods.
Finally, a sixth aspect of the invention provides a system which has a plurality of processor modules each comprising a processor, memory means, and communication means and where said communication means is able to input and output data at the same time. The system includes a parallel compiler which, when compiling a source program to an object program, relates a parallel processing program region of said source program to a run time library which executes the aforementioned methods. The object program is executed based on a communication schedule for processors determined by executing said run time library when said object program is executed.
In accordance with the aforementioned aspects, a communication graph representing the communication relation between processors is generated wherein the communication which is executed may be grasped as a whole. Each pair of nodes that communicate are linked by an edge. Each edge of a communication graph is a communication between processors which is performed in a certain communication step. Those edges of a communication graph have the same distance. Therefor, when one communication related to a certain processor is executed in a certain communication step, the processor can be prevented from being occupied in another communication. In this way, occurrences of the waiting state of the processor can be reduced.
Particularly when communication graphs are generated for the distances
1
through N−1 of N nodes, these graphs are equivalent to complete communication graphs of N nodes. The optimum communication schedule of the complete communication graph whose communication amount is the same can be considered to be the coloring problem of a complete graph, and N−1 colors, that is, N−1 communication steps are optimum. By using this concept, optimum communication steps are generated.
REFERENCES:
patent: 4387427 (1983-06-01), Cox et al.
patent: 4598400 (1986-07-01), Hillis
patent: 4814973 (1989-03-01), Hillis
patent: 4972314 (1990-11-01), Getzinger et al.
patent: 4984235 (1991-01-01), Hillis
patent: 5247694 (1993-09-01), Dahl
patent: 5590345 (1996-12-01), Barker et al.
patent: 5737623 (1998-04-01), Liebrock
patent: 5742821 (1998-04-01), Prasanna
Al-Mouhamed, Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs, IEEE Transactions on Software Engineering, vol. 16, No. 12, Dec. 1990.*
Gam
Komatsu Hideaki
Ogasawara Takeshi
Cutter Lawrence D.
Gonzalez Floyd A.
International Business Machines - Corporation
Nguyen-Ba Hoang-Vu Anthony
Powell Mark R.
LandOfFree
Determining a communication schedule between processors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Determining a communication schedule between processors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining a communication schedule between processors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2514012