计算机科学技术学报 ›› 2018,Vol. 33 ›› Issue (5): 966-983.doi: 10.1007/s11390-018-1868-6

所属专题: Computer Architecture and Systems

• Computer Architecture and Systems • 上一篇    下一篇

考虑供电噪声和散热约束的三维同构片上多核系统任务调度方案研究

Ying-Lin Zhao1,2,3, Student Member, IEEE, Jian-Lei Yang1,4, Member, IEEE, Wei-Sheng Zhao1,2,3, Senior Member, IEEE, Aida Todri-Sanial5,6,*, Member, IEEE, Yuan-Qing Cheng2,3,*, Member, CCF, ACM, IEEE   

  1. 1 Fert Beijing Research Institute, Beijing Advanced Innovation Center for Big Data and Brain Computing Beijing 100191, China;
    2 School of Electronic and Information Engineering, Beihang University, Beijing 100191, China;
    3 Qingdao Research Institute, Beihang University, Qingdao 266041, China;
    4 School of Computer Science and Engineering, Beihang University, Beijing 100191, China;
    5 Laboratory of Informatics, Robotics and Microelectronics, University of Montpellier, Montpellier 34095, France;
    6 National Center for Scientific Research, Montpellier 34095, France
  • 收稿日期:2017-04-07 修回日期:2018-05-09 出版日期:2018-09-17 发布日期:2018-09-17
  • 通讯作者: Aida Todri-Sanial,e-mail:aida.todri@lirmm.fr;Yuan-Qing Cheng,e-mail:yuanqing@ieee.org E-mail:aida.todri@lirmm.fr;yuanqing@ieee.org
  • 作者简介:Ying-Lin Zhao received his B.S. degree in computer science from Xidian University, Xi'an, in 2014, and now is pursuing his Master's degree in electrical engineering at School of Electrical and Information Engineering, Beihang University, Beijing. His research interests include architecture design and optimization of 3D ICs and non-volatile memory systems.
  • 基金资助:
    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61401008 and 61602022, and the State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, under Grant No. CARCH201602.

Power Supply Noise Aware Task Scheduling on Homogeneous 3D MPSoCs Considering the Thermal Constraint

Ying-Lin Zhao1,2,3, Student Member, IEEE, Jian-Lei Yang1,4, Member, IEEE, Wei-Sheng Zhao1,2,3, Senior Member, IEEE, Aida Todri-Sanial5,6,*, Member, IEEE, Yuan-Qing Cheng2,3,*, Member, CCF, ACM, IEEE   

  1. 1 Fert Beijing Research Institute, Beijing Advanced Innovation Center for Big Data and Brain Computing Beijing 100191, China;
    2 School of Electronic and Information Engineering, Beihang University, Beijing 100191, China;
    3 Qingdao Research Institute, Beihang University, Qingdao 266041, China;
    4 School of Computer Science and Engineering, Beihang University, Beijing 100191, China;
    5 Laboratory of Informatics, Robotics and Microelectronics, University of Montpellier, Montpellier 34095, France;
    6 National Center for Scientific Research, Montpellier 34095, France
  • Received:2017-04-07 Revised:2018-05-09 Online:2018-09-17 Published:2018-09-17
  • Contact: Aida Todri-Sanial,e-mail:aida.todri@lirmm.fr;Yuan-Qing Cheng,e-mail:yuanqing@ieee.org E-mail:aida.todri@lirmm.fr;yuanqing@ieee.org
  • Supported by:
    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61401008 and 61602022, and the State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, under Grant No. CARCH201602.

由于三维集成技术的兴起,片上多核系统现在可以将更多的IP核集成到片上以达到更高的能效。然而,由于特有的芯片堆叠结构,三维芯片也面临诸多挑战。其中,供电噪声是一个严重问题。在本文中,我们研究了不同核、不同层的供电噪声的耦合效应,发现供电噪声的变化与所运行的任务分配方案有很大关系。另一方面,三维芯片的高集成度也引发了严重的散热问题。在文中,我们提出了一个全新的同时考虑供电噪声和散热问题的任务调度方案。它主要有三部分组成。首先,我们通过在体系结构层次上分析任务的功耗信息抽取出供电网的激励。其次,我们开发了一个高效的供电网络求解程序来高效的得到供电噪声强度。之后,我们形式化了本文研究的任务调度问题并提出了一个启发式的算法进行求解。与之前提出的任务调度算法相比,我们所提出的方法对于2×2×2的三维片上多核系统可以降低12%的供电噪声,在3×3×3的三维片上多核系统上可以降低14%的供电噪声。由于供电噪声减小,任务运行时间也分别减少了5.5%和7.8%。

