非结构化异构多处理器系统中的动态任务调度建模

Hamid TABATABAEE; Mohammad Reza AKBARZADEH-T; Naser PARIZ

doi:10.1631/jzus.C1300204

Your Location：

Home >

Browse articles >

非结构化异构多处理器系统中的动态任务调度建模

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

- 非结构化异构多处理器系统中的动态任务调度建模
  Enhanced Publication
- Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems
- 信息与电子工程前沿（英文） 2014年15卷第6期页码：423-434
- Affiliations：
  
  1.Department of Computer Engineering, Islamic Azad University, Quchan Branch, Quchan, Iran
  2.Center of Excellence on Soft Computing and Intelligent Information Processing, Ferdowsi University of Mashhad, Mashhad, Iran
  3.Department of Electrical Engineering, Ferdowsi University of Mashhad, Mashhad, Iran
- Author bio：
  
  [ "Hamid TABATABAEE, E-mail: hamid.tabatabaee@Iauq.ac.ir" ]
- Funds：
- DOI：10.1631/jzus.C1300204
  中图分类号： TP301.6
- 纸质出版日期：2014-06，
  
  收稿日期：2013-08-01，
  
  修回日期：2014-04-11，
- Accepted：
Scan QR Code
非结构化异构多处理器系统中的动态任务调度建模[J]. 信息与电子工程前沿（英文）, 2014,15(6):423-434.

HAMID TABATABAEE, MOHAMMAD REZA AKBARZADEH-T, NASER PARIZ. Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems. [J]. Frontiers of information technology & electronic engineering, 2014, 15(6): 423-434.
非结构化异构多处理器系统中的动态任务调度建模[J]. 信息与电子工程前沿（英文）, 2014,15(6):423-434. DOI： 10.1631/jzus.C1300204.

HAMID TABATABAEE, MOHAMMAD REZA AKBARZADEH-T, NASER PARIZ. Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems. [J]. Frontiers of information technology & electronic engineering, 2014, 15(6): 423-434. DOI： 10.1631/jzus.C1300204.

摘要

研究目的

针对时变异构多处理器系统中关联任务调度提出一种算法。

方法提亮

该算法允许计算能力和处理器之间的连接随时间变化，考虑了链路竞争问题。引入线性切换状态空间建模范式，从系统工程学角度实现理论分析。理论分析显示了该模型在处理能力变化和连接失效情况下的鲁棒性。运用模糊决策程序处理多处理器系统中的变化。

重要结论

几个随机实验以及与近期提出的基准点分析法的比较，说明了所提算法的有效性。实验结果显示，使用此算法可以平均节省18%完工时间，且在系统规模较大时节省比例更高。

Abstract

An algorithm is proposed for scheduling dependent tasks in time-varying heterogeneous multiprocessor systems

in which computational power and links between processors are allowed to change over time. Link contention is considered in the multiprocessor scheduling problem. A linear switching-state space-modeling paradigm is introduced to enable theoretical analysis from a system engineering perspective. Theoretical analysis of this model shows its robustness against changes in processing power and link failure. The proposed algorithm uses a fuzzy decision-making procedure to handle changes in the multiprocessor system. The efficiency of the proposed algorithm is illustrated by several random experiments and comparison against a recent benchmark approach. The results show up to 18% average improvement in makespan

especially for larger scale systems.

关键词

动态任务调度模糊逻辑遗传算法非结构化环境线性切换状态空间

Keywords

Dynamic task schedulingFuzzy logicGenetic algorithmsUnstructured environmentLinear switching state space

references

A. Abraham, , , C. Grosan, , , H. Liu, , , 等. . Nature inspired meta-heuristics for grid scheduling: single and multi-objective optimization approaches. . In: Xhafa F., Abraham, A. (Eds.), Metaheuristisc for Scheduling in Distributed Computing Environments, , 2008. . 146((3):):247--272. . ..

S. Al-Sharaeh, , , B.E. Wells. . A Comparison of heuristics for list schedules using the Box-method and P-method for random digraph generation. . Proc. 28th Southeastern Symp. on System Theory, , 1996. . p.467--471. . DOI:10.1109/SSST.1996.493549http://doi.org/10.1109/SSST.1996.493549..

S.C. Cheng, , , D.F. Shiau, , , Y.M. Huang, , , 等. . Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints. . Expert Syst. Appl., , 2009. . 36((1):):852--860. . DOI:10.1016/j.eswa.2007.10.037http://doi.org/10.1016/j.eswa.2007.10.037..

C. Crăciun, , , D. Zaharie, , , F. Zamfirache. . Evolutionary task scheduling in static and dynamic environments. . Proc. IEEE Int. Joint Conf. on Computational Cybernetics and Technical Informatics, , 2010. . p.619--624. . ..

