STEINER PROBLEM IN OCTILINEAR ROUTING MODEL

Abstract

Routing of signal nets of VLSI circuits is a typical interconnection problem. The objective is to connect a set, or net, of terminals on a chip with minimum wirelength such that there exists a path between any two terminals. The problem may be solved sub-optimally by a minimum spanning tree (MST). Optimal interconnection can be obtained if the problem is formulated as the Steiner problem in which wires may meet at newly added terminals or Steiner points. The optimal interconnection is known as the Steiner minimal tree (SMT). The Steiner problem in Euclidean and rectilinear routing models has been well studied. There are two difficult issues: the first is to establish the Steiner ratio, which is defined lo be the lowest ratio of the length of a SMT to the length of a minimum spanning tree (MST) among all problem instances. It measures how closely the MST approximates the SMT. The Euclidean and rectilinear Steiner ratios are ?3/2 and 2/3, respectively. The other issue concerns with developing "good" heuristics to solve the problem which is known to be NP-complete. The performance ratio of an algorithm is the lowest ratio of the length of a SMT to the length of the Steiner trace produced by the algorithm among the problem instances. The challenge is to invent an algorithm that has a performance ratio strictly higher than the Steiner ratio. Most of the MST-based heuristics have performance ratio arbitrarily close to the Steiner ratio. In this thesis, we focus on a new geometric formulation for the Steiner problem in the model. We introduce a new routing model called the octilinear routing model. The new model allows two additional diagonal (±45°) wiring orientations on top of the rectilinear orientations. Recently, the model has been used in channel routing. Results have shown that overall routing area and wiring length required is generally lower than that for the traditional rectilinear routing model. This motivates us to look at the octilinear Steiner problem. In this thesis, we extend various important properties of SMT from the rectilinear model to the octilinear model. We show that a Steiner point in a SMT has three or four neighbors. Valid configurations of the edges incident on a vertex in the SMT are also given. These properties allow us to solve the 3-point octilinear Steiner problem. We, also establish that for the 3-point Steiner problem, the Steiner ratio is ( ?2 + 1 )/2?2 ?0.854. Partial results of the 4-point problem show that. it is likely that the general n-point Steiner problem has the same Steiner ratio. This would imply that an octilinear MST is a better approximation to octilinear SMT than a rectilinear MST is to rectilinear SMT. We also generalize the Hanan's Theorem and show that for any problem instance, there exists a SMT such that all Steiner points in the SMT lie on the generalized Hanan's grid. We propose a heuristic algorithm for the general n-point Steiner problem. When the problem size is less than ten, the algorithm produces Steiner tree which has an average of about 2.8-4% improvement over the cost of MST. For problems with more points, the average improvement hovers over the 4% mark. A possible explanation is that an octilinear MST is a very close approximation to octilinear SMT, thereby leaving little room for improvement.