Name
Title | ||
|---|---|---|
CDCTree: novel obstacle-avoiding routing tree construction based on current driven circuit model |
Abstract | ||
|---|---|---|
Routing tree construction is a fundamental problem in modern VLSI design. In this paper we propose CDC-Tree, an Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) heuristic algorithm to construct an OARSMT. CDC-Tree is based on the current driven circuit (CDC) model mapped from an escape graph. The circuit structure comes from the topology of the escape graph, with each edge replaced by a resistor indicating the wirelength of that edge. By performing DC analysis on the circuit and selecting the edges according to the current distribution to construct an OARSMT, the wirelength of the resulting tree is short. The algorithm has been implemented and tested on cases of different scales and with different shapes of obstacles. Experiments show that CDCTree can achieve shorter wirelength than the existing best algorithm, An-OARSMan, when the terminal number of a net is less than 50. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1118299.1118447 | ASP-DAC |
Keywords | Field | DocType |
different scale,novel obstacle-avoiding routing tree,escape graph,current distribution,best algorithm,current driven circuit model,circuit structure,different shape,shorter wirelength,heuristic algorithm,routing tree construction,current driven circuit,obstacle avoidance,vlsi design,network routing,circuit topology,network topology,routing | Obstacle,Mathematical optimization,Computer science,Current distribution,Heuristic (computer science),Microprocessor,Algorithm,Electronic engineering,Network topology,Resistor,Very-large-scale integration,Topology (electrical circuits) | Conference |
ISSN | ISBN | Citations |
2153-6961 | 0-7803-9451-8 | 9 |
PageRank | References | Authors |
0.79 | 10 | 5 |