同构多核处理器中考虑制造差异的调度优化

CHEN Zhi-xiang; LI Zhao-lin; CAO Shan; WANG Fang; ZHOU Jie

doi:10.1631/FITEE.1500035

Your Location：

Home >

Browse articles >

同构多核处理器中考虑制造差异的调度优化

计算机与自动化 | Updated：2022-06-06

- 同构多核处理器中考虑制造差异的调度优化
- Schedule refinement for homogeneous multi-core processors in the presence of manufacturing-caused heterogeneity
- 信息与电子工程前沿（英文） 2015年16卷第12期页码：1018-1033
- Affiliations：
  
  1.Department of Automation, Tsinghua University, Beijing 100084, China
  2.Institute of Microelectronics, Tsinghua University, Beijing 100084, China
  3.Research Institute of Information Technology, Tsinghua University, Beijing 100084, China
  4.Tsinghua National Laboratory for Information Science and Technology, Tsinghua University, Beijing 100084, China
  5.The School of Information and Electronics, Beijing Institute of Technology, Beijing 100084, China
- Author bio：
  
  [ "Zhi-xiang CHEN, E-mail: chen-zx10@mails.tsinghua.edu.cn" ]
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61225008, 61373074, and 61373090), the National Basic Research Program (973) of China (No. 2014CB349304), the Specialized Research Fund for the Doctoral Program of Higher Education, the Ministry of Education of China (No. 20120002110033), and the Tsinghua University Initiative Scientific Research Program
- DOI：10.1631/FITEE.1500035
  中图分类号： TP302
- 收稿：2015-02-01，
  
  修回：2015-11-04，
  
  纸质出版：2015-12
- Accepted：
Scan QR Code
同构多核处理器中考虑制造差异的调度优化[J]. 信息与电子工程前沿（英文）, 2015,16(12):1018-1033.

