US 5,021,947 A · Data-flow multiprocessor architecture with three dimensional multistage interconnection network for efficient signal and data processing

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.

Claims12

Dependent claims

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.

7 more elements

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.

11 more elements

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.

12 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims12