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.