Performance-Driven Routing-Tree Construction with Obstacle Consideration
Date Issued
2004
Date
2004
Author(s)
Chen, Sheng-Fong
DOI
en-US
Abstract
The optimization of Steiner minimal trees (SMT’s) is a very important problem in computer-aided design of VLSI circuits. Given a graph, the classical SMT problem is to construct a tree of the graph with the minimal total wirelength to reduce interconnect capacitance, cost of metal wiring, etc. by utilizing any additional vertices in the wiring plane. With the advances of VLSI technology, many constraints for the wiring need to be considered during the tree construction. For example, prerouted nets and a dense power mesh incur significant routing blockages, and the trend of high-speed VLSI designs makes performance-driven routing more popular.
To cope with the trends, we work on the constrained SMT problems as follows:
Given a set of pins and obstacles in the routing plane, our objective is to construct a Steiner minimal tree with minimal wirelength so that no pins and edges are in the obstacles. We develop a Steiner point moving algorithm to relocate all violated points (the points inside the obstacle) into their best feasible positions and then apply Zhou’s spanning graph based Steiner minimal tree algorithm to handlethe obstacle-aware Steiner minimal tree problem. We also extend the algorithm to consider timing constraints by finding the bounded radius Steiner minimal tree.
Experimental results show that we can construct the obstacle-aware Steiner minimal tree (OASMT) with 5000 pins and 100 obstacles within 9 seconds. The OASMT’s average quality is decreased only 2.1% of that obtained by the Steiner minimal tree construction without obstacles consideration. With the longest path constraint, we can make trade-off with total wirelength. The experimental show that our method is very efficient.
Subjects
繞線樹
反演幾何樹
障礙物
Routing-tree
Obstacle
Steiner tree
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-93-R91943074-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):cc1b84d879e72472e36dbaef20b6a58f