Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2016, Vol. 17 Issue (11): 1228-1244    DOI: 10.1631/FITEE.1500386
    
基于修正模拟退火算法及溢出面积模型的固定边界布图规划
De-xuan Zou, Gai-ge Wang, Gai Pan, Hong-wei Qi
School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China; School of Computer Science and Technology, Jiangsu Normal University, Xuzhou 221116, China
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
School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China; School of Computer Science and Technology, Jiangsu Normal University, Xuzhou 221116, China
 全文: PDF 
摘要： 概要：无边界布图规划研究面积及线长减少问题很难满足现代设计需求，因此通常被认为是无意义的。我们关注一种难度更大且更有意义的问题--固定边界布图规划。该问题将固定边界约束条件加入无边界布图规划中，使其在实体设计中更有趣、更具挑战性。本文的工作主要分为两部分。第一，提出了一种修正模拟退火算法（Modified simulated annealing algorithm, MSA）。在进化过程初期，用一种新的衰减方程来缓慢减小温度，以增强MSA的全局搜索能力。然后，用传统衰减方程来快速减小温度，以维持MSA的局部搜索能力。第二，设计了一种溢出面积模型来引导MSA寻找可行解，为精炼可行解节省了大量时间。另外，B*-tree是一种有效的布图规划表示法，它被用来执行MSA的扰动操作。最后，以六组带有不同空置率及高宽比的benchmark为例，证实本文所提方法在解决固定边界布图规划问题上的效率，这些问题包括电路n10，n30，n50，n100，n200和n300。与几种现有方法相比，本方法能够更有效地获得令人满意的目标函数值，它们与芯片面积、线长和固定边界约束有关。
关键词： 固定边界布图规划;  修正的模拟退火算法;  全局搜索;  溢出面积模型;  B*-tree表示法    
Abstract: 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.
Key words: Fixed-outline floorplanning    Modified simulated annealing algorithm    Global search    Excessive area model    B*-tree representation
收稿日期: 2015-11-07 出版日期: 2016-11-07
CLC:  TN4  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
De-xuan Zou
Gai-ge Wang
Gai Pan
Hong-wei Qi

引用本文:

De-xuan Zou, Gai-ge Wang, Gai Pan, Hong-wei Qi. A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints. Front. Inform. Technol. Electron. Eng., 2016, 17(11): 1228-1244.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/FITEE.1500386    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2016/V17/I11/1228

[1] Sepehr Tabrizchi, Nooshin Azimi, Keivan Navi. 基于碳纳米管场效应管的新型三元半加器及乘法器[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 423-433.
[2] Zamshed Iqbal Chowdhury, Md. Istiaque Rahaman, M. Shamim Kaiser. 千兆赫片上互联单壁纳米碳管电分析[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 262-271.
[3] Liang Geng, Ji-Zhong Shen, Cong-Yuan Xu . 采用内嵌时钟控制技术的低功耗双边沿隐形脉冲触发器[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(9): 962-972.
[4] Wei Zhang, You-de Hu, Li-rong Zheng. 基于驻波振荡器的PLL设计与仿真[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(3): 258-264.
[5] Mao-qun Yao, Kai Yang, Cong-yuan Xu, Ji-zhong Shen. 基于RTD三变量通用逻辑门的设计[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(8): 694-699.
[6] Shou-biao Tan, Wen-juan Lu, Chun-yu Peng, Zheng-ping Li, You-wu Tao, Jun-ning Chen. 用于低电压下SRAM灵敏放大器工艺变化鲁棒性时序的多级双复制位线延迟技术[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(8): 700-706.
[7] Ming-jun Ma, Zhong-he Jin, Hui-jie Zhu. 一种联合调制反馈和温度补偿改善闭环MEMS电容式加速度计漂移的方法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(6): 497-510.
[8] Kai Huang, Xiao-xu Zhang, Si-wen Xiu, Dan-dan Zheng, Min Yu, De Ma, Kai Huang, Gang Chen, Xiao-lang Yan. 面向多媒体特定应用的剖析和标注相结合MPSoC性能评估方法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(2): 135-151.
[9] Najam Muhammad Amin, Zhi-gong Wang, Zhi-qun Li. 基于65 nm CMOS工艺且应用于60 GHz接收机的折叠下变频混频器[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(12): 1190-1199.
[10] Xiao-hua Li, Ji-zhong Shen. 或-符合代数系统中的对称变量检测算法[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(12): 1174-1182.
[11] Hüseyin Oktay Erkol, Hüseyin Demirel. 多自由度系统运动学方程求解的VHDL应用[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(12): 1164-1173.
[12] Fa-en Liu, Zhi-gong Wang, Zhi-qun Li, Qin Li, Lu Tang, Ge-liang Yang. 基于90 nm CMOS工艺的31–45.5 GHz注入式锁定分频器[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(12): 1183-1189.
[13] Ting Guo, Zhi-qun Li, Qin Li, Zhi-gong Wang. 应用于硅基毫米波锁相环频率综合器的37GHz宽带可编程模分频器[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(12): 1200-1210.
[14] Qian-qi Le, Guo-wu Yang, William N. N. Hung, Xiao-yu Song, Fu-you Fan. 性能驱动的可靠片上网络分配和映射[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(11): 1009-1020.
[15] Kai-sheng Luo, Zheng Shi, Xiao-lang Yan, Zhen Geng. 基于支持向量机的反向光刻版图重定向算法[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(5): 390-400.