Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-05-17
2002-10-22
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06470486
ABSTRACT:
BACKGROUND OF THE PRESENT INVENTION
1. Technical Field
The present invention relates to electronic design automation and more particularly to delay-optimizing technology-mapping in the high-level synthesis of digital systems.
2. Description of the Prior Art
High-level synthesis (HLS) automates certain sub tasks of a digital system design in an electronic design automation (EDA) system. A system architect begins by designing and validating an overall algorithm to be implemented, e.g., using “C”, “C”++, a specialized language, or a capture system. The resulting architectural specification is partitioned into boards, chips, and blocks. Each block is a single process having its own control flow. There are usually tens to hundreds of such blocks in a modem large-scale chip design. Typical blocks represent whole filters, queues, pipeline stages, etc. Once a chip has been partitioned into its constituent blocks, any needed communication protocols have to be constructed. Such protocols depend on cycle-by-cycle communication between blocks.
So-called “scheduling” and “allocation” are applied one block at a time. Scheduling assigns operations such as additions and multiplications to states of a finite-state machine (FSM). Such FSM describes a control flow in an algorithm performed by a block being synthesized. Some operations are locked into particular states, and represent communication with other blocks. These input/output operations cannot be moved, or rescheduled, from one state to another, because to do so would probably upset the block-to-block communication protocol.
However, some other operations can be moved from one state to another. Moving operations from states that have many operations to states that have few allows hardware resources to be more evenly shared among operations. Timing problems can sometimes be resolved by moving certain operations from states in which operation delays cause timing problems into states in which such problems don't exist.
Allocation maps the operations of a scheduled FM to particular hardware resources. For example, three addition operations can be scheduled to only require a single adder. An appropriate adder is constructed, and the operations are assigned to the adder in a schedule. But complications can arise when more than one hardware resource of a given bit-width and function is needed. And so which resource to use for each operation must be decided. Considerations include multiplexing cost, the creation of false timing paths, register assignment, and even using large resources for small operations. Hardware resources can be used for multiple functions. Calculating a minimum set of resources for an entire process is difficult but rewarding. Sometimes alternative implementations will be possible. It is often possible to choose implementations that meet the overall timing resources (abstract functions) to gate level implementations.
Allocation includes calculating a register set and assigning data to registers for use in later states. For example, temporary variables are used to store intermediate results in a larger calculation. But the contents of such temporary variables could share a common register in different states. The contents are only needed in one state each. So it is possible to save on hardware by assigning the data that needs to be stored to such storage elements. But register and storage allocations can be complicated if data values can form mutually exclusive sets or can share storage. Data values often drive functional resources, and in turn are often produced by functional resources. A good assignment of data to storage will complex by the fact that there are many ways to map an individual Boolean gate, and each way has its own unique advantages.
Technology-independent, or Boolean, optimization follow scheduling and allocation. The circuit design comprises generic AND and OR gates connected in a netlist. Technology-independent optimization minimizes the number of literals in the netlist. An abstraction of Boolean gates lends itself to a highly mathematical treatment based on Boolean arithmatic. For example, the Boolean identity AB+AC=A(B+C) can be used to reduce the corresponding gate network. Technology mapping follows Boolean optimization, the abstract Boolean gates of the circuit are mapped to standard cells from a technology library. Standard library cells include simple AND, OR, or NOT functions, and much more complex functions. For example, full adders, and-or-invert gates, and multiplexers. Technology-library gates are available in a variety of drive strengths, delays, input loadings, etc. Technology mapping is made more complex by the fact that there are many ways to map an individual Boolean gate, and each way has its own unique advantages.
Technology mapping can sometimes be avoided by constructing custom gate layouts for the gates of a circuit, instead of selecting cells from a library of preconstructed and precharacterized cells. But this method is not commonly associated with automatic synthesis.
The layout tasks of cell placement and net routing follow technology mapping, the physical position of each cell on the chip is established (placement), and the nets necessary to interconnect the cells are laid out (routing). In application service provider
104
, the design intellectual property is downloaded to the user for placing and routing.
An abstract Boolean netlist is technology-mapped to standard-cell library elements, and involves matching and selection. A gate or a small collection of gates in a netlist is tested for logical equivalence to an element of the technology library to find a match. Matching can be done on an individual gate basis, or on a collection of gates. For example, there might be an AND-OR-INVERT gate in a technology library that would be capable of implementing an entire example netlist. Matching can also be partial, as in the case of a three-input gate in a technology library that could be used to implement a two-input gate in a netlist by tying one of its inputs to a constant.
Given that each of the gates of a netlist can be implemented by one or more gates from a technology library, one of the matches must be selected. Such a selection must “cover” the netlist. Each gate of the netlist must have a selected matching element. The circuit derived by replacing each abstract gate with its selected matching technology library gate must be logically equivalent to the original circuit. The derived circuit should minimize overall area, delay, and/or other properties, while obeying any design rules imposed by the library or the designer. The technology mapping phase is completed when all the abstract gates of a netlist have been replaced by equivalent technology library elements.
A final phase of logic synthesis is an optional iterative improvement. In this step, the entire netlist is optimized, a few gates at a time, by making local changes. One way to do this is represented by,
repeat {
choose a gate G
try alternative mappings of G, keeping any improvement
} until no further improvements can be found.
Each iterative improvement step can be slow, because a large number of alternative selections could be constructed, even for a small circuit. For example, in a circuit that has ten gates, each of which have ten possible technology matches. If all combinations are considered, there would be 1,010 possible implementations of the circuit. Depending on the circuit's topology and the properties of the library elements, the effects of alternative mappings can interact. Each gate might have to be visited many times before no further improvement could be obtained.
Attempts at iterative improvements can also be unreliable, as a good circuit may never be found. A local minima can occur, in which counter-intuitive “uphill moves” must be made that degrade the circuit in order to enable other changes that will have a desirable overall effect. If the uphill moves needed are outside the iterative improvement algorithm's horizon, the process gets stuck and
Get2Chip
Glenn Michael A.
Liu Andrea
Siek Vuthe
LandOfFree
Method for delay-optimizing technology mapping of digital logic 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 delay-optimizing technology mapping of digital logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for delay-optimizing technology mapping of digital logic will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2979099