Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-11-17
2002-03-05
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C326S039000, C326S041000
Reexamination Certificate
active
06353920
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to Field Programmable Gate Arrays (FPGAs). More particularly, the invention relates to a method for synthesizing wide gates into carry logic in an FPGA.
BACKGROUND
Programmable integrated circuits (ICs) are a well-known type of integrated circuit that may be programmed by a user to perform specified logic functions. (The term “programmable ICs” as used herein includes but is not limited to FPGAs, mask programmable devices such as Application Specific ICs (ASICs), Programmable Logic Devices (PLDs), and devices in which only a portion of the logic is programmable.) One type of programmable IC, 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 structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBs, 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.
A CLB typically includes one or more function generators (often implemented as lookup tables, or LUTs), and one or more registers that can optionally be used to register the LUT outputs. Some CLBs also include carry logic that is used to implement arithmetic functions such as adders, subtractors, counters, and multipliers. Implementing logic using carry chains can be faster, sometimes much faster, than implementing the equivalent logic in LUTs and passing carry signals from one bit to the next through the interconnect structure. The speed of a carry chain depends on the number of bits in the carry chain and the speed of each carry bit (among other factors). The speed of the equivalent logic implemented as LUTs depends on the number of levels of logic (i.e., the number of LUTs on the slowest path) required to implement the function. Usually, using the carry chain is faster. However, using the carry chain imposes placement constraints because the ordering of portions of the user's function is set by the carry chain.
Two forms of design entry are common: schematic entry and Hardware Description Languages (HDLs) such as Verilog and VHDL. When schematic entry is used, the designer specifies the exact implementation desired for his circuit. At a higher level, when HDL code is used, the circuit is described by its logical function. Synthesis software then translates the logical function into specific logic targeted for a specified FPGA. Although circuit elements can be manually instantiated in HDL code, this method is avoided since it is labor-intensive and the code can typically only be targeted to a specific programmable IC architecture.
Well-known synthesis tools such as those distributed by Synopsys, Inc., of Mountain View, Calif., recognize arithmetic functions in the HDL code and implement these functions using carry logic. Other functions such as wide logic gates and cascade circuits can also be implemented using carry logic. However, these other types of functions used in HDL code are not so implemented by the synthesis tools, even when the method that is used results in a much slower circuit. It would be desirable, therefore, for synthesis tools to implement logic in a manner that makes better use of the carry structure in order to minimize the delay of the circuit.
SUMMARY OF THE INVENTION
According to the invention, logic functions that can be implemented by the carry chain are detected, and if the carry chain implementation is faster than a conventional implementation, the functions are implemented using the carry chain. In the general case, to be implemented in a carry chain, the functions must be of a form that each logic operator operates on the output of a previous portion of the function. That is, the function must be able to be put into the form
F=
((( . . . (
f
0
$
f
1
)$
f
2
)$
f
3
) . . . $
f
n
)
where f
0
through f
n
represent portions of the function that can be implemented in a single LUT, and $ represents a logic operator such as AND, OR, XNOR, etc. When implemented in an FPGA having four-input lookup tables, the above form covers a very large number of functions because each of f
0
through f
n
can be any function of four or fewer input values. Further, the $ operators may occur in any order.
The simplest example, very commonly used, is a wide AND function in which the number of inputs is larger than the number of inputs to a single LUT. If software detects a number of inputs greater than a selected threshold, software will implement the function with adjacent LUTs and associated carry multiplexers. The software will assign the AND gate inputs to adjacent lookup tables, will assign a logic 1 to a carry-in input of the carry-chain multiplexer controlled by the first LUT, will assign logic 0 to the independent input of each carry-chain multiplexer being used to implement the AND function, will assign the AND function to each LUT in the chain implementing the function, and will take the wide AND output from the last carry-chain multiplexer implementing the function.
A wide OR gate is implemented similarly. However, each LUT is programed to generate the NOR function, the first carry multiplexer will receive logic 0 on its carry-in input and each carry multiplexer will receive logic 1 on its independent input.
When the software implements a function having mixed operators, it determines the state of the independent carry multiplexer input and the state of the carry-in input from the type of operator that follows.
The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.
REFERENCES:
patent: 5349250 (1994-09-01), New
patent: 5442306 (1995-08-01), Woo
patent: 5481206 (1996-01-01), New et al.
patent: 5606266 (1997-02-01), Pedersen
patent: 5629886 (1997-05-01), New
patent: 5761099 (1998-06-01), Pedersen
patent: 5811985 (1998-09-01), Trimberger et al.
patent: 5859542 (1999-01-01), Pedersen
patent: 5861761 (1999-01-01), Kean
patent: 5889411 (1999-03-01), Chaudhary
patent: 5898318 (1999-04-01), Pedersen
patent: 5903165 (1999-05-01), Jones et al.
patent: 6043676 (2000-03-01), Mendel et al.
patent: 6081914 (2000-06-01), Chaudhary
patent: 6118300 (2000-09-01), Wittig et al.
patent: 6150842 (2000-11-01), Agrawal et al.
patent: 6175247 (2001-01-01), Scalera et al.
patent: 0748049 (1996-11-01), None
patent: WO-9832229 (1998-07-01), None
E. Macii et al., FPGA Synthesis Using Look-Up Table and Multiplexor Based Architectures, Proceedings, 7th Mediterranean Electrotechnical Conference, pp. 302-305, vol. 1, Apr. 1994.*
J. Pal Singh, A Multiplier Generator for Xilinx FPGAs, Ninth International Conference on VLSI Design, pp. 322-323, Jan. 1996.*
“The Programmable Logic Data Book”, published 1998, available from Xilinx, Inc., 2100 Logic Drive, San Jose, California 95124.
“Altera Data Book”, published Mar., 1995, available from Altera Corporation, 2610 Orchard Parkway, San Jose , CA 95134-2020, pp. 42-46.
Fallside Hamish T.
Mohan Sundararajarao
Wittig Ralph D.
Maunu LeRoy D.
Smith Matthew
Thompson A. M.
Xilinx , Inc.
Young Edel M.
LandOfFree
Method for implementing wide gates and tristate buffers... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for implementing wide gates and tristate buffers..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for implementing wide gates and tristate buffers... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2857254