A Genetic Algorithm for Channel Routing in VLSI Design

The production of Integrated Circuits is a complicated process that includes several phases of which physical design is considered to be the main one. The physical design phase, in turn, is accomplished through several steps that include partitioning, floorplanning and placement, routing, and compaction. In the routing step, the goal is to complete the interconnections between blocks according to the specified net list. Channel routing is a detailed routing that deals with the routing problem in a rectangular area between blocks known as channel. Many versions of the channel routing problem have been shown to be computationally intractable. That is why many researchers have been developing heuristic techniques to obtain efficient solutions to the problem. In this paper, we introduce an evolution-based approach to solve the channel routing problem. In particular, we focus on a version of the problem with a goal of minimizing the number of routing tracks in the channel, and hence, reducing the channel size. This approach allows the exploration of more points in the search space as compared to traditional channel routing heuristics. Therefore, it reduces the probability of returning a local optimal solution that is far from the overall optimal solution.