[1]LIU Zheng.Research on STDS algorithm designing based on dynamic task scheduling[J].CAAI Transactions on Intelligent Systems,2015,10(2):324-332.[doi:10.3969/j.issn.1673-4785.201503013]
Copy

Research on STDS algorithm designing based on dynamic task scheduling

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 10 Number of periods: 2015 2 Page number: 324-332 Column: 学术论文—机器学习 Public date: 2015-04-25
Title:
Research on STDS algorithm designing based on dynamic task scheduling
Author(s):
LIU Zheng
College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
Keywords:
dynamic task scheduling; load balancing; scheduling granularity; waiting time; heterogeneous multi-core system
CLC:
TP316.4
DOI:
10.3969/j.issn.1673-4785.201503013
Abstract:
Efficient task scheduling is the key for multi-core systems to achieve high performance. However, most of the existing multi-core researches on task scheduling algorithms focus on algorithm optimization and load balancing under the static scheduling rather than dynamic scheduling and dynamic load balancing. Scalable task duplication based scheduling (STDS) is a new dynamic-balanced algorithm based on core load balancing. STDS was put forward specifically for dynamic scheduling and integrating the characteristics of heterogeneous multi-core. It shortens scheduling time by reasonably setting the scheduling granularity and reducing the frequency of scheduling. STDS sets the maximum and minimum ranges of the kernel load according to the different processing performance of each core of the heterogeneous multi-core processor, therefore controlling the core load at the same level and achieving the effect of load balance. The wait time of task and communications between tasks and kernel load will be considered together to pick up the most appropriate task during scheduling. The importance of each element can be adjusted by assigning another value to the real-time factor and load factor enabling it to adapt to various environment. The experimental results verified that the STDS algorithm is more efficient in the system with the most kernels. It also keeps a good load balance while maintaining the speed of task execution processing.
References:
[1] GENG X, XU G, ZHANG Y. Dynamic load balancing scheduling model based on multi-core processor[C]//2010 Fifth International Conference on Frontier of Computer Science and Technology (FCST).[S.l],2010: 398-403.
[2] GRAY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: W H Freeman and Company, 1979: 92-115.
[3] JIN H, CHEN H, CHEN J, et al. Real-time strategy and practice in service grid[C]//Proceedings of the 28th Annual International on Computer Software and Applications Conference, 2004. 2004: 161-166.
[4] HE X S, SUN X H,VON LASZEWSKI G. A QoS guided scheduling algorithm for grid computing[J]. Journal of Computer Science and Technology, 2003,18(4): 442-451.
[5] FREUND R F, GHERRITY M, AMBROSIUS S, et al. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet[C]//Proceedings on Heterogeneous Computing Workshop., 1998: 184-199.
[6] ARMSTRONG R, HENSGEN D, KIDD T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions[C]//Proceedings on Heterogeneous Computing Workshop., 1998: 79-87.
[7] 石威, 郑纬民. 相关任务图的均衡动态关键路径调度算法[J]. 计算机学报, 2001, 24(9): 991-997.SHI Wei, ZHENG Weimin. The balanced dynamic critical path scheduling algorithm of dependent task graph[J]. Chinese Journal of Computers, 2001, 24(9): 991-997.
[8] 李仁发, 刘彦, 徐成. 多处理器片上系统任务调度研究进展评述[J]. 计算机研究与发展, 2008, 45(9): 1620-1629.LI Renfa, LIU Yan, XU Cheng. A survey of task scheduling research progress on multiprocessor system-on-chip[J]. Journal of Computer Research and Development, 2008, 45(9): 1620-1629.
[9] 耿晓中. 基于多核分布式环境下的任务调度关键技术研究[D]. 吉林: 吉林大学, 2013:.GENG Xiaozhong. Research on key techniques of task scheduling based on multi-core distributed environment[D]. Jilin: Jilin University, 2013.
[10] 徐雨明,李肯立. 异构系统中DAG任务调度的双螺旋结构遗传算法[J]. 计算机研究与发展,2014,51(6): 1240-1252.XU Yuming, LI Kenli. A structure genetic algorithm for task scheduling double-helix on heterogeneous computing systems [J]. Journal of Computer Research and Development, 2014, 51(6): 1240-1252.
[11] VAIDYA V G, RANADIVE P, SAH S. Dynamic scheduler for multi-core systems[C]// International Conference on Software Technology and Engineering, 2010 2nd. Puerto Rico: IEEE, 2010, 1: V1-13-V1-16.
[12] 陈锐忠,齐德昱,林伟伟.一种面向非对称多核处理器的综合性调度算法. 软件学报, 2013, 24(2): 34-3357.CHEN Ruozhong, QI Deyu, LIN Weiwei. Comprehensive scheduling algorithm for asymmetric multi-core processors[J]. Journal of Software, 2013, 24(2): 34-3357.
[12] 邓晓衡, 卢锡城, 王怀民. iVCE中基于可信评价的资源调度研究[J]. 计算机学报, 2007, 30: 1750-1762.DENG Xiaoheng, LU Xicheng, WANG Huaimin. Study on trust evaluation based resource scheduling in iVCE[J]. Chinese Journal of Computers, 2007, 30: 1750-1762.
[12] KWOK Y K, AHMAD I. Benchmarking the task graph scheduling algorithms[C]//Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International... and Symposium on Parallel and Distributed Processing 1998. IEEE, 1998: 531-537.
[12] FORSGREN D, ESKILSON J, CHRISTENSSON M, et al. Simics:a full system simulation platform[J]. IEEE Computer, 2002, 35(2): 50-58.
Similar References:

Memo

-

Last Update: 2015-06-15

Copyright © CAAI Transactions on Intelligent Systems