Scheduling computation processes including all-to-all communications (A2A) for pipelined parallel processing among plurality of processor nodes constituting network of n-dimensional space

1. A method of scheduling a plurality of computation processes including all-to-all communications (A2A) among a plurality of processor nodes constituting a network of processor nodes having a torus or a mesh form based on n (n>2) dimensions on an n-dimensional space, the method comprising the steps of:

selecting, by a processor node, a first plurality of processor nodes from the plurality of processor nodes, the first plurality of processor nodes forming a longest axis corresponding to a dimension of said network of processor nodes as a first subgroup;

providing a first processing comprising an all-to-all longest communications (A2A-L) only among the first plurality of processor nodes included in the first subgroup;

selecting, by the processor node, a second plurality of processor nodes from the plurality of processor nodes, the second plurality of processor nodes including all remaining axes other than the longest axis as a second subgroup;

providing a second processing comprising an all-to-all plane communications (A2A-P) only among the second plurality of processor nodes included in the second subgroup; and

scheduling, using a plurality of threads in the processor node, the plurality of computation processes for pipelined parallel processing at the processor node in a first time interval and subsequent time intervals such that in a second time interval immediately following the first time interval and in said subsequent time intervals the first all-to-all longest communications processing (A2A-L) overlaps with the second all-to-all plane communications processing (A2A-P) across the plurality of threads in the processor node and such that a single thread of the processor node is only able to perform said first all-to-all longest communications processing (A2A-L) in the first time interval and said subsequent time intervals, and the completion of said first all-to-all longest communications processing (A2A-L) in the first subgroup occurs before proceeding to a next computation process at said single thread,

wherein said next computation process at said single thread includes said all-to-all plane communications processing (A2A-P) in the second subgroup, and

said scheduling including scheduling the plurality of computation processes for said pipelined parallel processing in such a way as to enable the first all-to-all longest communications processing (A2A-L) all at a first thread of the processor node and a Fast Fourier Transformation (FFT) computation process or a matrix transpose computation process at a second thread of the processor node to be processed in parallel.

2. The method according to claim 1 , further comprising the step of selecting a group including all nodes as a first group in a case where all axes have the same length and scheduling the computation processes in such a way that the all-to-all communications in the first subgroup are sequentially performed.

3. The method of claim 1 , wherein said network of processor nodes comprises one or more longest axes, said selected processor nodes of said first subgroup arranged in an axial form in a case where there is only one longest axis, or said selected processor nodes of said first subgroup arranged in a form based on the number of network dimensions which is equal to the number of the longest axes.

4. The scheduling method of claim 1 , configured for transforming a 1-Dimensional Fast Fourier Transform (FFT) of length N into a two-dimensional (2D) FFT (N>N 2 ) where N=N 1 ×N 2 , wherein N 1 and N 2 are the lengths of two FFT dimensions.

5. A method of scheduling a plurality of computation processes including all-to-all communications (A2A) among a plurality of processor nodes constituting a network of processor nodes having a cubic or non-cubic torus or mesh form on a three-dimensional space, the method comprising the steps of:

selecting, by a processor node, a first plurality of processor nodes from the plurality of nodes, the first plurality of processor nodes forming a longest axis corresponding to a dimension of said network of processor nodes as a first subgroup;

providing a first processing comprising an all-to-all longest communications (A2A-L) only among the first plurality of processor nodes included in the first subgroup;

selecting a second plurality of processor nodes from said plurality of processor nodes, the second plurality of processor nodes including all remaining axes other than the longest axis as a second subgroup;

providing a second processing comprising an all-to-all plane communications (A2A-P) only among the second plurality of processor nodes included in the second subgroup; and

