An Effective Scheduling and Mapping Algorithm of Tasks for Heterogeneous NoC-Based MPSoC

doi:10.7652/xjtuxb201506012

您当前的位置：

首页 >

文章列表页 >

An Effective Scheduling and Mapping Algorithm of Tasks for Heterogeneous NoC-Based MPSoC

更新时间：2025-07-09

- An Effective Scheduling and Mapping Algorithm of Tasks for Heterogeneous NoC-Based MPSoC
- Vol. 49, Issue 6, Pages: 72-76+125(2015)
- 作者机构：
  
  西安电子科技大学计算机学院,西安,710071
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201506012
  CLC： TN409
- Online First：10 June 2015，
  
  Published：2015
- 稿件说明：
移动端阅览
An Effective Scheduling and Mapping Algorithm of Tasks for Heterogeneous NoC-Based MPSoC[J]. 2015, 49(6): 72-76+125.
DOI：

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Study on the Thermodynamic Properties in the Anomalous Region of Supercritical Water

Influence of Structural Parameters on the Summer Operational Characteristics of a Three-Tower-in-One Indirect Air-Cooling System

A Structure-Semantics-Residual Collaborative Image Compression Framework：Towards Privacy Protection and High-Fidelity Reconstruction

A Fast Calculation Method for Thermal Flow Fields in Transformer Windings Based on PI-DeepONet

Related Author

No data

Related Institution

No data

⁰