Modified SA algorithm for wirelength minimization in VLSI circuits

摘要

In modern VLSI circuits, number of parameters viz, placement of components, dead space (un occupied space in the layout), wire length has to be minimized. The defined problems are non deterministic and NP hard optimization problem. Hence probabilistic (stochastic) methods are adopted to solve these problems. The minimization problems are multi objective optimization problems (MOO). Hence, for the convenience of computation, these MOO problems are converted into Single objective optimization (SOO) problems. It is observed from the previous research works that the bio-inspired algorithms have worked very well in the minimizing process. Evolutionary Algorithms, Genetic Algorithms, Memetic Algorithms were notable in solving the non deterministic hard problems. Moreover, Simulated annealing algorithm developed by Kirpatrick et.al, proved itself to be worthy in the minimization process. The major aim of this research work is to modify or customize the Simulated Annealing Algorithm (SAA) based on the user defined values and test it with various bench marks. This research work may be used to minimize the wire length between the blocks in complex VLSI problems. The capability of the proposed algorithm may be more efficient because of the mechanism of reducing the uphill moves made during the initial stage of the algorithm, extended search at each temperature and the improved neighborhood procedure.