Journal of VLSI Design Tools and Technology
A Cuckoo Search based Approach for Solving Standard Cell Placement Problem
Abstract
The standard cell placement (SCP) is an NP complete problem in VLSI layout which focuses on placing the cells at appropriate locations so as to minimize the resultant wirelength. The standard cell placement is one of the significant phases in VLSI circuit design. Many heuristic approaches have been developed in literature to solve this problem. The paper presents an efficient nature-inspired meta-heuristic algorithm for solving the standard cell placement problem based on cuckoo’s behavior. The performance of the proposed algorithm is tested against set of MCNC benchmarks circuits. The experimental results showed promising results of the proposed algorithm in comparison to the existing meta-genetic approach. Keywords: Cuckoo search, standard cells, VLSI, meta-heuristics, evolutionary algorithmsReferences (17)
- Sait SM, Youssef H. VLSI Physical Design Automation: Theory and Practice , McGraw-Hill, 1995.
- Banerjee P, Jones M. A Parallel Simulated Annealing for Standard Cell Placement on a Hypercube Computer. In Proceedings of the International Conference of Computer- Aided Design; 1986; 34–37p.
- Jones M, Banerjee P. Performance of a Parallel Algorithm for Standard Cell Placement on the Intel hypercube. In Proceedings of the 24th Conference of Design Automation; 1987; 807–813p.
- Grover LK. A New Simulated Anne aling Algorithm for Standard Cell Placement. In Proceedings of the International Conference on Computer -Aided Design ; Nov. 1986; 378–380p.
- Lin YL, Hsu YC, Tsai FS. SILK A Simulated Evolution Router. IEEE T . Comput. Aid. D. October 1989; 1108– 1114p.
- Cohoon J, Paris W. Genetic Placement. IEEE T . Comput. Aid. D. 1987; 6: 956– 964p.
- Louis S, Rawlins G. Using Genetic Algorithms to Design Structures . Technical Report . Indiana University, Bloomington; IN 47405; 1991.
- Vemuri RM, Vemuri RR. Geneticsynthesis: Performance-Driven logic Synthesis using Genetic Evolution . In Proceedings, First Great Lakes Symposium on VLSI ; Kalamazoo, MI, 1990; 312–317p.
- Shahookar K, Mazumdar P. A Genetic Approach to Standard Cell Placement Using Meta -Genetic Parameter Optimization. IEEE T . Comput. Aid. D. 1990; 9: 500–511p.
- Goldberg DE. Genetic Algorithms in Search, Optimization, and Machine Learning. Vol. 412. Reading Menlo Park: Addison-Wesley; 1989.
- Cohoon JP, Paris WD. Genetic Placement. Proceedings of IEEE International Conference on Computer Aided Design ; Santa Clara 1986; 422–425p.
- Bunglowala A, Singhi BM. Performance Evaluation and Comparison and Improvement of Standard Cell Placement Techniques in VLSI Design. In First International Conference on Emerging Trends in En gineering and Technology ; ICETET'08; IEEE, 2008; 468–473p.
- Minhas MR. An Evolutionary Algorithm for Low Power VLSI Cell Placement . In IEEE 46th Midwest Symposium on Circuits and Systems ; 2003; 3: 1540– 1543p.
- Najwa A, Menai M. Artificial Bee Colony for the Standard Cell Placement Problem . Int. J. Metaheuristics 2013; 2: 234–255p.
- Yang XS. Nature -inspired Metaheuristic Algorithm. Luniver Press, 2008.
- Yang X.S, Deb S. Cuckoo Search via L vy lights . In Proceedings of World Congress on Nature and Biolo gically Inspired Computing ; 2009 Dec; Piscataway, NJ, USA: IEEE Press; 2009; 210–214p.
- Yang XS, Deb S. Engineering Optimisation by Cuckoo Search . Int. J. Math. Model. Num. Optimis. 2010; 1(4): 330–343p.