scheduling, using a plurality of threads in the processor node, the plurality of computation processes for pipelined parallel processing at the processor node in a first time interval and subsequent time intervals such that in a second time interval immediately following the first time interval and in said subsequent time intervals the first all-to-all longest communications processing (A2A-L) overlaps with the second all-to-all plane communications processing (A2A-P) across the plurality of threads in the processor node and such that a single thread of the processor node is only able to perform said first all-to-all longest communications processing (A2A-L) in the first time interval and said subsequent time intervals, and the completion of said first all-to-all longest communications processing (A2A-L) in the first subgroup occurs before proceeding to a next computation process at said single thread,

wherein said next computation process at said single thread includes said all-to-all plane communications processing (A2A-P) in the second subgroup, and

said scheduling including scheduling the plurality of computation processes for said pipelined parallel processing in such a way as to enable the first all-to-all longest communications processing (A2A-L) at a first thread of the processor node, and a Fast Fourier Transformation (FFT) computation process or a matrix transpose computation process at a second thread of the processor node to be processed in parallel.

6. The method of claim 5 , wherein said network of processor nodes comprises a single longest axis, said selected processor nodes of said first subgroup arranged in an axial form in a case where there is only one longest axis, or said selected processor nodes of said first subgroup are arranged in a plane.

7. The scheduling method of claim 5 , configured for transforming a 1-Dimensional Fast Fourier Transform (FFT) of length N into a two-dimensional (2D) FFT (N>N 2 ) where N=N 1 ×N 2 , wherein N 1 and N 2 are the lengths of two FFT dimensions.

8. A computer program product for scheduling a plurality of computation processes including all-to-all communications (A2A) for one or more processors nodes among a plurality of processor nodes constituting a network of processor nodes having a torus or a mesh form based on n (n>2) dimensions on an n-dimensional space and causing the one or more processor nodes to execute the scheduling, the computer program product embodied as a non-transitory machine readable storage medium, the machine readable storage medium storing a program code executable by a processor device, the code comprising:

a code for causing the one or more processor nodes to select a first plurality of processor nodes from the plurality of nodes, the first plurality of processor nodes forming a longest axis corresponding to a dimension of said network of processor nodes as a first subgroup;

a code for causing the one or more processor nodes to provide a first processing comprising an all-to-all longest communications (A2A-L) only among the first plurality of processor nodes included in the first subgroup;

a code for causing the one or more processor nodes to select a second plurality of processor nodes from said plurality of processor nodes, the second plurality of processor nodes including all remaining axes other than the longest axis as a second subgroup;

a code for causing the one or more processor nodes to provide a second processing comprising an all-to-all plane communications (A2A-P) only among the second plurality of processor nodes included in the second subgroup; and

a code for causing the one or more processor nodes to schedule using a plurality of threads in a processor node, the plurality of computation processes for pipelined parallel processing at the processor node in a first time interval and subsequent time intervals such that in a second time interval immediately following the first time interval and in said subsequent time intervals the first all-to-all longest communications processing (A2A-L) overlaps with the second all-to-all plane communications processing (A2A-P) across the plurality of threads in the processor node and such that a single thread of the processor node is only able to perform said first all-to-all longest communications processing (A2A-L) in the first time interval and said subsequent time intervals, and the completion of said first all-to-all longest communications processing (A2A-L) in the first subgroup occurs before proceeding to a next computation process at said single thread,

wherein said next computation process at said single thread includes said all-to-all plane communications processing (A2A-P) in the second subgroup, and

said scheduling including scheduling the plurality of computation processes for said pipelined parallel processing in such a way as to enable the first all-to-all longest communications processing (A2A-L) at a first thread of the processor node, and a Fast Fourier Transformation (FFT) computation process or a matrix transpose computation process at a second thread of the processor node to be processed in parallel.

9. The computer program product according to claim 8 , further comprising a code for causing the one or more processor nodes to select a group including all nodes as a first group in a case where all axes have the same length and to schedule the computation processes in such a way that the all-to-all communications in the first subgroup are sequentially performed.

