Design Of A Job Scheduling Data Structure For Grid Resources

Ardi Pujiyanta; Fiftin Noviyanto

doi:10.24853/jurtek.16.2.283-290

Design Of A Job Scheduling Data Structure For Grid Resources

Ardi Pujiyanta, Fiftin Noviyanto

Abstract

Essentially, Grid computing is an infrastructure that offers high-speed computing capacity in a distributed system by utilizing geographically distributed resources. Grid resources are owned by different organizations and have their own policies and access models. Scheduling future jobs in a grid system requires a data structure capable of handling parallel jobs, known as the Message Passing Interface (MPI). A data structure model needs to be proposed to minimize search time, and efficiently add and remove MPI jobs. Data structures that support future scheduling models will improve resource utilization efficiency. This research proposes a data structure capable of handling future MPI job scheduling to increase resource utilization. Experimental results on the data structure show that the average memory consumption of the FCFS-LRH data structure is lower than that of FCFS and FCFS-EDS. For average empty timeslot searches, FCFS-LRH is faster than FCFS-EDS but slower than FCFS. The average data insertion speed of FCFS-LRH is faster than that of FCFS-EDS.

Keywords

MPI jobs, grid resources, data structures.

Full Text:

PDF

References

M. Singh, “An Overview of Grid Computing,” Proc. - 2019 Int. Conf. Comput. Commun. Intell. Syst. ICCCIS 2019, vol. 2019-Janua, pp. 194–198, 2019, doi: 10.1109/ICCCIS48478.2019.8974490.

R. Nawaz, W. Y. Zhou, M. U. Shahid, and O. Khalid, “A qualitative comparison of popular middleware distributions used in grid computing environment,” 2nd Int. Conf. Comput. Commun. Syst. ICCCS 2017, pp. 36–40, 2017, doi: 10.1109/CCOMS.2017.8075262.

L. Feng and G. Wei-Wei, “Research and Design of Task Scheduling Method Based on Grid Computing,” Proc. - 2nd Int. Conf. Smart City Syst. Eng. ICSCSE 2017, pp. 188–192, 2017, doi: 10.1109/ICSCSE.2017.54.

R. Umar, A. Agarwal, and C. R. Rao, “Advance Planning and Reservation in a Grid System,” Commun. Comput. Inf. Sci., vol. 293 PART 1, pp. 161–173, 2012, doi: 10.1007/978-3-642-30507-8_15.

A. Sulistio et al., “An Adaptive Scoring Job Scheduling algorithm for grid computing,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 5, no. 1, pp. 68–72, 2015, doi: 10.1177/1094342006068414.

A. Pujiyanta, L. E. Nugroho, and Widyawan, “Resource allocation model for grid computing environment,” Int. J. Adv. Intell. Informatics, vol. 6, no. 2, pp. 185–196, 2020, doi: https://doi.org/10.26555/ijain.v6i2.496.

A. Shukla, S. Kumar, and H. Singh, “An improved resource allocation model for grid computing environment,” Int. J. Intell. Eng. Syst., vol. 12, no. 1, pp. 104–113, 2019, doi: 10.22266/IJIES2019.0228.11.

L. O. Burchard, “Analysis of data structures for admission control of advance reservation requests,” IEEE Trans. Knowl. Data Eng., vol. 17, no. 3, pp. 413–424, 2005, doi: 10.1109/TKDE.2005.40.

L.-O. Burchard and H.-U. Heiss, “Performance Evaluation of Data Structures for Admission Control in Bandwidth Brokers,” Int. Symp. Perform. Eval. Comput. Telecommun. Syst. (SPECTS ’02), pp. 652–659, 2002, [Online]. Available: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.1535&rep=rep1&type=pdf.

B. Li, Y. Pei, H. Wu, and B. Shen, “Resource availability-aware advance reservation for parallel jobs with deadlines,” J. Supercomput., vol. 68, no. 2, pp. 798–819, 2014, doi: 10.1007/s11227-013-1067-8.

A. Pujiyanta, L. E. Nugroho, and Widyawan, “Job Scheduling Strategies in Grid Computing,” Int. J. Adv. Sci. Eng. Inf. Technol., vol. 12, no. 3, pp. 1293–1300, 2022, doi: 10.18517/ijaseit.12.3.10147.

N. Charbonneau and V. M. Vokkarane, “A survey of advance reservation routing and wavelength assignment in wavelength-routed WDM networks,” IEEE Commun. Surv. Tutorials, vol. 14, no. 4, pp. 1037–1064, 2012, doi: 10.1109/SURV.2011.111411.00054.

M. D. de Assuncao, “Enhanced Red-Black-Tree Data Structure for Facilitating the Scheduling of Reservations,” 2015, [Online]. Available: http://arxiv.org/abs/1504.00785.

A. Gadkar, T. Entel, J. M. Plante, and V. M. Vokkarane, “Slotted advance reservation for multicast-incapable optical wavelength division multiplexing networks,” J. Opt. Commun. Netw., vol. 6, no. 3, pp. 340–354, 2014, doi: 10.1364/JOCN.6.000340.

M. Barshan, H. Moens, J. Famaey, and F. De Turck, “Deadline-aware advance reservation scheduling algorithms for media production networks,” Comput. Commun., vol. 77, no. 2015, pp. 26–40, 2016, doi: 10.1016/j.comcom.2015.10.016.

M. Barshan, H. Moens, B. Volckaert, and F. De Turck, “A comparative analysis of flexible and fixed size timeslots for advance bandwidth reservations in media production networks,” 2016 7th Int. Conf. Netw. Futur. NOF 2016, 2017, doi: 10.1109/NOF.2016.7810118.

R. Brown, “Calendar Queues: A Fast 0(1) Priority Queue Implementation for the Simulation Event Set Problem,” Commun. ACM, vol. 31, no. 10, pp. 1220–1227, 1988, doi: 10.1145/63039.63045.

R. A. Guerin and A. Orda, “Networks with advance reservations: The routing perspective,” Proc. - IEEE INFOCOM, vol. 1, pp. 118–127, 2000, doi: 10.1109/infcom.2000.832180.

A. Brodnik and A. Nilsson, “A Static Data Structure for Discrete Advance Bandwidth Reservations on the Internet,” Swedish Natl. Comput. Netw. Work., vol. 41, pp. 1–15, 2003.

A. Sulistio, U. Cibej, S. K. Prasad, and R. Buyya, “GarQ: An efficient scheduling data structure for advance reservations of grid resources,” Int. J. Parallel, Emergent Distrib. Syst., vol. 24, no. 1, pp. 1–19, 2009, doi: 10.1080/17445760801988979.

L. Wu, P. Dang, T. Yu, and L. Nie, “Research on efficient non-slotted tree structures for advance reservation,” Commun. Comput. Inf. Sci., vol. 401, pp. 50–61, 2013, doi: 10.1007/978-3-642-53959-6_6.

DOI: https://doi.org/10.24853/jurtek.16.2.283-290