Analysis of List scheduling for Dependent Task

Sunita Kushwaha*, Sanjay Kumar **
* Ph.D. Scholar, School of Studies of Computer Science and Information Technology, Pt. Ravishankar Shukla University, Raipur, Chhattisgarh, India.
** Professor and Head, Department of Computer Science, Pt. Ravishankar Shukla University, Raipur, Chhattisgarh, India.
Periodicity:December - February'2018
DOI : https://doi.org/10.26634/jit.7.1.14093

Abstract

This is an era of High Performance Computing (HPC), in which more computing elements work together in parallel to enhance the computing power. Scheduling plays an important role to enhance the computing power in the multiprocessor environment. Scheduling of the tasks onto the machines of a multiprocessor environment has generally become a NP-complete (nondeterministic polynomial time) problem. Heuristic is a better way to solve the NP-complete problems. List heuristic scheduling is one of the best and widely used heuristic to use in a homogeneous multiprocessor environment. However, to achieve parallelism in multiprocessor environment is not so easy; it is influenced by various factors such as dependencies, system environment etc. In this paper, some list scheduling algorithms for dependent task sets are studied and their performance are evaluated on the basis of makespan. The EST (Earliest Processing Time) scheduling algorithm performs better and takes less makespan as compared to other scheduling algorithms namely LPT (Longest Processing Time), SPT (Shortest Processing Time) and ECT (Earliest Completion Time). The graphs show that EST performs better when the number of processes increases, than other algorithms.

Keywords

Direct Acyclic Graph, List Scheduling, Makespan, Independent Taskset, Dependent Taskset.

How to Cite this Article?

Kushwaha , S., & Kumar , S. (2018). Analysis of List Scheduling for Dependent Task. i-manager’s Journal on Information Technology, 7(1), 24-27. https://doi.org/10.26634/jit.7.1.14093

References

[1]. Andersson, B. (2003). Static-priority Scheduling on Multiprocessors (Doctoral dissertation, Chalmers University of Technology).
[2]. Braun, T. D., Siegel, H. J., Beck, N., Bölöni, L. L., Maheswaran, M., Reuther, A. I., ... & Freund, R. F. (2001). A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61(6), 810-837.
[3]. Chapin, S. J., & Weissman, J. B. (2002). Distributed and Multiprocessor Scheduling. Electrical Engineering and Computer Science. Retrieved from https://surface. syr.edu/eecs/40
[4]. Devi, U. C., & Anderson, J. H. (2006). Soft real-time scheduling on multiprocessors. (Doctoral dissertation University of North Carolina at Chapel Hill).
[5]. Funk, S. H. (2004). EDF scheduling on heterogeneous multiprocessors. (Doctoral dissertation University of North Carolina at Chapel Hill).
[6]. Garshasbi, M. S., & Effatparvar, M. (2013). Tasks scheduling on parallel heterogeneous multi-processor systems using genetic algorithm. International Journal of Computer Applications, 61(9). 23-27.
[7]. Hagras, T., & Jane?ek, J. (2003). Static vs. Dynamic List-Scheduling Per formance Comparison. Acta Polytechnica, 43(6), 16-21.
[8]. Ilavarasan, E., & Thambidurai, P. (2007). Low complexity performance effective task scheduling algorithm for heterogeneous computing environments. Journal of Computer Sciences, 3(2), 94-103.
[9]. Kumar, S. (2007, December). Mathematical modelling and simulation of a buffered Fault Tolerant Double Tree Network. In Advanced Computing and Communications, 2007. ADCOM 2007. International Conference on (pp. 422-433). IEEE.
[10]. Lee, Y. C., & Zomaya, A. Y. (2011). Energy conscious scheduling for distributed computing systems under different operating conditions. IEEE Transactions on Parallel and Distributed Systems, 22(8), 1374-1381.
[11]. Maheswaran, M., Ali, S., Siegel, H. J., Hensgen, D., &Freund, R. F. (1999). Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing, 59(2), 107-131.
[12]. Park, G. L., Shirazi, B., Marquis, J., & Choo, H. (1997, August). Decisive path scheduling: a new list scheduling method. In Parallel Processing, 1997, Proceedings of the 1997 International Conference on (pp. 472-480). IEEE.
[13]. Pathan, R. M. (2012). Three Aspects of Real-Time Multiprocessor Scheduling: Timeliness, Fault Tolerance, Mixed Criticality (Doctoral dissertation, Chalmers University of Technology).
[14]. Rusanova, O., & Korochkin, A. (1999, September). Scheduling problems for parallel and distributed systems. In ACM SIGAda Ada Letters (Vol. 19 No. 3, pp. 195-201). ACM.
[15]. Singh, K., Alam, M., & Sharma, S. K. (2015). A survey of static scheduling algorithm for distributed computing system. International Journal of Computer Applications, 129(2), 25-30.
[16]. Yang, J., Xu, H., Pan, L., Jia, P., Long, F., & Jie, M. (2011). Task scheduling using Bayesian optimization algorithm for heterogeneous computing environments. Applied Soft Computing, 11(4), 3297-3310.
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
USD EUR INR USD-ROW
Pdf 35 35 200 20
Online 35 35 200 15
Pdf & Online 35 35 400 25

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.