Massively parallel multiple-folded clustered processor mesh array

• US 6,041,398 A
• Filed: 06/26/1992
• Issued: 03/21/2000
• Est. Priority Date: 06/26/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pechanek, Gerald George, Vassiliadis, Stamatis, Delgado-Frias, Jose Guadalupe
• Primary Examiner(s): Follansbee, John A.
• Application Number:
  US07/904,916
• Time in Patent Office: 2,825 Days
• Field of Search: 395/27, 395/800, 395/21, 395/375, 364/DIG. 1, 364/513, 712/10-22, 712/202, 712/215, 708/100, 708/200, 710/100, 710/104, 711/229, 709/221, 713/100, 382/181, 706/15, 345/505
• US Class Current: 712/11
• CPC Class Codes: A21B 1/245 with a plurality of air nozzles to obtain an impingement effect on the food
• CPC Class Codes: A21B 1/48 with surfaces in the form of an endless band

Abstract

A massively parallel diagonal-fold mesh array processor provides a triangular diagonally folded mesh computer with the same functionality as a square mesh computer but with half the number of connection wires. The diagonal-fold mesh array processor is modified in this invention to provide a more general purpose processor node and to enhance the connectivity between the processing nodes while still providing the image processing and finite difference capabilities of the original structure. By repeatedly folding the triangular diagonal-fold array structure, processing elements are placed together which, with additional connections, allows the improvement in connectivity. This enhancement would be difficult to achieve in a standard mesh organization. The resultant folded structure maintains the functionality of the original mesh while expanding its capabilities. A bitonic sort example is presented which demonstrates the utility of the enhanced connectivity. The multiple folded array concept is applied to a six neighborhood hexagonal array demonstrating the general nature of the concept.

Claims

1. A triple-folded array parallel computing system comprising:

a plurality of processing elements (PEs) each coupled to a plurality of others of said PEs such that the plurality of PEs is logically equivalent to at least a square two dimensional array configuration of PEs having an equal number of PE'"'"'s as said computing system, for executing at least algorithms executable on the two dimensional array configuration;

each of the PEs comprising;

a plurality of I/O ports for sending and receiving instructions and data to and from coupled ones of the PEs, means for executing instructions, and means for storing instructions and data;

a portion of the PEs paired by a first diagonal fold in said square array into a plurality of symmetric PEs forming a first fold mesh, the symmetric PEs each comprising a pair of a first PE and a second PE sharing each of said I/O ports as shared ports for sending and receiving instructions and data such that each of the pair of PEs communicates with PEs originally coupled to the first PE and with PEs originally coupled to the second PE of said pair of PEs, said pair of PEs including PE_ij and PE_ji, where i and j are column and row designators of a PE in said logically equivalent square two dimensional array configuration, and where i and j are positive non-equal integers;

a remaining portion of the PEs configured into a plurality of diagonal PEs, the diagonal PEs each coupled to two symmetric PEs each via one of said shared ports; and

said plurality of symmetric PEs and diagonal PEs grouped by consecutive second and third folds in said first fold mesh, into a plurality of clusters each comprising a plurality of PEs, a portion of the clusters each comprising four symmetric PEs and a remaining portion of the clusters each comprising two diagonal PEs, the plurality of clusters each comprising an additional coupling between a pair of previously uncoupled PEs.

2. The computing system of claim 1 executing a convolution algorithm for image processing in said means for executing instructions.

3. The computing system of claim 1 wherein said I/O ports each comprise a bit serial interface.

4. The computing system of claim 1 wherein said I/O ports comprise an interface for broadcasting initialization parameters to each of said plurality of PEs.

5. The computing system of claim 1, wherein the PEs are interconnected using half as many coupling paths as the square two dimensional array.

6. The computing system of claim 1 executing a bitonic sorting algorithm comprising less than half the number of data transfers required by the two dimensional array configuration executing the bitonic sorting algorithm in said means for executing instructions.

7. A triple-folded array parallel computing system comprising:

a plurality of processing elements (PEs) each coupled to a plurality of others of said PEs such that the plurality of PEs is logically equivalent to at least a hexagonal array configuration of PEs having an equal number of PEs as said computing system, for executing at least algorithms executable on the hexagonal array configuration;

each of the PEs comprising;

a plurality of I/O ports for sending and receiving instructions and data to and from coupled ones of the PEs, means for executing instructions, and means for storing instructions and data;

a portion of the PEs paired by a first fold in said hexagonal array into a plurality of dual PEs, forming a first fold mesh, the dual PEs each comprising a pair of a first PE and a second PE sharing said ports as shared ports for sending and receiving instructions and data such that each of the pair of PEs communicates with PEs originally coupled to the first PE and with PEs originally coupled to the second PE of said pair of PEs;

another portion of the PEs remaining as individual PEs and coupled to a dual PE each via one of said shared ports; and

said plurality of dual PEs and individual PEs grouped by consecutive second and third folds in said first fold mesh, into a plurality of clusters comprising a plurality of PEs, a portion of the clusters each comprising three dual PEs and another portion of the clusters each comprising three individual PEs, said portion of clusters and said another portion of clusters each comprising an additional coupling between a pair of previously uncoupled PEs.