Title :
Modified SA algorithm for wirelength minimization in VLSI circuits
Author :
Laudis, Lalin L. ; Anand, S. ; Sinha, Amit Kumar
Abstract :
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.
Keywords :
VLSI; computational complexity; genetic algorithms; integrated circuit interconnections; minimisation; probability; simulated annealing; MOO; NP hard optimization problem; SAA; SOO; VLSI circuits; bio-inspired algorithms; dead space; evolutionary algorithms; genetic algorithms; memetic algorithms; multiobjective optimization problems; nondeterministic optimization problem; probabilistic methods; simulated annealing algorithm; single objective optimization; stochastic methods; wirelength minimization; Algorithm design and analysis; Annealing; Benchmark testing; Cooling; Minimization; Simulated annealing; Very large scale integration; Simulated Annealing; VLSI problems; Wirelength minimization;
Conference_Titel :
Circuit, Power and Computing Technologies (ICCPCT), 2015 International Conference on
Conference_Location :
Nagercoil
DOI :
10.1109/ICCPCT.2015.7159500