DEVELOPMENT OF MODIFIED METHODS AND MODELS OF SEARCH ADAPTATION FOR SOLVING THE PROBLEM OF PLANNING VLSI

Abstract

In this work, to solve the VLSI planning problem, a search algorithm has been developed
based on a modified ant colony method. The task of forming a VLSI plan is reduced to the task of
forming the corresponding Polish expression. The developed method for the synthesis of the Polish
expression includes the construction of a tree of cuts, the choice of the types of cuts (H or V), identification
and orientation of modules. The evolving population is split into pairs of agents. Each
member of the population is a pair of agents working together. In this case, the constructive algorithms
A1 and A2 used by the agents of the pair are different. The problem solved by Algorithm A1
is formulated as the problem of finding a one-to-one mapping Fk=M*→P of the set of modules M
with selected orientations, |M*|=|M| to the set P of positions of the template Sh. In fact, the solution
consists in choosing on the graph G1 a subset of edges E*1E1 included in the corresponding
mapping Fk. In Algorithm A2, the graph G2=(X, E2) is developed as a model of the search space
for solutions for choosing the type, sequence and location of cuts in the pattern Sh.
X={(x1i,x2i)|i=1,2,…,n} the set of vertices of the graph G2, corresponds to the set P of potential
positions of the template Sh for the possible placement of the names of the cut symbols in them.
Each potential position piP of the template Sh is modeled by two alternative vertices (x1i,x2i).
The choice of the vertex x1i when placing the cuts indicates that a cut of type V is placed in position
pi, the choice of vertex x2i indicates that a cut of type H is placed in position pi. Each iteration
l of the general algorithm includes an initial and three main stages. The initial stage is as follows.
Co-evolutionary memory matrices are nullified CEM*1 and CEM*2 are reset to zero. At the first
stage, each pair of agents dk=(a1k,a2k): – with constructive algorithms A1 and A2 he synthesizes
his solution Wk=(E1k
*,Sk); – the Polish expression Shk is formed, corresponding to the solution Wk;
– on the basis of Shk, a tree of sections Tk is formed; – on the basis of Tk, the plan Rk is formed and
the estimate of the solution Fk is calculated; – agents deposit (add) the pheromone to the cells of
the collective evolutionary memory (CEM) matrices CEM*1 and CEM*2 corresponding to the
solution edges Wk=(E1k
*,Sk) in the solution search graphs G1 and G2 in an amount proportional
to the solution estimate Fk. At the second stage, the pheromone accumulated in CEM*1 and
CEM*2 by agents of the population at iteration l is added to CEM 1 and CEM2. At the third stage,the pheromone is evaporated on the edges of the graphs G1 and G2. Tests have confirmed the
effectiveness of the proposed method. The time complexity of the algorithm, obtained experimentally,
coincides with theoretical studies and it is O(n2) for the considered test problems.