M.I. Daoud, , , N. Kharma. . A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. . J. Parall. Distr. Comput., , 2008. . 68((4):):399--409. . DOI:10.1016/j.jpdc.2007.05.015http://doi.org/10.1016/j.jpdc.2007.05.015..

X. Kong, , , J. Sun, , , W. Xu. . Permutation-based particle swarm algorithm for tasks scheduling in heterogeneous systems with communication delays. . Int. J. Comput. Intell. Res., , 2008. . 4((1):):61--70. . ..

Y.K. Kwok, , , I. Ahmad. . Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors. . IEEE Trans. Parall. Distr. Syst., , 1996. . 7((5):):506--521. . DOI:10.1109/71.503776http://doi.org/10.1109/71.503776..

Q.Q. Long, , , J. Lin, , , Z.X. Sun. . Agent scheduling model for adaptive dynamic load balancing in agent-based distributed simulations. . Simul. Modell. Pract. Theory, , 2011. . 19((4):):1021--1034. . DOI:10.1016/j.simpat.2011.01.002http://doi.org/10.1016/j.simpat.2011.01.002..

A.J. Page, , , T.J. Naughton. . Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing. . Proc. 19th IEEE Int. Parallel and Distributed Processing Symp., , 2005. . p.152--159. . DOI:10.1109/IPDPS.2005.184http://doi.org/10.1109/IPDPS.2005.184..

A.J. Page, , , T.M. Keane, , , T.J. Naughton. . Scheduling in a dynamic heterogeneous distributed system using estimation error. . J. Parall. Distr. Comput., , 2008. . 68((11):):1452--1462. . DOI:10.1016/j.jpdc.2008.07.004http://doi.org/10.1016/j.jpdc.2008.07.004..

A.J. Page, , , T.M. Keane, , , T.J. Naughton, , , 等. . Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. . J. Parall. Distr. Comput., , 2010. . 70((7):):758--766. . DOI:10.1016/j.jpdc.2010.03.011http://doi.org/10.1016/j.jpdc.2010.03.011..

R. Prodan, , , T. Fahringer. . Dynamic scheduling of scientific workflow applications on the grid: a case study. . Proc. 20th ACM Symp. on Applied Computing, , 2005. . p.687--694. . DOI:10.1145/1066677.1066835http://doi.org/10.1145/1066677.1066835..

A.Z.S. Shahul, , , O. Sinnen. . Scheduling task graphs optimally with A*. . J. Supercomput., , 2010. . 51((1):):310--332. . ..

K. Shin, , , M. Cha, , , M. Jang, , , 等. . Task scheduling algorithm using minimized duplications in homogeneous systems. . J. Parall. Distr. Comput., , 2008. . 68((8):):1146--1156. . DOI:10.1016/j.jpdc.2008.04.001http://doi.org/10.1016/j.jpdc.2008.04.001..

O. Sinnen. . Task scheduling for parallel systems (1st Ed.). . JohnWiley & Sons-Interscience, , 2007. ..

O. Sinnen, , , L.A. Sousa, , , F.E. Sandnes. . Toward a realistic task scheduling model. . IEEE Trans. Parall. Distr. Syst., , 2006. . 17((3):):263--275. . DOI:10.1109/TPDS.2006.40http://doi.org/10.1109/TPDS.2006.40..

S.N. Sivanandam, , , P. Visalakshi. . Dynamic task scheduling with load balancing using hybrid particle swarm optimization. . Int. J. Open Probl. Comput. Math., , 2009. . 2((3):):475--488. . ..

H. Tabatabaee-Yazdi, , , M.R. Akbarzadeh-T. . The linear switching state space: a new modeling paradigm for task scheduling problems. . Int. J. Innov. Comput. Inform. Contr., , 2013. . 9((4):):1651--1677. . ..

M. Yoo. . Real-time task scheduling by multiobjective genetic algorithm. . J. Syst. Softw., , 2009. . 82((4):):619--628. . DOI:10.1016/j.jss.2008.08.039http://doi.org/10.1016/j.jss.2008.08.039..

M. Yoo, , , M. Gen. . Scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm in heterogeneous multiprocessors system. . Comput. Oper. Res., , 2007. . 34((10):):3084--3098. . DOI:10.1016/j.cor.2005.11.016http://doi.org/10.1016/j.cor.2005.11.016..

浏览量

Downloads

CSCD

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

Submit

工具集

关联资源

A fuzzy integrated congestion-aware routing algorithm for network on chip

Bio-inspired heuristics hybrid with interior-point method for active noise control systems without identification of secondary path

A dynamic signal coordination control method for urban arterial roads and its application

A framework for analysis of extended fuzzy logic