Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
1999-12-30
2003-10-14
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S046000
Reexamination Certificate
active
06633181
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of Programmable Logic Arrays (PLAs), Field Programmable Gate Arrays (FPGAs) and Programmable Logic Devices (PLDs). More particularly, the present invention relates to a programmable logic array architecture in which individual logic elements are based on a bit sliceable arithmetic logic unit (ALU), each bit slice being individually programmable to perform low-level Boolean and gate-level operations, as well as higher-level logic and arithmetic functions.
2. Description of the Related Art
FIG. 1
illustrates a programmable logic element
100
used in a conventional programmable logic device. Typically, a logic device includes a two-dimensional array of elements such as element
100
disclosed in U.S. Pat. No. 5,274,581.
As shown, element
100
implements a four-input look-up table
102
which is programmable to produce a desired binary output signal value for each of the sixteen possible combinations of its four binary input signals A, B, C and D. When element
100
is to be used as one stage of a two-input adder or subtracter, a four-input look-up table is much more than is needed to provide just a sum out or carry value. Accordingly, the four-input look-up table is provided as shown in
FIG. 1
as two three-input look-up tables
104
,
106
so that the one element
100
can provide both a sum out on its normal output, and important precedents to the carry out value on outputs X and Y.
Element
100
also provides further inputs and outputs that enable its use as one place in a binary operation such as addition, subtraction or counting. Specifically, element
100
includes a carry in input, typically from the carry out output of another adjacent logic element. Element
100
further includes a cascade connect input, also typically from another adjacent logic element, which can allow the cascade connect output from the adjacent logic element to be combined with the output of the look-up table in element
100
if desired. In addition to its regular data output from driver
108
, element
100
includes a cascade connect output, which typically is applied to the cascade connect input of an adjacent logic element. A carry out signal is similarly applied to the carry in input of another, typically adjacent logic element.
FIG. 2
illustrates how the four-input look-up table
102
of element
100
is realized as two three-input look-up tables
104
,
106
using standard logic symbols.
The prior art programmable element, and programmable arrays based thereon, are subject to many drawbacks. For example, when attempting to program structures for performing higher-level functions (such as arithmetic and complex logic operations), many logic elements are required to be combined together, which leads to larger structures and reduced performance, including slow carry propagation. However, this is necessary to maintain the ability to perform lower-.level functions. Further, to allow logic elements to be combined together to perform expanded logic operations, combinational logic must be included in each element, even when such operations are not programmed, thus leading to wasteful circuitry. Moreover, the prior art structures can only be statically programmed to perform different levels of functionality.
What is needed in the art, therefore, is a multi-scale programmable logic device that can be dynamically configured to select different scales of functionality. The present invention fulfills this need, among others.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the invention to overcome the abovementioned problems in the prior art.
It is another object of the invention to provide a programmable logic array architecture that allows digital logic to be programmed using both small-scale blocks as well as medium scale blocks.
It is another object of the invention to provide a programmable logic array architecture that can provide multi-scale functionality and maintain high performance.
It is another object of the invention to provide a programmable logic array architecture that can achieve fast carry propagation.
It is another object of the invention to provide a programmable logic array architecture that can provide multi-scale functionality and maintain a single programmable logic element.
It is another object of the invention to provide a programmable logic array architecture that simplifies the programming of complex arithmetic and random logic functions.
It is another object of the invention to provide a programmable logic array architecture that is capable of being dynamically reconfigured to perform different levels of combinational logic functions.
These and other objects of the present invention are fulfilled by a novel architecture for a multi-scale programmable logic array (MSA) to be used in the design of complex digital systems. In the MSA, the static program for the array, stored in configuration memory, defines the functional behavior of each bit-slice circuit and the functional behavior of the ALU controller for a group of bit-slice circuits. These circuits are called the cluster blocks of the architecture. The configuration memory program also controls the flow of logic variables between the cluster blocks.
According to an aspect of the invention, the MSA concept allows digital logic to be programmed using both small-scale blocks (also called gate level blocks) as well as medium scale blocks (also called Register Transfer Level or RTL blocks). Prior art approaches used separate structures to achieve this capability or accepted the reduced performance and increased cost of having a single programmable logic type. The MSA concept is based on a bit sliceable Arithmetic Logic Unit (ALU). Each bit-slice may be programmed to perform a basic Boolean logic operation or to contribute to higher-level functions that are further programmed by an ALU controller circuit. In one embodiment of the invention, the ALU controller level also allows the primitive logic operations computed at the bit-slice level to be combined to perform complex random logic operations. The data shifting capability of this new programmable logic architecture according to another aspect of the invention reduces the complexity of the programmable routing needed to implement shift operations including multiplier arrays. The new array also allows logic variables under program control to dynamically modify the micro-program of each ALU. This technique is called configuration overlay and simplifies the programming of complex arithmetic and random logic functions.
REFERENCES:
patent: 5258668 (1993-11-01), Cliff et al.
patent: 5260610 (1993-11-01), Pedersen et al.
patent: 5260611 (1993-11-01), Cliff et al.
patent: 5274581 (1993-12-01), Cliff et al.
patent: 5343406 (1994-08-01), Freeman et al.
patent: 5357152 (1994-10-01), Jennings, III
patent: 5414377 (1995-05-01), Freidin
patent: 5426378 (1995-06-01), Ong
patent: 5436574 (1995-07-01), Veenstra
patent: 5726584 (1998-03-01), Freidin
patent: 5742180 (1998-04-01), DeHon et al.
patent: 5920202 (1999-07-01), Young et al.
patent: 5926036 (1999-07-01), Cliff et al.
patent: 5963050 (1999-10-01), Young et al.
patent: 5977793 (1999-11-01), Reddy et al.
patent: 5982195 (1999-11-01), Cliff et al.
patent: 5986465 (1999-11-01), Mendel
patent: 0 507 507 (1992-10-01), None
patent: 0 668 659 (1995-02-01), None
Bechade, R.A. et al., “Programmable Arithmetic/Logic Circuit,” IBM Technical Disclosure Bulletin, U.S. IBM Corp., New York, vol. 3, No. 11, Apr. 1981, pp. 4870-4873, XP-000713711.
Carr & Ferrell LLP
Cho James H
Stretch, Inc.
Tokar Michael
LandOfFree
Multi-scale programmable array does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-scale programmable array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-scale programmable array will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3168097