Patent US5828858A successfully refreshed from Google Patents.
US5828858A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Worm-hole run-time reconfigurable processor field programmable gate array (FPGA)
Assignee: Virginia Tech Intellectual Properties Inc
•
Filing: 1996-09-16
•
Granted: 1998-10-27
•
Expires: 2016-09-16
Abstract
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.
Inventors
- 👤 Peter Athanas
- 👤 Ray A. Bittner, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 15:06
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/76; G06F15/78; G06F15/7867; G06F15/16; G06F15/163; G06F15/173; G06F15/17337; G06F15/17343; G06F15/17356; G06F15/17368; G06F15/17381
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
121 words
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.
Claim 2
Dependent Claim
121 words
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.
Claim 3
Dependent Claim
90 words
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.
Claim 4
Dependent Claim
59 words
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.
Claim 5
Dependent Claim
106 words
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.
Claim 6
Dependent Claim
23 words
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.
Claim 7
Dependent Claim
29 words
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.
Claim 8
Independent Claim
77 words
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.
Claim 9
Independent Claim
77 words
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.
Claim 10
Dependent Claim
21 words
The method of claim 7 wherein the self-configuring header is a variable size programming header and the data is variable size.
Claim 11
Dependent Claim
68 words
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.
Claim 12
Dependent Claim
53 words
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.
Claim 13
Dependent Claim
41 words
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.
Claim 14
Dependent Claim
132 words
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.
Claim 15
Dependent Claim
132 words
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.
References Cited (Backward Citations)
US5105424A
Cited
US5175733A
Cited
US5509128A
Cited
US5497498A
Cited
US5535342A
Cited
US5583990A
Cited
US5535406A
Cited
US5701416A
Cited
US5671432A
Cited
US5745734A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-26 | 2002-04-27 | 2002-10-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-26 | 2006-04-27 | 2006-10-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-26 | 2010-04-27 | 2010-10-27 | $7700.00 | Window Closed / Lapsed |