Implementation of A Genetic Algorithm for Channel Routing in VLSI Circuits


The first steps in the physical design of VLSI chips are partitioning and floorplanning. Partitioning is the process of dividing the chip into smaller pieces so that each piece is easier to deal with. Floorplanning is the process of providing a shape and a location for each block. The next step is to optimally place the standard cells within each block and the file step is to perform the routing between the blocks. Although many algorithms have been proposed for VLSI routing, there is plenty of room for improvement as the problem is NP-complete.

In computer science, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection. Genetic algorithms are commonly used to generate high-quality solutions to optimization. They rely on on bio-inspired operators such as mutation, crossover and selection.

The purpose of this project is to implement the following paper which uses a genetic algorithm to solve the channel routing problem:

The routing tool may be implemented in any language.

Prerequisites: Background in programming and data structures.

Supervisor : Amnon Stanislavsky