Data-flow multiprocessor architecture with three dimensional multistage interconnection network for efficient signal and data processing

• US 5,021,947 A
• Filed: 01/30/1990
• Issued: 06/04/1991
• Est. Priority Date: 03/31/1986
• Status: Expired due to Fees

• Current Assignee: Hughes Aircraft Company (Rtx Corporation)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Campbell, Michael J., Tucker, George K., Finn, Dennis J., Vedder, Rex W., Vahey, Michael D.
• Primary Examiner(s): Lee, Thomas C.
• Application Number:
  US07/474,707
• Time in Patent Office: 490 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/736, 382/49
• US Class Current: 712/25
• CPC Class Codes: G06F 9/4494 data driven

Abstract

A data-flow architecture and software environment for high-performance signal and data procesing. The programming environment allows applications coding in a functional high-level language 20 which a compiler 30 converts to a data-flow graph form 40 which a global allocator 50 then automatically partitions and distributes to multiple processing elements 80, or in the case of smaller problems, coding in a data-flow graph assembly language so that an assembler 15 operates directly on an input data-flow graph file 13 and produces an output which is then sent to a local allocator 17 for partitioning and distribution. In the former case a data-flow processor description file 45 is read into the global allocator 50, and in the latter case a data-flow processor description file 14 is read into the assembler 15. The data-flow processor 70 consists of multiple processing elements 80 connected in a three-dimensional bussed packet routing network. Data enters and leaves the processor 70 via input/output devices 90 connected to the processor. The processing elements are designed for implementation in VLSI (Very large scale integration) to provide realtime processing with very large throughput. The modular nature of the computer allows adding more processing elements to meet a range of throughout and reliability requirements. Simulation results have demonstrated high-performance operation, with over 64 million operations per second being attainable using only 64 processing elements.

Claims

1. A method of data-flow multiprocessing for highly efficient data and signal processing, including the steps of:

writing a program of instructions in a high-level language onto a storage medium;

reading said program of instructions from said storage medium into a compiler;

compiling by said compiler said instructions by translating said instructions into a plurality of machine instructions;

inputting a file describing a data-flow processor having multiple processing elements, with an identification scheme for said processing elements being formed in accordance with a three-dimensional array of processing elements, into a global allocator program;

running said global allocator program in order to process said plurality of machine instructions in order to assign said machine instructions to a plurality of said processing elements in said data-flow processor for execution of said machine instructions;

inputting a plurality of data into said data-flow processor in order to execute said program in said data-flow processor; and

executing said machine instructions in said data-flow processor; and

wherein said executing step includes a step of employing a template memory in each of said processing elements for identifying data elements from a plurality of said processing elements for arithmetic operations.

2. A method of data-flow multiprocessing for highly efficient data and signal processing, including the steps of:

writing a program of instructions in a graph assembly language onto a storage medium;

reading said program of instructions from said storage medium into an assembler;

inputting a file describing a data-flow processor into an assembler;

assembling by said assembler said instructions by translating said instructions into a plurality of machine instructions;

inputting said machine instructions into a local allocator program for allocation of machine instructions to a data-flow processor having multiple processing elements with an identification scheme for said processing elements being formed in accordance with a three-dimensional array of processing elements in said data flow processor;

running said local allocator program in order to process said plurality of machine instructions in order to assign said machine instructions to a plurality of said processing elements in said data-flow processor for execution of said machine instructions;

inputting a plurality of data into said data-flow processor in order to execute said program in said data-flow processor;

executing said machine instructions in said data-flow processor; and

wherein said executing step includes a step of employing a template memory in each of said processing elements for identifying data elements from a plurality of said processing elements for arithmetic operations.

3. Data-flow apparatus for highly efficient data and signal processing, comprising:

a compilation means for translating instructions written in a high-level data-flow language into a plurality of machine instructions;

a first input ;

means for communicating programs written in said high-level data-flow language to said compilation means;

a data-flow processing means for operating on a plurality of machine instructions;

a global allocation means for accepting a plurality of outputs from said compilation means and for accepting a file of instructions describing said data-flow processing means, said global allocation means allocating said machine, instructions from said compilation means among a plurality of data flow processing elements of said data-flow processing means;

said data-flow processing means further including;

said plurality of data-flow processing elements with an identification scheme for said processing elements being formed in accordance with a three-dimensional array, each of said processing elements including;

a communication part, a processor part, a plurality of first memories, and a template memory for identifying data elements from a plurality of said processing elements for arithmetic operations wherein said communication part, said processor part, and said memories are connected to a bus means;

a bussed packet routing network including a plurality of communications buses connecting said processing elements;

a second input means coupled to said data-flow processing means in order to communicate a plurality of data to said data-flow processing means; and

a plurality of output means coupled to said data-flow processing means in order to communicate a plurality of results from said data-flow processing means to an output terminal means.

4. Data-flow apparatus for highly efficient data and signal processing, comprising:

an assembling means for translating instructions written in a data-flow graph language into a plurality of machine instructions;

