Full Text:   <3974>

Summary:  <2117>

CLC number: TP301.6

On-line Access: 2014-06-06

Received: 2013-08-01

Revision Accepted: 2014-01-17

Crosschecked: 2014-04-11

Cited: 1

Clicked: 9610

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

Journal of Zhejiang University SCIENCE C 2014 Vol.15 No.6 P.423-434

http://doi.org/10.1631/jzus.C1300204


Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems


Author(s):  Hamid Tabatabaee, Mohammad Reza Akbarzadeh-T, Naser Pariz

Affiliation(s):  Department of Computer Engineering, Islamic Azad University, Quchan Branch, Quchan, Iran; more

Corresponding email(s):   hamid.tabatabaee@Iauq.ac.ir

Key Words:  Dynamic task scheduling, Fuzzy logic, Genetic algorithms, Unstructured environment, Linear switching state spaceAn erratum to this article can be found at doi:10.1631/jzus.C13e0204


Hamid Tabatabaee, Mohammad Reza Akbarzadeh-T, Naser Pariz. Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems[J]. Journal of Zhejiang University Science C, 2014, 15(6): 423-434.

@article{title="Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems",
author="Hamid Tabatabaee, Mohammad Reza Akbarzadeh-T, Naser Pariz",
journal="Journal of Zhejiang University Science C",
volume="15",
number="6",
pages="423-434",
year="2014",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1300204"
}

%0 Journal Article
%T Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems
%A Hamid Tabatabaee
%A Mohammad Reza Akbarzadeh-T
%A Naser Pariz
%J Journal of Zhejiang University SCIENCE C
%V 15
%N 6
%P 423-434
%@ 1869-1951
%D 2014
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1300204

TY - JOUR
T1 - Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems
A1 - Hamid Tabatabaee
A1 - Mohammad Reza Akbarzadeh-T
A1 - Naser Pariz
J0 - Journal of Zhejiang University Science C
VL - 15
IS - 6
SP - 423
EP - 434
%@ 1869-1951
Y1 - 2014
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1300204


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.

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

研究目的:针对时变异构多处理器系统中关联任务调度提出一种算法。
方法提亮:该算法允许计算能力和处理器之间的连接随时间变化,考虑了链路竞争问题。引入线性切换状态空间建模范式,从系统工程学角度实现理论分析。理论分析显示了该模型在处理能力变化和连接失效情况下的鲁棒性。运用模糊决策程序处理多处理器系统中的变化。
重要结论:几个随机实验以及与近期提出的基准点分析法的比较,说明了所提算法的有效性。实验结果显示,使用此算法可以平均节省18%完工时间,且在系统规模较大时节省比例更高。

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

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Abraham, A., Grosan, C., Liu, H., et al., 2008. 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, 146(3):247-272.

[2]Al-Sharaeh, S., Wells, B.E., 1996. 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, p.467-471.

[3]Cheng, S.C., Shiau, D.F., Huang, Y.M., et al., 2009. Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints. Expert Syst. Appl., 36(1):852-860.

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

[5]Daoud, M.I., Kharma, N., 2008. A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. J. Parall. Distr. Comput., 68(4):399-409.

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

[7]Kwok, Y.K., Ahmad, I., 1996. Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors. IEEE Trans. Parall. Distr. Syst., 7(5):506-521.

[8]Long, Q.Q., Lin, J., Sun, Z.X., 2011. Agent scheduling model for adaptive dynamic load balancing in agent-based distributed simulations. Simul. Modell. Pract. Theory, 19(4):1021-1034.

[9]Page, A.J., Naughton, T.J., 2005. Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing. Proc. 19th IEEE Int. Parallel and Distributed Processing Symp., p.152-159.

[10]Page, A.J., Keane, T.M., Naughton, T.J., 2008. Scheduling in a dynamic heterogeneous distributed system using estimation error. J. Parall. Distr. Comput., 68(11):1452-1462.

[11]Page, A.J., Keane, T.M., Naughton, T.J., et al., 2010. Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. J. Parall. Distr. Comput., 70(7):758-766.

[12]Prodan, R., Fahringer, T., 2005. Dynamic scheduling of scientific workflow applications on the grid: a case study. Proc. 20th ACM Symp. on Applied Computing, p.687-694.

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

[14]Shin, K., Cha, M., Jang, M., et al., 2008. Task scheduling algorithm using minimized duplications in homogeneous systems. J. Parall. Distr. Comput., 68(8):1146-1156.

[15]Sinnen, O., 2007. Task scheduling for parallel systems (1st Ed.). John Wiley & Sons-Interscience.

[16]Sinnen, O., Sousa, L.A., Sandnes, F.E., 2006. Toward a realistic task scheduling model. IEEE Trans. Parall. Distr. Syst., 17(3):263-275.

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

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

[19]Yoo, M., 2009. Real-time task scheduling by multiobjective genetic algorithm. J. Syst. Softw., 82(4):619-628.

[20]Yoo, M., Gen, M., 2007. Scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm in heterogeneous multiprocessors system. Comput. Oper. Res., 34(10):3084-3098.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE