Electronic digital logic circuitry – Multifunctional or programmable – Having details of setting or programming of interconnections...
Reexamination Certificate
1999-12-31
2001-04-24
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Having details of setting or programming of interconnections...
C326S038000, C326S039000, C326S040000, C326S041000
Reexamination Certificate
active
06222381
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of fine-grained self-configurable hardware. In particular, it relates to a self-configurable parallel processing system composed of a regular collection of cells whose specific behavior is controlled by software contained within each cell. More particularly, it relates to a self-configurable processing system where each cell's software is stored in a non-shifting memory contained within the cell.
Reconfigurable devices are hardware whose specific behavior can be specified via software contained within the device. Such devices have found numerous applications in a variety of areas. They are useful for rapid prototyping, for allowing minor changes to be made to circuitry in the field, or for reusing a small amount of hardware for different applications. More recently, reconfigurable devices have been used extensively in evolvable hardware research, where circuits are designed not by humans, but by machines, using a trial-and-error approach.
A common problem with reconfigurable devices is how to modify their configuration as quickly as possible. Early reconfigurable devices, such as U.S. Pat. No. 5,128,559 to Steele (1992), use RAM within the device to store configuration information. This RAM is controlled via an external processor, which sends configuration strings into the RAM, thereby determining the configuration of the device.
This approach has serious drawbacks, since as the device size increases, so does the size of the configuration string. U.S. Pat. No. 5,394,031 to Britton, et al. (1995) describes a reconfigurable device which is partially reconfigurable, meaning that if only one piece of the configuration is being changed, the entire configuration string need not be sent. Rather, a subset describing just the changed pieces can be sent to update the existing configuration. This allows minor modifications to a device's existing configuration, but does not improve the speed for reconfiguring large sections of the device.
U.S. Pat. No. 5,742,180 to DeHon, et al. (1998) describes a reconfigurable device supporting multiple contexts, so the configuration of circuits within the device can be changed rapidly via a relatively short context-switch command. However, this only allows rapid switching among pre-programmed contexts. Loading in a new configuration for the entire device is still extremely time-consuming, with configuration time generally increasing with device size.
All these devices suffer from a common problem, in that their reconfiguration is externally controlled, which fundamentally limits the configuration bandwidth. Since the configuration information is being supplied by an external controller, there is an inherent bottleneck in the transmission of configuration information.
U.S. Pat. No. 5,886,537 to Macias, et al. (1999) describes a self-configurable device which circumvents this fundamental limitation. This device consists of a large number of regularly-connected reconfigurable cells. These cells can process data as well as configuration information interchangeably, thus allowing the task of configuring the device to be distributed among the reconfigurable cells themselves. In this case, a device with more cells therefore automatically contains more configuration controllers as well. This allows configuration of multiple sections of the device to occur in parallel, offering tremendous speedup potential. This device also has other advantages, including a regular structure which has benefits both in terms of fault tolerance and ease of manufacturing.
However, the device described in U.S. Pat. No. 5,886,537 has disadvantages as well. Its biggest disadvantage is the complexity of the underlying cell structure. The largest part of each cell's circuit is the memory employed for storing the cell's configuration information. This memory is implemented as a shift register, since the basic configuration mechanism is to serially shift in a new configuration truth table, while serially shifting out the cells' old truth table.
One disadvantage of using a shift register is the size required to implement such a circuit. In the prototype cMOS implementation of the device, approximately 50% of each cell's 2500 transistors were used for implementing the shift register. Moreover, higher-dimensional versions of the basic cell require significantly more bits for their truth table. For example, whereas a 4-sided cell requires 128 bits of storage, a 6-sided cell requires 768 bits of storage for the truth table. In contrast, the other parts of the circuit grow linearly with the number of sides. So a 6-sided device might require 1900 transistors for miscellaneous logic vs. 7500 for the memory, meaning the memory alone accounts for 80% of the device's transistors. Therefore, it is advantageous to reduce the size and complexity of the truth table memory within the basic cell.
Additionally, in the system described by U.S. Pat. No. 5,886,537, since a cell's truth table is actually being shifted as the cell is programmed, the truth table stored within a cell during its programming is generally only correct after the cell is fully programmed. Even if only a few bits are being changed, the entire truth table is disturbed by the programming operation. If the cell were to momentarily or prematurely leave its configuration (C-) mode, the truth table (which the cell would immediately start executing) would be incorrect. Viewed another way, as a bit is shifted into a cell's truth table, there is no way to know the final position of that bit in the cell's truth table. The bit is shifted throughout the truth table, and its eventual position depends on when the cell exits C-mode.
This is a serious drawback for evolvable hardware work, where essentially random bit streams will be loaded into a cell's truth table. Without knowing the position each bit will occupy in the target cell's truth table, there is no way to prevent the programmed cell from entering an unrecoverable state. While such unrecoverable states do not physically damage the device, they do make individual cells unusable until the entire system is reset.
OBJECTS AND ADVANTAGES
Accordingly, several objects and advantages of the present invention are:
a) to provide a configurable data processing cell whose behavior can be specified via an internally stored truth table;
b) to provide a cell structure whereby each cell can process both data and configuration information from neighboring cells;
c) to provide a self-configurable system composed of a regular collection of such cells, thereby allowing distributed, internal configuration control;
d) to provide a cell structure which can utilize a truth table memory with fewer transistors than a shift register with the same storage capacity;
e) to provide a cell structure which can utilize a truth table memory which is higher density than a shift register with the same storage capacity;
f) to provide a cell programming paradigm where each bit loaded into a cell's truth table immediately occupies its correct intended location in the truth table;
g) to provide a cell programming paradigm which allows a truth table to be partially configured, with only the loaded bits being changed;
h) to provide a cell programming paradigm which allows a partial programming cycle to be followed by another programming cycle, such that the second cycle begins at the start of the truth table, even though the first cycle terminated prior to reaching the end of the truth table.
Further objects and advantages are to provide a cell structure in which certain subsystems of each cell's circuitry can be shared among multiple cells, thereby leading to smaller and simpler individual cells. Still further objects and advantages will become apparent from a consideration of the ensuing descriptions and drawings.
REFERENCES:
patent: 4034356 (1977-07-01), Howley et al.
patent: 5128559 (1992-07-01), Steele
patent: 5394031 (1995-02-01), Britton et al.
patent: 5450557 (1995-09-01), Kopp et a
Durbeck Lisa J. K.
Macias Nicholas J.
Tan Vibol
Tokar Michael
LandOfFree
Self-configurable parallel processing system made from... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Self-configurable parallel processing system made from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-configurable parallel processing system made from... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2524674