A Parallel Scheduling Algorithm of Multi-Core Processor Based on Task Clustering and Duplication

Abstract:

This thesis presents a parallel scheduling algorithm of multi-core processor based on task clustering and duplication. This algorithm, using the strategy of task clustering, gives priority to the operation of thread nodes of the same process on the same processor and effectively reduces time complexity of task scheduling. In order to avoid the unbalanced task load on the processors, it will employ their ultimate values to control the load. Finally, for achieving the optimal time of task operations, this algorithm, with the adoption of task duplication strategy, looks for the key tasks and duplicates them so as to fully utilize the resources of each core on the processor and improve the efficiency of task scheduling. The analysis of the experiment shows that, with the increasing number of task scheduling, the time of task operation of this algorithm is always the least.

• Periodical: Advanced Materials Research (Volumes 546-547)
• Pages: 1421-1426
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.546-547.1421
• Online since: July 2012
• Authors: Xiao Hui Ma
• Keywords: Multi-Core Processor, Scheduling, Task Clustering, Task Duplication

References

[1] LIU YI, ZHANG XIN, LI HE, et al, Allocating tasks in multi-core processor based parallel system, Proceedings of the 2007 IFIP International Conference on Network and Parallel Computing Workshops, Washington DC, IEEE Computer Society, 2007, pp.748-753.

DOI: 10.1109/npc.2007.26

[2] ZHANG Guojun, QI Guangyu. A New Model of Task Algorithm Scheduling in Parallel Processing Systems [J]. Computer Engineering & Science, 2001, 23(6): 12-14.

[3] Tong Xiaonian, He Bingjiao, Shu Wanneng and Yu Cheng, A new task scheduling algorithm based on parallel prlcessing systems, Journal of South-Central University for Nationalities (Nat. Sci. Edition), vol. 26, No. 2, Jun. 2007, pp.72-74.

[4] YUAN Yun and SHAO Shi, Tasks scheduling algorithm for parallel system with multi-core processor, Computer Application, vol. 28, Dec. 2008, pp.280-282.

[5] Tao Xie and Xiao Qin, Scheduling Security-Critical Real-Time applications on clusters, IEEE Trans on Computers, 2006, 55(7), pp.864-879.

DOI: 10.1109/tc.2006.110

[6] Yu-Kong K, Ahmad I, Benchmarking and comparison of the task graph scheduling algorithms, Parallel and Distributed Computing, 1999, 59(2), pp.381-422.

DOI: 10.1006/jpdc.1999.1578

[7] YIN Yang-mei, XU Cheng and LIU Yan, Improved real-time task scheduling algorithms for heterogeneous multiprocessors, Application Research of Computers, vol. 27, No. 4, Apr 2010, pp: 1236-1238.

[8] HE Kun, ZHAO Yong and HUANG Wen-Qi, A Clustering and Scheduling Algorithm Based On Task Duplication, Chinese Journal of Computers, vol. 31, No. 5, May 2008, pp: 733-740.

DOI: 10.3724/sp.j.1016.2008.00733

[9] Bansal S, Kumar P and Singh K, An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems, IEEE Transactions on Parallel and Distributed Systems, 2003, 14(6), pp: 533-544.

DOI: 10.1109/tpds.2003.1206502