Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2002-03-12
2003-10-07
Tran, Anh (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S038000, C326S039000
Reexamination Certificate
active
06630841
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to Field Programmable Gate Arrays (FPGAs). More particularly, the invention relates to structures and methods for implementing user circuits by combining multiple logic blocks in an FPGA.
BACKGROUND OF THE INVENTION
Programmable logic devices (PLDs) are a well-known type of digital integrated circuit that may be programmed by a user to perform specified logic functions. One type of PLD, the field programmable gate array (FPGA), typically includes an array of configurable logic elements (CLEs) surrounded by a ring of programmable input/output blocks (IOBs). The CLEs and IOBs are interconnected by a programmable interconnect structure. (The programmable interconnect structure between CLEs and IOBs is also referred to as general interconnect). The CLEs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLES, IOBs, and interconnect structure are configured. The configuration data may be read from memory (e.g., an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
One significant task when implementing a user circuit in an FPGA is the assignment of user logic into the various CLEs and IOBs. This process includes “mapping”, where the user circuit is divided into pieces that will fit into a single CLE, IOB, or a portion thereof, and “placement”, where each mapped piece of logic is assigned to a particular CLE or IOB (or portion thereof) in a particular location on the FPGA. The final step in implementing the circuit is called “routing”, where the mapped and placed logic is connected together using the programmable interconnect structure. The mapping, placement, and routing processes are typically performed by computer software, which reads in a description of the user circuit (for example, in the form of a netlist) and provides the bitstream that is used to program the device, as described above.
In practice, each CLE is typically formed from several smaller logic blocks, such as 4-input lookup tables (LUTs). Because each block has a fixed size, and the size of the block is usually fairly small to facilitate the efficient implementation of small logic functions, the implementation of larger user circuits requires the use of several logic blocks. Sometimes these logic blocks can be accommodated within a single CLE, in which case the general interconnect need not be used to connect the blocks. In other cases, the required number of logic blocks is too large for a single CLE. The necessary logic blocks must then be connected using the general interconnect, which is typically slower than connections within a single CLE. Thus, user circuits up to a certain size (i.e., the size that will fit in a single CLE) are typically faster than user circuits of a larger size. Further, user circuits that fit into a single logic block (e.g., a single 4-input LUT) result in the fastest implementations.
Therefore, it is desirable to provide structures and methods for combining two or more logic blocks in such a way as to permit user circuits too large for a single logic block to function at more nearly the same operating speed as user circuits within a single logic block.
SUMMARY OF THE INVENTION
The invention provides a configurable logic element (CLE) for a field programmable gate array (FPGA) that includes “expanders” (i.e., configurable connector circuits having two or more functions) that allow for fast signal communication between logic blocks. Expanders allow the configurable interconnection of a plurality of logic blocks, for example, a plurality of Versatile Implementation Modules (VIMs), to form a single logical entity including two or more VIMs (i.e., a “VIM complex”) that can implement large user circuits such as PALs, lookup tables, multiplexers, tristate buffers, and memories.
A user circuit requiring two or more logic blocks that is implemented using expanders is significantly faster than other implementations enabled by prior art structures.
In one embodiment, a CLE according to the invention includes four “slices”. Each slice includes two logic blocks—for example, the hybrid LUT/PAL logic elements first described by Wittig et al. in U.S. Pat. No. 6,150,838, entitled “FPGA Configurable Logic Block With Multi-Purpose Logic/Memory Circuit”, which is incorporated herein by reference. The combination of Wittig's hybrid LUT/PAL structure with the novel expanders described herein allows for the construction of both large PALs (spanning multiple VIMs) and large user circuits requiring the combination of many look-up tables (LUTs) with minimal performance degradation. In this embodiment, VIMs can be combined within a single slice, between two or more slices, or even across CLE boundaries, and either vertically, horizontally, or both. Further, while adjacent slices or logic blocks are most commonly combined, non-adjacent elements can also be combined by configuring the expanders to bypass intervening elements.
In another embodiment of the invention, more limited logic blocks are used, such as those comprising only LUT functions or only product term generator functions.
One embodiment includes a configurable logic block having at least two configurable modes. In a first mode, the logic block provides two N-input LUTs having N shared inputs and two separate outputs. The outputs are then combined using an expander to generate an (N+1)-input function. In a second mode, the logic block provides two N-input LUTs having M unshared inputs, where M is less than N. In one embodiment, the logic block includes a third mode, in which it provides a plurality of product term output signals based on the values of the N input signals.
REFERENCES:
patent: 5362999 (1994-11-01), Chiang
patent: 5432719 (1995-07-01), Freeman et al.
patent: 5473266 (1995-12-01), Ahanin et al.
patent: 5473267 (1995-12-01), Stansfield
patent: 5801547 (1998-09-01), Kean
patent: 5815726 (1998-09-01), Cliff
patent: 5828229 (1998-10-01), Cliff et al.
patent: 5936424 (1999-08-01), Young et al.
patent: 6020759 (2000-02-01), Heile
patent: 6144573 (2000-11-01), Heile
patent: 6150838 (2000-11-01), Wittig et al.
patent: 6480025 (2002-11-01), Altaf
patent: 913 944 (1999-05-01), None
Xilinx, Inc.; “Virtex-II Platform FPGA Handbook”; published Dec. 2000; available from Xilinx, Inc., 2100 Logic Drive, San Jose, California 95124; pp. 46-54.
Xilinx, Inc.; “The Programmable Logic Data Book” 9/96; available from Xilinx, Inc. 2100 Logic Drive, San Jose, California 95124; pp. 4-11 to 4-20 and 4-294 to 4-296.
Xilinx, Inc.; “The Programmable Logic Data Book” 2000; available from Xilinx, Inc. 2100 Logic Drive, San Jose, California 95124; pp. 3-9 to 3-11 and 3-79 to 3-82.
Wilton, Steve J. E.; “SMAP: Heterogenous Technology Mapping for Area Reduction in FPGAs with Embedded Memory Arrays”, published 2-98; ACM/SIGDA International Symposium on Field-Programmable Gate Arrays.
Mohan Sundararajarao
New Bernard J.
Wittig Ralph D.
Cartier Lois D.
Tran Anh
Xilinx , Inc.
LandOfFree
Configurable logic element with expander structures does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Configurable logic element with expander structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Configurable logic element with expander structures will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3171947