VLSI Cell Placement Techniques
Placement By Genetic Algorithm- Introduction
Genetic algorithm-based optimization is applied to the VLSI hardware design domain at various design levels:
1. VLSI ASIC Design: A multi-objective genetic floor planner has been developed for simultaneous optimization of area and wirelength in VLSI ASICs (layouts).
2. FPGA based Hardware Applications: A customizable general purpose GA IP core has been developed for FPGA based applications that need a stochastic optimization engine. ·
3. Extreme Environment Electronics: A genetic algorithm-based VLSI ASIC has been developed to evolve analog circuits, monitor their performance in extreme environments, and compensate any performance degradation.
Genetic Algorithms
Genetic algorithms operate on strings of data in which each string represents a solution, in a way resembles the workings of natural evolution. Historically, it preceded simulated annealing , but it has only recently been widely applied for solving problems in diverse fields, including VLSI placement .By defining a population, these algorithms maintain a number of solutions which it will operate upon in the future. The technique to generate new solutions is to choose parents from the population that would then pass their attributes to its offspring. This process is called the crossover. After the crossover, a new population must be generated using the old population and the new offspring. Another process with happens after this is known as the mutation process. Mutation processes happen to produce new genetic variation, so that diversity is maintained. The algorithm continues iteratively usually until no improvements are detected for a long time. The significance of the operators like crossover, mutation, inversion and selection can be explained :
Crossover
It is the main genetic operator. It operator generates an offspring by combining schemata from both parents. The simplest way to achieve crossover would be to choose a random cut point and generate the offspring by combining the segment of one parent to the left of the cut point with the segment of the other parent to the right of the cut point. This method works well with the bit string representation. The below Figure 1 shows the example of crossover.
Mutation
Mutation is a background operator and produces some random incremental changes in offspring that was generated by crossover. The mechanism most commonly used is pairwise interchange as shown in Figure 2. In genetic algorithms, mutation serves the crucial role of replacing the genes lost from the population during the selection process. And in terms of the placement problem, a gene consisting of an ordered triple of a cell and its associated ideal coordinates may not be present in any of the individuals in the population.
Inversion
The inversion operator takes a random segment in a solution string and inverts it end for end. This operation is performed in such a way that it does not modify the solution represented by the string but only modifies the representation of the solution. So the interpretation of the symbol remains unchanged as when the symbol is moved in an array, the serial number of it is also moved. In the cell placement problem, the x- and y-coordinates stored with each cell perform this function. Thus, no matter where the cell coordinate triple is located in the population array, it will have the same interpretation in terms of the physical layout.
Selection.
A selection procedure in order to choose the next generation from the combined set of parent and offspring. There is a lot of diversity in the selection functions used by various researchers. The three most commonly used selection methods are competitive, random, and stochastic.
The genetic algorithm is a new and powerful technique. This method depends for its success on the proper choice of the various parameters and functions that control processes like mutation,selection, and crossover. If the functions are selected properly, a good placement will be obtained. The major problem in formulating a genetic algorithm for module placement is to choose the functions most suitable for a problem. A great deal of research is currently being conducted on it.
