片上网络异构多核系统任务调度与映射

杨鹏飞; 王泉

doi:10.7652/xjtuxb201506012

您当前的位置：

首页 >

文章列表页 >

片上网络异构多核系统任务调度与映射

更新时间：2025-07-09

- 片上网络异构多核系统任务调度与映射
- An Effective Scheduling and Mapping Algorithm of Tasks for Heterogeneous NoC-Based MPSoC
- 西安交通大学学报 2015年49卷第6期页码：72-76+125
- 作者机构：
  
  西安电子科技大学计算机学院,西安,710071
- 作者简介：
- 基金信息：
  
  : 2014-10-21。作者简介: 杨鹏飞(1985—),男,博士生;王泉(通信作者),男,教授,博士生导师。基金项目: 国家自然科学基金资助项目(61474087)
- DOI：10.7652/xjtuxb201506012
  中图分类号： TN409
- 网络首发：2015-06-10，
  
  纸质出版：2015
- 稿件说明：
移动端阅览
杨鹏飞, 王泉. 片上网络异构多核系统任务调度与映射[J]. 西安交通大学学报, 2015,49(6):72-76+125.

An Effective Scheduling and Mapping Algorithm of Tasks for Heterogeneous NoC-Based MPSoC[J]. 2015, 49(6): 72-76+125.
杨鹏飞, 王泉. 片上网络异构多核系统任务调度与映射[J]. 西安交通大学学报, 2015,49(6):72-76+125. DOI： 10.7652/xjtuxb201506012.

An Effective Scheduling and Mapping Algorithm of Tasks for Heterogeneous NoC-Based MPSoC[J]. 2015, 49(6): 72-76+125. DOI： 10.7652/xjtuxb201506012.

摘要

针对传统任务模型包含有效信息少

任务调度算法效率低、效果差的问题

设计了新的任务模型

提出了一种改进的粒子群算法(optimized particle swarm optimization

oPSO)。新模型增加了对任务类型及任务间迁移成本、计算单元类型及其运行成本等特性的描述。通过分析任务调度问题的需求

制定了oPSO算法的编解码方案

设定了算法各个关键部分参数及计算方法

并解决了粒子群算法(PSO)在任务调度前期收敛速度过快、后期易陷入局部最优的问题。在不同任务规模下分别对遗传算法(GA)、PSO以及oPSO算法进行调度仿真对比

当IP核数目为100左右时

oPSO算法较GA算法和PSO算法运行时间至少缩短10%

系统功耗至少降低15%

实验结果表明:oPSO算法调度效果明显优于其他算法

且各节点上功耗更为均衡

适用于解决任务调度问题。

Abstract

A new task model is designed and an optimized particle swarm optimization(oPSO)algorithm is proposed to solve the problem that the traditional task DAG model contains less information and the existing task scheduling algorithms based on the model are of inefficiency. The new model adds the description of task type and some real inter-task relations such as transfer cost of the task

the type of processing element(PE)and its running cost. After the requirements of task scheduling and mapping are analyzed

a new scheme of coding and decoding is formulated

key parameters of the algorithm and their calculation are proposed

and the shortcomings of the particle swarm optimization algorithm such as poor local search capacity in the early period and being easily trapped into local optima in the late period of the algorithm are overcome. Simulations and comparisons with the GA and PSO algorithms under different IP scales show that when the number of IPs is about 100

the execution time and the power consumption of the oPSO algorithm reduce at least 10% and 15%

respectively

the scheduling effect of oPSO is much better than those of other algorithms

and the energy consumption on each IPs is balanced. Thus it can be concluded that the proposed algorithm is applicable for the solution of task scheduling.

关键词

Keywords

references

ADDO-QUAYE C. Thermal-aware mapping and placement for 3-D NoC designs [C]∥Proceedings of the 2005 IEEE International SOC Conference. Piscataway, NJ, USA: IEEE, 2005: 25-28.

SINGH A K, WU Jigang, PRAKASH A, et al. Mapping algorithms for NoC-based heterogeneous MPSoC platforms [C]∥Proceedings of the 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools. Piscataway, NJ, USA: IEEE, 2009: 133-140.

TOPCUOGLU H, HARIRI S, WU Minyou. Performance-effective and low-complexity task scheduling for heterogeneous computing [J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.

DAOUD M I, KHARMA N. Efficient compile-time task scheduling for heterogeneous distributed computing systems [C]∥Proceedings of the 12th International Conference on Parallel and Distributed Systems. Piscataway, NJ, USA: IEEE Computer Society, 2006: 1-9.

WU Minyou, GAJSKI D D. Hypertool: a programming aid for message-passing systems [J]. IEEE Transactions on Parallel and Distributed Systems, 1990, 1(3): 330-343.

CHUNG Y C, RANKA S. Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors [C]∥Proceedings of the Supercomputing '92. Piscataway, NJ, USA: IEEE, 1992: 512-521.

ANMAD I, KWORK Y K. A new approach to scheduling parallel programs using task duplication [C]∥Proceedings of the International Conference on Parallel Processing. Piscataway, NJ, USA: IEEE, 1994: 47-51.

SAYUTI M N S M, INDRUSIAK L S. Real-time low-power task mapping in networks-on-chip [C]∥Proceedings of the 2013 IEEE Computer Society Annual Symposium on VLSI. Piscataway, NJ, USA: IEEE, 2013: 14-19.

FERRANDI F, LANZI P L, PILATO C, et al. Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(6): 911-924.

SILVA L, NEDJAH N, MOURELLE L. ACO approach in static routing for network-on-chips with 3D mesh topology [C]∥Proceedings of the 2013 IEEE 4th Latin American Symposium on Circuits and Systems. Piscataway, NJ, USA: IEEE, 2013: 1-4.

HOFFMANN R, RAUBE T. Dynamic task scheduling and load balancing on cell processors [C]∥Proceedings of the 2010 18th Euromicro International Conference on Parallel, Distributed and Network-Based Processing. Piscataway, NJ, USA: IEEE Computer Society, 2010: 205-212.

SIDHU M S, THULASIRAMAN P. A load-rebalance PSO heuristic for task matching in heterogeneous computing systems [C]∥Proceedings of the 2013 IEEE Symposium on Swarm Intelligence. Piscataway, NJ, USA: IEEE, 2013: 180-187.

AMOLD O, FETTWEIS G. Power aware heterogeneous MPSoC with dynamic task scheduling and increased data locality for multiple applications [C]∥Proceedings of the 2010 International Conference on Embedded Computer Systems. Piscataway, NJ, USA: IEEE, 2010: 110-117.

YANG Pengfei, WANG Quan. Effective task scheduling and IP mapping algorithm for heterogeneous NoC-based MPSoC [J]. Mathematical Problems in Engineering, 2014, 2014: 202748.

DICK R P, RHODES D L, WOLF W. TGFF: task graphs for free [C]∥Proceedings of the 6th International Workshop on Hardware/Software Codesign. Piscataway, NJ, USA: IEEE Computer Society, 1998: 97-101.

浏览量

下载量

CSCD

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

提交

工具集

关联资源

电子级超纯氮深冷空分流程节能优化研究

采用机器学习的大规模并行程序I/O性能建模与预测方法

电动车辆间接热系统快速除湿响应迟滞机理及优化控制策略

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建