A parallel computer and its all-to-all communications method

Claim 2

The parallel computer according to Claim 1, further comprising: a host computer (10) for generating the contents of said phase table (12) containing the data pointing to source and destination processors for each transmission phase depending on the structure of should torus network and the number of said processors.

Claim 3

The parallel computer according to Claim 1, wherein each of said processors forming part of said n-dimensional torus network (15) further comprises: sending DMA control means (22) for controlling a sending of messages to other processors, receiving DMA control means (23) for controlling a receiving of messages from other processors, routing control means (14) for controlling the routing of messages in said torus network (15), central processing means (20) for controlling the operation of all processors.

Claim 4

The parallel computer according to Claim 1, wherein, in the entire process in the inter-processor communications, said phase control table (12) is generated as a table used in combining source and destination processors in each phase, each of said processors forming said n-dimensional torus network (15) selects phases one by one from said phase control table (12) in said phase control means (11) of itself forming part of said n-dimensional torus network (15), said processor determines whether or not it is a current source processor, if no, no actions are taken, if yes, the message is sent to a destination processor, and then processors are synchronized until control is transferred to the next phase, and it is determined whether or not all phases in said phase control table (12) have been selected, if no, the process of and those after selecting phases one by one from said phase control table (12) are repeated, and if yes, the entire process terminates.

Claim 5

The parallel computer according to Claim 1, wherein, in generating said phase control table (12) for storing data pointing to source and destination processors for a predetermined number of transmission phases depending on the structure of said torus network and the number of said processors, if the number of processors a Is an even number, then the first processor element (PE) in a one-dimensional torus network is designated as processor A, the second PE as processor B, the (a/2 + 1)th PE as processor C, (a/2 + 2)th PE as processor D, two phases for inter-processor path ABCDA and path ADCBA in opposite directions to each other are determined, said processor A is shifted clockwise by one from said first PE, and likewise, processors B, C, and D are shifted together, two phases for inter-processor path ABCDA and path ADCBA in opposite directions to each other are determined, it is determined whether or not processor A has arrived at the position of the a/2th PE, if no, a process (subroutine α = S42 - S44) for repeating the processes from step 42 where processor A is shifted from said first PE, and likewise, processors B, C, and D are shifted together are repeated, if yes, the first processor is returned to the position of processor A, the second PE to processor B, the (a/2 + 1)th PE to processor C, and the (a/2 + 2)th PE to processor D, processors B and D are shifted clockwise by one, two phases for path ABCDA and path ADCBA in opposite directions to each other are determined, subroutine α is executed, it is determined whether or not the number of processors a is a multiple of 4, if yes, it is determined whether or not processor B has arrived at the position of the a/4th PE, if no, the processes from S51 where said processors B and D are shifted clockwise by one are repeated, if yes, the first processor is designated as processor A, the (a/4 + 1)th PE as processor B, the (a/2 + 1)th PE as processor C, and the (3a/4 + 1)th PE as processor D, two phases for path ABCDA and path ADCBA in opposite directions to each other are determined, processor A is shifted clockwise by one from said first PE, and likewise, processors B, C, and D are shifted together, two phases for path ABCDA and path ADCBA in opposite directions to each other are determined, it is determined whether or not processor A has arrived at the position of the a/4th PE, if no, the processes from step 62 where processor A is shifted, and likewise, processors B, C, and D are shifted together are repeated, if the number of said processors a is determined not to be a multiple of 4 (in S54), then it is determined whether or not processor B has arrived at the position of the ((a-2)/4 + 1)th PE, if no, the processes from step S51 where said processors B and D are shifted counterclockwise by one are repeated, if processor B is determined to have arrived at the position of the ((a-2)/4 + 1)th PE (in S56), or if processor A is determined to have arrived at the position of the a/4th PE (in S64), then the first PE is designated as processor A, the (a/2 + 1)th PE as C, the (a/4 + 1)th PE as E, and the (3a/4 + 1)th processor as F, the two-point cycle of path ACA and one phase in which processors E and F send messages to themselves are determined, processor A is shifted clockwise by one from said first PE, and likewise, processors C, E, and F are shifted together, the two-point cycle of path ACA and one phase in which processors E and F send messages to themselves are determined, it is determined whether or not processor A has arrived at the position of the a/2th PE, if no, the processes from step 62 where processor A is shifted, and likewise, processors C, E, and F are shifted togethe are regeated, if yes, it is determined whether or not the connection channel is two-directional, if no, then no actions are taken, if yes, a cycle is selected from phases in the same representation in which processor A is shifted to form another cycle operating in the direction opposite to the original phase, thus generating a new phase, it is determined whether or not the dimension of a torus network is two-dimensional, if no, that is, if it is one-dimensional, then the phase control table generating process terminates, if yes, that is, if it is two-dimensional, then two phases are retrieved from the already generated phases to determine one new phase through a cross-product method, it is determined whether or not all combinations are determined for the already generated phases, if not, the processes from S86 in which two phases are retrieved from the already generated phases to determine one new phase through a cross-product method are repeated, when all combinations are determined, a plurality of independent phases are superposed to determine one new phase, and thus the phase control table generating process terminates.

