A Hybrid Simulated Annealing Algorithm for Nonslicing VLSI Floorplanning

作者：Chen, Jianli^*; Zhu, Wenxing; Ali, M. M.

来源：IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews , 2011, 41(4): 544-553.

DOI：10.1109/TSMCC.2010.2066560

• B*-tree
• bias search strategy
• local search
• simulated annealing
• very large scale integrated-circuit (VLSI) floorplanning

Floorplanning in very large scale integrated-circuit (VLSI) design is the first phase in the process of designing the physical layout of a chip. This makes the floorplanning problem of paramount importance, since it determines the performance, size, yield, and reliability of VLSI chips [1]. From the computational point of view, the VLSI floorplanning is an NP-hard problem. In this paper, we present a hybrid simulated annealing algorithm (HSA) for nonslicing VLSI floorplanning. The HSA uses a new greedy method to construct an initial B*-tree, a new operation on the B*-tree to explore the search space, and a novel bias search strategy to balance global exploration and local exploitation. Experimental results on Microelectronic Center of North Carolina (MCNC) benchmarks [29] show that the HSA can quickly produce optimal or nearly optimal solutions for all the tested problems.

• 出版日期2011-7
• 单位福州大学