Integrated circuit design synthesis using slack diagrams

An updated integrated circuit (IC) design is generated by applying a histogram-based algorithm to an invalid, current IC design. The histogram-based algorithm includes worst negative slack (WNS) optimization followed by total negative slack (TNS) optimization. WNS optimization uses the slack histogram for the current IC design to generate an invalid, but improved, intermediate IC design. TNS optimization uses the slack histogram of the intermediate IC design to generate the updated IC design.

BACKGROUND OF THE INVENTION

The present invention relates generally to integrated circuits, and more particularly to techniques for designing integrated circuits.

In an integrated circuit (IC), signals are transferred between different pairs of sequential circuit elements, e.g., from a transmitting (a.k.a. launch) flip-flop to a receiving (a.k.a. capture) flip-flop. In order to operate properly, each signal transfer between each pair of sequential circuit elements must be completed within one clock cycle.

Slack refers to the difference between the required time and the arrival time, e.g., the difference between a clock cycle and the time taken during a signal transfer from a launch element to a capture element. In a valid IC design, each signal transfer path has slack that is either positive (indicating that the signal transfer duration is shorter than one clock cycle) or zero (indicating that the signal transfer duration is equal to one clock cycle). If one or more signal paths in an IC design have negative slack (indicating that the signal transfer duration is greater than one clock cycle), then those signal paths are referred to as failing paths, and the IC design is invalid.

Increasing market demands for high performance and low power in SoC (System on Chip) integrated circuits places a lot of focus on design-optimization techniques from synthesis through design closure. Synthesis techniques play a vital role in the choice of data path operators and gate-level optimization. With shrinking design cycles, this necessitates that synthesis tools give best QoR (Quality of Results) in terms of performance and power with minimum iterations.

In some design scenarios, top failing paths cannot be optimized further because of constraints not being mature (e.g., due to the design being in an initial phase) or design architectural issues. In such cases, the synthesis engine may leave many sub-optimal paths (paths not fully optimized) beneath the top failing paths. EDA (Electronic Design Automation) algorithms are presently coded to put high effort on the top failing paths, while the paths below them get a very low weight/effort. This can result in (i) multiple iterations between the physical implementation team and the STA (Static Timing Analysis) team and (ii) a lot of sub-optimal paths in the design. The problem is seen across SoCs with no effective solution available from the EDA industry so far.

FIG. 1shows a high-level block/flow diagram of a conventional technique for designing an integrated circuit. In step106, the RTL (Register Transfer Level)102and Lib (Library)104information are stitched together where the top-level design and its references are resolved. Also, during this step, data structures, based on top-level design references, are built, and the semantics of the RTL files are verified as well. The RTL and Lib databases contain the timing information of the technology cells that are used during synthesis.

In step108, timing and design constraints are specified for the IC. In step110, a synthesis engine is used to generate a current design for the IC. In step112, it is determined whether the current IC design meets the timing constraints specified in step108, including whether each signal transfer path in the current IC design has either positive or zero slack. If so, then the current IC design is valid, and the process continues to step116, where a gate-level netlist for Placement and Routing (PnR) is generated for the current IC design.

If, however, step112determines that one or more of the signal transfer paths in the current IC design have negative slack, then processing returns to step108to modify the constraints for another iteration of the technology mapping of step110. In some situations, the number of iterations of steps108,110, and112can become large without ever being able to generate a valid IC design. Accordingly, it would be advantageous to be able to move to the PnR step without an excessive number of iterations to address timing issues.

DETAILED DESCRIPTION OF THE INVENTION

Detailed illustrative embodiments of the present invention are disclosed herein. However, specific structural and functional details disclosed herein are merely representative for purposes of describing example embodiments of the present invention. The present invention may be embodied in many alternate forms and should not be construed as limited to only the embodiments set forth herein. Further, the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of example embodiments of the invention.

In one embodiment, the present invention provides a method for designing an integrated circuit (IC). The method comprises (a) generating an invalid, current design for the IC; (b) generating a current slack histogram for the current design; and (c) generating an updated design for the IC by applying a histogram-based algorithm to the current design based on the current slack histogram.

The top failing path in an invalid IC design is the signal transfer path having the worst negative slack (WNS), i.e., the negative slack having the greatest magnitude. During the design phase of an integrated circuit, a particular design can be characterized using a slack histogram, which represents the slack values for all of the different signal transfer paths in the design.

The slack histograms can be used during the IC design phase to assess whether the IC design process is proceeding in the right direction, i.e., towards an IC design having no negative slack at all.

Conventional electronic design automation (EDA) tools focus on reducing the magnitude of the negative slack for the top failing paths in an existing IC design (i.e., those paths having WNS values). At each iteration, an EDA tool attempts to eliminate the existing top failing paths from the current IC design. Presently, optimization done by EDA tools is hindered because of top failing paths, thus impacting the overall QoR of the design. As explained previously, top failing paths cannot be optimized further because of constraints not being mature (e.g., due to the design being in an initial phase) or design architectural issues that lead to sub-optimal paths beneath the top failing paths.

The present invention is related to a histogram-based algorithm that helps in reducing WNS and/or TNS of an invalid IC design. Depending on whether WNS or TNS is used as the objective, the algorithm uses the timing slack histogram to effectively search for the sub-optimality in the IC design and optimizes the timing slack space.

Unlike conventional EDA algorithms, optimization based on a histogram-based algorithm is not hindered by any bottlenecks in the IC design (e.g., constraints or design issues) for achieving the best possible timing QoR. A typical SoC can have multiple histogram peaks and conventional EDA algorithms never use this information for optimization.

A histogram-based algorithm of the present invention not only divides the slack histogram into multiple Gaussian distributions, but also utilizes the slack histogram to detect sub-optimal zones in an IC design to achieve the improved timing QoR. Histogram-based algorithms of the present invention have been used on ARM core and SoC designs and have achieved better timing QoR as compared to traditional algorithms followed by EDA tools.

FIG. 3shows a high-level block/flow diagram of a technique for designing an integrated circuit according to one embodiment of the present invention. Steps306-316ofFIG. 3are similar to corresponding steps106-116ofFIG. 1. The main difference is that, when a current IC design fails step312, instead of returning directly to step308(as was done inFIG. 1), processing proceeds to the histogram-based algorithm314of the present invention before returning to step308in order to update the design or timing constraints to deal with the remaining top failing paths.

The preferred histogram-based algorithm is a two-phase approach for effective WNS and TNS optimization during synthesis. The first phase, called WNS optimization, focuses on WNS reduction by optimizing the top failing paths. This WNS reduction is used to analyze the current IC design to check the maximum possible frequency (i.e., core frequency) and constraints development. The second phase, called TNS optimization, focuses on TNS reduction by optimizing all of the remaining failing paths in the updated IC design generated during WNS optimization.

The following discussion is presented using exemplary slack histogram200ofFIG. 2.

The WNS-optimization phase considers a given slack histogram200as multiple Gaussian distributions. The algorithm considers the portion of slack histogram200corresponding to the top failing paths (i.e., the123WNS paths having a WNS value of about −435 ps) to be the peak202of the first Gaussian distribution in slack histogram200.

The algorithm then traverses slack histogram200towards less-negative paths (i.e., to the right inFIG. 2) to identify the next significant peak216at −270 ps as the center of the second Gaussian distribution in slack histogram200. Significant peaks may be identified by comparing the numbers of paths in three consecutive histogram bins to identify situations in which the middle bin has a number of paths significantly larger (e.g., greater than some threshold difference) than its two adjacent bins. Note that the peak at −360 ps is considered to be insignificant and is therefore ignored by the algorithm, because the number of paths (i.e., 54) of that bin is not sufficiently larger than the 47 and 50 paths of the two adjacent bins.

The algorithm considers the second peak216to be the mean of a normal Gaussian distribution. The algorithm considers the endpoint204just after the first peak202to be the −3σ point of this second Gaussian distribution in slack histogram200.

