Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2001-05-15
2002-10-15
Lee, Michael G. (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S038000, C326S039000, C326S040000, C326S047000
Reexamination Certificate
active
06466052
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to Field Programmable Gate Arrays (FPGAs). More particularly, the invention relates to a structure and method for implementing wide multiplexers in an FPGA using a horizontal chain structure.
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 blocks (CLBs) surrounded by a ring of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure. The CLBs, IOBs, and interconnect are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBs, IOBs, and interconnect 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 such FPGA, the Xilinx Virtex® FPGA, is described in detail in pages 3-75 through 3-96 of the Xilinx 2000 Data Book entitled “The Programmable Logic Data Book 2000” (hereinafter referred to as “the Xilinx Data Book”), published April, 2000, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, which pages are incorporated herein by reference. (Xilinx, Inc., owner of the copyright, has no objection to copying these and other pages referenced herein but otherwise reserves all copyright rights whatsoever.)
The Virtex CLB is composed of two similar elements called “slices”, as described by Young et al. in U.S. Pat. No. 5,920,202 and shown in
FIGS. 4A and 4B
therein. (U.S. Pat. No. 5,920,202 is hereby incorporated herein by reference.) These figures are reproduced in
FIGS. 1A and 1B
of the present specification. Young et al. describe the figures in detail, therefore, the description is not repeated here.
FIG. 2
is a simplified drawing of the Virtex CLB of
FIGS. 1A and 1B
, showing how the F
5
and F
6
multiplexers of the two slices can be interconnected to implement wide functions. The two slices are designated SA and SB. Included in
FIG. 2
are the four 4-input function generators F, G, H, J. The outputs of function generators F and G (F′ and G′, respectively) are combined with a fifth independent input BFF in multiplexer F
5
B to produce output F
5
B′, which can be any function of five inputs, or some functions of up to nine inputs. (In the present specification, the same reference characters are used to refer to terminals, signal lines, and their corresponding signals.) The outputs of function generators H and J (H′ and J′, respectively) are combined with a fifth independent input BHH in multiplexer F
5
A to produce output F
5
A′, which can be any function of five inputs, or some functions of up to nine inputs.
The outputs F
5
A′ and F
5
B′ of multiplexers F
5
A and F
5
B are combined with a sixth independent input BGG in multiplexer F
6
B, and with a different sixth independent input BJJ in multiplexer F
6
A. The two multiplexers F
6
A and F
6
B therefore produce two outputs F
6
A′ and F
6
B′, respectively. One of outputs F
6
A′ and F
6
B′ can be any function of six inputs; the other output can be any function of six inputs provided that five inputs are shared between the two 6-input functions. Some functions of up to nineteen inputs can also be generated in a single CLE.
As described above, the four 4-input function generators F, G, H, J shown in
FIGS. 1A
,
1
B, and
2
can each be used to implement any function of up to four inputs. Therefore, each function generator can implement one 2-to-1 multiplexer. The F and G function generators and the F
5
B multiplexer can together implement a 4-to-1 multiplexer. Similarly, the outputs of the H and J function generators can be combined in the F
5
A multiplexer to implement another 4-to-1 multiplexer. The four function generators, the two F
5
multiplexers, and one of the F
6
multiplexers can together implement an 8-to-1 multiplexer.
However, this multiplexer implementation is limiting in that the entire multiplexer is implemented as a compact block instead of as a distributed structure. In some applications, it is desirable to implement a multiplexer in such a fashion that the floorplan matches the layout of other circuits in the application. Thus, for applications such as datapaths and ALUs, for example, it is desirable to implement a wide multiplexer as a structure distributed along a horizontal chain of slices. Further, the fact that carry chains are often implemented in a vertical fashion means that a horizontal multiplexer would be efficient in emulating the internal busses that are often used in datapaths, ALUs, and other ordered circuit structures. Therefore, it is desirable to provide structures and methods for implementing multiplexers along a horizontal chain of logic elements in an FPGA.
SUMMARY OF THE INVENTION
The invention provides methods and structures for implementing wide multiplexers in programmable logic devices (PLDs) such as Field Programmable Gate Arrays (FPGAs). According to a first embodiment, a configurable logic structure includes a function generator, a carry multiplexer, and an OR gate. The function generator is configured to implement a multiplexing function (under control of a first select signal) and an AND function (ANDing the output of the multiplexer with a second select signal). By ANDing the output of the multiplexer with the second select signal, a second level of multiplexing can be added by selectively setting the values of the second select signal in different ones of the logic structures. The carry multiplexer is configured to perform an AND function between an output of the function generator and a third select signal. Again, various values of the third select signal can be used on different ones of the logic structures. Thus, with three select signals available, an 8-to-1 multiplexer can be implemented by combining the outputs of four different logic structures that use different values of the select signals. This combination of outputs is performed by forming an OR chain, with the OR input of each stage being provided by the associated carry multiplexer. The OR input of the first stage is a logic low value; the OR output of the final stage is the output of the wide multiplexer function.
As will be clear to those of ordinary skill in the art of PLD design, the 8-to-1 multiplexer described herein is purely exemplary, and wide multiplexers of virtually any size can be formed using the structures and methods of the invention. The described multiplexer is merely selected as being particularly suited to implementation in the Virtex-II FPGA architecture from Xilinx, Inc., where a distributed 8-to-1 multiplexer can be implemented in four function generators.
The distributed multiplexing function of the invention has advantages for certain applications having structured layouts, such as ALUs and other datapath functions. For example, the distributed structure of the invention allows the emulation of internal busses used within the application. Also, having a multiplexer structure distributed along with the related logic can reduce path delays. Further, the number of CLBs required to implement many user designs is reduced, because (in one embodiment) only a portion of the logic within the configurable logic structure is used. The unused resources are still available to implement other user functions.
Another advantage of the described embodiment is that each circuit element used to implement the multiplexing function has another use for which it was primarily designed. The carry multiplexer is primarily used to implement carry chains. The OR gate is primarily used to perform a Sum-Of-Products function. Therefore, in the preferred embodiment, no extra circuitry need be added to the CLB to enable the
Cartier Lois D.
Lee Michael G.
Paik Steven S.
Xilinx , Inc.
LandOfFree
Implementing wide multiplexers in an FPGA using a horizontal... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Implementing wide multiplexers in an FPGA using a horizontal..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementing wide multiplexers in an FPGA using a horizontal... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2981096