Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2002-04-22
2003-06-10
Chang, Daniel (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S038000
Reexamination Certificate
active
06577159
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of cell-based parallel processing systems. In particular, it relates to high speed routing in a self-configurable system. More particularly, it relates to a system for automatic activation of high-speed bypass routing in a Cell Matrix self-configurable system.
Detailed background on the Cell Matrix can be found in the references, including U.S. Pat. No. 5,886,537. This invention does not directly involve the C-mode behavior of a cell. Only the D-mode operation is directly affected by the present invention.
Most reconfigurable hardware devices (FPGAs) consist of two sets of elements: one set which implements the logical circuits, and another which controls the routing among those logical circuits. Both sets of elements are configured in a fashion which is decided at compile time, i.e., before the device is actually configured. U.S. Pat. No. 5,457,410 is an example of this.
In a self-configurable system such as the Cell Matrix, both logical configuration and routing decisions may be made at run-time, rather than at compile time. Moreover, on a Cell Matrix, the elements which implement logical circuits and those which control routing are exactly the same. These elements, which are called cells, are indistinguishable except for their current configuration. At any time, a given cell may be operating as either a logic element, or as a wire connecting other cells together, or as both.
This fine-grained approach has a number of advantages over other reconfigurable devices, including greater flexibility, easier configuration, scalability of the architecture, and improved fault tolerance. Additionally, whereas other reconfigurable devices such as that disclosed in U.S. Pat. No. 6,292,022 include a fixed number of dedicated routing resources, a Cell Matrix has no dedicated resources. Therefore, a routing-intensive application may use many cells for routing, whereas a more centralized circuit may use most available resources for implementing logic instead of routing. This leads to potentially better resource utilization on a Cell Matrix vs. other reconfigurable devices with dedicated routing resources.
However, there is a performance penalty in using cells to connect other cells together. While cells operate in an unclocked fashion in D mode (in which they are processing inputs and producing outputs accordingly), there is still a non-zero propagation delay t associated with each cell, where t is the time from a change in a cell's inputs to the corresponding change in the cell's outputs. When a series of n cells are configured to act as a wire, i.e., with each cell passing information to a neighboring cell bucket-brigade fashion, there is a minimal propagation delay of n*t. For very large n, as is envisioned with future nano-scale Cell Matrices, this delay can become significant.
Existing FPGAs avoid this issue by using dedicated routing resources, which transfer information throughout the device with minimal delays. On a Cell Matrix, such resources do not exist, and their inclusion would complicate configuration, impair scalability, and reduce the system's tolerance to faults. However, for certain cases, it is possible to have the cells within the matrix autonomously detect their own usage as a wire, and automatically access high-speed connections which bypass the intervening cells, thereby reducing transmission time to 2*t, the propagation delay of two cells (one at each end). This allows the Cell Matrix to remain extremely homogeneous, scalable, and fault tolerant, while eliminating the extensive propagation delays which occur in a wire constructed from Cell Matrix cells such as those outlined in U.S. Pat. No. 6,222,381.
Additionally, with many methods for configuring programmable devices, such as described in U.S. Pat. No. 6,216,259 the configuration string must explicitly specify how routing resources are to be used, thereby complicating the generation of configuration strings. This is particularly troublesome for autonomous, self-configuring systems, since global knowledge may be required for utilization of hierarchical routing resources.
OBJECTS AND ADVANTAGES
Accordingly, several objects and advantages of the present invention are:
a) to augment a Cell Matrix cell to allow for high-speed transmission of information through a series of cells by bypassing each cell's normal input->output mechanism, instead using a direct bypass line;
b) to provide a mechanism which can utilize mechanical switches, allowing for the creation of direct connections between some of a cell's inputs and outputs, thereby further minimizing transmission time across a series of cells;
c) to provide a mechanism for automatically detecting, within each cell, opportunities for high-speed wiring, thereby allowing bypass wiring decisions to be made at run-time, and to be made locally without external intervention;
d) to provide a mechanism for disconnecting unneeded inputs from internal logic circuitry, thereby avoiding needless capacitive loads on such inputs;
e) to allow a Cell Matrix cell to operate correctly both before and after bypass circuitry has been activated;
f) to preserve the scalability of the Cell Matrix architecture by avoiding the addition of structures outside the individual cells;
g) to preserve the homogeneity of the Cell Matrix architecture by allowing all cells to remain identical to each other; and
h) to preserve the fault tolerance of the Cell Matrix architecture by avoiding the addition of permanent, long wires which cross multi-cell regions of the matrix.
Further objects and advantages are to provide a system whose design is regular enough to allow easy manufacturing of larger systems from smaller ones. Still further objects and advantages will become apparent from a consideration of the ensuing description and drawings.
REFERENCES:
patent: 5457410 (1995-10-01), Ting
patent: 5883525 (1999-03-01), Tavana et al.
patent: 5886537 (1999-03-01), Macias et al.
patent: 6054871 (2000-04-01), New
patent: 6216259 (2001-04-01), Guccione et al.
patent: 6292022 (2001-09-01), Young et al.
patent: 6297667 (2001-10-01), Macias
Macias Nicholas Jesse
Raju Murali Dandu
Chang Daniel
Cho James H
LandOfFree
Method and apparatus for automatic high-speed bypass routing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for automatic high-speed bypass routing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for automatic high-speed bypass routing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3110962