Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-12-16
2001-08-28
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06282695
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to digital logic, and more specifically, to a network of logic gates, such as dynamic logic gates.
BACKGROUND INFORMATION
The use of dynamic logic is an efficient way of increasing circuit speed and reducing die area of integrated circuitry. The basic dynamic gate, shown in
FIG. 1
, includes a logic structure whose output node is precharged to VDD by a P-type transistor (the “precharge” transistor) and conditionally discharged to ground by an N-type transistor (the “evaluate” transistor). The precharge and evaluate transistors are typically connected to a single phase clock. During the precharge phase, the clock is low and the output node is precharged to VDD. At the completion of the precharge phase, the clock goes high and the path to VDD is turned off while the path to ground is conditionally turned on. In this evaluate phase, depending on the state of the data inputs, the output will either be at a high level or will be pulled down.
This dynamic logic is advantageous in that it generally requires fewer transistors than static logic. These circuits are often cascaded as shown in FIG.
2
. However, when many of these circuits are cascaded, delays in propagating the signal through the cascaded blocks can mount.
Referring next to
FIG. 3
, there is illustrated a sea of logic circuitry having an input and an output, which may be implemented within a portion of a data processing system. Such logic circuitry can be represented by a sea of Boolean equations. Within the sea of logic circuitry, there is a critical path, which for a particular set of designated criteria results in the highest cost for that designated criteria. Quite typically, the primary criteria with which a designer is concerned is the amount of time it takes for a signal to travel from the input to the output. The critical path within the logic circuitry is the path requiring the longest amount of time for the traveling of such a signal. Naturally, other criteria may be utilized such as circuit costs or area.
Nevertheless, it is often desired to minimize the timing required for such a sea of logic circuitry. One of the most fruitful techniques for doing so is to redesign the circuitry along the critical path in order to shorten the amount of time it takes for a signal to travel from the input to the output over such a critical path. Of course, once an identified critical path has been redesigned, another critical path within the sea of logic circuitry may be established.
What is needed in the art is an efficient and flexible system and method for restructuring logic circuitry in order to minimize a particular cost criteria, such as the amount of time it takes for a signal to travel through a particular path within the logic circuitry.
SUMMARY OF THE INVENTION
The present invention utilizes a process of building dynamic AO (AND/OR) and OA (OR/AND) books using a weighted cost function that results in a basic greedy algorithm. The greed of the algorithm is controlled such that the current critical path and any logic that is near critical will be processed first. This allows the “best” choice of building a specific block (e.g., an AND block) into an OA with the ORs that feed it or into an AO for the OR that it feeds.
The aggressive gathering and splitting of AND and OR sections of logic, combined with the selection of the pin subset to use in forming AO and OA books results in a relatively high percentage of these books being used.
Factors in the cost benefit of building a particular book are the delay cost weight, area cost weight, estimated delay, estimated area, ratio of time to area, change in slack, change in number of blocks, and average slack improvement seen by involved paths. Any block that is within a threshold (e.g., fixed amount of time, or slack) of the critical path is examined against a set of available patterns to see if there is a positive benefit in building an AO or OA.
The books available in the target technology are summarized into internal tables, allowing a very fast and efficient test of patterns performing AO and OA books. The number of ports (first stage logic function in a complex book, e.g., the AND function of an AO) and pins available in each port can be queried by the code to reject patterns that cannot be directly mapped to an available technology book.
In addition, the delay and area of each type of book is gathered. The timing tool is modified to use technology estimates that are sensitive to the number of pins on the logic function. These estimates are either derived from the default delay of the default power level at a specific capacitive load (when the book can be directly mapped) or derived from a formula that estimates what delay in area would be achieved later when the book is factored and repowered to meet technology limits (e.g., a 64-input AND is not directly implementable but can still be estimated by the formula to be much slower than a 16-input AND, while the estimation for a 4-input AND is derived from the actual timing rules for a technology AND book).
Every block in the selected section of logic (paths that are within a threshold of the current worst path) is examined to see if any logic restructuring to form AO or OA books can be performed. If any pattern is found acceptable (positive benefit as viewed by the cost function) it is considered. After all available patterns at this point are examined, only the pattern with the best benefit (at this block) is kept. It is added to a list for selecting the best overall pattern(s) to actually form. When all selected blocks have been examined, the list of restructuring points is sorted by the cost function score, with the best improvement first. As in any greedy algorithm, all previous choices are kept. However, with this aggressive approach, previous decisions are examined for additional benefit (adding/swapping pins on parts, adding/removing parts, etc.).
The processing of the list can have different levels of “aggressiveness” (high, medium, and low), controlling how patterns that overlap are handled. A high aggressiveness only processes the first entry and then rebuilds the entire list. This is the most accurate for selecting blocks on the “best” critical path (allowing it to move as a result of building this AO or OA), but does not generally give better results than the medium aggressiveness level and consumes a significant amount of CPU time.
The medium aggressiveness level processes the list until it finds an item on the list that no longer exists or for which the benefit has gone below the predicted benefit (when the list was built and sorted). This item was a place where a block was involved in more than one pattern and some higher benefit pattern absorbed a required block (pattern overlap) or which used to be on the critical path but is not now due to some other higher benefit pattern.
The low aggressiveness level merely skips pattern overlap till the end of the sorted list, requiring the least amount of CPU time in rebuilding lists.
The list is rebuilt if the aggressiveness level is set to HIGH or MEDIUM and the list processing was exited prior to reaching the end of the list (pattern overlap). When the normal end of list is encountered, the algorithm checks the current worst critical path against the stored slack for the worst critical path prior to the restructuring. If the worst slack is improved by at least some specified amount, then the process is repeated. Pre- and post-blocks (remnants of splitting a block, e.g., 4 pins were available but the port only accepts 2 pins) formed by one pattern may create additional opportunities to other patterns.
After the algorithm exits, the terms in the cost function and the threshold that control which logic to process can be modified to form more AO and OA books farther and farther off the critical path until all the logic has been processed. This naturally puts the most effort into speeding the critical paths without ignoring the savings that may occur in the non-critical logic.
The use of dynamic logic and the formation
Reddy Lakshmi Narasimha
Rosser Thomas Edward
England Anthony V. S.
International Business Machines - Corporation
Kordzik Kelly K.
Smith Matthew
Speight Jibreel
LandOfFree
System and method for restructuring of logic circuitry does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for restructuring of logic circuitry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for restructuring of logic circuitry will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2535152