SEARCH POPULATION ALGORITHM FOR VLSI ELEMENTS PLACEMENT

Abstract

The paper considers a population search algorithm for the placement of VLSI components.
By analogy with the process of the emergence and formation of crystals from matter, the process
of generating a solution by sequential manifestation and concretization of the solution based on an
integral placer of alternatives is called the method of crystallization of a placer of alternatives.
The solution Qk of the placement problem is represented as a bijective mapping Fk = A → P, each
element of the set A corresponds to one single element of the set P and vice versa. The
metaheuristic of crystallization of a placer of alternatives underlying the algorithm searches for
solutions taking into account collective evolutionary memory, which means information reflecting
the history of the search for a solution and the memory of the search procedure. A distinctive feature
of the metaheuristic used is that it takes into account the tendency to use alternatives from the
best found solutions. Compact data structures for storing solution interpretations and memory are
proposed. An algorithm associated with evolutionary memory seeks to memorize and reuse ways
to achieve better results. The developed algorithm belongs to the class of population. The iterative
process of finding solutions includes three stages. At the first stage of each iteration, the constructive
algorithm generates nq solutions Qk. The work of the constructive algorithm is based on the
indicators of the main integral placer of alternatives – the matrix R, which stores the integral indicators
of the solutions obtained at the previous iterations. The process of assigning an item to a
position involves two stages. In the first stage, the element is selected, and in the second stage, the
position pj. In this case, the restriction must be fulfilled: each element corresponds to one position
pj. The estimate ξk of the solution Qk and the estimate of the utility δk of the set of positions Pk selected
by the agents are calculated. The work uses a cyclical method of forming decisions.
In this case, the accumulation of estimates of the integral utility δk in the main integral placer of
alternatives R is performed after the complete formation of the set of solutions Q. At the second
stage of the iteration, the estimates of the integral utility δk are increased in the main integral
placer of alternatives − the matrix R. At the third stage of the iteration, the estimates of the utility
δk of the integral placer of alternatives R are reduced by a priori a given value δ*. The algorithm
ends after the specified number of iterations has been completed. Comparative analysis with other
solution algorithms was carried out on standard test examples (benchmarks) of the IBM corporation,
while the solutions synthesized by the CAF algorithm exceed the solution efficiency of the
known methods by an average of 6%. The time complexity of the algorithm is O(n2)-O(n3)