关键词: 供电噪声, 供电网络, 任务调度算法, 温度, 三维片上多核系统

Abstract: Thanks to the emerging 3D integration technology, The multiprocessor system on chips (MPSoCs) can now integrate more IP cores on chip with improved energy efficiency. However, several severe challenges also rise up for 3D ICs due to the die-stacking architecture. Among them, power supply noise becomes a big concern. In the paper, we investigate power supply noise (PSN) interactions among different cores and tiers and show that PSN variations largely depend on task assignments. On the other hand, high integration density incurs a severe thermal issue on 3D ICs. In the paper, we propose a novel task scheduling framework considering both the PSN and the thermal issue. It mainly consists of three parts. First, we extract current stimuli of running tasks by analyzing their power traces derived from architecture level simulations. Second, we develop an efficient power delivery network (PDN) solver to evaluate PSN magnitudes efficiently. Third, we propose a heuristic algorithm to solve the formulated task scheduling problem. Compared with the state-of-the-art task assignment algorithm, the proposed method can reduce PSN by 12% on a 2×2×2 3D MPSoCs and by 14% on a 3×3×3 3D MPSoCs. The end-to-end task execution time also improves as much as 5.5% and 7.8% respectively due to the suppressed PSN.

Key words: power supply noise(PSN), power delivery network(PDN), task scheduling algorithm, temperature, 3D MPSoCs

[1] Borkar S, Chien A A. The future of microprocessors. Communications of the ACM, 2011, 54(5):67-77
[2] Martin G. Overview of the MPSoC design challenge. In Proc. the 43rd ACM/IEEE Design Automation Conference, July 2006, pp.274-279.
[3] Todri-Sanial A, Tan C S. Physical DesiCircuits (1st edition). CRC Press, 2015.
[4] Tendler J M, Dodson J S, Fields J S, Le H, Sinharoy B. POWER4 system microarchitecture. IBM Journal of Research and Development, 2002, 46(1):5-25.
[5] Todri A, Marek-Sadowska M, Kozhaya J. Power supply noise aware workload assignment for multi-core systems In Proc. the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 2008, pp.330-337.
[6] Wang Y, Xu J, Xu Y et al. Power gating aware task scheduling in MPSoC. IEEE Transactions on Very Large Scale Integration Systems, 2011, 19(10):1801-1812.
[7] Huang G, Bakir M, Naeemi A, Chen H, Meindl J D. Power delivery for 3D chip stacks:Physical modeling and design implication. In Proc. the 2007 IEEE Electrical Performance of Electronic Packaging, October 2007, pp.205-208.
[8] Sabry M M, Sridhar A, Atienza D, Temiz Y, Leblebici Y, Szczukiewicz S, Borhani N, Thome J R, Brunschwiler T, Michel B. Towards thermally-aware design of 3D MPSoCs with inter-tier cooling. In Proc. the 2011 Design, Automation and Test in Europe Conference and Exhibition, March 2011, pp.1466-1471.
[9] Kuuoglu H, Alam M A. A unified modeling of NBTI and hot carrier injection for MOSFET reliability. In Proc. the 10th International Workshop on Computational Electronics, October 2004, pp.28-29.
[10] Micheli G D. Synthesis and Optimization of Digital Circuits (1st edition). McGraw-Hill Science/Engineering/Math, 1994.
[11] Chantem T, Hu X S, Dick R P. Temperature-aware scheduling and assignment for hard real-time applications on MPSoCs. IEEE Transactions on Very Large Scale Integration Systems, 2011, 19(10):1884-1897.
[12] Chen H H, Ling D D. Power supply noise analysis methodology for deep-submicron VLSI chip design. In Proc. the 34th Design Automation Conference June 1997, pp.638-643.
[13] Zhuo C, Wilke G, Chakraborty R et al. A silicon-validated methodology for power delivery modeling and simulation. In Proc. the 2012 IEEE/ACM International Conference on Computer-Aided Design, November 2012, pp.255-262.
[14] Khan N H, Alam S M, Hassoun S. Power delivery design for 3-D ICs using different through-silicon via (TSV) technologies. IEEE Transactions on Very Large Scale Integration Systems, 2011, 19(4):647-658.
[15] Healy M B, Lim S K. Power delivery system architecture for many-tier 3D systems. In Proc. the 60th Electronic Components and Technology Conference, June 2010, pp.1682-1688.
[16] Conn A R, Haring R A, Visweswariah C. Noise considerations in circuit optimization. In Proc. the 1998 ComputerAided Design of Integrated Circuits and Systems, November 1998, pp.220-227
[17] Sun C, Shang L, Dick R P. Three-dimensional multiprocessor system-on-chip thermal optimization. In Proc. the 5th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, September 2007, pp.117-122.
[18] Huang W, Stan M R, Skadron K. Parameterized physical compact thermal modeling. IEEE Transactions on Components & Packaging Technologies, 2005, 28(4):615-622.
[19] Todri A, Kundu S, Girard P et al. A study of tapered 3-D TSVs for power and thermal integrity. IEEE Transactions on Very Large Scale Integration Systems, 2013, 21(2):306-319.
[20] Zhou X, Yang J, Xu Y, Zhang Y, Zhao J. Thermal-aware task scheduling for 3D multicore processors. IEEE Transactions on Parallel & Distributed Systems, 2010, 21(1):60-71.
[21] Huang W, Ghosh S, Velusamy S, Sankaranarayanan K, Skadron K, Stan M R. HotSpot:A compact thermal modeling methodology for early-stage VLSI design. IEEE Transactions on Very Large Scale Integration Systems, 2006, 14(5):501-513.
[22] Dick R P, Rhodes D L, Wolf W. TGFF:Task graphs for free. In Proc. the 6th International Workshop on Hardware/Software Codesign, March 1998, pp.97-101.
[23] Xu Z, Gu X, Scheuermann M, Rose K, Webb B C, Knickerbocker J U, Lu J Q. Modeling of power delivery into 3D chips on silicon interposer. In Proc. the 62nd IEEE Electronic Components and Technology Conference, June 2012, pp.683-689.
[24] Zhang R, Wang K, Meyer B H, Stan M R, Skadron K. Architecture implications of pads as a scarce resource. In Proc. the 41st International Symposium on Computer Architecture, June 2014, pp.373-384.
[25] Brooks D, Tiwari V, Martonosi M. Wattch:A framework for architectural-level power analysis and optimizations. In Proc. the 27th International Symposium on Computer Architecture, June 2000, pp.83-94.
[26] Sherwood T, Perelman E, Hamerly G, Calder B. Automatically characterizing large scale program behavior. In Proc. the 10th International Conference on Architectural Support for Programming Languages and Operating Systems, October 2002, pp.45-57.
[27] Cheng Y, Todri-Sanial A, Bosio A, Dilillo L, Girard P, Virazel A. Power supply noise-aware workload assignments for homogeneous 3D MPSoCs with thermal consideration. In Proc. the 19th Asia and South Pacific Design Automation Conference, January 2014, pp.544-549.
[28] Gupta M S, Oatley J L, Joseph R, Wei G Y, Brooks D M. Understanding voltage variations in chip multiprocessors using a distributed power-delivery network. In Proc. the 2007 Design, Automation and Test in Europe Conference and Exhibition, April 2007.
[29] Nassif S R, Kozhaya J N. Fast power grid simulation. In Proc. the 37th Design Automation Conference, June 2000, pp.156-161.
[30] Su H, Liu F, Devgan A, Acar E, Nassif S. Full chip leakage estimation considering power supply and temperature variations. In Proc. the 2003 International Symposium on Low Power Electronics and Design, August 2003, pp.78-83.
[31] Chen T H, Chen C C P. Efficient large-scale power grid analysis based on preconditioned Krylov-subspace iterative methods. In Proc. the 38th Design Automation Conference, June 2001, pp.559-562.
[32] Li F, Nicopoulos C, Richardson T, Xie Y, Narayanan V, Kandemir M. Design and management of 3D chip multiprocessors using network-in-memory. In Proc. the 33rd International Symposium on Computer Architecture, June 2006, pp.130-141.
[33] Kwok Y, Ahmad I. Static task scheduling and allocation algorithms for scalable parallel and distributed systems:Classification and performance comparison. In Annual Review of Scalable Computing, Kwong Y C (eds.), World Scientific Publishing Company, 2003, pp.107-227.
[34] Choi J, Cher C Y, Franke H, Hamann H, Weger A, Bose P. Thermal-aware task scheduling at the system software level. In Proc. the 2007 International Symposium on Low Power Electronics and Design, August 2007, pp.213-218.
[35] Huang L, Yuan F, Xu Q. Lifetime reliability-aware task allocation and scheduling for MPSoC platforms. In Proc. the 2009 Design, Automation & Test in Europe Conference and Exhibition, April 2009, pp.51-56.
[36] Cheng Y, Zhang L, Han Y, Li X. Thermal constrained task allocation for interconnect energy reduction in 3-D homogeneous MPSoCs. IEEE Transactions on Very Large Scale Integration Systems, 2013, 21(2):239-249.
[37] Howard J, Dighe S, Hoskote Y et al. A 48-Core IA-32 message-passing processor with DVFS in 45nm CMOS. In Proc. the 2010 International Solid-State Circuits Conference, February 2010, pp.108-109.
[38] Cadix L, Rousseau M, Fuchs C et al. Integration and frequency dependent electrical modeling of Through Silicon Vias (TSV) for high density 3DICs. In Proc. the 2010 International Interconnect Technology Conference, January 2010, pp.1-3.
[39] Saint-Laurent M, Swaminathan M. Impact of power-supply noise on timing in high-frequency microprocessors. IEEE Transactions on Advanced Packaging, 2004, 27(1):135-144.
[40] Arabi K, Saleh R, Meng X. Power supply noise in SoCs:Metrics, management, and measurement. IEEE Design & Test of Computers, 2007, 24(3):236-244.
[41] Firouzi F, Kiamehr S, Tahoori M B. Modeling and estimation of power supply noise using linear programming. In Proc. the 2011 IEEE/ACM International Conference on Computer-Aided Design, October 2011, pp.537-542.
[42] Joseph R, Brooks D, Martonosi M. Control techniques to eliminate voltage emergencies in high performance processors. In Proc. the 9th International Symposium on High-Performance Computer Architecture, February 2003, pp.79-90.
[43] Grochowski E, Ayers D, Tiwari V. Microarchitectural simulation and control of di/dt-induced power supply voltage variation. In Proc. the 8th High-Performance Computer Architecture, February 2002, pp.7-16.
[44] Huang G, Sekar D C, Naeemi A et al. Compact physical models for power supply noise and chip/package co-design of gigascale integration. In Proc. the 57th Electronic Components and Technology Conference, May 2007, pp.1659-1666.
[45] Healy M B, Lim S K. Distributed TSV topology for 3-D power-supply networks. IEEE Transactions on Very Large Scale Integration Systems, 2012, 20(11):2066-2079.
[46] Zhang C, Pavlidis V F, Micheli G D. Voltage propagation method for 3-D power grid analysis. In Proc. the 2012 Design, Automation & Test in Europe Conference & Exhibition, April 2012, pp.844-847.
[47] Todri-Sanial A, Cheng Y. A study of 3-D power delivery networks with multiple clock domains. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(11):3218-3231.
[48] Coskun A K, Rosing T S, Whisnant K. Temperature aware task scheduling in MPSoCs. In Proc. the 2007 Design, Automation and Test in Europe Conference and Exhibition, March 2007, pp.1659-1664.
[49] Shang L, Peh L S, Kumar A et al. Thermal modeling, characterization and management of on-chip networks. In Proc. the 37th IEEE/ACM International Symposium on Microarchitecture, December 2004, pp.67-78.
[50] Jung H, Rong P, Pedram M. Stochastic modeling of a thermally-managed multicore system. In Proc. the 45th ACM/IEEE Design Automation Conference, June 2008, pp.728-733.
[51] Qian L, Zhu Z. Analytical heat transfer model for threedimensional integrated circuits incorporating through silicon via effect-RETRACTED. LET Micro & Nano Letters, 2012, 7(9):994-996.
[52] Hameed F, Faruque M A A, Henkel J. Dynamic thermal management in 3D multicore architecture through run-time adaptation. In Proc. the 2011 Design, Automation & Test in Europe Conference & Exhibition, March 2011.
[53] Jayaseelan R, Mitra T. Temperature aware task sequencing and voltage scaling. In Proc. the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 2008, pp.618-623.
[54] Liao C H, Wen C H P, Chakrabarty K. An online thermalconstrained task scheduler for 3D multi-core processors. In Proc. the 2015 IEEE/ACM Design, Automation & Test in Europe Conference & Exhibition, March 2015, pp.351-356.
[55] Momtazpour M, Sanaei E, Goudarzi M. Power-yield optimization in MPSoC task scheduling under process variation. In Proc. the 11th International Symposium on Quality Electronic Design, March 2010, pp.747-754.
[56] Hu J, Marculescu R. Energy- and performance-aware mapping for regular NoC architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(4):551-562.
[57] Ghasemazar M, Pakbaznia E, Pedram M. Minimizing the power consumption of a chip multiprocessor under an average throughput constraint. In Proc. the 11th International Symposium on Quality Electronic Design, March 2010, pp.362-371.
[1] Jing Wang, Yi-Ci Cai, Qiang Zhou. 基于电流追踪的供电网络温度感知电迁移分析方法[J]. 计算机科学技术学报, 2021, 36(5): 1133-1144.
[2] Yuan-Qing Cheng, Lei Zhang, Yin-He Han, Xiao-Wei Li. 电路级划分的三维片上多核系统中测试外壳扫描链的硅通孔数目最小化研究[J]. , 2013, 28(1): 119-128.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 闵应骅;. Guest Editor s Introduction:Fault-Tolerant Computing[J]. , 1990, 5(2): 3 -4 .
[2] 高小山; 朱长才;. Automated Generation of Kempe Linkageand Its Complexity[J]. , 1999, 14(5): 460 -467 .
[3] . 通用式GF(2m)乘法器[J]. , 2007, 22(1): 28 -38 .
[4] 徐殿祥, Omar El-Ariss, 许巍峰, 王林章. 暂缺[J]. , 2009, 24(5): 949 -961 .
[5] Min-Yi Guo, Zi-Li Shao, Edwin Hsing-Mean Sha. [J]. , 2011, 26(3): 373 -374 .
[6] Chao Li, Rui Wang, Yang Hu, Ruijin Zhou, Ming Liu, Long-Jun Liu, Jing-Ling Yuan,. 可再生能源驱动的绿色数据中心下的自主电源供给及供电异常处理[J]. , 2014, 29(4): 618 -630 .
[7] Wen-Gang Zhou, Hou-Qiang Li, Yijuan Lu, Qi Tian. 基于空间上下文分析的大规模部分拷贝图像检索[J]. , 2014, 29(5): 837 -848 .
[8] Juan Fang, Zhen-Yu Leng, Si-Tong Liu, Zhi-Cheng Yao, Xiu-Feng Sui. 面向GPU-CPU异构体系结构的异构片上网络设计空间探索[J]. , 2015, 30(1): 74 -83 .
[9] Chong Wang, Kai-Qi Huang. 基于视觉反馈模型的鲁棒物体识别[J]. , 2015, 30(2): 325 -339 .
[10] Yan-Tao Jia, Yuan-Zhuo Wang, Xue-Qi Cheng. 微博中融合结构和交互信息的链接预测学习[J]. , 2015, 30(4): 829 -842 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: