Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
1995-06-02
2003-03-11
Le, Don (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S038000, C326S047000
Reexamination Certificate
active
06531890
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to programmable logic block cell structures and in particular to an optimized programmable logic allocator in a very high-density complex programmable logic device (CPLD) that provides enhanced logic utilization and enhanced logic efficiency.
DESCRIPTION OF RELATED ART
Programmable logic device (PLD) designers have consistently sought to maximize logic efficiency for a fixed amount of logic resources. One measure of logic efficiency in a programmable logic device is the number of product terms available per input/output (I/O) pin and the number of product terms at each node, usually a macrocell output line, that can be feedback to a programmable array in the PLD. Typically, in a programmable logic device, the product terms are not connected directly to an I/O pin but rather reach the I/O pin through a macrocell and perhaps other logic. Nevertheless, in each PLD, a specific number of product terms can be associated with each input/output pin. Similarly, a specific number of product terms can be associated with the output line of the macrocell or other logic.
Historically, low-density PLDs encompass monolithic block based structures in 20- to 28-pin packages with a density ranging from eight to sixteen macrocells. The architecture of a typical low-density PLD includes a programmable array logic (PAL) (PAL is a registered U.S. trademark of Advanced Micro Devices of Sunnyvale, Calif.), or a field programmable logic array (FPLA) with an integrated array of logic, I/O macrocells, and I/O pins.
Fundamentally, a simple PAL architecture incorporates a two-level logic array that has a programmable-AND plane, that consists of multiple product terms, and a fixed-OR plane. FPLA devices have both a programmable-AND plane and a programmable-OR plane. Typically, any logic function can be implemented in a low-density PAL device as long as the design requirements do not exceed the number of input signals, output signals, the logic product terms, and other logic functions, such as registers, clocks, polarity control etc., that are available in the PAL device.
The low-density PAL device is a simple structure and has the advantage of higher speed in comparison to a FPLA. In the low-density PAL device, a fixed and equal amount of logic, i.e., number of product terms, was associated with each output pin. Seven or eight product terms per each output pin was typical for first and second generation bipolar and CMOS PAL devices such as 16xx, 20xx, 16V8 and 20V8. One example of a low-density PAL device is shown in Birkner et al., U.S. Pat. No. 4,124,899 entitled “Programmable Array Logic Circuit” and issued on Nov. 7, 1978, which is incorporated herein by reference in its entirety.
These low-density PAL devices had a fully committed structure which means that all of the internal elements and fixed logic allocation structure are closely coupled. The closely coupled structure, e.g., a PAL structure with a fixed product-term distribution, has several advantages including regularity or symmetry; a simple structure; a known amount of logic with each output pin; and ease of design changes.
While a PAL structure with a fixed product-term distribution had the above advantages, a fixed allocation of product terms had some major disadvantages. Since the number of product terms in the low-density PAL devices for each output pin was fixed and not steerable or sharable between adjacent output pins, the product terms associated with a particular output pin were wasted if that output pin was not utilized. Thus, the silicon efficiency was low.
Another major disadvantage of a fixed product-term distribution per output pin was that an optimal allocation of logic resources was not possible in most cases. Different logic applications seldom need the same and equal number of product terms for all output pins. There are many occasions when seven to eight product terms per output pin are not enough to handle complex logic functions, especially for complex state machines. Applications requiring only one more product-term than the fixed number of product terms for only one output pin cannot be implemented in a low-density PAL device.
Experience has shown that for a broad range of applications, eight product terms per output pin are on average more than enough. However, as for any average, eight product terms are insufficient in some cases. For example, FIG. 2 in Munoz et. al., “Automatic Partitioning of Programmable Logic devices,”
VLSI Systems Design Magazine
, pp 74-78, October 1987, is a graph of product-term requirements for a relatively large sample of logic functions. This and other studies have shown that a large percentage of logic functions (on the order of 30 to 40%) require less than four product terms. However, a relatively significant “tail” exists where eight product terms are not enough.
One way to achieve increased product-term utilization over the fixed product-term distribution in low-density PAL devices is to provide a PLD with a fixed, variable product-term distribution per output pin. The concept behind the fixed, variable product-term distribution was to have a judicious allocation of logic resources and to allocate product terms in a variable but fixed distribution fashion such that some OR gates are driven by a few product terms, e.g., four or eight, and other OR gates are driven by a relatively large number of product terms, e.g., twelve or sixteen.
One of the first PAL devices to introduce a variable product-term distribution was sold by Advanced Micro Devices (AMD) of Sunnyvale, Calif. under Model No. PAL22V10. The number of product terms per I/O pin in the PAL22V10 architecture was 8, 10, 12, 14, 16, 16, 12, 14, 12, 10, and 8. This fixed, variable, static distribution of product terms enhanced the PAL device's logic utilization by allowing use of the PAL device in a broader range of applications. Various PLDs that have incorporated the a fixed, variable, static distribution of product terms include PLDs sold by AMD under Model Nos. PALCE22V10 and PALCE29M16/29MA16. U.S. Pat. No. 4,717,912 issued to Harvey et. al., in January 1988, which is incorporated herein by reference in its entirety, illustrates a PLD with a fixed, variable product-term distribution.
While the fixed, variable distribution of product terms also results in a potentially better allocation of resources thereby enhancing product-term utilization over a comparable PLD with a fixed allocation of product terms, the fixed, variable distribution of product terms also results in a potentially inefficient silicon structure. Specifically, this product-term distribution increases the average number of product terms per output pin over the low-density PAL structures. The increase in the average number of product terms results in a bigger die size, potentially slower speed, and a greater likelihood of wasted resources.
The fixed, variable distribution of product terms restricts only a limited number of output macrocells and output pins to the largest amount of logic, and system designers have to pre-assign logic functions that require larger logic resources to only those particular output pins. Also, since the product-term distribution is fixed, output pins with a smaller number of product terms do not have access to unused product-term resources from other macrocells. This results in potential waste of internal resources. Extension of the fixed, variable product-term distribution to higher density devices with more output pins and macrocells would result in significantly larger, more expensive and slower devices.
The fixed, variable product-term distribution increases the complexity of the logic fitting software task because each user logic function must be examined and then, depending upon the demand for product-term resources, assigned to a specific output macrocell which has the minimum product terms needed to fulfill the required product-term demand. This software complexity becomes significantly worse for multiple interconnected programmable logic blocks that each have a fixed,
Agrawal Om P.
Schmitz Nicholas A.
Sharpe-Geisler Bradley A.
Lattice Semiconductor Corporation
Le Don
LandOfFree
Programmable optimized-distribution logic allocator for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programmable optimized-distribution logic allocator for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable optimized-distribution logic allocator for a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3008429