Genetic Algorithms In VLSI Floorplanning
International Journal of Engineering Research & Technology (IJERT)ISSN: 2278-0181Vol. 1 Issue 8, October - 2012Genetic Algorithms In VLSI FloorplanningChinmay Gore, Fiona Britto, Mandar RajeUniversity of MumbaiAbstractWith the aim of achieving optimum solutions in VLSIdesign, genetic algorithms are now used in partitioning,floorplanning and many other stages of system design.GAs also aim at optimizing conflicting parameters, ning is the problem ofplacing a given set of circuit modules in the plane tominimize a weighted sum of the area of the boundingrectangle containing all the modules; and an estimationof the total interconnection wire length (or any suitableproximity measure)[3].IJERTGenetic Algorithms are search oriented empiricaltechniques, which are derived from the Theory ofNatural Evolution by Charles Darwin. With the help ofgenetic operators like inheritance, mutation, selectionand crossover, these algorithms are capable of solvingoptimization problems. Genetic Algorithms are a subsetof Evolutionary Algorithms that are being extensivelyapplied in Very Large Scale Integrated Circuit (VLSI)design. Research endeavours in this domain are beingpursued worldwide. In this article, we present anoverview of various Genetic Algorithms that are usedin the optimization of the very first stage of the VLSIphysical design process - floorplanning.form a new population set. Using this set of fitterindividuals, GAs try to achieve a good solution to thepredefined problem.Keywords: Genetic Algortihm, VLSI Design,Floorplanning, Optimization, Area, Wirelength1.1 NomenclatureReaders will come across the following terminologiesquite frequently:1. IntroductionThe Very Large Scale Integrated (VLSI) circuitindustry is progressing towards the ultimate flatteningof Moore‟s Law[1]. Advances in manufacturingtechniques and sophisticated physical design toolsfacilitate development of microchips with high packagedensity. The advent of deep sub-micron technology hasa multitude of attractive designing prospects. However,these rapid advances in technology have tremendouslyincreased the design complexity of VLSI circuits,necessitating robust optimization techniques in manystages of VLSI design. Critical problems such ascrosstalk, congestion etc. deter the exploitation of thistechnology‟s full potential.A Genetic Algorithm (GA) makes use of selection,mutation, crossover, derived from the Theory ofEvolution proposed by Charles Darwin. Over a periodof time, individuals respond to changes in theirsurrounding environment, that is they adapt, and theindividuals who fail to adapt become extinct. Theindividuals which survive are considered to be fit andwww.ijert.orgIndividual- It means any possible solution to a givenoptimization problem.Population- Population is referred to as group of allindividuals.Search Space- All possible solutions to the problemconstituent search space.Chromosome- It infers to blueprint of an individual.Trait- Trait is possible aspect of an individual.Allele- Possible settings for a trait are defined asAllele.Locus- Position of a gene on chromosome is defined asLocus.Genome- Genome is referred to as Collection of allchromosomes for an individual.The rest of the article is organised as follows:Section 2 describes the problem statement,Section3gives a gist of Genetic Algorithms and the varioussteps involved in it. Several variations of GAs are1
International Journal of Engineering Research & Technology (IJERT)ISSN: 2278-0181Vol. 1 Issue 8, October - 2012elaboratedin Section 4 followed by the concludingsection of this paper.2. Problem DefinitionSpecificationPartitioningLogic pactionTestingFig.1 VLSI Design FlowFor a rectangular module with width W, height H andarea A, its Aspect Ratio(r) is defined as the ratio ofH/W. It is possible to have a rectangular module whoseW and H may vary, but the aspect ratio of the modulemust remain constant. Such a module is termed as asoft rectangular module[23]. The Aspect Ratio for softrectangular modules may vary from 1/r to r, givingnumerous possible solutions for the floorplan. As citedby Shingo NAKAYA et al[7], the number ofpossibilities for the placement of modules increasesexponentially with the increase in the number ofmodules. Therefore, designs in the nano-scale era putforth a tedious challenge in front of the physical designengineers.IJERTFig. 1 describes the design flow in VLSI. Based on userspecification and system constraints, a logical design iscreated. Once the design is synthesized and simulatedwith the help of Computer Aided Design (CAD) tools,we proceed todesigning the system at the transistorlevel. This level of design is influenced greatly by thefabrication technology. After verification of thephysical design, chips are fabricated. The chipssatisfying operational and quality standards arelaunched.While working at the physical design level,circuit partitioning and floorplanningare the primarysteps which influence the later stages. Circuitpartitioning refers to thedivision of circuits into smallerparts for facilitating design and layout[17]. Theprimeobjectives of circuit partitioning are minimizing thenumber of interconnections in partitions and reducingthe delay due to interconnections.Floorplanning represents top level spatial structure of achip. It is basically the placement of different modulesor circuit blocks to minimize chip area and interconnectlength. Floorplanning is done in two steps [22]:The first step locates modules on the chip to minimizethe interconnect length. The second step alters thewidth and the length of the modules so as to obtainminimum area.Objectives which must be satisfied by partitioning are:1. Mincut problem- Partitioning should reducenumberof interconnects between modules. This reduces notonly delay but also modules but also minimizesinterface between partitions, making designindependent and easy to fabricate [21].2. Partitioning may result into generation of a criticalpath connecting two modules. Delay betweenpartitions is significantly more than that withinpartition. So timing constraints must be considered.3. With proper partitioning, it is possible to attainminimum area, thereby reducing the cost offabrication.www.ijert.orgFloorplanning aims at minimizing the interconnectlength. Interconnects are conductor tracks between twoor more modules[1][18]. They contribute to distributedparasitic components such as Series Resistance(R) andShunt Capacitance(C).These parasitics vary directlywith the interconnect length.They are responsible ing cut off frequency ωc, where,ωc (R.C)-1 .Equation (i)Equation (i) implies there are restrictions on themaximum frequency of a signal which can propagateover the interconnect without significant amplitude andphase distortion. Moreover, a majority of thesynchronous circuits suffer from clock skew and clockjitter problems, which are caused by interconnects.Clock skew is termed as the difference in the clockarrival times of two flip-flops (sequential blocks) whichmust be operated simultaneously[1] [18]. Clock jittercan be termed as clock signal affected with noise,which may result into unwanted transitions in between.3. Genetic AlgorithmsGeneticAlgorithmsarebasically stochasticoptimization techniques. In compliance with CharlesDarwin‟s theory of natural evolution, these algorithmsare based on the „survival of the fittest‟ phenomenonwhich is prominent in nature. Genetic Algorithms are2
International Journal of Engineering Research & Technology (IJERT)ISSN: 2278-0181Vol. 1 Issue 8, October - 2012used quite often to obtain solutions for optimizationand search hildrenEvaluated ChildrenPopulationEvaluationDiscardFig. 2 Genetic Algorithm Reproduction CycleThe population with mutated bits is then evaluated forfitness and again the entire cycle of selection, crossoverreplacement and mutation is carried out. This cycle isrepeated for number of iterations specified by theprogrammer.One of the merits of Evolutionary Algorithms isavailability of a ready solution at any stage. Thissolution may not be the global optimal solution, but itcan be a good solution. So, the stopping criteria is notspecified in the algorithm itself. However, iffitnessdoes not improve significantly for predefined numberof runs, the GA is terminated. This number of runs isdecided by system size and complexity.IJERTGAs produce several alternative solutions (termed aspopulation) for a given problem. Based on its analogyto chromosomes in natural systems, every individual inpopulation is referred to as chromosome or string. Thepopulation size of a GA determines the amount ofinformation contained in it. This population is evolvedover a number of generations.Mutation: Once population replacement occurs,mutation is performed randomly on the bits withnominal mutation probability. Probability of mutationis critical; since the number of bits which will bemutated depends on this probability. The conventionalbinary mutation operator is nothing but the simpleinversion of any random bits in the population,depending on the probability of mutation. Mutations ofbits differ from the conventional binary mutationoperator. Mutation alters the partition which is assignedto the random number of components, whereprobability of mutation governs the number ofcomponents affected. In order to avoid drastic changesin the population, the probability of mutation is usuallychosen to be low[24] [25] [26].Genetic Algorithms aim at obtaining optimal solutionto a given problem. They are heuristic procedures,often represented as the function optimizers[24] [25][26]. Even though they do not vouch to find optimumsolution all the time, they are capable of deliveringgood solutions for variety of problems.Fitness Evaluation: Each individual is assessed for itsfitness function based on the cost computed. Dependingon the fitness values, individuals are randomly chosenfor the crossover operation, using roulette wheelselection, tournament selection [24] [25] [26] etc.Crossover: Every individual is considered for selectionas a parent for the crossover stage. The probability ofselection depends upon the fitness value of theindividual. If the fitness value of the offspringgenerated is more than some constituents of thepopulation, then the individuals with the lowest fitnessvalues are substitute with the fitter offsprings. Noreplacement is made if fitness value of offspring is lessthan lowest weak individuals. In short, in thisalgorithm, novel offsprings replace an equivalentnumber of futile solutions from the previouspopulation, along with supporting better solutions toexist over several generations. Probability ofoccurrence of crossover is usually 60 to 70%.www.ijert.orgCommon terminating criteria for Genetic Algorithmsare:1. Obtaining solution satisfying minimum criteria2. Fixed number of generations reached3. Allocated budget such as computational timereached4. Manual inspection5. Lack of significant increase in fitness of highestranking solution6. Combinations of above conditions.4. Compendium of AlgorithmsThis section discusses three prominent categoriesofGenetic Algorithms for optimum floorplanning. Eventhough basic procedure for Genetic Algorithms issimilar, with more or less modifications in operations,diverse optimization problems are addressed. Results ofthese algorithms are also included.3
International Journal of Engineering Research & Technology (IJERT)ISSN: 2278-0181Vol. 1 Issue 8, October - 20124.1 GAPE: Distributed Genetic AlgorithmIn the paper „Distributed Genetic Algorithms for theFloorplan Design Problem‟ [4], authors have proposedanew algorithm GAPE ( Genetic Algorithm Based ontheory of Punctuated Equilibrium). PunctuatedEquilibrium is governed by two principals: rapidevolution of new species (allopatric speciation) andstability (stasis) [27].Under the constraint of equivalent“work,” GAPE has performed better than the simulatedannealing approach, both in terms of the average costof the solutions found and the best-found solution, inalmost all the problem instances tried.Factors influencing performance of Parallel GA are:1. Number of islands2. Migration interval3. Size of sub-population on different islands4. Crossover and Mutation probabilities5. Selection rallelGAControllerRTGAPE was an early attempt which overcamedrawbacks of simulated annealing [15]. Unlikesimulated annealing, this algorithm can beimplemented over distributed computer and localmemory. Sequential Algorithms will not be suitable forlocal memory, message passing, distributed models ofcomputation There are many simple avenues toparallelize a sequential genetic algorithm (assuming aglobalshared memory), e.g., selecting and crossing overpairs of solutions in parallel, and mutating solutionsinparallel.algorithm is based on island-based model as shown byfig.3. From fig.3, it can be stated that Island can betermed as a group of sub-population out of which bestindividual is selected via Sequential Genetic Algorithmand passed on to migration scheme.IJEConsider R1, R2 and R3 to be randomly selectedinstances with 25 modules. Area of these modules isselected from a random uniform distribution {1, 20}.R1 and R2 have Upper bound (ui)equal to 3 and for R3,(ui) is selected from uniform distribution over {1, 4}.All three modules are with flexible settings that islower bound (li) and upper bound (ui) are governed byequation (ii).li (ui)-1SequentialGASubPopulationMigration.Equation (ii).Results obtained are as follows: for R1, the averagescore obtained by GAPE is 2964.6 and that by SA is3144.3. Similarly GAPE average scores for R2 and R3are 3452.2 and 3063.7 respectively. On the other hand,SA produced average results for R2 and R3 as 3652.0and 3186.9 respectively. The results clearly infers tosuperiority of GAPE over simulated annealing mMigration PolicyMigrantsFig. 3 Model of Parallel GAforPerformance of Parallel GA on various bench marksare tabulated as per following.Parallel Genetic Algorithms are capable of deliveringbetter results than Sequential Algorithms, even thoughresources used by both of them for computation aresame. The paper “A Parallel Genetic Algorithm forFloorplan Area Optimization” [5] presents a GeneticAlgorithm modified from Sequential Algorithm. Thewww.ijert.org4
International Journal of Engineering Research & Technology (IJERT)ISSN: 2278-0181Vol. 1 Issue 8, October - 2012MigrationInterval1 generation5 generations10 generations15 3740.009260.004440.00760Table1. Statistics for empirical results on bench mark(2 islands)MigrationInterval1 generation5 generations10 generations15 4580.005890.008260.00633Table2. Statistics for empirical results on bench mark(4 7490.013140.01083Table3. Statistics for empirical results on bench mark(8 islands)Best0.93934Mean0.9262024.4 Genetic Algorithm for VLSI DesignAutomationIn „A Genetic Algorithm for VLSI Design Automation‟[23], Schnecke et al. present an algorithm which aimson arriving at a simultaneous optimum solution for bothplacement of modules and routes for interconnectionnets during layout generation. The input is a set ofmodules – fixed and flexible, a binary tree is used tocharacterize the placement of these modules. Due toproblem specific genotype encoding as a binary tree, itis possible to compute the detailed routing at the timeof module placement. The algorithm proposes twomutation operators- one which change the partiallayouts and the other which changes the structure of thebinary tree. A suggestion to implement a new type ofrecombination operator is made which can replace theexisting crossover operators and operate on a pool offitter individuals. The thesis stresses on using new andproblem specific genetic operators in order to arrive atthe global optima.RTBestIJEMigrationInterval1 generation5 generations10 generations15 generationsChromosome encoding presented in this paper is basedon Sequence Pair [28]. Mutation and local searchoperators are based on four basic perturbations viz.swap, reflection/rotation, insertion and reversal.Moreover, authors have proposed three new crossoveroperators. Fitness function is defined as the „area of thesmallest rectangle enclosing the floorplan‟. HybridGenetic Algorithms vouch quality of solutions. On thecontrary, they take more time for computation assystem complexity increases.Standard Deviation0.07786Table4. Statistics for empirical results for sequentialGA on the benchmark5. Conclusion and Future ScopeParallel GA is apt for clusters of computationalstructures or multi-computers of distributed memory.Toachieve best possible performance, however, number ofislands and migration interval must be ensured to be indirect relation. Migration web service is used bysequential GA to send its best individual to and receivebest individual from the parallel GA web service.4.3 Hybrid Genetic AlgorithmIf local search operators are incorporated with GeneticAlgorithm, it ameliorates searching capability of hybridalgorithm so obtained. Local Search algorithm searchesfor solution in small areas while Global Searchalgorithm scans larger areas for the same. Similarapproach is proposed in “A Hybrid Genetic Algorithmfor the Floorplan Optimization Problem” [6].www.ijert.orgCombining the merits of various Genetic Algorithms, itis possible to achieve highly optimum solution whichcan resolve conflicting parameters simultaneously,leading to circuit designs that would be far better thanthose available today. There has been a trade-offbetween achieving optimized area and runtime of analgorithm. Implementing these algorithms collectivelywill give a better chance to resolve this trade off.Distributed Genetic Algorithm provides the GAPEmethod which proves its efficacy over simulatedannealing, Hybrid algorithm can efficiently optimizethe floorplan design due to its local search operator. Onthe similar lines, Parallel Genetic Algorithms areproven for faster computation having advantages overSequential Algorithms. Thus in future, we can combinethese stellar advantages of these individual algorithmsand implement a Genetic Algorithm which will take5
International Journal of Engineering Research & Technology (IJERT)ISSN: 2278-0181Vol. 1 Issue 8, October - 2012care of resolving these parameters simultaneously. Thiswill enable us to implement area optimized designsalong with shorter run time of an algorithm and higherefficiency. The work presented in this paper provides acompendium of advantages of these algorithms.Collective implementation and investigation of novelGenetic Algorithms will be a promising prospect forobtaining optimized solutions for complexfloorplanning problems.6. ReferencesIJERT[1] Neil H.E Weste and Kamran Eshraghian, Principles ofCMOS VLSI Design, Pearson Education, Delhi, 2005.[2] Srilata Raman, L.M. Patnail, “Performance Driven MCMPartitioning through an Adaptive Genetic Algorithm”,IEEETRANSACTIONS ON VERY LARGE SCALEINTEGRATION (VLSI) SYSTEMS, VOL. 4, NO. 4,DECEMBER 1996[3] D. F. Wong and C. L. Liu, “Floorplan Design of VLSIcircuits”, Algorithmica, Springer, New York, 1989.[4] James P. Cohoon, Shailesh U. Hegde,Worthy N. Martinand Dana S. Richards, “Distributed Genetic Algorithms forthe Floorplan Design Problem”, IEEE transactions oncomputer-aided design, VOL IO, NO. 4. APRIL 1991.[5]Maolin Tang and Raymond Y. K. Lau, “A Parallel GeneticAlgorithm for Floorplan Area Optimization”, SeventhInternational Conference on Intelligent Systems D
Fig.1 VLSI Design Flow Fig. 1 describes the design flow in VLSI. Based on user specification and system constraints, a logical design is created. Once the design is synthesized and simulated with the help of Computer Aided Design (CAD) tools, we proceed todesigning the system at the transistor level.
VLSI IC would imply digital VLSI ICs only and whenever we want to discuss about analog or mixed signal ICs it will be mentioned explicitly. Also, in this course the terms ICs and chips would mean VLSI ICs and chips. This course is concerned with algorithms required to automate the three steps “DESIGN-VERIFICATION-TEST” for Digital VLSI ICs.
Memetic Algorithms. The approach combines a hierarchical design technique, Genetic Algorithms, constructive techniques and advanced local search to solve VLSI circuit layout in the form of circuit partitioning and placement. Results obtained indicate that Memetic Algorithms based on local search, clustering and good initial solutions im-
VLSI Design 2 Very-large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining thousands of transistors into a single chip. VLSI began in the 1970s when complex semiconductor and communication technologies were being developed. The microprocessor is a VLSI device.
VL2114 RF VLSI Design 3 0 0 3 VL2115 High Speed VLSI 3 0 0 3 VL2116 Magneto-electronics 3 0 0 3 VL2117 VLSI interconnects and its design techniques 3 0 0 3 VL2118 Digital HDL Design and Verification 3 0 0 3 VL2119* Computational Aspects of VLSI 3 0 0 3 VL2120* Computational Intelligence 3 0 0 3
Dr. Ahmed H. Madian-VLSI 3 What is VLSI? VLSI stands for (Very Large Scale Integrated circuits) Craver Mead of Caltech pioneered the filed of VLSI in the 1970’s. Digital electronic integrated circuits could be viewed as a set
genetic algorithms, namely, representation, genetic operators, fitness evaluation, and selection. We discuss several advanced genetic algorithms that have proved to be efficient in solving difficult design problems. We then give an overview of applications of genetic algorithms to different domains of engineering design.
Metaheuristic Algorithms Genetic Algorithms: A Tutorial “Genetic Algorithms are good at taking large, potentially huge search spaces and navigating them, looking for optimal combinations of things, solutions you might not otherwise find in a lifetime.” - Salvatore Mangano Computer Design, May 1995 Genetic Algorithms: A Tutorial
A. Anatomi Tulang Belakang 1. Anatomi Tulang Kolumna vertebralis atau yang biasa disebut sebagai tulang belakang merupakan susunan dari tulang-tulang yang disebut dengan vertebrae. Pada awal perkembangan manusia, vertebrae berjumlah 33 namun beberapa vertebrae pada regio sacral dan coccygeal menyatu sehingga hanya terdapat 26 vertebrae pada manusia dewasa. 26 vertebrae tersebut tersebar .
