In this article, we propose new approaches for solving the useful-skew tree (UST) routing problem [Xi and Dai 1997]: clock routing subject to general skew constraints. The clock layout synthesis engine of our UST algorithms is based on the deferred-merge embedding (DME) paradigm for the zero-skew tree (ZST) [Edahiro 1992; Chao et al. 1992] and bounded-skew tree (BST) [Cong and Koh 1995; Huang et al. 1995; Kahng and Tsao 1997; Cong et al. 1998] routings; hence, the names UST/DME and Greedy-UST/DME for our UST algorithms. Our novel contribution is that we simultaneously perform skew scheduling and tree routing so that each local skew range is incrementally refined to a skew value that minimizes the wirelength increase during the bottom-up merging phase of DME. As a result, not only is the skew schedule feasible, but also the wirelength increase is minimized at each merging step of clock tree construction. The experimental results show very encouraging improvement over the previous BST/DME algorithm on three ISCAS89 benchmarks under general skew constraints in terms of total routing wirelength.

We propose new approaches for solving the useful-skew tree (UST) routing problem, Clock routing subject to general skew constraints. The clock layout synthesis engine of our UST algorithms is based on the deferred-merge embedding (DME) paradigm for zero-skew tree and bounded-skew tree routings; hence, the names UST/DME and Greedy-UST/DME for our algorithms. They simultaneously perform skew scheduling and tree routing such that each local skew range is incrementally refined to a skew value that minimizes the wirelength during the bottom-up merging phase of DME. The resulting skew schedule is not only feasible, but is also best for routing in terms of wirelength. The experimental results show very encouraging improvement over the previous BST/DME algorithm on three ISCAS89 benchmarks under general skew constraints in terms of total wirelength.

We study the minimum-cost bounded-skew routing tree problem under the pathlength (linear) and Elmore delay models. This problem captures several engineering tradeoffs in the design of routing topologies with controlled skew. Our bounded-skew routing algorithm, called the BST/DME algorithm, extends the DME algorithm for exact zero-skew trees via the concept of a merging region . For a prescribed topology , BST/DME constructs a bounded-skew tree (BST) in two phases: (i) a bottom-up phase to construct a binary tree of merging regions which represent the loci of possible embedding points of the internal nodes, and (ii) a top-down phase to determine the exact locations of the internal nodes. We present two approaches to construct the merging regions: (i) the Boundary Merging and Embedding (BME) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the Interior Merging and Embedding (IME) algorithm which employs a sampling strategy and a dynamic programming-based selection technique to consider merging points that are interior to, as well as on the boundary of, the merging regions. When the topology is not prescribed, we propose a new Greedy -BST/DME algorithm which combines the merging region computation with topology generation. The Greedy-BST/DME algorithm very closely matches the best known heuristics for the zero-skew case and for the unbounded-skew case (i.e., the Steiner minimal tree problem). Experimental results show that our BST algorithms can produce a set of routing solutions with smooth skew and wire length tradeoffs.

Academic clock routing research results has often hadlimited impact on industry practice, since such practical considerationsas hierarchical buffering, rise-time and overshoot constraints,obstacle- and legal location-checking, varying layer parasitics andcongestion, and even the underlying design flow are often ignored.This paper explores directions in which traditional formulationscan be extended so that the resulting algorithms are more usefulin production design environments. Specifically, the following issuesare addressed: (i) clock routing for varying layer parasiticswith nonzero via parasitics; (ii) obstacle-avoidance clock routing;(iii) a new topology design rule for prescribed-delay clock routing;and (iv) predictive modeling of the clock routing itself. Wedevelop new theoretical analyses and heuristics, and present experimentalresults that validate our new approaches.

This paper presents new single-layer, i.e., planar-embeddable, clock tree constructions with exact zero skew under either the linear or the Elmore delay model. Our method, called Planar-DME, consists of two parts. The first algorithm, called Linear-Planar-DME, guarantees an optimal planar zero-skew clock tree (ZST) under the linear delay model. The second algorithm, called Elmore-Planar-DME, uses the Linear-Planar-DME connection topology in constructing a low-cost ZST according to the Elmore delay model. While a planar ZST under the linear delay model is easily converted to a planar ZST under the Elmore model by elongating tree edges in bottom-up order, our key idea is to avoid unneeded wire elongation by iterating the DME construction of ZST and the bottom-up modification of the resulting nonplanar routing. Costs of our planar ZST solutions are comparable to those of the best previous nonplanar ZST solutions, and substantially improve over previous planar clock routing methods.

We study the minimum-cost bounded-skewrouting tree (BST) problem under the linear delay model.This problem captures several engineering tradeoffs in the design of routing topologies with controlled skew.We propose three tradeoff heuristics.(1) For a fixed topology Extended-DME (Ex-DME) extends the DME algorithm for exact zero-skew trees via the concept of a merging region.(2) For arbitrary topology and arbitrary embedding, Extended Greedy-DME (ExG-DME) very closely matches the best known heuristics for the zero-skew case,and for the infinite-skew case (i.e., the Steiner minimal tree problem).(3) For arbitrary topology and single-layer (planar) embedding, the Extended Planar-DME (ExP-DME) algorithm exactly matches the best known heuristic for zero-skew planar routing, and closely approaches the best known performance for the infinite-skew case.Our work provides unifications of the clock routing and Steiner tree heuristic literatures and gives smooth cost-skew tradeoff that enable good engineering solutions.

We study the minimum-cost bounded-skew routing tree problem under the Elmore delay model. We present two approaches to construct bounded-skew routing trees: (i) the Boundary Merging and Embedding (BME) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the Interior Merging and Embedding (IME) algorithm which employs a sampling strategy and dynamic programming to consider merging points that are interior to, rather than on the boundary of, the merging regions. Our new algorithms allow accurate control of Elmore delay skew, and show the utility of merging points inside merging regions.

Stochastic hill-climbing algorithms, particularly simulated annealing (SA) and threshold acceptance (TA), have become very popular for global optimization applications. Typical implementations of SA or TA use monotone temperature or threshold schedules, and are not formulated to accommodate practical time limits. We present a new threshold acceptance strategy called Old Bachelor Acceptance (OBA), which has three distinguishing features: (i) it is specifically motivated by the practical requirement of optimization within a prescribed time bound, (ii) the threshold schedule is self-tuning, and (iii) the threshold schedule is non-monotone, with threshold values even allowed to become negative. The standard implementation of the TA method of Dueck and Scheuer is a special case of OBA. Experiments using several classes of symmetric traveling salesman problem instances show that OBA can outperform previous hill-climbing methods for time-critical optimizations. A number of directions for future work are suggested. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.