Claim 6

A communications method using a parallel computer having a one-dimensional torus network comprising a processors, wherein if the number of processors a is an even number, the theoretical lower limit L on the number of necessary phases for all-to-all inter-processor communications obtained by multiplying the average number of the moving distances of messages by the number of processors and by the number of said messages transmitted by each processor, and then by dividing the resultant product by the total number N of communications path is L=a²/4 for a one-directional channel or L=a²/8 for a two-directional channel, where the distance between processors is all 1; each processor sends a message to all processors including itself; the shortest distance between processors is assumed including directions opposite to each other; the average value D of the moving distances of messages sent from one processor to all target processors is assigned at a/4; the sum of communication paths N is calculated where the communication path between adjacent processors is 1 for a one-directional connection channel, and 2 for a two-directional connection channel.

Claim 7

A communications method using a parallel computer having a one-dimensional torus network comprising a processors, wherein if the number of processors a is an odd number, the theoretical lower limit L on the number of necessary phases for all-to-all inter-processor communications obtained by multiplying the average number of the moving distances of messages by the number of processors and by the number of said messages transmitted by each processor, and then by dividing the resultant product by the total number N of communications path is calculated, where the distance between processors is all 1; each processor sends a message to all processors including itself; the shortest distance between processors is assumed including directions opposite to each other; the average value D of the moving distances of messages sent from one processor to all target processors is assigned at (a²-1)/4a; the sum of communication paths N is calculated where the communication path between adjacent processors is 1 for a one-directional connection channel, and 2 for a two-directional connection channel.

Claim 8

A communications method using a parallel computer having an n-dimensional torus network (15) comprising a₁ x a₂ x ... a n processors, comprising steps of: sequentially operating predetermined a max P/4 transmission and reception phases where an interprocessor connection channel is one-directional, the maximum value of a₁, a₂, ... , a n determined deponding on the structure of a torus network is defined as a max , and the total number of processors is P, and enabling each processor to send a message to its destination processors predetermined in each phase.

Claim 9

The communications method using a parallel computer according to Claim 8, wherein when the dimension of a torus network indicates a value more than 1, the communications path in each phase is determined by combining the communications paths each being assumed in a phase Where each dimension of a torus network is one-dimensional, and a max P/4 phases are used by superposing phases having a plurality of mutually independent communications.

Claim 10

The communications method using a parallel computer according to Claim 8, wherein when a communications path is determined between a source processor and a destination processor in each phase, a i processors in a torus in an n-dimensional torus network are divided into two adjacent groups each comprising a i /2 processors, a processor at the end of a first group is designated as the first processor, the second processor is selected from the remaining processors in the first group, the processors separate from said first and second processors by a₁/2 are selected as the third and the fourth processors in a second group, and these first, second, third, and fourth processors form a four-point cycle communications path.

Claim 11

The communications method using a parallel computer according to Claim 10, wherein when the dimension of a torus network indicates a value more than 1, the communications path in each phase is determined by combining the communications paths each being assumed in a phase where each dimension of a torus network is one-dimensional, and a max P/4 phases are used by superposing phases having a plurality of mutually independent communications.

Claim 12

A communications method using a parallel computer having an n-dimensional torus network (15) comprising a₁ x a₂ x ... a n processors, wherein when an inter-processor connection channel is one-directional, predetermined a max P/8 transmission phases are sequentially operated, where the maximum value of a₁, a₂, ... , a n determined depending on the structure of a torus network is defined as a max , and the total number of processors is P, and each processor sends a message to its destination processors predetermined in each phase.

Claim 13

The communications method using a parallel computer according to Claim 12, wherein when the dimension of a torus network indicates a value more than 1, the communications path in each phase is determined by combining the communications paths each being assumed in a phase where each dimension of a torus network is one-dimensional, and a max P/8 phases are used by superposing phases having a plurality of mutually independent communications.

Claim 14

A communications method using a parallel computer according to Claim 12, wherein in phases in which an inter-processor connection channel is one-directional, all-to-all communications are performed by superposing two phases mutually independent and having communication directions ogposite to each other, and by using a phase in which a communications path is determined when its interprocessor connection channel is two-directional.

Claim 15

The communications method using a parallel computer according to Claim 14, wherein when the dimension of a torus network indicates a value more than 1, the communications path in each phase is determined by combining the communications paths each being assumed in a phase where each dimension of a torus network is one-dimensional, and a max P/8 phases are used by superposing phases having a plurality of mutually independent communications.