Search

Search Results

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

  O.B. Lebedev, А.А. Zhiglatiy, Е.О. Lebedevа

  2021-12-24

  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.