Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin990820742.pdf (6.3 MB)

ETD Abstract Container

Abstract Header

QUANTITATIVE ANALYSIS OF TABU SEARCH ALGORITHM FOR A VLSI PLACEMENT APPLICATION

SHARMA, VIKAS
http://rave.ohiolink.edu/etdc/view?acc_num=ucin990820742

Abstract Details

2001, MS, University of Cincinnati, Engineering : Computer Engineering.
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.
Dr. Karen C. Davis (Advisor)
88 p.
Tabu; tabu tenure; tenure; candidate list; Tabu Search; Wirelength; Algorithm

Recommended Citations

Citations

  • SHARMA, V. (2001). QUANTITATIVE ANALYSIS OF TABU SEARCH ALGORITHM FOR A VLSI PLACEMENT APPLICATION [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin990820742

    APA Style (7th edition)

  • SHARMA, VIKAS. QUANTITATIVE ANALYSIS OF TABU SEARCH ALGORITHM FOR A VLSI PLACEMENT APPLICATION. 2001. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin990820742.

    MLA Style (8th edition)

  • SHARMA, VIKAS. "QUANTITATIVE ANALYSIS OF TABU SEARCH ALGORITHM FOR A VLSI PLACEMENT APPLICATION." Master's thesis, University of Cincinnati, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=ucin990820742

    Chicago Manual of Style (17th edition)

ucin990820742
716
© 2001, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.