Our Simultaneous Placement and Gate-Sizing Algorithm

In Fig. 5.4, we display a possible search tree for our running example that has been pruned as aresult ofbounding. The partial solution 5 = ( b ), (c (- Ci), (d di) is eventually extended to form a complete solution however, in exploring the partial solution S = [ b bi), (c ci), (d d2), search is aborted. By visual inspection of Fig. 5.2, the distance between candidates Ci and d2 is relatively large, and contributes to an excessively long delay in S.  

One question raised by the backtracking framework is how to compute upper bounds on worst negative slack when only a subset of candidate assignments have been chosen. Traditional versions of Static Timing Analysis assume that all timing arcs have been Axed, whereas in our model, a disjunctive set of choices remains until a leaf node (i.e., a fully instantiated solution) in search is encountered. 

5 Gate Sizing During Timing-Driven Placement 

Since these weakened delay values must hold in any fully instantiated solution, the soundness of the procedure is preserved. Although the worst slack estimate calculated from this procedure may not be achievable in any complete solution, we are guaranteed that no extension of the partial solution can improve upon it. 

If a candidate assignment for one movable gate has been chosen, some entries in the conditional delay function may be disregarded. For instance, in Fig. 5.5, we consider the case when the partial solution S includes the decisions [ d d ), 

---