Multi-layer channel routing

A channel is a rectangular area of a VLSI (Very Large Scale Integrated) chip which is used to make electrical connections between circuits on the chip. Channel Routing is the problem of providing the interconnections for all circuits attached to the periphery of the channel such that the total area of the channel is minimized. Previous heuristics for solving the channel routing problem have focused on channels which have only two layers of interconnect available. Recent VLSI fabrication advances now allow more than two layers of interconnect. This dissertation is an investigation into channel routing using multiple layers of interconnection. A formal description of the multi-layer channel routing problem is presented. In the reserved z-layer model of channel routing adjacent layers of interconnect are reserved for wires which run in orthogonal directions. Thus there are three reserved z-layer models: the HiVi+l, HiVi and Hi+lVi models, where i \u3e 0 denotes the number of horizontal (H) and vertical (V) layers of interconnect available. Previous techniques for modeling constraints which must be satisfied in order to produce a routing for a channel are unified by the definition of the channel constraint graph. r The intrinsic complexity of the channel routing problem is investigated and it is shown that channel routing using restricted-doglegs in the H2Vl model is NP-complete. Optimal algorithms for routing channels in the HiVi+ 1 model are presented which have runtime complexity linear in the size of the corresponding channel constraint graph. Heuristic algorithms are developed which route channels in the Hi Vi and Hi+ 1 Vi models. These heuristics are shown to have runtime linear in the size of the corresponding channel constraint graph. Upper bounds on the worst case performance of these heuristics are proved. Results of experiments which included routing many randomly generated channels having characteristics of channels found in industrial VLSI design environments are reported. These experiments show that the channel routing heuristics developed in this dissertation route almost 100% of these randomly generated channels using only two rows above the theoretic minimum in the Hi Vi and Hi+ 1 Vi models, i\u3e2