Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-10-26
2001-08-14
An, Meng-Al T. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C712S220000, C712S225000, C712S020000, C709S200000, C709S213000, C709S212000, C709S236000
Reexamination Certificate
active
06275845
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a communications apparatus in a multiprocessor system in which a plurality of processors are connected by communication paths having a variety of performance levels. More particularly, the invention relates to a collective communication apparatus in which a plurality of processors participate in communication and data is scattered and/or gathered.
BACKGROUND OF THE INVENTION
Collective communication in which a plurality of processors participate can be divided into scatter collective communication, in which one processor serving as a root scatters data to all other processors, and gather collective communication, in which one processor serving as the root gathers data from all processors. Data is sent and received between the root processor and other processors in both of types of collective communication. If this is realized in simple fashion, data need only be sent individually between the root processor and other processors.
When such processing is actually carried out, however, the processors execute communication serially, the result of which is greatly degraded performance. In general, therefore, collective communication is performed through parallel processing as much as possible by using a binary-tree approach. More specifically, as shown in
FIG. 7
, which illustrates schematically the scattering of data in scatter collective communication, it is known that the expansion and gathering of data in a plurality of processors proceed in steps of the square of
2
, whereby high-speed processing can be achieved. The system comprises 16 processors, among which those indicated by the black circles are processors that possess data and those indicated by the white circles are processor that wait for data. At step
1
, the first data possessing processor, which is located at the extreme left, delivers data to the neighboring second processor by communicating with this processor. At step
2
, the first and second processors possessing data each skip one processor to communicate with third and fourth processors, respectively, that are waiting for data. As a result, the first through fourth processors come to possess data. Thus, at step
4
, the eight processors on the left side communicate with the eight processors on the right side. As a result, all 16 processors come to possess data in four steps.
SUMMARY OF THE DISCLOSURE
However, if there is a difference in the data transfer capability of the communication paths that connect the plurality of processors participating in collective communication, there will be instances where communication concentrates in the communication path having the lowest transfer performance, depending upon how the participating processors are arranged in the binary tree. This invites a decline in the performance of collective communication.
Thus, if there is a difference in the data transfer performance of the communication paths that connect a plurality of processors when collective communication is carried out using the binary-tree approach as is for all processors of a multiprocessor system, communication may concentrate in the communication path having the lowest transfer performance. The result can be degraded collective communication performance.
Accordingly, an object of the present invention is to provide a collective communication apparatus, system or method in which a decline in communications performance is mitigated in collective communication in a multiprocessor system.
Other objects of the present invention will become apparent in the entire disclosure.
According to one aspect of the present invention, the foregoing object is attained by providing a collective communication apparatus in a multiprocessor system constituted by a plurality of processors connected by communication paths having various performance levels, comprising processor group defining means, master-processor registration updating means, collective communication execution control means, and list-referring collective communication execution means. The processor group defining means defines sets of processors or of previously decided master processors, which participate in program execution and are connected by communication paths of the same performance levels when collective communication is executed, as processor groups in dependence upon the performance levels of the communication paths, to create processor group lists on a per-performance level basis upon deciding a provisional master processor in any of the groups of processors. The master-processor registration updating means updates the created processor group lists in such a manner that a root processor specified by a collective communication request will become a master processor. The collective communication execution control means presents the lists in order of increasing performance if the collective communication request is a scatter request, and/or in order of decreasing performance if the collective communication request is a gather request. The list-referring collective communication execution means refers to the list delivered from the collective communication execution control means and, if its own processor is included in any of the lists, performing collective communication with all processors included in the list.
According to a second aspect of the present invention, there is provided a collective communication apparatus in a multiprocessor system constituted by a plurality of processors connected by communication paths having various performance levels, wherein each processor comprises:
(a) processor group defining means for defining processor groups, each of which comprises processors capable of implementing data transfer on a communication path of the same performance level, from the plurality of processors connected by the communication paths having various performance levels, and creating lists of processor groups on a per-performance basis in terms of the communication paths;
(b) collective communication execution control means for controlling/deciding, in dependence upon type of collective communication and on the basis of the lists, the order in which communication is executed; and
(c) list-referring collective communication execution means for referring to the lists and performing collective communication with the processors in accordance with the order controlled/decided by the collective communication execution control means.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.
REFERENCES:
patent: 4814979 (1989-03-01), Neches
patent: 5371896 (1994-12-01), Gove et al.
patent: 5440687 (1995-08-01), Coleman et al.
patent: 5673423 (1997-09-01), Hillis
patent: 5828894 (1998-10-01), Wilkinson
patent: 5948060 (1999-09-01), Gregg et al.
patent: 6047323 (2000-04-01), Krause
Kirk L. Johnson, “The impact of Communication Locality on Large-Scale Multiplrocessor Performance,” Proceedings of the 19th Annual International Symposium on Computer Architecture; pp. 392-402, May, 1992, Queenland Australia.
An Meng-Al T.
Lin Wen-Tai
NEC Corporation
Sughrue Mion Zinn Macpeak & Seas, PLLC
LandOfFree
Collective communication apparatus in multiprocessor system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Collective communication apparatus in multiprocessor system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Collective communication apparatus in multiprocessor system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2456319