Binary tree parallel processor

• US 4,860,201 A
• Filed: 09/02/1986
• Issued: 08/22/1989
• Est. Priority Date: 09/02/1986
• Status: Expired due to Term

• Current Assignee: Fifth Generation Computer Corporation
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Miranker, Daniel P., Stolfo, Salvatore J.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/902,547
• Time in Patent Office: 1,085 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 712/11
• CPC Class Codes: G06F 11/0724 in a multiprocessor or a multi-core unit multiprocessors per se G06F15/80
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/22 Detection or location of defective computer hardware by testing during standby operation or during idle time, e.g. start-up testing
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 15/8023 Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: G06F 9/4494 data driven
• CPC Class Codes: G06N 5/00 Computing arrangements using knowledge-based models

Abstract

A plurality of parallel processing elements are connected in a binary tree configuration, with each processing element except those in the highest and lowest levels being in communication with a single parent processing element as well as first and second (or left and right) child processing elements. Each processing element comprises a processor, a read/write or random access memory, and an input/output (I/O) device. The I/O device provides interfacing between each processing element and its parent and children processing elements so as to provide significant improvements in propagation speeds through the binary tree. The I/O device allows the presently preferred embodiment of the invention to be clocked at 12 megahertz, producing in the case of a tree of 1023 processors, each having an average instruction cycle time of 1.8 μs, a system with a raw computational throughput of approximately 570 million instructions per second. The I/O device communicates data and queries from the root processing element to all other N processing elements in the array in one processor instruction cycle instead of in O(log₂ N) processor instruction cycles as in prior art binary tree arrays. Primitive queries are executed in parallel by each processing element and the results made available for reporting back to the root processing element. In several important cases, these results can be combined and reported back to the root processing element in a single processor instruction cycle instead of in O(log₂ N) processor instruction cycles as in prior art binary tree arrays. Thus, the elapsed time for a broadcast and report operation is in effect a constant time regardless of the number of processors in the array.

Claims

1. A parallel processor array comprising:

a plurality of processing elements, each comprising;

a processor having an arithmetic logic unit, control store, program sequences and instruction decoder;

a read/write memory associated with said processor;

an input/output means associated with said processor and read/write memory;

means for interconnecting said processing elements in a binary tree in which each processing element except those at extremities of the binary tree is connected to one parent processing element and at least first and second child processing elements;

said input/output means comprising;

means for broadcasting information received from a parent processing element to said child processing elements, such that common information is distributed to each processing element of the binary tree or a subtree thereof without direct control of the processors of the processing elements; and

means for determining a priority among respective values of information received from said child processing elements and information received from the processor with which said input/output means is associated without direct control of the processors of the processing elements;

wherein the input/output means of the processing elements connected in said binary tree cooperate so that information is broadcast from a first parent processing element to the child processing elements in said binary tree or subtree that are most remote from said first parent processing element, and a priority is determined among values of information at each processing element in said binary tree or subtree, each in a time on the order of the logarithm of the number of processing elements in said binary tree or subtree multiplied by the time for the broadcasting of information from a parent processing element to child processing elements connected thereto, and the time required to determine priority amoung values of information received from the processor of a processing element and the child processing elements connected thereto, respectively.

2. The apparatus of claim 1 wherein said broadcasting means comprises:

a register having a serial data input and an output to said processor,

a flip-flop,

first means for applying data signals simultaneously to said serial data input and said flip-flop, and

second means for applying data signals from said flip-flop to said first means in first and second child processing elements, whereby data signals are propagated through the binary tree or subtree by means of the flip-flops of the processing elements of the binary tree or subtree.

3. The apparatus of claim 2 further comprising:

means for generating a register full signal when said register is full and

means for disabling the transmission of additional data to said plurality of processing elements while said register full signal is being generated.

4. The apparatus of claim 1 wherein the determining means comprises:

first, second and third register, said first register storing data associated with said processing element and said second and third registers storing data associated with said first and second child processing elements,

a comparator for comparing the data stored in said first, second and third registers to select a winning data in accordance with a predetermined priority, and

means for reporting said winning data to one of said second or third registers in a parent processing element.

5. The apparatus of claim 4 further comprising means for disabling each processing element whose data is not selected a winning data, as a result of which every processing element except one is disabled by the time the winning data is reported to the first parent processing element in the binary tree or subtree.

6. The apparatus of claim 5 further comprising means for reporting to the first parent processing element in the binary tree information stored by the processing element that is not disabled.

7. The apparatus of claim 1 further comprising means for subdividing the binary tree into a plurality of sub-trees.

8. The apparatus of claim 7 wherein each sub-tree is operated in a single instruction multiple data mode and the plurality of sub-trees are operated in a multiple instruction multiple data mode.

9. The apparatus of claim 7 wherein at least two of the sub-trees execute identical programs on identical data and the results of such program execution are compared to detect faults in the sub-trees.