多核嵌入式系统内联网络优化调度

J4 ›› 2016, Vol. 38 ›› Issue (04): 617-623.

• 论文 • 下一篇

多核嵌入式系统内联网络优化调度

杜家宜，李仁发，堵琳娜

（湖南大学信息科学与工程学院,湖南长沙 410082）

收稿日期:2015-02-28 修回日期:2015-06-16 出版日期:2016-04-25 发布日期:2016-04-25
基金资助:
国家自然科学基金（61173014,61173036）；湖南省科技厅科技计划项目(2014GK3043)

Task optimization scheduling to inter-connection network
on embedded system with chip multi-processors

DU Jiayi，LI Renfa,DU Linna

（School of Information Science and Engineering,Hunan University,Changsha 410082,China）

Received:2015-02-28 Revised:2015-06-16 Online:2016-04-25 Published:2016-04-25

摘要/Abstract

摘要：

处理核之间的通信问题是多核系统中不可避免的问题，根据具体应用，进行核间内联网络的定制和设计是一个可行的研究方向。针对该问题提出了任务节点的通信调度算法，通过采用点对点连接作为内联网络的方式，在不增加系统调度长度的前提下，构造出满足系统核间通信需求、核间点对点连接数最少的内联网络。同时还给出了核间通信调度确定算法和内联网络构造算法，为内联网络的设计提供依据。实验表明，与传统的HLFET算法相比，提出的调度算法能极大减少嵌入式系统中的核间点对点连接数目。

关键词: 内联网络, 任务调度算法, 点对点连接

Abstract:

Communication between cores is significant for the performance of embedded system of chip multiprocessors （CMPs）. It is a promising solution to design and customize the interconnection network based on a particular application. We propose a task optimization scheduling for communication connection algorithm （TOCCA）when connection is of the type of P2P. The interconnected network has minimal P2P connections and satisfies the communication demands, while not increasing the makespan. Besides, to help deploy the network, we present a deterministic algorithm of data transition (DDT) and a construction algorithm of interconnection network (CICN). Experimental results show that the TOCCA can dramatically reduce the number of P2P connections in comparison with the HLFET algorithm.

Key words: inter-connection network;task scheduling;P2P connection

杜家宜，李仁发，堵琳娜. 多核嵌入式系统内联网络优化调度[J]. J4, 2016, 38(04): 617-623.

DU Jiayi，LI Renfa,DU Linna. Task optimization scheduling to inter-connection network
on embedded system with chip multi-processors [J]. J4, 2016, 38(04): 617-623.

参考文献［19］