CHEN Zhi-xiang, LI Zhao-lin, CAO Shan, et al. Schedule refinement for homogeneous multi-core processors in the presence of manufacturing-caused heterogeneity[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(12): 1018-1033.
同构多核处理器中考虑制造差异的调度优化[J]. 信息与电子工程前沿（英文）, 2015,16(12):1018-1033. DOI： 10.1631/FITEE.1500035.

CHEN Zhi-xiang, LI Zhao-lin, CAO Shan, et al. Schedule refinement for homogeneous multi-core processors in the presence of manufacturing-caused heterogeneity[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(12): 1018-1033. DOI： 10.1631/FITEE.1500035.

摘要

目的

面向具有多个同构核心的处理器平台，考虑纳米级工艺下制造导致的差异性，实现性能最佳的调度优化。

创新点

提出一种离线生成多个候选调度结合在线调度绑定的方案，从而充分开采了制造差异性下的核心最大可工作频率的变化，取得了整体上的高性能。

方法

首先，考虑制造差异导致的性能变化，提出一种离线结合在线的调度优化方案。在离线阶段，考虑制造差异的分布情况，以期望性能为指标，选择代表性的芯片工作点并得到其对应的最佳调度，用于生成候选调度并存储在芯片上。其中，通过芯片工作点采样来解决芯片工作点数量的指数增长问题，并且将期望性能的最优化求解在一定的约束下转化为芯片工作点之间的关系，从而降低整体方案的复杂度。在在线阶段，芯片启动时，根据当前芯片的工作点与候选调度对应的芯片工作点之间的关系确定性能最优的调度。

结论

针对纳米工艺下呈现制造差异的多核处理器平台，提出了一种自适应的调度优化策略，实现了性能上的提升。

Abstract

Multi-core homogeneous processors have been widely used to deal with computation-intensive embedded applications. However

with the continuous down scaling of CMOS technology

within-die variations in the manufacturing process lead to a significant spread in the operating speeds of cores within homogeneous multi-core processors. Task scheduling approaches

which do not consider such heterogeneity caused by within-die variations

can lead to an overly pessimistic result in terms of performance. To realize an optimal performance according to the actual maximum clock frequencies at which cores can run

we present a heterogeneity-aware schedule refining (HASR) scheme by fully exploiting the heterogeneities of homogeneous multi-core processors in embedded domains. We analyze and show how the actual maximum frequencies of cores are used to guide the scheduling. In the scheme

representative chip operating points are selected and the corresponding optimal schedules are generated as candidate schedules. During the booting of each chip

according to the actual maximum clock frequencies of cores

one of the candidate schedules is bound to the chip to maximize the performance. A set of applications are designed to evaluate the proposed scheme. Experimental results show that the proposed scheme can improve the performance by an average value of 22.2%

compared with the baseline schedule based on the worst case timing analysis. Compared with the conventional task scheduling approach based on the actual maximum clock frequencies

the proposed scheme also improves the performance by up to 12%.

关键词

Keywords

references

P. Aguilera , J. Lee , A. Farmahini-Farahani , 等 . Process variation-aware workload partitioning algorithms for GPUs supporting spatial-multitasking . Design, Automation and Test in Europe Conf. and Exhibition , 2014 . p.176.1 - 176.6 . DOI: 10.7873/date.2014.189 http://doi.org/10.7873/date.2014.189 .

S. Bell , B. Edwards , J. Amann , 等 . TILE64 processor:a 64-core SoC with mesh interconnect . IEEE Int. Solid-State Circuits Conf. , 2008 . p.588 - 598 . DOI: 10.1109/isscc.2008.4523070 http://doi.org/10.1109/isscc.2008.4523070 .

K.A. Bowman , S.G. Duvall , J.D. Meindl . Impact of die-to-die and within-die parameter fluctuations on the maximum clock frequency distribution for gigascale integration . IEEE J. Solid-State Circ. , 2002 . 37 ( 2 ): 183 - 190 . DOI: 10.1109/4.982424 http://doi.org/10.1109/4.982424 .

K.A. Bowman , A.R. Alameldeen , S.T. Srinivasan , 等 . Impact of die-to-die and within-die parameter variations on the clock frequency and throughput of multi-core processors . IEEE Trans. VLSI Syst. , 2009 . 17 ( 12 ): 1679 - 1690 . DOI: 10.1109/TVLSI.2008.2006057 http://doi.org/10.1109/TVLSI.2008.2006057 .

H. Chon , T. Kim . Timing variation-aware task scheduling and binding for MPSoC . Proc. Asia and South Pacific Design Automation Conf. , 2009 . p.137 - 142 . DOI: 10.1109/aspdac.2009.4796470 http://doi.org/10.1109/aspdac.2009.4796470 .

R.P. Dick , D.L. Rhodes , W. Wolf . TGFF:task graphs for free . Proc. 6th Int. Workshop on Hardware/Software Codesign , 1998 . p.97 - 101 . DOI: 10.1109/hsc.1998.666245 http://doi.org/10.1109/hsc.1998.666245 .

M. Dietrich , J. Haase . Process Variations and Probabilistic Integrated Circuit Design . Springer, New York , 2012 . p.69 - 89 . DOI: 10.1007/978-1-4419-6621-6 http://doi.org/10.1007/978-1-4419-6621-6 .

F. Ferrandi , P.L. Lanzi , C. Pilato , 等 . Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , 2010 . 29 ( 6 ): 911 - 924 . DOI: 10.1109/tcad.2010.2048354 http://doi.org/10.1109/tcad.2010.2048354 .

L. Huang , Q. Xu . Performance yield-driven task allocation and scheduling for MPSoCs under process variation . Proc. 47th Design Automation Conf. , 2010 . p.326 - 331 . DOI: 10.1145/1837274.1837358 http://doi.org/10.1145/1837274.1837358 .

W. Huang , K. Rajamani , M.R. Stan , 等 . Scaling with design constraints:predicting the future of big chips . IEEE Micro , 2011 . 31 ( 4 ): 16 - 29 . DOI: 10.1109/MM.2011.42 http://doi.org/10.1109/MM.2011.42 .

ITRS . International Technology Roadmap for Semiconductors . Available from , http://www.itrs.net/reports.html http://www.itrs.net/reports.html , [Accessed on Feb. 1, 2015] 2013 .

B. Khailany , W.J. Dally , U.J. Kapasi , 等 . Imagine:media processing with streams . IEEE Micro , 2001 . 21 ( 2 ): 35 - 46 . DOI: 10.1109/40.918001 http://doi.org/10.1109/40.918001 .

B. Khodabandeloo , A. Khonsari , F. Gholamian , 等 . Scenario-based quasi-static task mapping and scheduling for temperature-efficient MPSoC design under process variation . Microprocess. Microsyst. , 2014 . 38 ( 5 ): 399 - 414 . DOI: 10.1016/j.micpro.2014.05.006 http://doi.org/10.1016/j.micpro.2014.05.006 .

Y.C. Lin , F. Lu , K.T. Cheng . Pseudo-functional scan-based BIST for delay fault . Proc. 23rd IEEE VLSI Test Symp. , 2005 . p.229 - 234 . DOI: 10.1109/vts.2005.69 http://doi.org/10.1109/vts.2005.69 .

D. Mirzoyan , B. Akesson , K. Goossens . Processvariation aware mapping of real-time streaming applications to MPSoCs for improved yield . Proc. 13th Int. Symp. on Quality Electronic Design , 2012 . p.41 - 48 . DOI: 10.1109/isqed.2012.6187472 http://doi.org/10.1109/isqed.2012.6187472 .

D. Mirzoyan , B. Akesson , K. Goossens . Processvariation-aware mapping of best-effort and real-time streaming applications to MPSoCs . ACM Trans. Embed. Comput. Syst. , 2014 . 13 ( 2s ): 61.1 - 61.24 . DOI: 10.1145/2490819 http://doi.org/10.1145/2490819 .

M. Momtazpour , M. Goudarzi , E. Sanaei . Variation-aware task and communication scheduling in MPSoCs for power-yield maximization . IEICE Trans. Fundament. Electron. Commun. Comput. Sci. , 2010a . 93 ( 12 ): 2542 - 2550 . DOI: 10.1587/transfun.e93.a.2542 http://doi.org/10.1587/transfun.e93.a.2542 .

M. Momtazpour , E. Sanaei , M. Goudarzi . Poweryield optimization in MPSoC task scheduling under process variation . Proc. 11th Int. Symp. on Quality Electronic Design , 2010b . p.747 - 754 . DOI: 10.1109/isqed.2010.5450497 http://doi.org/10.1109/isqed.2010.5450497 .

M. Momtazpour , M. Ghorbani , M. Goudarzi , 等 . Simultaneous variation-aware architecture exploration and task scheduling for MPSoC energy minimization . Proc. 21st Symp. on GLSVLSI , 2011 . p.271 - 276 . DOI: 10.1145/1973009.1973063 http://doi.org/10.1145/1973009.1973063 .

M. Momtazpour , M. Goudarzi , E. Sanaei . Static statistical MPSoC power optimization by variation-aware task and communication scheduling . Microprocess. Microsyst. , 2013 . 37 ( 8B ): 953 - 963 . DOI: 10.1016/j.micpro.2012.02.008 http://doi.org/10.1016/j.micpro.2012.02.008 .

F.A. Omara , M.M. Arafa . Genetic algorithms for task scheduling problem . J. Parall. Distrib. Comput. , 2010 . 70 ( 1 ): 13 - 22 . DOI: 10.1016/j.jpdc.2009.09.009 http://doi.org/10.1016/j.jpdc.2009.09.009 .

K. Ramamritham . Allocation and scheduling of precedence-related periodic tasks . IEEE Trans. Parall. Distrib. Syst. , 1995 . 6 ( 4 ): 412 - 420 . DOI: 10.1109/71.372795 http://doi.org/10.1109/71.372795 .

A. Raychowdhury , S. Ghosh , K. Roy . A novel on-chip delay measurement hardware for efficient speed-binning . Proc. 11th IEEE Int. On-Line Testing Symp. , 2005 . p.287 - 292 . DOI: 10.1109/iolts.2005.10 http://doi.org/10.1109/iolts.2005.10 .

S.R. Sarangi , B. Greskamp , R. Teodorescu , 等 . VARIUS:a model of process variation and resulting timing errors for microarchitects . IEEE Trans. Semicond. Manufact. , 2008 . 21 ( 1 ): 3 - 13 . DOI: 10.1109/tsm.2007.913186 http://doi.org/10.1109/tsm.2007.913186 .

L. Singhal , E. Bozorgzadeh . Process variation aware system-level task allocation using stochastic ordering of delay distributions . Proc. IEEE/ACM Int. Conf. on Computer-Aided Design , 2008 . p.570 - 574 . DOI: 10.1109/iccad.2008.4681633 http://doi.org/10.1109/iccad.2008.4681633 .

S. Stuijk , M. Geilen , T. Basten . SDF3:SDF for free . Proc. 6th Int. Conf. on Application of Concurrency to System Design , 2006 . p.276 - 278 . DOI: 10.1109/acsd.2006.23 http://doi.org/10.1109/acsd.2006.23 .

M.B. Taylor , J. Kim , J. Miller , 等 . The raw microprocessor:a computational fabric for software circuits and general-purpose programs . IEEE Micro , 2002 . 22 ( 2 ): 25 - 35 . DOI: 10.1109/mm.2002.997877 http://doi.org/10.1109/mm.2002.997877 .

H. Topcuoglu , S. Hariri , M.Y. Wu . Performanceeffective and low-complexity task scheduling for heterogeneous computing . IEEE Trans. Parall. Distrib. Syst. , 2002 . 13 ( 3 ): 260 - 274 . DOI: 10.1109/71.993206 http://doi.org/10.1109/71.993206 .

R. Von Mises . Mathematical Theory of Probability and Statistics . Academic Press, New York , 1964 . p.329 - 367 . DOI: 10.1016/b978-1-4832-3213-3.50010-5 http://doi.org/10.1016/b978-1-4832-3213-3.50010-5 .

F. Wang , Y. Chen , C. Nicopoulos , 等 . Variationaware task and communication mapping for MPSoC architecture . IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. , 2011 . 30 ( 2 ): 295 - 307 . DOI: 10.1109/tcad.2010.2077830 http://doi.org/10.1109/tcad.2010.2077830 .

Y. Yi , W. Han , X. Zhao , 等 . An ILP formulation for task mapping and scheduling on multi-core architectures . Design, Automation and Test in Europe Conf. and Exhibition , 2009 . p.33 - 38 . DOI: 10.1109/date.2009.5090629 http://doi.org/10.1109/date.2009.5090629 .

Z. Yu , B.M. Baas . High performance, energy efficiency, and scalability with GALS chip multiprocessors . IEEE Trans. VLSI Syst. , 2009 . 17 ( 1 ): 66 - 79 . DOI: 10.1109/tvlsi.2008.2001947 http://doi.org/10.1109/tvlsi.2008.2001947 .

W. Zhao , F. Liu , K. Agarwal , 等 . Rigorous extraction of process variations for 65-nm CMOS design . IEEE Trans. Semicond. Manufact. , 2009 . 22 ( 1 ): 196 - 203 . DOI: 10.1109/tsm.2008.2011182 http://doi.org/10.1109/tsm.2008.2011182 .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据