The algorithm then evenly divides the bins of the histogram between that −3σ point204and the mean point216into the following three different cost groups (CGs) having the following graded weights:First CG206between the −3σ point204and the −2σ point208(i.e., paths having slack values greater than or equal to about −420 ps and lower than about −370 ps) having the highest graded weight of, for example, 10;Second CG210between the −2σ point208and the −1σ point212(i.e., paths having slack values greater than or equal to about −370 ps and lower than about −320 ps) having the lesser graded weight of, for example, 8; andThird CG214between the −1σ point212and the mean point216(i.e., paths having slack values greater than or equal to about −320 ps and lower than or equal to about −270 ps) having the still lesser graded weight of, for example, 6.
The bin at −435 ps corresponding to the first peak202forms the top cost group CG_TOP having the lowest weight of, for example, 1.

The algorithm then executes incremental timing optimization with the weights assigned to different cost groups. The incremental timing optimization shifts the focus towards those paths having greater weights assigned. Incremental timing optimization can be described as running another round of timing optimization. The optimization refers to logical restructuring of failing paths by resizing, buffering, or logical transformations in order to reduce the magnitude of the negative slack value of a violating path.

FIG. 4shows a comparison of slack histogram200ofFIG. 2and the slack histogram400that is generated by applying WNS optimization in accordance with the present invention to slack histogram200ofFIG. 2. As shown inFIG. 4, the failing paths in slack histogram400are partially shifted to the right side (i.e., lower-magnitude negative slack) as compare to those in slack histogram200.

As described previously with respect ofFIG. 2, the bin at −435 ps in slack histogram200corresponds to the top cost group CG_TOP, and the three bins at −420 ps, −405 ps, and −390 ps correspond to the first cost group206in slack histogram200. As shown inFIG. 4, the number of failing paths in those four bins of slack histogram400is significantly smaller than the number of failing paths in those same four bins of slack histogram200.

Following the first phase of the WNS optimization, the second phase of TNS optimization is performed. The objective of TNS optimization is to continue to push the slack histogram towards the right side and to reduce the histogram peaks.

In TNS optimization, the algorithm masks away the top failing paths (i.e., the WNS paths) by pushing them under the top cost group CG_TOP having the lowest weight. For the rest of the paths in the slack histogram, the algorithm finds high-density/concentration zones of negative slack in the design space. The algorithm divides the design space into multiple high-density buckets to be used by an optimizer.

The algorithm calculates WNS-based Z-scores and TNS-based Z-scores. A Z-score (aka standard score or Z) is a measure of the divergence of a data point (X) from the most probable data point value (i.e., the mean value) and is expressed in terms of the number of standard deviations (σ) from the mean value (μ). Thus, Z=(X−μ)/σ. The Z-score tells if a data point is high or low and by how much. Z-scores greater than zero are above average, while Z-scores less than zero are below average.

A WNS-based Z-score is directly calculated using the slack histogram, where X is a particular slack value along the x axis, and the standard deviation σ and mean value μ are calculated based on the area under the slack histogram. A TNS-based Z-score is calculated using a “TNS-contribution” curve in which the y axis represents the contribution of each slack value to the TNS, where that TNS contribution is the product of a slack value and the number of data paths having that slack value (i.e., the y axis value in the slack histogram). For the TNS-based Z-score, X is again a particular slack value along the x axis, and the standard deviation σ and mean value μ are calculated based on the area under the TNS-contribution curve.

The more negative the Z-score, the higher the gravity or heaviness of the data point and the more contribution to the TNS value by the data point. The more positive the Z-score, the lighter the data point. Z-scores are used to standardize scores from different groups of data points. Z-scores help in shadowing away the effect of low WNS points with higher FEP (timing end point) count (i.e., discarding paths having low-magnitude, negative WNS values that could easily fade away during the placement and routing stage). In general, there may be many paths having low-magnitude, negative WNS values that can contribute significantly to the TNS value, but which correspond to histogram bins that are not the focus of optimization.

TNS can be a misleading factor in deciding the contents of the buckets. The solution is to include the impact of WNS by calculating the Z-scores for both TNS and WNS using the same formula presented above.

The gravity (or heaviness) of every data point in the slack histogram depends upon the combined Z-scores for both TNS and WNS. The algorithm forms a separate cost group for data points with very large-magnitude negative TNS-based Z-scores (e.g., less than or equal to −1.0). For those data points, the algorithm finds the corresponding WNS-based Z-score. If the WNS-based Z-score is, e.g., greater than 1.0, then the algorithm calculates an effective TNS by dividing the original TNS by the WNS-based Z-score, and the new, effective TNS is bucketed accordingly.

