Compile-Time Task Scheduling in Computer Networks Using Non-Preemptive Processing and Time Quantum

Nadhir Ben Halima

doi:10.15866/irecap.v5i3.5766

Compile-Time Task Scheduling in Computer Networks Using Non-Preemptive Processing and Time Quantum

Nadhir Ben Halima^(1*)

^(*) Corresponding author

Authors' affiliations

DOI: https://doi.org/10.15866/irecap.v5i3.5766

Abstract

Efficient parallel processing can be obtained with powerful scheduling algorithms. An efficient and reliable scheduling algorithm is proposed. The algorithm is called Time Quantum Task Scheduling (TQTS). In TQTS the processing Maskespan is divided into non-overlapping cycles. Each cycle is defined by specific time quantum. The tasks can be assigned to any of the available processors in specific cycle. This approach obtains more organized task scheduling compared to previous approaches. In addition, free time slots can be used by other applications running on the same parallel system. Results showed that the idle time of each processor is reduced and the algorithm is more powerful and efficient than other related approaches.
Copyright © 2015 Praise Worthy Prize - All rights reserved.

Keywords

Parallel Algorithms; Task Scheduling; Precedence Graph; Task Graphs; Static Scheduling

Full Text:

PDF

References

Hsu, T.S., Lee, J., Lopez, D.R., and Royce, W., “Task Allocation on a Network of Processors,” IEEE Transaction on Computers, Vol. 49, No. 12, pp. 1339-1353, December 2000.
http://dx.doi.org/10.1109/12.895858

Dertouzos, M.L., and Mok, A.K., "Multiprocessor on-line scheduling of hard-real-time tasks", IEEE Trans. on Software Engineering, 15 (12) (1989) 1497-1506.
http://dx.doi.org/10.1109/32.58762

Sarkar, V., Partitioning and Scheduling Parallel Programs for Multiprocessors, The M.I.T Press, Cambridge, MA, 1989.

Hamid Arabnejad and Jorge G. Barbosa, “List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table” IEEE Transactions on Parallel and Distributed Systems, Vol. 25, No.3, March 2014
http://dx.doi.org/10.1109/tpds.2013.57

H. Topcuoglu, S. Hariri, and M. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 3, pp. 260-274, Mar. 2002.
http://dx.doi.org/10.1109/71.993206

Yuming Xu, Kenli Li, Tung Truong Khac, Meikang Qiu, “A Multiple Priority Queueing Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems”, IEEE 14th International Conference on High Performance Computing and Communications, pp. 639-646, 2012
http://dx.doi.org/10.1109/hpcc.2012.91

Fatos Xhafa, Javier Carretero, “A Tabu Search Algorithm For Scheduling Independent Jobs In Computational Grids” Computing and Informatics, Vol. 28, 2009, 1001–1014, 2009

Wei-Neng Chen, “An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem With Various QoS Requirements”, IEEE transactions on system, man and cybernetics, part C: applications and reviews, Vol. 39, NO. 1, pp. 29-43, 2009.
http://dx.doi.org/10.1109/tsmcc.2008.2001722

C. Boeres, J.V. Filho, and V.E.F. Rebello, “A Cluster-Based Strategy for Scheduling Task on Heterogeneous Processors,” Proc. 16th Symp. Computer Architecture and High Performance Computing, pp. 214-221, 2004.
http://dx.doi.org/10.1109/sbac-pad.2004.1

B. Cirou and E. Jeannot, “Triplet: A Clustering Scheduling Algorithm for Heterogeneous Systems,” Proc. Int’l Conf. Parallel Processing Workshops, pp. 231-236, 2001.
http://dx.doi.org/10.1109/icppw.2001.951956

T. Hagras and J. Jane_cek, “A Simple Scheduling Heuristic for Heterogeneous Computing Environments,” Proc. Second Int’l Symp. Parallel and Distributed Computing, pp. 104-110, 2003.
http://dx.doi.org/10.1109/ispdc.2003.1267650

Krishnamoorthy, V., and Efe, K., "Task scheduling with and without communication delays: A unified approach", European Journal of Operational Research, 89 (1996) 366-379.
http://dx.doi.org/10.1016/0377-2217%2894%2900255-x

Refbacks

There are currently no refbacks.

Username
Password
Remember me