a first input means for communicating programs written in said high-level data-flow graph language and for communicating a file of instructions describing a data-flow processing means to said assembling means;

a data-flow processing means for operating on a plurality of machine instructions;

said data-flow processing means further including;

a plurality of data-flow processing elements with an identification scheme said for processing elements being formed in accordance with a three-dimensional array, each of said processing elements including a communications part, a processor part, a plurality of first memories, and a template memory for identifying data elements from a plurality of said processing elements for arithmetic operations wherein said communication part, said processor part, and said memories are connected to a bus means;

a bussed packet routing network including a plurality of communications buses connecting said processing elements;

a local allocation means for accepting a plurality of outputs from said assembling means, said local allocation means allocating said machine instructions from said assembling means among the processing elements of said data-flow processing means;

a second input means coupled to said data-flow processing means in order to communicate a plurality of data to said data-flow processing means; and

a plurality of output means coupled to said data-flow processing means in order to communicate a plurality of results from said data-flow processing means to an output terminal means.

5. Data-flow apparatus for highly efficient data and signal processing, comprising:

a compilation means for translating instructions written in a high-level data-flow language into a plurality of machine instructions;

a first input means for communicating program written in said high-level data-flow language to said compilation means;

a data-flow processing means for operating on a plurality of machine instructions, said data-flow processing ;

means including a plurality of data-flow processing elements, and a three-dimensional bussed packet routing network including a plurality of communications buses connecting said processing elements;

a global allocation means for accepting a plurality of outputs from said compilation means and for accepting a file of instructions describing said data-flow processing means, said global allocation means allocating said machine instructions from said composition means among the processing elements of said data-flow processing means;

a second input means coupled to said data-flow processing means in order to communicate a plurality of data to said data-flow processing means; and

a plurality of output means coupled to said data-flow processing means in order to communicate a plurality of results from said data-flow processing means to an output terminal means; and

wherein said processing element further comprises;

a plurality of communication means for transmission and reception of digital signals;

a first communication part connected to said plurality of communication means, which includes a plurality of first queues, a plurality of connections between said first queues, and a first memory connected to one of said first queues;

a processor part which includes a plurality of micromachines, a plurality of second queues, a plurality of second memories, and a plurality of connections between said micromachines, said second memories, and said second queues;

a plurality of third memories connected to receive addresses from said processor part and to supply to or receive data from said processor part; and

a bus connecting said communication part to said processor part.

6. Data-flow apparatus for highly efficient data and signal processing as described in claim 5 in which said three-dimensional bussed packet routing network further includes a bidirectional plane bus, a bidirectional column bus, and a bidirectional row bus, and in which each said processing element is connected to said bidirectional plane, column, and row buses.

7. Data-flow apparatus for highly efficient data and signal processing as described in claim 6 in which each said communication part of each said processing element further includes:

a bidirectional processor bus;

a first-in-first-out plane input buffer queue, connected to said plane bus;

a first-in-first-out plane output buffer queue, connected to said plane bus;

a first-in-first-out column input buffer queue, connected to said column bus;

a first-in-first-out column output buffer queue, connected to said column bus;

a first-in-first-out row input buffer queue, connected to said row bus;

a first-in-first-out row output buffer queue, connected to said row bus;

a first-in-first-out processor input buffer queue, connected to said processor bus;

a first-in-first-out processor output buffer queue, connected to said processor bus;

a first internal bus connected to said processor input, plane input, column input, and row input buffer queues for sending packets from said processor, plane, column, and row input buffer queues to said processor, plane, column, and row output queues

a second internal bus connected to said processor output, plane output, column output, and row output buffer queue for sending packets from said processor, plane, column, and row input buffer queues to said processor, plane, column, and row output buffer queues;

an error memory; and

a bidirectional error memory bus connecting said error memory to said processor input buffer queue; and

each said processor part of each said processing element further includes;

a template memory controller micromachine;

a fire detect memory, forming part of said template memory controller micromachine;

an arithmetic and logic unit (ALU) micromachine;

a microprocessor, forming part of said ALU micromachine;

a micromemory, forming part of said ALU micromachine which controls said ALU micromachine;

a destination tagger micromachine;

a destination memory controller micromachine;

a template memory, connected to said template memory controller micromachine so as to receive addresses from said template memory controller micromachine and to receive data from or supply data to said template memory controller micromachine;

a first-in-first-out firing queue, connected from said template memory controller micromachine to said ALU micromachine;

a first-in-first-out result queue connected from said ALU micromachine to said destination tagger micromachine;

a bidirectional controller bus linking said destination memory controller micromachine to said template memory controller micromachine;

a first-in-first-out feedback queue connected from said destination tagger micromachine to said bidirectional controller bus;

a first-in-first-out "to communication" queue connected from said destination tagger micromachine to said bidirectional processor bus;

a first-in-first-out "from communication" queue connected from said bidirectional processor bus to said bidirectional controller bus;

a first-in-first-out associated information queue;

a first-in-first-out destination queue;

