The Genetic Placement Algorithm: Genie
Genie: The Genetic Placement Algorithm
Genie is one of the first genetically dependent placement algorithms for the assignment of modules to chip locations. To formulate its solutions from the solution space, the algorithm uses a directed-evolution methodology. The following is the pseudocode:
- Initial population construction
Two proposed methods for generating the initial population. The first is to construct the population randomly, the second is to use a greedy clustering technique to place the cells. Genie uses the conventional wire length function based on the bounding rectangle. It does not account for cell overlap or row lengths, owing to the gate array layout style.
2. Parent choice function
The parent choice function chooses the parent pairs. Four alternatives were considered here. Pair a random string with the fittest string, choose both parents randomly and select parents stochastically, where the probability of each individual being selected as parent is proportional to its fitness, but allows only individuals with above average fitness to reproduce. Here, parents are chosen randomly, there is little improvement after several generations and hence no convergence to a good placement.
3. Crossover operator
The parents’ offspring are generated by the crossover operator. There have been two crossover operators mentioned. The first picks a random module es and moves its four nearest neighbors in parent 1 into neighboring slots in parent 2 with the least amount of disruption to the other modules.
4. Selection function
Configurations can persist into the next generation is determined by the selection function. Select the best string and p -1 random strings for survival into the next generation, where p is the population size; select p random strings; select strings stochastically, with the probability of selection proportional to fitness The outcomes are identical to those obtained with the parent choice function.
5. Mutation function
To reduce the placement cost, you can either perform a series of random interchanges or use a greedy technique. The greedy operator selects a module e on a net Z and looks for a module et on the same net that is the furthest away from es. The displaced modules are then moved one position at a time before a vacant location is identified by bringing et close to es. As a result, the perimeter of net Z’s bounding rectangle is diminished while the remainder of the placement is minimally disturbed.
