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)