a destination memory, connected to said destination memory controller micromachine so as to receive addresses from said destination memory controller micromachine; and

a bidirectional destination memory data bus connected to said destination memory and linking said destination memory with said destination queue, said associated information queue, and said ALU micromachine, to communicate data between said destination memory and said destination queue, said associated information queue, and said ALU micromachine.

8. Data-flow apparatus for highly efficient data and signal processing as described in claim 7 in which said processor part of said processing element and said communication part of said processing element are both implemented in very large scale integration (VLSI) circuitry.

9. Data-flow apparatus for highly efficient data and signal processing, comprising:

an assembly means for translating instructions written in a data-flow graph language into a plurality of machine instructions;

a first input means for communicating programs written in said data-flow graph language and for communicating a file of instructions describing a data-flow processing means to said assembling means;

a data-flow processing means for operating on a plurality of machine instructions, said data-flow processing means including a plurality of data-flow processing elements, and a three-dimensional bussed packet routing network including a plurality of communications buses connecting said processing elements;

a local allocation means for accepting a plurality of outputs from said assembling means, said local allocation means allocating said machine instructions from said assembling means among the processing elements of said data-flow processing means;

a second input means coupled to said data-flow processing means in order to communicate a plurality of data to said data-flow processing means; and

a plurality of output means coupled to said data-flow processing means in order to communicate a plurality of results from said data-flow processing means to an output terminal means; and

wherein each said processing element further includes;

a plurality of communication means for transmission and reception of digital signals;

a communication part which includes a plurality of first queue, a plurality of connections between said first queues, and a first memory connected to one of said first queues;

a processor part which includes a plurality of micromachines, a plurality of second queues, a plurality of second memories, and a plurality of connections between said micromachines, said second memories, and said second queues;

a plurality of third memories connected so as to receive addresses form said processor part and to supply to or receive data from said processor part; and

a bus connecting said communication part to said processor part.

10. Data-flow apparatus for highly efficient data and signal processing as described in claim 9 in which said three-dimensional bussed packet routing network further includes a bidirectional plane bus, a bidirectional column bus, and a bidirectional row bus, and in which each said processing element is connected to said bidirectional plane, column, and row buses.

11. Data-flow apparatus for highly efficient data and signal processing as described in claim 10 in which each said communication part of each said processing element further includes:

a bidirectional processor bus;

a first-in-first-out plane input buffer queue, connected to said plane bus;

a first-in-first-out plane output buffer queue, connected to said plane bus;

a first-in-first-out column input buffer queue, connected to said column bus;

a first-in-first-out column output buffer queue, connected to said column bus;

a first-in-first-out row input buffer queue, connected to said row bus;

a first-in-first-out row output buffer queue, connected to said row bus;

a first-in-first-out processor input buffer queue, connected to said processor bus;

a first-in-first-out processor output buffer queue, connected to said processor bus;

a first internal bus connected to said processor input, plane input, column input, and row input buffer queues for sending packets from said processor, plane, column, and row input buffer queues to said processor, plane, column, and row output queues;

a second internal bus connected to said processor output, plane output, column output, and row output buffer queue for sending packets from said processor, plane, column, and row input buffer queues to said processor, plane, column, and row output buffer queues;

an error memory; and

a bidirectional error memory bus connecting said error memory to said processor input buffer queue; and

each said processor part of each said processing element further includes;

a template memory controller micromachine;

a fire detect memory, forming part of said template memory controller micromachine;

an arithmetic and logic unit (ALU) micromachine;

a microprocessor, forming part of said ALU micromachine;

a micromemory, forming part of said ALU micromachine, which controls said ALU micromachine;

a destination tagger micromachine;

a destination memory controller micromachine;

a template memory, connected to said template memory controller micromachine so as to receive addresses from said template memory controller micromachine and to receive data from or supply data to said template memory controller micromachine;

a first-in-first-out firing queue, connected from said template memory controller micromachine to said ALU micromachine;

a first-in-first-out result queue connected from said ALU micromachine to said destination tagger micromachine;

a bidirectional controller bus linking said destination memory controller micromachine to said template memory controller micromachine;

a first-in-first-out feedback queue connected from said destination tagger micromachine to said bidirectional controller bus;

a first-in-first-out "to communication" queue connected from said destination tagger micromachine to said bidirectional processor bus;

a first-in-first-out "from communication" queue connected from said bidirectional processor bus to said bidirectional controller bus;

a first-in-first-out associated information queue;

a first-in-first-out destination queue;

a destination memory, connected to said destination memory controller micromachine so as to receive addresses from said destination memory controller micromachine; and

a bidirectional destination memory data bus connected to said destination memory and linking said destination memory with said destination queue, said associated information queue, and said ALU micromachine, to communicate data between said destination memory and said destination queue, said associated information queue, and said ALU micromachine.

12. Data-flow apparatus for highly efficient data and signal processing as described in claim 11 in which said processor part of said processing element and said communication part of said processing element are both implemented in very large scale integration (VLSI) circuitry.