Parallel processing system including control computer for dividing an algorithm into subalgorithms and for determining network interconnections

• US 5,016,163 A
• Filed: 06/30/1987
• Issued: 05/14/1991
• Est. Priority Date: 08/30/1985
• Status: Expired due to Fees

• Current Assignee: Anthony J.G. Hey, Christopher R. Jesshope, Denis A. Nicole, Edward K. Lloyd, Patrick S. Pope
• Original Assignee: Anthony J.G. Hey, Christopher R. Jesshope, Denis A. Nicole, Edward K. Lloyd, Patrick S. Pope
• Inventors: Pope, Patrick S., Hey, Anthony J. G., Jesshope, Christopher R., Nicole, Denis A., Lloyd, Edward K.
• Primary Examiner(s): Eng, David Y.
• Assistant Examiner(s): MOHAMED, AYNI Y
• Application Number:
  US07/140,668
• Time in Patent Office: 1,414 Days
• Field of Search: 370/60, 364/200 MS File, 364/900 MS File
• US Class Current: 710/316
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

The device 10 comprises a large number of transputers T₁ to T₁₆ (only T₁ and T₁₆ are shown), T_mem, T_x, T_y, T_z, T_t. These are divided into a set of working transputers T₁ to T₁₆, and a set of interface transputers T_x, T_y, T_z, T_t providing input/output facilities for the device, both sets being under the control of a transputer T_mem.

The transputer T_mem receives instructions for the device and breaks them down into programs for parallel processing by the transputers T₁ to T₁₆. These transputers will normally need to communicate, and the necessary connections are provided by a switch network 12, under the control of the transputer T_mem.

The programs are so allocated to the transputers T₁ to T₁₆ and the switch network 12 is so arranged that direct connections are provided between any transputers which must communicate for the execution of their respective programs.

Other connection arrangements are described, including a universal circuit capable of connecting the transputers T₁ to T₁₆ to form any theoretically possible network.

Claims

1. A data processing device for performing parallel data processing on an algorithm by a plurality of computers performing the data processing in parallel, comprising:

a. a plurality of fully programmable data processing computers for performing the data processing in parallel each fully programmable data processing computer having a plurality of input and output ports;

b. a switch network for effecting connections between the plurality of data processing computers; and

c. a control computer means including;

means for receiving instructions defining an algorithm to be executed, said algorithm comprising at least a number of subalgorithms which may be executed concurrently,

means for translating the algorithm into said subalgorithms for execution in parallel by said plurality of data processing computers,

means for programming the data processing computers to execute the subalgorithms, and

means for controlling the switch network to provide direct connections between the data processing computers which must communicate for the execution of their respective subalgorithms, and

wherein said switch network comprises at least one switch circuit having a first and a second plurality of connections for respective computer ports, and the switch network configuration being controlled by the control computer means to connect the first plurality of connections in any permutation to the second plurality of connections, and

wherein at least some of the computers each have first and second data ports, all of the first ports being connected to respective connections of said first plurality of connections, and all of the second ports being connected to respective connections of said second plurality of connections, and

wherein at least some of the data processing computers form a group, each data processing computer having a plurality of pairs of data ports and wherein corresponding pairs of data ports from each data processing computer of the group are connected to respective common switch circuits, with the ports of each pair being connected, respectively, to one of a first plurality of connections to one of said circuits and to one of a second plurality of connections of said one of said circuits.

2. A data processing device according to claim 1, wherein each data processing computer of said group has a number of ports for connection to other data processing computers of the group, said number of ports being a power of two, and wherein the control means determines the network of connections required between the members of the group for the execution of the algorithm, derives from said network a set of derived networks equivalent to the said network, each derived network requiring only two connections to any computer, and controls each switch circuit to connect ports of one or more data processing computers with corresponding ports to any other data processing computer to configure the data processing computers as a respective derived network.