| The main research object of this article is the layout problem of very large scale integrated circuit（VLSI）.This problem is a key part of chip design and manufacturing,and it is proved to be a classical NP-hard combinatorial optimization problem,which not only has significant impact on performance indicators such as wire network routability,chip reliability,power consumption,and delay,etc.At the same time,VLSI layout is an indispensable link to break through the Electronic Design Automatic（EDA）software,and it is also the only way for the localization of EDA software in my country.Therefore,the study of VLSI layout has very important theoretical research value and practical engineering significance.In this thesis,the VLSI layout problem is transformed into the least cost network flow problem by problem transformation.In polynomial time,a layout scheme aiming at the minimum sum of connections in a given position diagram is obtained,and the neighborhood operator is designed according to the weight of layout circuit modules to improve the quality of the layout scheme.Firstly,a highly efficient decoding algorithm（PRGED）based on position diagram is proposed by transforming the problem "sequence pair （?） position relation graph （?）mathematical model （?）minimum cost flow problem" to obtain a layout scheme with the goal of minimizing the sum of lines under a given position diagram.The algorithm is mainly divided into three parts: first,for a given sequence pair,through analysis,the positional relationship diagram between any two layout circuit modules is obtained.Then,an integer programming model of the VLSI layout problem with the goal of minimizing the connection is established under this positional relationship graph,and the original problem is converted into a dual problem through dual transformation,which is exactly a minimum cost network flow problem.Finally,by constructing the network graph,the minimum cost flow algorithm is used to obtain the layout scheme with the goal of minimizing the sum of the connections under the given position graph in polynomial time.Secondly,in order to improve the quality of layout scheme,a weighted VLSI layout algorithm（SAVLSIL）is proposed based on PRGED algorithm,simulated annealing algorithm,initial sequence pair construction,and probabilistic selection of modules to change the neighborhood operator according to the weight of layout circuit modules.The algorithm first defines the weight of the layout circuit module according to the number and area of the pin,and generates the initial sequence pair and the initial solution according to the initial layout.Then,according to the weight of the layout circuit module,the neighborhood operator is changed to obtain the new position diagram and the new layout scheme.Finally,the new layout scheme is evaluated: unconditionally accept the better layout scheme,accept the probability of the worse layout scheme.MCNC and GSRC two classical layout test sets were used to test the proposed algorithm.After comparing with the layout algorithm that achieves the best solution in the current literature,it is found that the proposed algorithm can solve a better solution and can well meet the different requirements in different application scenarios. |
