The week's pick
Reseach Article
Parallel Simulated Annealing Algorithm for Standard Cell Placement in VLSI Design
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 87 - Number 1 |
| Year of Publication: 2014 |
| Authors: Aaquil Bunglowala, Manisha Jain |
10.5120/15172-3047
|
Aaquil Bunglowala, Manisha Jain . Parallel Simulated Annealing Algorithm for Standard Cell Placement in VLSI Design. International Journal of Computer Applications. 87, 1 ( February 2014), 23-26. DOI=10.5120/15172-3047
Abstract
Simulated Annealing (SA) is a stochastic based heuristic optimization technique based on physical process of metal crystallization. Optimization of Non-Deterministic polynomial hard (NP-hard) problems of non-trivial sizes is done using heuristic approach. Until now, simulated annealing (SA), genetic algorithm (GA) and Hopfield neural network (HNN) were individually used for solving the standard cell placement (SCP) problem. Simulated annealing established as a powerful SCP optimization tool, its drawback has always been its appetite for computational resources. In light of this, we are interested in the application of these parallel simulated annealing algorithms with respect to standard cell placement. Several generalized algorithms proposed for parallelizing simulated annealing, only a few have been applied to cell placement. Parallel moves has been the most popular strategy and in this paper we present a new implementation of this approach.
References
- Kirkpatrick, S. , Gelatt, C. D. , & Vecchi, M. P. 1989. Optimization by Simulated Annealing. Science 220, 671-680.
- Metropolis, N. , Rosenbluth, A. W. , Rosenbluth, M. N. , Teller, A. H. , Teller, E. 1953. Equation of State Calculation by Fast Computing Machines. J. of Chem. Phys. , 21, 1087-1091.
- Khushro, Shahookar, Pinaki, Mazumder 1990. A Genetic Algorithm for Standard cell Placement", Proceedings of EURO-DAC, 660-664.
- Banerjee, M. , Jones, H. & Sargent, J. S. 1990. Parallel Simulated annealing algorithms for standard cell placement on hypercube multiprocessors. IEEE Transaction on Parallel and Distributed Systems.
- Durand, M. D. 1989. Accuracy vs. speed in placement. IEEE Design & Test of Computer. 8-34.
- Kravitz, S. A. , & Rutenbar, R. A. 1987). Placement by simulated annealing on a Multiprocessor. IEEE Transaction on Computer-Aided Design 6.
- Rose, J. S. , Snelgrove, W. M. , & Vranesic, Z. G. 1988. Parallel standard cell placement algorithms with quality equivalent to si. mulated annealing. IEEE Transactions on Computer- Aided Design 7.
- Rutenbar, R. A. 1989. Simulated Annealing Algorithms, An Overview. IEEE Circuits and Devices Magazine, 5, No. 1, 19-26.
- Bunglowala, A. , & Singhi, B. M. Memetic Algorithms as a Solution to combinatorial Optimization Problem. Proceedings of 2nd PIMR International Conference.
- Bunglowala, A. , Singhi, B. M. 2008. Performance Evaluation And Comparison and Improvement of standard Cell placement in VLSI Design. International Conference on Emerging Trends in Engineering and Technology.
- Bunglowala, A. , & Singhi, B. M. 2008. A solution to Combinatorial Optimization Problem using Memetic Algorithm. International Journal of Computer System Application.
- Hajek, B. 1988. Cooling Schedules for Optimal Annealing. Mathematics of Operations Research, 13, No. 2, 311-329.
- Beumont, O. , Legrand, A. and Robert, Y. 2003. Optimal algorithms for scheduling divisible workloads on heterogeneous systems. Processing Symposium.
- Mitra, D. , Romeo, F. , and Sangiovanni-Vincentelli, A. 1986. Convergence and Finite Time Behavior of Simulated Annealing. Advances in Applied Probability, 18, 747-771.
Index Terms
Keywords