VLSI floor planning optimization using genetic algorithm and cross entropy method / Angeline Teoh Szu Fern

Angeline Teoh, Szu Fern (2012) VLSI floor planning optimization using genetic algorithm and cross entropy method / Angeline Teoh Szu Fern. Masters thesis, University of Malaya.

Preview

PDF (Thesis M.A) Download (2450Kb) | Preview

Abstract

This project is about VLSI floorplanning optimization. Floorplanning optimization is used to minimize the deadspace of the floorplan. This is to reduce cost for die fabrication, minimize resistance in the circuit and also reduce heat produced. Hence, VLSI floorplanning is important in IC design. Floorplanning optimization consists of representation and optimization algorithm. In present work, Dot Model (DM) and Corner Bottom Left List (CBLL) were developed as floorplan representation. These two models are based on topological placement method. DM is optimized using genetic algorithm (GA). GA is a widely used optimization algorithm based on the concept of survival of the fittest. This means that a population with random generated sequence will be generated and the fitness of the population will be evaluated. The best quantile of the population will be maintained and genetic operations will be performed on these chromosomes. The selected best quantile population will be brought to the next generation. GA is able use the representation for DM by modifying the chromosomes to match the tuples for DM for optimization. Two methods of optimization are used for CBLL. They are Cross Entropy and also Genetic Algorithm. CE is a new algorithm that was recently developed using probability. This method consists of 2 phases which are the random data generation and then update of the probabilities based on the performance of the data generated. This method is used to reduce the stochastic of data generation as the second iteration will have influence of the first iteration data. The generation of strings are based on three dimensional matrices to obtain the probability between each block to another block. These algorithms are tested on MCNC benchmarks which are apte, xerox, hp, ami33 and ami49. DM-GA gives fair results of deadspace for the benchmarks tested. However, DM uses a long runtime to decode the floorplan. CBLL- GA has shorter optimization runtime compared to DM-GA because CBLL can decode the string much faster. Both methods give almost similar deadspace iii area. CBLL-CE gives the least deadspace area. CE is able to calculate and give the relationship of the local deadspace area during placement and determine the best combination between the adjacent blocks. However, CE requires longer run time compared to GA because the parameters of the random mechanism need to be updated in each iteration.

Actions (For repository staff only : Login required)