DocumentCode :
990574
Title :
A Memetic Algorithm for VLSI Floorplanning
Author :
Tang, Maolin ; Yao, Xin
Author_Institution :
Queensland Univ. of Technol., Brisbane, Qld.
Volume :
37
Issue :
1
fYear :
2007
Firstpage :
62
Lastpage :
69
Abstract :
Floorplanning is an important problem in very large scale integrated-circuit (VLSI) design automation as it determines the performance, size, yield, and reliability of VLSI chips. From the computational point of view, VLSI floorplanning is an NP-hard problem. In this paper, a memetic algorithm (MA) for a nonslicing and hard-module VLSI floorplanning problem is presented. This MA is a hybrid genetic algorithm that uses an effective genetic search method to explore the search space and an efficient local search method to exploit information in the search region. The exploration and exploitation are balanced by a novel bias search strategy. The MA has been implemented and tested on popular benchmark problems. Experimental results show that the MA can quickly produce optimal or nearly optimal solutions for all the tested benchmark problems
Keywords :
VLSI; circuit layout CAD; circuit optimisation; computational complexity; genetic algorithms; integrated circuit layout; search problems; NP-hard problem; VLSI floorplanning problem; design automation; hybrid genetic algorithm; local search method; memetic algorithm; optimal solution; very large scale integrated-circuit chip; Benchmark testing; Circuit testing; Design automation; Genetic algorithms; Integrated circuit interconnections; NP-hard problem; Search methods; Space exploration; Space technology; Very large scale integration; Floorplanning; genetic algorithm (GA); local search; memetic algorithm (MA); very large scale integrated circuit (VLSI); Algorithms; Artificial Intelligence; Biomimetics; Computer Simulation; Computer-Aided Design; Equipment Design; Equipment Failure Analysis; Models, Theoretical; Semiconductors; Software; Systems Theory;
fLanguage :
English
Journal_Title :
Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on
Publisher :
ieee
ISSN :
1083-4419
Type :
jour
DOI :
10.1109/TSMCB.2006.883268
Filename :
4067090
Link To Document :
بازگشت