The algorithm merges the remaining data points in the slack histogram until they achieve the gravity/heaviness of high-Z-score (e.g., less than or equal to −1.0) data points. The algorithm keeps adding consecutive data points until the condition (X1+X2+ . . . +Xn<μ−σ) is not met. At that point, the algorithm forms a cost group consisting of that set of data points (X1, X2, . . . , Xn). The process is then repeated until all of the data points in the slack histogram are in cost groups. The algorithm assigns equal weights to all of the cost groups, except for the top cost group CG_TOP, which has the lowest weight assigned by the algorithm.

FIG. 5shows the cost-group clustering of TNS optimization applied to slack histogram200ofFIG. 2. In particular,FIG. 5shows cost groups504,506, and508in addition to the top cost group CG_TOP502. AlthoughFIG. 5shows TNS optimization applied to slack histogram200, in a preferred implementation, TNS optimization is applied to the results of WNS optimization (e.g., slack histogram400ofFIG. 4).FIG. 5is intended merely to demonstrate the operations of TNS optimization. Note that WNS and TNS optimization are independent operations that can be performed separately, although WNS optimization is preferably followed by TNS optimization.

The algorithm then executes incremental timing optimization with the weights applied as per the TNS-based Z-scores.

FIG. 6shows a comparison of slack histogram200ofFIG. 2and the slack histogram600that is generated by applying TNS optimization in accordance with the present invention to slack histogram200ofFIG. 2. Like the WNS optimization described previously, TNS optimization shifts the slack histogram to the right and reduces the histogram peaks. WNS and TNS optimization bring the negative slack much lower compared to conventional approaches that work only on the top failing paths. Following WNS and TNS optimization, remaining top failing paths are addressed by updating timing and/or design constraints (as in step308ofFIG. 3). The use of WNS and TNS optimization can accelerate the overall design process.

In certain embodiments of the present invention, the histogram-based algorithm utilizes information from the slack histogram for a current IC design and assigns weights to paths that are sub-optimal so as to improve the TNS of the IC design. Information in the slack histogram is decoded to further optimize the IC design so that the TNS can be improved. The algorithms spend more time in analyzing actual violating paths than on the sub-optimal paths.

Actual violating paths are paths that violate because of constraints not being mature (due to the design being in an initial phase) or design architectural issues. Whereas, sub-optimal paths are paths that are not fully optimized by the EDA tool. Sub-optimal paths have negative slack but not necessarily because of timing constraints. They could have negative slack because the EDA tool could not focus much on these paths during optimization because of the focus placed on the top failing paths.

Histogram-based algorithms of the present invention can be applied to the design of SoCs having an initial set of constraints so that maximum concentration can be spent on actual violating paths and not on sub-optimal paths, making the optimization cycle iterative after every constraint update.

Although the present invention has been described in the context of a histogram-based algorithm that involves WNS optimization followed by TNS optimization, in other embodiments, a histogram-based algorithm might involve only one of WNS and TNS optimization.

FIG. 7is a schematic block diagram of an exemplary computer system700for performing the methods of the present invention described above. The computer system700includes a processor702coupled to a memory704and additional memory or storage706coupled to the memory704. The computer system700also includes a display device708, input devices710and712, and software714. The software714includes operating system software716, applications programs718, and data720. The applications programs718can include, among other things, a histogram-based optimizer that implements the WNS and TNS optimization algorithms of step314, and the data720can include the inputs and outputs from the various processing step shown inFIG. 3.

The computer system700and the constituent parts are all well known in the art, and the novelty resides in the methods and steps described above regarding gate level simulation. When software or a program is executing on the processor702, the processor becomes a “means-for” performing the steps or instructions of the software or application code running on the processor702. That is, for different instructions and different data associated with the instructions, the internal circuitry of the processor702takes on different states due to different register values, etc., as is known in the art. Thus, any means-for structures described herein relate to the processor702as it performs the steps of the methods disclosed herein.