EFFICIENT ALGORITHMS FOR OVER-THE-CELL CHANNEL ROUTING IN VLSI DESIGN USING TWO AND THREE ROUTING LAYERS

Abstract

Advances in VLSI fabrication technology have made it possible to use more than two routing layers for interconnections. The added routing layers allow IC designers to utilize areas above the standard cells for routing in order to reduce the total chip area. This poses a new channel routing problem which is referred to as over-the-cell channel routing problem (OTC-CRP).

The over-the-cell (OTC) channel routing can be divided into various classes depending on the physical models of the standard cell libraries. A survey on the existing models is presented in this thesis. In addition, a new routing model, i.e., the constrained terminals over-the-cell channel routing model is proposed to improve the utilization of areas over the standard cells for routing. Correspondingly, this model introduces a new routing problem which is called constrained terminals over-the-cell channel routing problem (CTOC-CRP).

The HERO-V algorithm is presented in this thesis to solve the traditional two-layer OTC channel routing problem. This algorithm can efficiently select a subset of net segments to be routed over the cells with consideration of density distribution in the channel, and by making use of the vacant terminals, this algorithm reduces the longest path in the vertical constraint graph, as well as the maximum cliques in the horizontal constraint graph. At the same time, cycles in the vertical constraint graph are eliminated as much as possible. This algorithm performs better than all pervious algorithms. As tis algorithm is based on the analysis of the constraints in a channel, the study of these constraints is concluded by presenting a new lower bound for the traditional channel routing problem where restricted doglegs are allowed.

For constrained terminals over-the-cell (CTOTC) channel routing, the PC-TPTC algorithm is presented to deal with the routing problem. This algorithm is based on a maximum weight independent chord set algorithm to select proper subset of the OTC candidates for planar routing in the OTC areas. As such, the MWICS algorithm based on the dynamic programming approach is presented to find the maximum weight independent chord set of m chords which are incident to v vertices in a circle where two chords may share a common vertex. The MWICS algorithm has a time complexity of O(mv). Previously, researchers believed that this problem can be solved in time complexity of O(v3). The performance of the PCTOTC algorithm is also analyzed theoretically and it has been found that this algorithm has a performance ratio of at least 51%. The performance ratio of an algorithm is the ratio of the cardinality of the solution obtained by the algorithm to the cardinality of an optimal solution.

The PCTOCTC- algorithm, which is modified form the PCTOTC algorithm, is presented too, to solve the traditional three-layer OTC channel routing problem. Extensive experiments were conducted to verify the efficiencies of the proposed algorithms, from the PRIMARY 1 benchmark examples, it has been found that HERO-V, PCTOTC- and PCTOTC can reduce the total channel height by 41.3%, 64.0% and 71.5% respectively. They have performed better than all other algorithms proposed by previous research works. Based upon the same benchmark examples, it has been observed that the proposed OTC routing algorithms can also reduce the total number of vias and the total wire length, thus contributing positively to the yield of IC production and the circuit performance.