Parallel Scheduling of Grid Jobs on Quadcore Systems using Grouping Methods
Asian Journal of Research in Computer Science,
As Grid computing continues to make inroads into different spheres of our lives and multicore computers become ubiquitous, the need to leverage the gains of multicore computers for the scheduling of Grid jobs becomes a necessity. Most Grid schedulers remain sequential in nature and are inadequate in meeting up with the growing data and processing need of the Grid. Also, the leakage of Moore’s dividend continues as most computing platforms still depend on the underlying hardware for increased performance. Leveraging the Grid for the data challenge of the future requires a shift away from the traditional sequential method. This work extends the work of  on a quadcore system. A random method was used to group machines and the total processing power of machines in each group was computed, a size proportional to speed method is then used to estimates the size of jobs for allocation to machine groups. The MinMin scheduling algorithm was implemented within the groups to schedule a range of jobs while varying the number of groups and threads. The experiment was executed on a single processor system and on a quadcore system. Significant improvement was achieved using the group method on the quadcore system compared to the ordinary MinMin on the quadcore. We also find significant performance improvement with increasing groups. Thirdly, we find that the MinMin algorithm also gained marginally from the quadcore system meaning that it is also scalable.
- parallel scheduling
- machine grouping
- job grouping
How to Cite
Amdahl GM. Validity of the single processor approach to achieving large scale computing capabilities. AFIPS Conference Proceedings - 1967 Spring Joint Computer Conference, AFIPS 1967;483–485.
Larus J. Spending Moore’s dividend. Communications of the ACM, 2009;52(5):62–69. Available:https://doi.org/10.1145/1506409.1506425
Myhrvold, N. The next fifty years of software. ACM 97 Conference; 1997.
Wang PH, Collins JD, Chinya GN, Jiang H, Tian X, Girkar M, Yang NY, Lueh GY, Wang H. EXOCHI: Architecture and programming environment for a heterogeneous multi-core multithreaded system. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2007;156–166.
Schauer B. Discovery Guides Multicore Processors-A Necessity. In ProQuest discovery guides; 2008.
Zhuravlev S, Saez JC, Blagodurov S, Fedorova A, Prieto M. Survey of scheduling techniques for addressing shared in multicore processors. ACM Reference Format. 2012;45(4).
Dongarra J, Mathieu F, Thomas H, Mathias J, Julien L, Yves R. Hierarchical QR factorization algorithms for multi-core clusters. Parallel Computing. 2013;39(4–5):212–213.
Jin H, Jespersen D, Mehrotra P, Biswas R, Huang L, Chapman B. High performance computing using MPI and OpenMP on multi-core parallel systems. Parallel Computing. 2011;37(9):562–575.
Mustafa B, Rafiya, S, Waseem A. Parallel Implementattion of Doolittle Algorithm using Open MP for multicore machines. 2015 IEEE International Advance Computing Conference. 2015;575–578.
Abraham GT, James A, Yaacob N. Priority-grouping method for parallel multi-scheduling in Grid. Journal of Computer and System Sciences, 2015b;81(6):943–957.
Ernemann C, Hamscher V, Schwiegelshohn U, Yahyapour R, Streit A. On Advantages of Grid Computing for Parallel Job Scheduling. 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid. 2002;339–39.
Muthuvelu N, Liu J, Soe L, Venugopal S, Sulistio A, Buyya R. A dynamic job grouping-based scheduling for deploying applications with fine-grained tasks on global grids. Australian Workshop on Grid Computing and E-Research, 2005;41–48.
Selvi S, Thamarai M, Sheeba, santha K, Prabavathi, K, Kannan G. Estimating job execution time and handling missing job requirements using rough set in grid scheduling. International Conference on Computer Design and Applications. 2010;295–301.
Soni VK, Sharma R, Mishra Manoj K. Grouping-based job scheduling model in grid computing. In World Academy of Science, Engineering and Technology.2010;41.
Sharma R, Soni VK, Mishra MK, Bhuyan P, Utpal CD. An agent based dynamic resource scheduling model with FCFS-job grouping strategy in grid computing. Waset ICCGCS; 2010.
Mon TZ, Cho MM. MIPS group job scheduling model for deploying applications. International Conference on Advances in Engineering and Technology (ICAET). 2014;1234–1245.
Pinel F, Dorronsoro B, Bouvry P. Solving very large instances of the scheduling of independent tasks problem on the GPU. Journal of Parallel and Distributed Computing Parallel Distributed Computing. 2012;73(1):101–110.
Wan L, Li K, Liu J, Li K. GPU implementation of a parallel two-list algorithm for the subset-sum problem. Concurrency and Computation: Practice and Experience. 2015;27(1):119–145.
Cuomo S, De Michele P, Di Nardo E, Marcellino L. Parallel implementation of a machine learning algorithm on GPU. Journal of Parallel Programming. 2018;46(5):923–942.
Abraham GT, James A, Yaacob N. Group-based Parallel Multi-scheduler for Grid computing. Future Generation Computer Systems. 2015a;50:140–153.
Abraham GT. Group-based parallel multi-scheduling methods for grid computing. Coventry University; 2016.
Ibarra OH, Kim CE. Heuristic algorithms for scheduling independent tasks on nonidentical processors. Journal of the ACM. 1977;24(2):280–289.
Canabe M, Nesmachnow S. Parallel implementations of the MinMin heterogeneous computing scheduler in GPU. CLEI Electronic Journal. 2012;15(3):8–8.
Etminani K, Naghibzadeh M. A min-min max-min selective algorihtm for grid task scheduling. In 2007 3rd IEEE/IFIP International Conference in Central Asia on Internet, 2007;1–7.
Freund RF, Gherrity M, Ambrosius S, Campbell M, Halderman M, Hensgen D, Siegel HJ. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet. In Proceedings Seventh Heterogeneous Computing Workshop IEEE(HCW 98). 1998;184–199.
Lavanya M, Shanthi B, Saravanan S. Multi objective task scheduling algorithm based on SLA and processing time suitable for cloud environment. Computer Communications. 2020;151:183– 195.
Maheswaran M, Ali S, Siegel H, Hensgen D, Freund RF. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing. 1999;59(2):107–131.
Mishra SK, Sahoo B. Load balancing in cloud computing: A big picture. Journal of King Saud University - Computer and Information Sciences. 2020;32(2):149–158.
Zhou Z, Li F, Zhu H, Xie H, Jemal HA, Morshed UC. An improved genetic algorithm using greedy strategy toward task scheduling optimization in cloud environments. Neural Computing and Applications, 2020;32(6):1531– 1541.
Iosup A, Li H, Jan M, Anoep S, Dumitrescu C, Wolters L, Epema DHJ. The Grid Workloads Archive. Future Generation Computer Systems. 2008;24:672– 686.
Bell’s law for the birth and death of computer classes: A theory of the computer’s evolution. IEEE Solid-State Circuits Society Newsletter. 2008;13 (4):8–19.
Abstract View: 344 times
PDF Download: 209 times