Cover Image

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

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. Flo...

Full description

Saved in:
Bibliographic Details
Main Author: Angeline Teoh, Szu Fern
Format: Thesis
Published: 2012
Subjects:
T Technology (General)
TA Engineering (General). Civil engineering (General)
Online Access:http://studentsrepo.um.edu.my/8391/1/KGA090053_Thesis_Content.pdf
http://studentsrepo.um.edu.my/8391/
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.um.stud.8391
record_format eprints
spelling my.um.stud.83912018-05-18T02:31:25Z VLSI floor planning optimization using genetic algorithm and cross entropy method / Angeline Teoh Szu Fern Angeline Teoh, Szu Fern T Technology (General) TA Engineering (General). Civil engineering (General) 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. 2012-07-27 Thesis NonPeerReviewed application/pdf http://studentsrepo.um.edu.my/8391/1/KGA090053_Thesis_Content.pdf 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. http://studentsrepo.um.edu.my/8391/
institution Universiti Malaya
building UM Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Malaya
content_source UM Student Repository
url_provider http://studentsrepo.um.edu.my/
topic T Technology (General)
TA Engineering (General). Civil engineering (General)
spellingShingle T Technology (General)
TA Engineering (General). Civil engineering (General)
Angeline Teoh, Szu Fern
VLSI floor planning optimization using genetic algorithm and cross entropy method / Angeline Teoh Szu Fern
description 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.
format Thesis
author Angeline Teoh, Szu Fern
author_facet Angeline Teoh, Szu Fern
author_sort Angeline Teoh, Szu Fern
title VLSI floor planning optimization using genetic algorithm and cross entropy method / Angeline Teoh Szu Fern
title_short VLSI floor planning optimization using genetic algorithm and cross entropy method / Angeline Teoh Szu Fern
title_full VLSI floor planning optimization using genetic algorithm and cross entropy method / Angeline Teoh Szu Fern
title_fullStr VLSI floor planning optimization using genetic algorithm and cross entropy method / Angeline Teoh Szu Fern
title_full_unstemmed VLSI floor planning optimization using genetic algorithm and cross entropy method / Angeline Teoh Szu Fern
title_sort vlsi floor planning optimization using genetic algorithm and cross entropy method / angeline teoh szu fern
publishDate 2012
url http://studentsrepo.um.edu.my/8391/1/KGA090053_Thesis_Content.pdf
http://studentsrepo.um.edu.my/8391/
_version_ 1738506136610406400
score 13.211869

Similar Items