An automated routing method for VLSI with three interconnection layers

Recently, to the extent allowed by the fabricating technology, approaches have been made to develop an automated router for the multi-layer IC layout design. In this thesis, we examine the VLSI routing problem where three layers are available for interconnection;We investigate the routing problem in three stages: global routing, power/ground routing, and channel routing. The global routing for three-interconnection layer model is not much different from that of two-layer madel. We study the global routing problem for two cases: gate array and general cell layout. In our three-layer grid model, power/ground wires keep the direction-per-layer scheme as signal net wires. However, the power/ground routing is further constrained by the width of wires and the layers they are laid on;The channel routing stage of our router is based on directional model where overlaps of horizontal wire segments are allowed. We improve the dogleg method so that it is applicable to the three-layer model and it can handle multi-terminal nets more efficiently. Applying the extensive dogleg method and the three-layer merge algorithm, we not only remove the cyclic vertical constraints graph but also eliminate the effect of the height of long vertical constraints tree to the channel width and thus we reduce the lower bound of the channel width to half of the density of the channel. We expand the applicability of channel router by eliminating some of the limitations assumed in channel routing problems by some existing algorithms. Routability conditions are examined for various cases of channel routing problem;The major result presented in this dissertation is an algorithm for a channel routing problem. Given a rectangular channel with terminals on top and bottom sides, the algorithm will find a three-layer channel routing which minimizes the channel width and the wire length. Experimental results show that our router is close to optimal