A new general connectivity model and its applications to timing-driven Steiner tree routing
Dongsheng Wang, E.S. Kuh · 2002
In this paper, we first construct a general connectivity graph from a given net based on some pertinent observations of the Elmore delay model. The graph is defined as a weighted directed connection graph (DCG) which is used to describe the "edge connectivity" of all the edges on the graph. Then a timing-driven Steiner tree routing approach, called the C-Tree algorithm, is proposed. It constructs an initial spanning tree by the method of edge elimination on graph DCG. Next, the initial tree is improved to achieve a better area/delay trade-off by maximizing "path connectivity" of the minimum connectivity path (MCP). Finally, the spanning tree is transformed to the corresponding Steiner tree. Experiments show that the C-Tree algorithm is promising.