10. The computer program product of claim 8 , wherein said network of processor nodes comprises one or more longest axes, said selected processor nodes of said first subgroup arranged in an axial form in a case where there is only one longest axis, or said selected processor nodes of said first subgroup arranged in a form based on the number of network dimensions which is equal to the number of the longest axes.

11. The computer program product of claim 8 configured for transforming a 1-Dimensional Fast Fourier Transform (FFT) of length N into a two-dimensional (2D) FFT (N 1 , N 2 ) where N=N 1 ×N 2 , wherein N 1 and N 2 are the lengths of two FFT dimensions.

12. A computer program product for scheduling a plurality of computation processes including all-to-all communications (A2A) for one or more processor nodes among a plurality of processor nodes constituting a network of processor nodes having a cubic or non-cubic torus or mesh form on a three-dimensional space and causing the one or more processor nodes to execute the scheduling, the computer program product embodied as a non-transitory machine readable storage medium, the machine readable storage medium storing program code executable by a processor device comprising:

a code for causing the one or more processor nodes to select a first plurality of processor nodes from the plurality of nodes, the first plurality of processor nodes forming a longest axis corresponding to a dimension of said network of processor nodes as a first subgroup;

a code for causing the one or more processor nodes to provide a first processing comprising an all-to-all longest communications (A2A-L) only among the first plurality of processor nodes included in the first subgroup;

a code for causing the one or more processor nodes to select a second plurality of processor nodes from said plurality of processor nodes, the second plurality of processor nodes including all remaining axes other than the longest axis as a second subgroup;

a code for causing the one or more processor nodes to provide a second processing comprising an all-to-all plane communications (A2A-P) only among the second plurality of nodes included in the second subgroup; and

a code for causing the one or more processor nodes to schedule using a plurality of threads in a processor node the plurality of computation processes for pipelined parallel processing at the processor node in a first time interval and subsequent time intervals such that in a second time interval immediately following the first time interval and in said subsequent time intervals the first all-to-all longest communications processing (A2A-L) overlaps with the second all-to-all plane communications processing (A2A-P) across the plurality of threads in the processor node and such that a single thread of the processor node is only able to perform said first all-to-all longest communications processing (A2A-L) in the first time interval and said subsequent time intervals, and the completion of said first all-to-all longest communications processing (A2A-L) in the first subgroup occurs before proceeding to a next computation process at said single thread,

wherein said next computation process at said single thread includes said all-to-all plane communications processing (A2A-P) in the second subgroup, and

said scheduling including scheduling the plurality of computation processes for said pipelined parallel processing in such a way as to enable the first all-to-all longest communications processing (A2A-L) at a first thread of the processor node and a Fast Fourier Transformation (FFT) computation process or a matrix transpose computation process at a second thread of the processor node to be processed in parallel.

13. The computer program product of claim 12 , wherein said network of processor nodes comprises a single longest axis, said selected processor nodes of said first subgroup arranged in an axial form in a case where there is only one longest axis, or said selected processor nodes of said first subgroup are arranged in a plane.

14. A parallel computer system comprising: a processor; wherein the processor is configured to performing a plurality of computation processes including all-to-all communications (A2A) in parallel among a plurality of processor nodes constituting a network of processor nodes having a torus or mesh form based on n (n>2) dimensions on an n-dimensional space, the parallel computer system performing the plurality of computation processes in parallel by:

selecting a first plurality of processor nodes from said plurality of processor nodes, the first plurality of processor nodes forming a longest axis corresponding to a dimension of said network of processor nodes as a first subgroup;

providing a first processing comprising an all-to-all longest communications (A2A-L) only among the first plurality of processor nodes included in the first subgroup;

selecting a second plurality of processor nodes from said plurality of processor nodes, the second plurality of processor nodes including all remaining axes other than the longest axis as a second subgroup;

providing a second processing comprising an all-to-all plane communications (A2A-P) only among the second plurality of processor nodes included in the second subgroup; and

