A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints  

作　　者：De-xuan ZOU Gai-ge WANG Gai PAN Hong-wei QI 

机构地区：[1]School of Electrical Engineering and Automation, Jiangsu Normal University [2]School of Computer Science and Technology, Jiangsu Normal University

出　　处：《Frontiers of Information Technology & Electronic Engineering》2016年第11期1228-1244,共17页信息与电子工程前沿（英文版）

基　　金：supported by the National Natural Science Foundation of China(Nos.61403174 and 61503165);the Natural Science Foundation of the Jiangsu Higher Education Institutions of China(No.14KJB 520011);the Jiangsu Provincial Science Foundation for Youths(No.BK20150239)

摘　　要：Outline-free floorplanning focuses on area and wirelength reductions, which are usually meaningless, since they can hardly satisfy modern design requirements. We concentrate on a more difficult and useful issue, fixed-outline floorplanning. This issue imposes fixed-outline constraints on the outline-free floorplanning, making the physical design more interesting and challenging. The contributions of this paper are primarily twofold. First, a modified simulated annealing(MSA) algorithm is proposed. In the beginning of the evolutionary process, a new attenuation formula is used to decrease the temperature slowly, to enhance MSA's global searching capacity. After a period of time, the traditional attenuation formula is employed to decrease the temperature rapidly, to maintain MSA's local searching capacity. Second, an excessive area model is designed to guide MSA to find feasible solutions readily. This can save much time for refining feasible solutions. Additionally, B*-tree representation is known as a very useful method for characterizing floorplanning. Therefore, it is employed to perform a perturbing operation for MSA. Finally, six groups of benchmark instances with different dead spaces and aspect ratios—circuits n10, n30, n50, n100, n200, and n300—are chosen to demonstrate the efficiency of our proposed method on fixed-outline floorplanning. Compared to several existing methods, the proposed method is more efficient in obtaining desirable objective function values associated with the chip area, wirelength, and fixed-outline constraints.Outline-free floorplanning focuses on area and wirelength reductions, which are usually meaningless, since they can hardly satisfy modern design requirements. We concentrate on a more difficult and useful issue, fixed-outline floorplanning. This issue imposes fixed-outline constraints on the outline-free floorplanning, making the physical design more interesting and challenging. The contributions of this paper are primarily twofold. First, a modified simulated annealing（MSA） algorithm is proposed. In the beginning of the evolutionary process, a new attenuation formula is used to decrease the temperature slowly, to enhance MSA＇s global searching capacity. After a period of time, the traditional attenuation formula is employed to decrease the temperature rapidly, to maintain MSA＇s local searching capacity. Second, an excessive area model is designed to guide MSA to find feasible solutions readily. This can save much time for refining feasible solutions. Additionally, B＊-tree representation is known as a very useful method for characterizing floorplanning. Therefore, it is employed to perform a perturbing operation for MSA. Finally, six groups of benchmark instances with different dead spaces and aspect ratios—circuits n10, n30, n50, n100, n200, and n300—are chosen to demonstrate the efficiency of our proposed method on fixed-outline floorplanning. Compared to several existing methods, the proposed method is more efficient in obtaining desirable objective function values associated with the chip area, wirelength, and fixed-outline constraints.

关 键 词：Fixed-outline floorplanning Modified simulated annealing algorithm Global search Excessive area model B＊-tree representation 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]