On the bounded-skew clock and steiner routing problems

We study the minimum-cost bounded-skewrouting tree (BST) prob-lem under the linear delay model. This problem captures several engineering tradeoffs in the design of routing topologies with con-trolled 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) algo-rithm 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 rout-ing and Steiner tree heuristic literatures and gives smooth cost-skew tradeoff that enable good engineering solutions.