Search

In this paper, we present ObSteiner, an exact algorithm for the construction of obstacle-avoiding rectilinear Steiner minimum trees (OARSMTs) among complex rectilinear obstacles. This is the first paper to propose a geometric approach to optimally solve the OARSMT problem among complex obstacles. The optimal solution is constructed by the concatenation of full Steiner trees among complex obstacles, which are proven to be of simple structures in this paper. ObSteiner is able to handle complex obstacles, including both convex and concave ones. Benchmarks with hundreds of terminals among a large number of obstacles are solved optimally in a reasonable amount of time. [ABSTRACT FROM PUBLISHER]

This paper presents an efficient method to solve the obstacle-avoiding rectilinear Steiner tree (OARSMT) problem optimally. Our work is developed based on the GeoSteiner approach in which full Steiner trees (FSTs) are first constructed and then combined into a rectilinear Steiner minimum tree (RSMT). We modify and extend the algorithm to allow obstacles in the routing region. For each routing obstacle, we first introduce four virtual terminals located at its four corners. We then give the definition of FSTs with blockages and prove that they will follow some very simple structures. Based on these observations, a two-phase approach is developed for the construction of OARSMTs. In the first phase, we generate a set of FSTs with blockages. In the second phase, the FSTs generated in the first phase are used to construct an OARSMT. Finally, experiments on several benchmarks are conducted. Results show that the proposed method is able to handle problems with hundreds of terminals in the presence of multiple obstacles, generating an optimal solution in a reasonable amount of time. [ABSTRACT FROM PUBLISHER]

In this paper, we present an algorithm called FOARS for obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction. FOARS applies a top-down approach which first partitions the set of pins into several subsets uncluttered by obstacles. Then an obstacle-avoiding Steiner tree is generated for each subset by an obstacle aware version of the rectilinear Steiner minimal tree algorithm FLUTE. Finally, the trees are merged and refined to form the OARSMT. To guide the partitioning of pins, we propose a novel algorithm to construct a linear-sized obstacle-avoiding spanning graph which guarantees to contain a rectilinear minimum spanning tree if there is no obstacle. Experimental results show that FOARS is among the best algorithms in terms of both wirelength and runtime for testcases both with and without obstacles. [ABSTRACT FROM AUTHOR]

In this paper, we present a performance and thermal-aware Steiner routing algorithm for three-dimensional (3-D) stacked integrated circuits. Our algorithm consists of two steps: tree construction and tree refinement. Our tree construction algorithm builds a delay-oriented Steiner tree under a given thermal profile. We show that our 3-D tree construction involves minimization of two-variable Elmore delay function. In our tree refinement algorithm, we reposition the through-silicon-vias (TSVs) used in existing Steiner trees while preserving the original routing topology for further thermal optimization under a performance constraint. We employ a novel scheme to relax the initial nonlinear programming formulation to integer linear programming and consider all TSVs from all nets simultaneously. Our tree construction algorithm outperforms the popular 3-D maze routing by 52% in terms of performance at the cost of 15% wirelength and 6% TSV count increase for four-die stacking. In addition, our TSV relocation results in 9 % maximum-temperature reduction at no additional area cost. We also provide extensive experimental results, including the following: 1) the wirelength and delay, distribution of various types of 3-D interconnects; 2) the impact of TSV RC parasitics on routing and TSV relocation; and 3) the impact of various bonding styles on routing and TSV relocation. Last, we provide results on two-die stacking. [ABSTRACT FROM AUTHOR]

Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is an essential part of routing. Recently, IC routing and related researches have been extended from Manhattan architecture (λ2-geometry) to Y-/X-architecture (λ3-/λ4-geometry) to improve the chip performance. This paper presents an O(n log n) heuristic, λ-OAT, for obstacle-avoiding Steiner minimal tree construction in the A-geometry plane (λ-OASMT). In this paper, based on obstacle-avoiding constrained Delaunay triangulation, a full connected tree is constructed and then embedded into λ-OASMT by zonal combination. To the best of our knowledge, this is the first work addressing the λ-OASMT problem. Compared with most recent works on OARSMT problem, A-OAT obtains up to 30-Kx speedup with quality solution. We have tested randomly generated cases with up to 10 K terminals and 10-K rectilinear obstacles within 4 seconds on a Sun V880 workstation (755-MHz CPU and 4-GB memory). The high efficiency and accuracy of λ-OAT make it extremely practical and useful in the routing phase. [ABSTRACT FROM AUTHOR]