A GENETIC ALGORITHM BASED APPROACH TO SOLVE VLSI FLOORPLANNING PROBLEM

Definition −VLSI (Very Large Scale Integration) floor planning is known to be NP-hard (Non-Deterministic Polynomial-time Hard) problem. There is a need to develop automated algorithms to decide the relative positions of circuits on a VLSI chip. During the floor planning phase, the major objective is to minimize area (deadspace) in a chip. In this paper, in order to find the near to optimal solution for floor planning problem a genetic algorithm has been applied for outline-free floor plans. A heuristic placement strategy is used in our work which helps in deciding the positions of rectangular modules on a chip. Microelectronics Centre of North Carolina (MCNC) benchmark circuits are used to test the performance of our algorithm and experimental results show that genetic algorithm and heuristic placement strategy are able to produce near to optimal solutions which are comparable with various techniques proposed in literature for outline-free floor plans.