Powerful combination of genetic and greedy algorithms for over the cell channel routing problem

Abstract

Over the cell (OTC) channel routing problem is one of the well-known VLSI layout problems. OTC channel routing allows restricted wiring over the areas occupied by circuit blocks (cells) and results in significant reductions in channel widths, and consequently, in the overall chip area. In this paper, a highly efficient OTC channel router based on genetic algorithms combined with a powerful greedy routing method is presented. Nets to be wired are divided into two groups; those to be wired within the channel and those to be wired over the cells. Based on this information, and the horizontal and vertical constraints among different nets, chromosome encoding are formed in an optimal manner such that decoding into a solution is computationally simple and infeasible configurations are avoided. The overall problem is solved in three main steps: optimal allocation of nets to be routed over the cells, routing over the cells, and routing within the channel. Routing within the channel is performed using a very fast and quite efficient greedy algorithm [Hashimoto and Stevens]. The results we obtained are optimal and, for the available benchmark channel routing problems in literature, our solutions are better than those obtained by almost all other methods.