固定边框的多电压布图规划算法

doi:10.3969/j.issn.0372-2112.2017.08.010

电子学报 ›› 2017, Vol. 45 ›› Issue (8): 1873-1881.DOI: 10.3969/j.issn.0372-2112.2017.08.010

固定边框的多电压布图规划算法

杜世民^1,2, 夏银水², 杨润萍¹, 钱利波²

1. 宁波大学科学技术学院, 浙江宁波 315211;
2. 宁波大学信息科学与工程学院, 浙江宁波 315211

收稿日期:2016-08-21 修回日期:2016-12-20 出版日期:2017-08-25
- 通讯作者:
- 夏银水
- 作者简介:
- 杜世民,男,1976年生于浙江东阳.宁波大学科学技术学院副教授,博士.研究方向为集成电路设计自动化、低功耗SoC设计.E-mail:dushimin@nbu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61131001，No.61501268，No.61471211）; 浙江省自然科学基金 (No.LY15F030008）

Fixed-Outline Muti-voltage Floorplanning Algorithm

DU Shi-min^1,2, XIA Yin-shui², YANG Run-ping¹, QIAN Li-bo²

1. Department of Information Science and Engineering, Ningbo University, Ningbo, Zhejiang 315212, China;
2. College of Science & Technology, Ningbo University, Ningbo, Zhejiang 315211, China

Received:2016-08-21 Revised:2016-12-20 Online:2017-08-25 Published:2017-08-25

摘要/Abstract

摘要： 多电压设计是应对SoC功耗挑战的一种有效方法，但会带来线长、面积等的开销。为减少线长、芯片的空白面积及提高速度，提出了一种改进的固定边框多电压布图方法.对基于NPE（Normalized Polish Expression）表示的布图解，采用形状曲线相加算法来计算其最优的布图实现，并通过增量计算方法来减少计算NPE及多电压分配的时间.为使所得布图解满足给定的边框约束，提出了一个考虑固定边框约束的目标函数，并采用删除后插入（Insertion after Delete，IAD）算子对SA求得布图解进行后优化.实验结果表明，和已有方法相比，所提出方法在线长和空白面积率方面有较明显优势，且所有电路在不同高宽比、不同电压岛数下均实现了极低的空白面积率（< <1%）.

关键词: 低功耗, 多电压, 布图规划, 固定边框

Abstract: Multiple Supply Voltage (MSV) design is an effective ways to deal with SoC power challenge,but brings overhead on wirelength area,etc.To reduce wirelength,chip's dead space ratio and improve algorithm speed,an improved fixed outline multi-voltage floorplanning algorithm is proposed.For a given floorplan solution represented by NPE (Normalized Polish Expression),We use the shape curve adding algorithm to calculate its optimal floorplan implementation,and adopt an incremental calculation method in the process of NPE calculation and voltage assignment to reduce runtime.An improved objective function including fixed-outline constraint is proposed,and the IAD (Insertion After Delete) operator is used to post-optimize the obtained floorplan of SA.Experimental results show that compared with the existing methods,our algorithm has advantages on wirelength and dead space ratio,and all circuits achieve extremely low dead space ratio (<<1%) under different aspect ratio and different voltage island number.

Key words: low power, multiple supply voltage, floorplanning, fixed-outline

中图分类号:

TP391

杜世民, 夏银水, 杨润萍, 钱利波. 固定边框的多电压布图规划算法[J]. 电子学报, 2017, 45(8): 1873-1881.

DU Shi-min, XIA Yin-shui, YANG Run-ping, QIAN Li-bo. Fixed-Outline Muti-voltage Floorplanning Algorithm[J]. Acta Electronica Sinica, 2017, 45(8): 1873-1881.

参考文献

[1] Qiang Ma,Evangeline F Y Young.Multivoltage floorplan design[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2010,29(4):607-617.
[2] Chu Zhufei,Xia Yinshui,Wang Lunyao,Wang Jian.Efficient nonrectangular shaped voltage island aware floorplanning with nonrandomized searching engine[J].Microelectronics Journal,2014,45(4):382-393.
[3] Jai-Ming Lin,Zhi-Xiong Hung.SKB-Tree:A fixed-outline driven representation for modern floorplanning problems[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2012,20(3):473-484.
[4] Qian Zaichen,Evangeline F.Y.Young.Multi-voltage floorplan design with optimal voltage assignment[A].Proceedings of the 2009 international Symposium on Physical Design[C].New York:ACM,2009.13-18.
[5] 杜世民,夏银水,储著飞,杨润萍.电压岛驱动的多级布图规划优化算法[J].西安电子科技大学学报(自然科学版),2015,42(6):184-190. Du Shi-min,Xia Yin-shui,Chu Zhu-fei,Huang Cheng,Yang Run-ping.Voltage island-driven multilevel floorplanning optimization algorithm[J].Journal of Xidian University,2015,42(6):184-190.(in Chinese)
[6] Aminollah Mahabadi,Ahmad Khonsari,Behnam Khodabandeloo,et al.Critical path-aware voltage island partitioning and floorplanning for hard real-time embedded systems[J].Integration,the VLSI Journal,2015,48(1):21-35.
[7] Zhen Meng,Song Chen,Lu Huang.Irregularly shaped voltage islands generation with hazard and heal strategy[A].IEEE 16th International Symposium on Quality Electronic Design[C].California:IEEE,2015.1-4.
[8] Wan-Ping Lee,Hung-Yi Liu,Yao-Wen Chang.An ILP algorithm for post-floorplanning voltage-island generation[A].Proceedings of the 2007 IEEE/ACM International Conference on Computer-Aided Design[C].New Jersey:IEEE Press,2007.650-655.
[9] Wai-Kei Mak,Jr-Wei Chen.Voltage island generation under performance requirement for SoC designs[A].Proceedings of the Asia and South Pacific Design Automation Conference[C].Washington,DC:IEEE Computer Society,2007.798-803.
[10] S N.Adya,I L Markov.Fixed-outline Floorplanning:enabling hierarchical design[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2003,11(6):1120-1135.
[11] D F Wong,C L Liu.A new algorithm for floorplan design[A].Proceedings of the 23rd ACM/IEEE Design Automation Conference[C].Las Vegas:IEEE Computer Society Press,1986.101-107.
[12] 杜世民,夏银水,储著飞,等.面向软模块的稳定固定边框布图规划算法[J].电子与信息学报,2014,36(5):1258-1265. Du Shi-min,Xia Yin-shui,Chu Zhu-fei,et al. A stable fixed-outline floorplanning algorithm for soft module[J].Journal of Electronics & Information Technology,2014,36(5):1258-1265.(in Chinese)
[13] Yan J Z,Chu Chris.DeFer:deferred decision making enabled fixed-outline floorplanning algorithm[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2010,29(3):367-381.
[14] P Sivaranjani,A Senthil Kumar.Thermal-aware non-slicing VLSI floorplanning using a smart decision-making PSO-GA based hybrid algorithm[J].Circuits,Systems,and Signal Processing,2015,34(11):3521-3542.
[15] 王伟,张欢,方芳,等.2TF:一种协同考虑过硅通孔和热量的三维芯片布图规划算法[J].电子学报,2012,40(5):971-976. WANG Wei,ZHANG Huan,FANG Fang,et al..TF:A collaborative considered TSV and thermal floorplanning algorithm for three-dimensional chip[J].Acta Electronica Sinica,2012,40(5):971-976.(in Chinese)

固定边框的多电压布图规划算法

Fixed-Outline Muti-voltage Floorplanning Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王强, 李森, 王天施, 刘晓琴. 辅助电路损耗低的并联谐振直流环节逆变器[J]. 电子学报, 2022, 50(11): 2813-2816.
[2]	蒋万春, 廖凯琴. 节能以太网的节能策略综述[J]. 电子学报, 2021, 49(9): 1830-1839.
[3]	唐晓庆, 谢桂辉, 佘亚军, 俞杨. 基于MCU的无源Wi-Fi散射通信方法[J]. 电子学报, 2019, 47(10): 2069-2075.
[4]	孙海洋, 陈珍, 杨冠男, 高波. 基于采样精度切换的毫米波无线通信空闲侦听机制研究[J]. 电子学报, 2018, 46(9): 2115-2122.
[5]	陈田, 易鑫, 王伟, 刘军, 梁华国, 任福继. 一种低功耗双重测试数据压缩方案[J]. 电子学报, 2017, 45(6): 1382-1388.
[6]	雷才洪. 单片CDCTA-C低功耗电控调谐双模式三阶正交振荡器的设计[J]. 电子学报, 2017, 45(3): 599-604.
[7]	杨骁, 娄付军, 徐锦里, 李靖坤, 邱伟彬. 峰值电流模DC-DC转换器中多功能误差放大器电路设计[J]. 电子学报, 2017, 45(2): 508-512.
[8]	仇径, 罗嘉蕙, 项晓燕, 陈志坚. 基于热点行搜索的低功耗数据高速缓存[J]. 电子学报, 2016, 44(1): 110-114.
[9]	汪正锋, 宁宁, 吴霜毅, 杜翎, 蒋旻, 闫小艳, 王伟. 一种基于电压窗口技术的超低功耗SAR ADC[J]. 电子学报, 2016, 44(1): 211-215.
[10]	曹向荣, 张晓林. 采用预测校正的动态可重构指令Cache[J]. 电子学报, 2014, 42(5): 982-986.
[11]	姜小波, 叶德盛, 吴文涛, 徐向民. 低功耗异步LDPC解码器运算通路设计[J]. 电子学报, 2013, 41(4): 685-689.
[12]	唐枋, 唐建国. 用于CMOS图像传感器的12位低功耗单斜坡模数转换器设计[J]. 电子学报, 2013, 41(2): 352-356.
[13]	姜小波, 叶德盛. 一种新型低功耗异步比较器的设计方法[J]. 电子学报, 2012, 40(8): 1650-1654.
[14]	邓立宝;乔立岩;俞洋;彭喜元. 一种改进的层次化SOCs并行测试封装扫描单元[J]. 电子学报, 2012, 40(5): 949-954.
[15]	王伟;张欢;方芳;陈田;刘军;李欣;邹毅文. 2TF:一种协同考虑过硅通孔和热量的三维芯片布图规划算法[J]. 电子学报, 2012, 40(5): 971-976.