New Bound-Based Net Criticality Metrics for Timing-Driven Physical Design

Abstract

A target of this work is improving timing characteristics of layout and optimizing design flow by reducing the number of iterations required for a timing closure. This goal is achieved by introducing new criticality metrics that could be computed prior to placement and routing respectively and converted to weights of nets supplied to a placer and to a router. These new metrics are defined as a ratio of a net parameter to a net delay bound.

The net delay bounds used in this paper are computed by the Iterative Minimax algorithm of Youssef et. al. (see references in the text). This algorithm has the lowest time complexity (linear) among all algorithms proposed for the computation of delay bounds and corresponds well with therequirements of layout tools. In this paper, a contribution is also made to the bound on the delays theory by proving that there is an infinite number of solutions for the zero-slack distribution problem. It is also explained why net bounds derived from a linear programming formulation could be difficult to implement on the placement step of layout.

Part II:

This report proposes new net criticality metrics and one pass design flow methodology for timing-driven physical design. The proposed net criticality metrics employ net parameters and bounds on net delays derived by the Minimax algorithm. The criticality metrics were mapped to weightsin the Cadence Silicon Ensemble DSM Automatic Layout System and produced in one-pass layouts with the clock cycle approximately 29% faster in average than without criticality evaluation. Criticality metrics are independent of layout tools producing actual placement and routing.Criticality calculation could be integrated with any layout system that allows weights for individual nets on the placement and routing steps. In the section on Criticality Metrics, it is proven that the net parameters strongly correlated to net delay could be used in formulas for criticality metrics. They provide the same relative ranking of nets with respect to the net criticality metrics as the projected net delays. On this ground, the new criticality metrics based on net parameters and delay bounds are introduced for placement and routing stages of layout respectively. These criticality metrics computed for each net in the design are sorted in the descending order to produce relative ranking of nets with respect to the net criticality. From the ordered list of criticality metrics weights are derived by layout systems. In the experimental part of this work, the proposed design flow and the criticality metrics were integrated with the Cadence SE (Silicon Ensemble) DSM Automatic Layout System (version 5.2.158). The SE system was allowed to place and route a set of designs in several modes with and without weights produced from the proposed new criticality metrics. With weights provided by the new criticality metrics, the SE system achieved reduction in the clock cycle by 27% in average for the set of tests in one iteration of layout. It also significantly outperformed attempts to reduce a clock rate by repeated iterations of layout and by using timing-driven version of the SE Layout System. A conclusion is that new metrics could be useful for all layout tools that allow weights to be assigned to nets.