［1］	Gangwar A,Balakrishnan M,Kumar A. Impact of intercluster communication mechanisms on ILP in clustered VLIW architectures ［J］. ACM Transactions on Design Automation of Electronic Systems (TODAES),2007,12(1):1.
［2］	Bambha N K,Bhattacharyya S S. Joint application mapping/interconnect synthesis techniques for embedded chipscale multiprocessors ［J］. IEEE Transactions on Parallel and Distributed Systems,2005,16(2):99112.
［3］	Kaneko S,Kondo H,Masui N,et al. A 600 MHz singlechip multiprocessor with 4.8 gb/s internal shared pipelined bus and 512 kb internal memory ［J］. IEEE Journal of SolidState Circuits,2004,39(1):184193.
［4］	Eisley N,Peh L S,Shang L. Leveraging onchip networks for data cache migration in chip multiprocessors.［C］∥Proc of the 17th International Conference on Parallel Architectures and Compilation Techniques,2008:197207.
［5］	Wang Y F, Zhang Y Z, Gao T. Survey on energyefficient task scheduling with bus conflict avoidance for multicore embedded systems ［J］. Application Research of Computer, 2014, 31(4):961964. 961964. (in Chinese)
［6］	Kundu P,Peh L S. Guest editors’ introduction:Onchip interconnects for multicores ［J］. IEEE Micro,2007,27(5):35.
［7］	Hur J Y. Customizing and hardwiring onchip interconnects in FPGAs ［D］. South Korea:PhD dissertation,TU Delft,2011.
［8］	Zhang Y,Li H,Min Y,et al. Selected transition time adjustment for tolerating crosstalk effects on networkonchip interconnects ［J］. Vry Larg Al Ngraon:l,2011,19(10):17871800.
［9］	Zhang P, Fan X Y, Huang X P. Researching of onchip debug based on bus access ［J］. Computer Measurement & Control, 2014, 22(2):510512,518. (in Chinese)
［10］	Dong W X, Shen H B, Quan L, et al. Poweraware mapping basedon genetic algorithm for networkonchip ［J］. Journal of Zhejiang University(Science Edition), 2010, 37(6):654656. (in Chinese)
［11］	Mishra A,Tripathi A K. Complexity of a problem of energy efficient realtime task scheduling on a multicore processor ［J］. Complexity,2014,21(1):259267.
［12］	Kim S C,Lee S. Decentralized task scheduling for a fixed priority multicore embedded RTOS ［J］. Computing,2013,97(6):563555.
［13］	Xu C, He Y X, Chen Y. A task scheduling method to increase the reliability of the multicore system ［J］. Acta Electronica Sinica, 2013, 41(5):10191024. (in Chinese)
［14］	Olivier S L, Porterfield A K, Wheeler K B, et al. Scheduling task parallelism on multisocket multicore systems ［C］∥Proc of the 1st International Workshop on Runtime and Operating Systems for Supercomputers,2011:4956.
［15］	Chung I H,Lee C R,Zhou J,et al. Scalable communicationaware task mapping algorithms for interconnected multicore systems ［C］∥Proc of IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW),2012:187192.
［16］	Yamazaki H,Konishi K,Shin S,et al. Multistep scheduling algorithm for parallel and distributed processing in heterogeneous systems with communication costs ［J］. Mathematical Problems in Engineering,2013,11:13111325.
［17］	Momtazpour M, Goudarzi M, Sanaei E. Static statistical MPSoC power optimization by variationaware task and communication scheduling ［J］. Microprocessors and Microsystems,2013,37(8):953963.
［18］	Han L, Chen X L, Li X. Scheduling algorithm with communication overhead reduction ［J］. Computer Systems & Applications, 2014, 23(9):6571. (in Chinese)
［19］	Liu C X, Shi F, Xue L C, et al. Hierarchical shared multichannel scratch pad memory architecture for embedded MPSoC ［J］. Journal of ComputerAided Design & Computer Graphics, 2010, 22(8):13901398. (in Chinese)
［20］	Hu J,Xue C J,Tseng W C,et al. Reducing write activities on nonvolatile memories in embedded CMPs via data migration and recomputation ［C］∥Proc of the 47th ACM/IEEEDesign Automation Conference (DAC),2010:350355.
	附中文参考文献：
［5］	王颖锋,张彦周,高韬. 多核嵌入式系统总线冲突避免的节能调度综述［J］. 计算机应用研究,2014,31(4):961964.
［9］	张鹏,樊晓桠,黄小平. 基于总线访问的片上调试方法研究［J］. 计算机测量与控制,2014,22(2):510512.
［10］	董文箫,沈海斌,全励,等. 基于遗传算法的片上网络低功耗映射［J］. 浙江大学学报(理学版),2010,37(6):654656.
［13］	徐超,何炎祥,陈勇,等. 一种多核系统可靠性加强的任务调度方法［J］. 电子学报,2013,41(5):10191024.
［18］	韩乐,陈香兰,李曦. 一种降低核间通信开销的调度算法［J］. 计算机系统应用,2014,23(9):6571.
［19］	刘彩霞,石峰,薛立成,等. 层次化共享多通道便签存储器的嵌入式多核体系［J］. 计算机辅助设计与图形学学报,2010,22(8):13901398.

[1]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[2]	秦勃1，朱勇1，秦雪2. 基于Spark框架的乘潮水位计算与可视化平台[J]. J4, 2015, 37(12): 2216-2221.
[3]	乔付. 具有模糊多目标的网格任务调度算法[J]. J4, 2014, 36(09): 1644-1649.
[4]	吴俊张大方张伟鹏祝勇刚. 一个扩展的以QoS为指向的网格任务调度算法[J]. J4, 2005, 27(4): 66-67.
[5]	段中兴张德运. 实时多任务操作系统优先级反转与预防[J]. J4, 2005, 27(2): 62-64.
[6]	窦文贾焰邹鹏. 一种构造自愿计算网络的新方法[J]. J4, 2004, 26(6): 62-66.
[7]	张国俊[1] 齐广玉[2]. 并行处理系统中的一种新的任务调度算法模型[J]. J4, 2001, 23(6): 12-14.

多核嵌入式系统内联网络优化调度

Task optimization scheduling to inter-connection network
on embedded system with chip multi-processors

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献［19］

相关文章 7

编辑推荐

Metrics

本文评价

多核嵌入式系统内联网络优化调度

Task optimization scheduling to inter-connection network on embedded system with chip multi-processors

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 ［19］

相关文章 7

编辑推荐

Metrics

本文评价

Task optimization scheduling to inter-connection network
on embedded system with chip multi-processors

参考文献［19］