Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2000-10-31
2001-10-02
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S038000
Reexamination Certificate
active
06297667
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of cell-based parallel processing systems composed of a regular collection of processing cells whose behavior is controlled by software contained within each cell. In particular, it relates to a processing system called the Cell Matrix (U.S. Pat. No. 5,886,537 (Macias, et al.)) composed of self-dual processing cells which each operate in one of two modes, one mode being a data processing mode, and the other being a code processing mode. More particularly, it relates to configurations of such cells to enable non-adjacent cells to interact with each other as if they were adjacent.
Self-dual processing cells are programmable logic devices which can interchangeably process both data and code. Such cells are self-dual in that they are able to both configure other cells and be configured by other cells. Collections of self-dual cells can be assembled into a self-reconfigurable system, called a cell matrix. U.S. Pat. No. 5,886,537 discusses in detail such self-dual processors as well as their assembly into a processing matrix.
Devices such as field programmable gate arrays (FPGAs) and programmable logic devices (PLDs) generally employ mechanisms to allow their programmable blocks to interact with each other despite their possibly non-adjacent locations. For example, U.S. Pat. No. 5,212,652 (Agrawal, et al.) describes an interconnect system to allow flexible connection among the device's logic blocks, including connections between blocks on opposite sides of the device.
In contrast, the cells within a cell matrix interact only with nearby cells which are adjacent according to a fixed, pre-defined system topology. This simple interaction scheme has several advantages over more sophisticated routing systems.
Since both data and configuration information are exchanged only among small sets of neighbors, there is no need for system-wide address and data buses. Since the set of possible sources and destinations is limited to the number of adjacent cells, the size of each cell's address space is fixed, independent of the total number of cells in the system.
Hence a matrix of such cells is infinitely scalable, in that two such matrices can simply be attached along their boundaries, with adjacent boundary cells connected between the two matrices, to produce a larger matrix. This scalability has profound advantages in terms of manufacturing large cell matrices. This simple interconnection scheme also has tremendous benefits in terms of fault tolerance, since it eliminates most architecturally-critical failure points.
Additionally, the presence of local control at all points within the matrix allows reconfiguration tasks to be distributed throughout the matrix, allowing multiple configurations to be performed in parallel. This offers dramatic speedup potential of configuration tasks for extremely large matrices as compared to an externally-configured device.
It is therefore clear that the local-only interaction scheme of a cell matrix has definite advantages over a system with centralized control and global communications, such as an FPGA. However, these advantages come at a price. Because cells are only configurable by adjacent neighboring cells, there remains the question of how one set of cells can configure another set of non-adjacent remote cells. Since any cell has direct access to only a small, fixed number of adjacent neighboring cells, there is no direct way to configure collections of cells, i.e., there is no direct way to build useful circuits.
This is also a problem in trying to bootstrap an empty cell matrix. In a two-dimensional matrix, only cells which lie along an edge are directly accessible from outside the matrix. There is no way to access internal cells except via their neighbors, which may themselves be internal (non-edge) cells, and therefore only be accessible by their neighbors, and so on. There is thus no direct way for an external controller to configure internal cells within a cell matrix.
OBJECTS AND ADVANTAGES
Accordingly, several objects and advantages of the present invention are:
a) to provide a configuration of cells, called a wire, which allow one set of cells to configure a remote cell in a cell matrix;
b) to provide a configuration of cells, called an extendible wire, which operates as a wire but can also be extended by simply adding more cells to its end;
c) to provide sequences of configuration steps for extending an extendible wire;
d) to provide sequences of configuration steps for breaking an extendible wire and returning control to an earlier point in the wire; and
e) to provide sequences of configuration steps for programming cells near but not adjacent to the end of a wire.
Further objects and advantages are to provide circuit configurations and sequences which can be used for building wires in a previously-configured region of a cell matrix. Still further objects and advantages will become apparent from a consideration of the ensuing description and drawings.
REFERENCES:
patent: 5883525 (1999-03-01), Tavana et al.
patent: 6054871 (2000-04-01), New
patent: 6222381 (2001-04-01), Durbeck et al.
patent: 6255849 (2001-07-01), Mohan
Le Don Phu
Tokar Michael
LandOfFree
Circuits and sequences for enabling remote access to and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuits and sequences for enabling remote access to and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuits and sequences for enabling remote access to and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2582838