Worm-hole run-time reconfigurable processor field programmable gate array (FPGA)

• US 5,828,858 A
• Filed: 09/16/1996
• Issued: 10/27/1998
• Est. Priority Date: 09/16/1996
• Status: Expired due to Term

• Current Assignee: Virginia Tech Intellectual Properties, Inc. (Virginia Polytechnic Institute and State University)
• Original Assignee: Virginia Tech Intellectual Properties, Inc. (Virginia Polytechnic Institute and State University)
• Inventors: Athanas, Peter, Bittner, Ray A. Jr.
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US08/714,348
• Time in Patent Office: 771 Days
• Field of Search: 395/311, 395/653, 395/284
• US Class Current: 710/317
• 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 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture

Abstract

Higher performance is gained through a new architecture which implements a new method of computational resource allocation, utilization and programming based on the concept of Worm-hole Run-Time Reconfiguration (RTR). A stream-driven Worm-hole RTR methodology extends contemporary data-flow paradigms to utilize the dynamic creation of operators and pathways, based upon stream processing in which parcels of data move through custom created pathways and interact with other parcels to achieve the desired computation. These parcels independently allocate the necessary computing resources and data paths as they navigate through the platform. The Worm-hole RTR platform consists of a large number of configurable functional units that perform the custom computations and rich, configurable interconnection pathways between the functional units. Once a computational pathway has been established (sensitized) by the head of the stream parcel, data are processed through the pathway with zero overhead. All ports entering the computing platform serve both to configure operations and pathways and to pass computational data streams. As a result, programming and configuration is not limited to a single port. Configuration through multiple independent ports allows greater concurrency, faster reconfiguration, and fewer computational dependencies, all with relatively low cost in silicon.

Claims

1. A data stream driven Worm-hole run-time reconfigurable field programmable gate array (FPGA) implemented on a single chip comprising:

a plurality of independent bi-directional data ports for receiving one or more data streams and outputting one or more data streams, each said data stream containing variable length self-configuring header information and variable length data;

a mesh of interconnected and configurable functional units capable of performing programmed arithmetic operations as defined by said header information; and

an interconnection network responsive to said header information for configuring pathways interconnecting data ports and configurable functional units, said field programmable gate array being configurable at run-time through said plurality of independent bi-directional ports to partially reconfigure for one task while simultaneously performing computations for another task.

2. The data stream driven Worm-hole run-time reconfigurable field programmable gate array recited in claim 1 wherein said mesh of interconnected and configurable functional units comprises an array of interconnected functional unit cells, each cell within the array having four nearest neighbor connections, right and left edges of the array being connected as nearest neighbors forming a toroidal structure, cells along a top of the array receiving inputs from the interconnection network and one output from a bottom of each column of the array being fed back into the interconnection network.

3. The data stream driven Worm-hole run-time reconfigurable field programmable gate array recited in claim 2 further comprising skip bus connections consisting of bi-directional bus segments that run between nearest neighbor cells of the array, the skip bus segments being individually programmable to go in either direction and linked together, providing a data paths between arbitrary cells within the array.

4. The data stream driven Worm-hole run-time reconfigurable field programmable gate array recited in claim 3 wherein each of said function unit cells comprises:

first and second input registers for receiving operands;

a barrel shifter connected to said first register, said barrel shifter being programmable to conditionally shift to the left or to the right to facilitate implementation of multipliers and floating point arithmetic;

an arithmetic logic unit receiving as inputs outputs of the barrel shifter and the second input register; and

a conditional unit connected to receive as inputs outputs of said arithmetic logic unit and said second register and selecting one input as an output.

5. The data stream driven Worm-hole run-time reconfigurable field programmable gate array recited in claim 4 wherein said interconnection network is a crossbar switch.

6. The data stream driven Worm-hole run-time reconfigurable field programmable gate array recited in claim 5 further comprising a dedicated multiplier connected to the crossbar switch for performing multiplication operations.

7. A method of allocating resources in a Worm-hole run-time reconfigurable field programmable gate array (FPGA), comprising the steps of:

inputting a plurality of data streams comprising a self-configuring header and data; and

stripping configuration information from headers of said plurality of data streams and programming computational elements and interconnection resources in the system to form a self-steering stream paths within the system allowing said plurality of data streams to propagate through the field programmable gate array simultaneously.

8. The method of claim 7 wherein the self-configuring header is a variable size programming header and the data is variable size.

9. The method of claim 7 wherein the data streams are object oriented data streams and the self-configuring header contains codes which indicate types of operations to be performed, further comprising the steps of:

comparing the codes against a library of possible physical implementation strategies; and

implementing an efficient method given available hardware resources in the system by mapping an allocation of available hardware to codes in the header.

10. The method of claim 7 wherein computational elements and interconnection resources in the field programmable gate array have addresses and headers of data streams are composed of packets containing addresses, the computational elements and interconnection resources responding only to packets containing their address or a broadcast address to form said self-steering stream paths.

11. The method of claim 10 further comprising the step of modifying addressing information within the header to provide dynamic resource allocation and function remapping allowing several competing processes to allocate resources in the field programmable gate array as they become available.

12. A data stream driven Worm-hole run-time reconfigurable field programmable gate array (FPGA), comprising:

a plurality of independent bi-directional data ports for receiving one or more data streams and outputting one or more data streams, each said data stream containing variable length self-configuring header information and variable length data;

a plurality of interconnected and configurable functional units capable of performing programmed operations as defined by said header information;

at least one interconnection network responsive to said header information for configuring pathways interconnecting data ports and configurable functional units; and

at least one stream controller connected to said interconnection network, said field programmable gate array being dynamically configurable by said stream controller at run-time through said plurality of independent bi-directional ports to partially reconfigure for one task while simultaneously performing computations for another task.