Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems

Hamid TABATABAEE; Mohammad Reza AKBARZADEH-T; Naser PARIZ

doi:10.1631/jzus.C1300204

Your Location：

Home >

Browse articles >

Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems

Computer & Automation | Updated：2022-05-19

- Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems
- 非结构化异构多处理器系统中的动态任务调度建模
- Frontiers of Information Technology & Electronic Engineering Vol. 15, Issue 6, Pages: 423-434(2014)
- 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
  CLC： TP301.6
- Received：01 August 2013，
  
  Revised：2014-;4-11，
  
  Published：2014-06
- Accepted：
Scan QR Code
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：

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

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.493549 http://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.037 http://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.015 http://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.503776 http://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.002 http://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.184 http://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.004 http://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.011 http://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.1066835 http://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.001 http://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.40 http://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.039 http://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.016 http://doi.org/10.1016/j.cor.2005.11.016 . .

Views

166

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

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

Related Author

Shahrouz YASREBI

Akram REZA

Mohammad NIKRAVAN

Seena VAZIFEDAN

Muhammad Asif Zahoor RAJA

Muhammad Saeed ASLAM

Naveed Ishtiaq CHAUDHARY

Wasim Ullah KHAN

Related Institution

Department of Computer Engineering, Shahr-e-Qods Branch, Islamic Azad University, Tehran

Department of Computer Architecture, Science and Research Branch, Islamic Azad University, Tehran

Department of Electrical Engineering, COMSATS Institute of Information Technology, Attock Campus, Attock

Pakistan Institute of Engineering and Applied Sciences

Department of Electronic Engineering, International Islamic University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