Swagata Saha Sau ¹, Rajat Kumar Pal ²

Affiliations
1 Department of Computer Science, Sammilani Mahavidyalaya, Baghajatin, Kolkata – 700075, West Bengal, IN
2 Department of Computer Science and Engineering, University of Calcutta, Kolkata –700009, West Bengal, IN

Abstract

Objectives: The wire length minimization of Channel routing problem is NP-hard. There are several heuristic algorithms available in the literature to get the feasible routing solutions using some limited instances. Here we want to generate all possible random channel instances based on Genetic Algorithm (GA). Methods/ Statistical Analysis: The present paper is described in three phases. In the first phase, we generate fixed size initial population based on some strategies and define the fitness value of each individual by the total number of vertical and horizontal constraints present in the channel. The best individual is obtained among the population based on height fitness value. In the second phase, we select two individuals based on Roulette Wheel Selection strategies and get two offspring's using single point crossover. We continue this process until the number of offspring's reached to the size of the population. To keep the population size fixed we apply reduction methods among the initial population along with all offspring are based on minimum fitness value. In the third phase, we randomly choose some channels for mutation and we find the best individuals among current population. This methodology will be continuing until and unless we reach the goal. Findings: The proposed method works efficiently for complex problems arise in VLSI physical design automation and it gives acceptable results in terms of different channel instances. Applications/Improvement: The newly designed method for different difficult channel instances generation techniques will help to judge any newly developed algorithm in the field of VLSI physical design automation.

Keywords

Channel Instance, Channel Routing Problem, Genetic Algorithm.

Full Text