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.
['Jason Cong', 'Andrew B. Kahng', 'Cheng-Kok Koh', 'C.-W. Albert Tsao']
Bounded-skew clock and Steiner routing