scheduling, using a plurality of threads in a processor node, the plurality of computation processes for pipelined parallel processing at the processor node in a first time interval and subsequent time intervals such that in a second time interval immediately following the first time interval and in said subsequent time intervals the first all-to-all longest communications processing (A2A-L) overlaps with the second all-to-all plane communications processing (A2A-P) across the plurality of threads in each processor node and such that a single thread of the processor node is only able to perform said first all-to-all longest communications processing (A2A-L) in the first time interval and said subsequent time intervals, and the completion of said first all-to-all longest communications processing (A2A-L) in the first subgroup occurs before proceeding to a next computation process at said single thread,

wherein said next computation process at said single thread includes said all-to-all plane communications processing (A2A-P) in the second subgroup, and

said scheduling including scheduling the plurality of computation processes for said pipelined parallel processing in such a way as to enable the first all-to-all longest communications processing (A2A-L) all at a first thread of the processor node and a Fast Fourier Transformation (FFT) computation process or a matrix transpose computation process at a second thread of the processor node to be processed in parallel.

15. The parallel computer system of claim 14 , wherein said network of processor nodes comprises one or more longest axes, said selected processor nodes of said first subgroup arranged in an axial form in a case where there is only one longest axis, or said selected processor nodes of said first subgroup arranged in a form based on the number of network dimensions which is equal to the number of the longest axes.

16. The parallel computer system of claim 14 configured for transforming a 1-Dimensional Fast Fourier Transform (FFT) of length N into a two-dimensional (2D) FFT (N>N 2 ) where N=N 1 ×N 2 , wherein N 1 and N 2 are the lengths of two FFT dimensions.

17. A parallel computer system comprising: a processor; wherein the processor is configured to perform a plurality of computation processes including all-to-all communications (A2A) in parallel among a plurality of processor nodes constituting a network of processor nodes having a cubic or non-cubic torus or mesh form on a three-dimensional space, the parallel computer system performing the plurality of computation processes in parallel by:

selecting a first plurality of processor nodes from said plurality of processor nodes, the first plurality of processor nodes forming a longest axis corresponding to a dimension of said network of processor nodes as a first subgroup;

providing a first processing comprising an all-to-all longest communications (A2A-L) only among the first plurality of processor nodes included in the first subgroup;

selecting a second plurality of processor nodes from said plurality of processor nodes, the second plurality of processor nodes including all remaining axes other than the longest axis as a second subgroup;

providing a second processing comprising an all-to-all plane communications (A2A-P) only among the second plurality of nodes included in the second subgroup; and

scheduling, using a plurality of threads in a processor node, the plurality of computation processes for pipelined parallel processing at the processor node in a first time interval and subsequent time intervals such that in a second time interval immediately following the first time interval and in said subsequent time intervals the first all-to-all longest communications processing (A2A-L) processing overlaps with the second all-to-all plane communications processing (A2A-P) across the plurality of threads in the processor node and such that a single thread of the processor node is only able to perform said first all-to-all longest communications processing A2A-L in the first time interval and said subsequent time intervals, and the completion of said first all-to-all longest communications processing (A2A-L) in the first subgroup occurs before proceeding to a next computation process at said single thread,

wherein said next computation process at said single thread includes said all-to-all plane communications processing (A2A-P) in the second subgroup, and

said scheduling including scheduling the plurality of computation processes for said pipelined parallel processing in such a way as to enable the first all-to-all longest communications processing (A2A-L) at a first thread of the processor node and a Fast Fourier Transformation (FFT) computation process or a matrix transpose computation process at a second thread of the processor node to be processed in parallel.

18. The parallel computer system of claim 17 , wherein said network of processor nodes comprises a single longest axis, said selected processor nodes of said first subgroup arranged in an axial form in a case where there is only one longest axis, or said selected processor nodes of said first subgroup arranged in a plane.