SIMD machine using cube connected cycles network architecture for vector processing

• US 4,621,339 A
• Filed: 06/13/1983
• Issued: 11/04/1986
• Est. Priority Date: 06/13/1983
• Status: Expired due to Fees

• Current Assignee: Duke University
• Original Assignee: Duke University
• Inventors: Wagner, Robert A., Poirier, Charles J.
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): WILLIAMS JR, ARCHIE E
• Application Number:
  US06/503,654
• Time in Patent Office: 1,240 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/488-491
• US Class Current: 712/22
• CPC Class Codes: G06F 15/8007 single instruction multiple data [SIMD] multiprocessors

Abstract

A single instruction, multiple data stream parallel computer using bit-serial arithmetic whereby the machine'"'"'s basic operation is performing Boolean operations on huge vectors of 0'"'"'s and 1'"'"'s. The machine utilizes an architectural approach whereby the memory of a conventional machine having 2^k words each t bits long, is reorganized into p registers each 2^k bits in length and adding processor logic to each bit position of the registers and a communication network being added which allows for the 2^k pieces of processing logic to interact. This machine is capable of executing a wide variety of algorithms at a speed of 2^k /p to 2^k /p² faster than conventional machines. The machine provides for an ability to handle a variety of algorithms by interconnecting the individual processor elements in a general interconnection network capable of performing a permutation of n bits held one in every processor element in a time of (O(log(n)).

Claims

1. A single instruction multiple data processor comprising:

a plurality of processing elements, interconnected in a Cube Connected Cycle Network design and using interprocessor communication links which carry one bit at a time in both directions simultaneously;

controller means for controlling each of said plurality of processor elements which feeds each of said processor elements identical local memory addresses, identical switching control bits, identical Boolean function selection codes, and distinct activation control bits, depending on each of said processor'"'"'s position in said Cube Connected Cycles Network in a prescribed fashion; and

a plurality of input/output devices connected to said network by a plurality of switching devices wherein,

each of said plurality of processing elements comprises;

two single-bit accumulator registors (A, B);

two Boolean function generator units, each of which computes any one of 2⁸ possible Boolean functions of three Boolean variables as specified by Boolean function codes sent 2 at a time by said controller to each of said processing elements;

3. A single instruction multiple data processor according to claim 1, wherein a multiple of 32 of said plurality of processing elements are placed on one VLSI chip in such a way that all processing elements on one chip use the same address decoding circuits.

4. A single instruction muliple data processor according to claim 1, wherein one of the addressable bits of said memory inhibits the changing of information in the remainder of said memory when said addressable bit is in a predetermined one of its states.

5. A single instruction multiple data processor according to claim 1, wherein each processing element holds single bits and wherein said processing element is designed so that in one memory cycle the value of the contents of the addressed cell can be read out and routed through the Boolean function circuitry so that the result of said combination can be routed in order to replace the contents of the addressed cell of said processing element of said memory.

6. A single instruction multiple data processor according to claim 1, wherein each of said processing elements has a position number with those of said plurality of processing elements having the same position number being controlled simultaneously in response to a distinct activation control bit which is sent to each of said processing elements whereby the value of said distinct activation control bit determines which said processing elements respond to instructions given to all said processing elements so that the control of those processing elements having the same position number is independent of others of said processing elements having different position numbers.

8. A single instruction multiple data processor according to claim 1 wherein said plurality of processing elements are formed in an array wherein each of said processing elements has at least as much silicon area, on the same chip, devoted to the bits of addressable memory accessable to each of said processing elements, as is devoted to the Boolean Logic and information routing circuitry within said each processing element and wherein in said bits of addressable memory includes any of at least 100 bits of addressable memory and wherein said processing elements provide for a computation of the SUM and CARRY bits of a single-bit binary addition in one memory cycle.

2. switching circuit means controlled by said controller which select the three inputs to the logic function generators and to which switching circuitry provides that the output of one of said generators is fed to a first one of said registers (B) and the output of the other generator is fed to a second one of said registers (A) and an addressed memory cell of a local memory wherein said local memory consists of at least k bits and at most p bits where p is chosen to be appropriate to VLSI technology so that the space on a VLSI chip required by an entire processing element is at least one-half devoted to the processing elements'"'"'s memory.

7. A single instruction multiple data processor comprising:

a plurality of processing elements, interconnected in a Cube Connected Cycle Network design and using interprocessor communication links which carry one bit at a time in both directions simultaneously;

controller means for controlling each of said plurality of processor elements which feeds each of said processor elements identical local memory addresses, identical switching control bits, identical Boolean function selection codes, and distinct activation control bits, depending on each of said processor'"'"'s position in said Cube Connected Cycles Network in a prescribed fashion; and

a plurality of input/output devices connected to said network by a plurality of switching devices wherein,

said cube connected cycles consist of Q * 2^Q processing elements arranged in 2^Q cycles of Q processing elements each, wherein each processing element X is numbered by a pair of X_c, X_p where X_c is the cycle number to which processing element X belongs and X_p is processing elements X'"'"'s position number within its cycle and wherein connections are provided between each processing element and its successor, predecessor and lateral neighbors defined between processing element (c, p) and the processing elements numbered (C, (p+1) mod Q), (C,(p-1) mod Q), and (D, p) such that the absolute value of C-D=2^P.