Methods for operating parallel computing systems employing sequenced communications

Claim 1

A method for parallel processing, comprising: (a) inputting data and a problem-solving algorithm for a problem to be solved by a N-dimension parallel computer using logarithmic fanout; (b) configuring a sufficient subspace of dimension m required to solve the problem, where m is less than or equal to N; (c) mapping a n-dimension spatial grid, where n is less than or equal to m, by allocating work to specific processors of the parallel computer; (d) opening the subspace and inputting the data, execution parameters, and the algorithm into the subspace using logarithmic fanout; (e) processing data according to algorithm within each processor; (f) writing messages to each of the selected neighboring processors paired in directions in a specified order of writing first to the neighboring processor in a fore orientation and then writing to the neighboring processor in an aft orientation such that the startup, copy, and transfer time for a subsequent message overlaps the transfer time for a previous message; (g) repeating step (f) until all selected neighboring processors of the n-dimensional spatial grid have been written to; (h) and, when at a boundary, and in the direction of a boundary where there is only one orientation, writing to only one processor associated with that orientation; (i) subsequently reading messages from each of the selected neighboring processors in paired directions in the same order of directions, but reading first from the neighboring processor in the aft orientation and then reading from the neighboring processor in the fore orientation such that the startup and transfer time for a subsequent message overlaps the transfer and copy time for a previous message; (j) repeating step (i) until all selected neighboring processors of the n-dimensional spatial grid have been read; and (k) and, when at a boundary, and in the direction of a boundary where there is only one orientation, reading from only one processor associated with that orientation; (l) outputting the solution to the problem; (m) closing the subspace; and (n) displaying the solution to the problem.

Claim 2

A method for parallel processing, comprising: (a) inputting data and a problem-solving algorithm for a problem to be solved by a N-dimension parallel computer using logarithmic fanout; (b) configuring a sufficient subspace of dimension m required to solve the problem, where m is less than or equal to N; (c) mapping a n-dimension spatial grid, where n is less than or equal to m, by allocating work to specific processors of the parallel computer; (d) opening the subspace and inputting the data, execution parameters, and the algorithm into the subspace using logarithmic fanout; (e) processing data according to algorithm within each processor; (f) writing messages to each of the selected neighboring processors paired in directions in a specified order of writing first to the neighboring processor in a fore orientation and then writing to the neighboring processor in an aft orientation such that the startup, copy, and transfer time for a subsequent message overlaps the transfer time for a previous message; (g) repeating step (f) until all selected neighboring processors of the n-dimensional spatial grid have been written to; (h) and, when at a boundary, and in the direction of a boundary where there is only one orientation, writing to only one processor associated with that orientation; (i) subsequently reading messages from each of the selected neighboring processors in paired directions in the same order of directions, but reading first from the neighboring processor in the aft orientation and then reading from the neighboring processor in the fore orientation such that the startup and transfer time for a subsequent message overlaps the transfer and copy time for a previous message; (j) repeating step (i) until all selected neighboring processors of the n-dimensional spatial grid have been read; and (k) and, when at a boundary, and in the direction of a boundary where there is only one orientation, reading from only one processor associated with that orientation; (l) outputting the solution to the problem; (m) closing the subspace; and (n) displaying the solution to the problem.

Claim 5

A method of organizing and communicating information in a MIMD parallel processing computer system, wherein the parallel processing computer system includes a plurality of processors interconnected with a plurality of neighboring processors, comprising: a) within each processor, obtaining computational results and then grouping said computational results in dependent variable arrays; b) organizing the dependent variable arrays into large data structures; c) concatenating the data structures into a single message; and d) communicating the single message by global exchange, whereby bi-directional communications of the single message are initiated in a specified sequential order between a processor and selected of its neighboring processors and the communications are overlapped.

Claim 6

A method of organizing and communicating information in a MIMD parallel processing computer system, wherein the parallel processing computer system includes a plurality of processors interconnected with a plurality of neighboring processors, comprising: a) within each processor, obtaining computational results and then grouping said computational results in dependent variable arrays; b) organizing the dependent variable arrays into large data structures; c) concatenating the data structures into a single message; and d) communicating the single message by global exchange, whereby bi-directional communications of the single message are initiated in a specified sequential order between a processor and selected of its neighboring processors and the communications are overlapped.

Claim 11

A method of increasing the efficiency of a N dimension parallel processing computer, wherein the parallel processing computer includes a plurality of processors interconnected with up to N neighboring processors, comprising: a) allocating data associated with a given problem to specific processors of the parallel processing computer; b) inputting parameters and programs into each processor with logarithmic fanout; c) combining items of data into a single message; and d) simultaneously communicating the single message between neighboring processors with a global exchange technique, whereby bidirectional communications of the single message are initiated in a specified sequential order between a processor and selected of its neighboring processors and the communications are overlapped.

Claim 12

A method of increasing the efficiency of a N dimension parallel processing computer, wherein the parallel processing computer includes a plurality of processors interconnected with up to N neighboring processors, comprising: a) allocating data associated with a given problem to specific processors of the parallel processing computer; b) inputting parameters and programs into each processor with logarithmic fanout; c) combining items of data into a single message; and d) simultaneously communicating the single message between neighboring processors with a global exchange technique, whereby bidirectional communications of the single message are initiated in a specified sequential order between a processor and selected of its neighboring processors and the communications are overlapped.

Claim 15

A method for increasing the efficiency of a N dimension parallel processing computer, wherein the parallel processing computer includes a plurality of processors interconnected with up to N neighboring processors, comprising: a) allocating specific problem solving functions of a given problem to specific processors; b) inputting parameters and programs to each processor with logarithmic fanout; c) combining items of data into a single message; and d) simultaneously exchanging data between selected neighboring processors, whereby bidirectional communications of the exchanged data are initiated in a specified sequential order between a processor and selected of its neighboring processors; and e) overlapping processor initiated communications with neighboring processors.

Claim 16

A method for increasing the efficiency of a N dimension parallel processing computer, wherein the parallel processing computer includes a plurality of processors interconnected with up to N neighboring processors, comprising: a) allocating specific problem solving functions of a given problem to specific processors; b) inputting parameters and programs to each processor with logarithmic fanout; c) combining items of data into a single message; and d) simultaneously exchanging data between selected neighboring processors, whereby bidirectional communications of the exchanged data are initiated in a specified sequential order between a processor and selected of its neighboring processors; and e) overlapping processor initiated communications with neighboring processors.