Details

QUANTITATIVE ANALYSIS OF TABU SEARCH ALGORITHM FOR A VLSI PLACEMENT APPLICATION

by SHARMA, VIKAS

Abstract (Summary)
The abundance of difficult combinatorial optimization problems in practical settings such as telecommunications, financial planning and VLSI design automation has motivated the development of powerful optimization techniques. Simulated Annealing, Genetic algorithms, Network Flow and other heuristics have long been explored for solvingthese problems. During the recent years, miniaturization of the chip sizes and increasing densities of logic have posed a continuous design-related challenge to the VLSI design automation community. Promising results have been reported from the application of Tabu Search algorithm to VLSI circuit partitioning, floorplanning, placement and routing. Tabu Search leverages the ability to store solutions already visited and to make strategic solutions on the basis of the stored information for achieving optimal solutions. This thesis presents a quantitative analysis of the various parameters of Tabu Search. In particular, we look at the techniques of moving out of the current search space called diversification methodologies and strategies for determining the best solution in the current search space called intensification methodologies. This is achieved by applying a tabu tenure on the moves, thus forbidding execution of certain moves for some iterations. In addition, we generate a candidate list of moves for selecting moves for future executions. Our approach makes use of a Tabu Search-based Force Directed placement technique. We perform physical placements of VLSI circuits on a two-dimensional array. In the first step, the circuit cells are placed randomly and their respective tendencies to move in all the four directions are computed. This is followed by selection of the moves for swap on the basis of candidate list implementations. Intensification and diversification phases are repeated alternately. An optimized ratio of the number of iterations of intensification and diversification phases ensures good quality solutions with low processing time. We have demonstrated that our Tabu Search-based placement approach achieves a speed up ranging from 5 to 17 times over a similarly implemented Simulated Annealing-based placement algorithm, depending on the circuit size.
Bibliographical Information:

Advisor:

School:University of Cincinnati

School Location:USA - Ohio

Source Type:Master's Thesis

Keywords:

ISBN:

Date of Publication:01/01/2001

© 2009 OpenThesis.org. All Rights Reserved.