(Universitas Ahmad Dahlan, Indonesia)(2) Lukito Edi Nugroho
(Universitas Gadjah Mada, Indonesia)(3) Widyawan Widyawan
(Universitas Gadjah Mada, Indonesia)*corresponding author
AbstractGrid computing is a collection of heterogeneous resources that is highly dynamic and unpredictable. It is typically used for solving scientific or technical problems that require a large number of computer processing cycles or access to substantial amounts of data. Various resource allocation strategies have been used to make resource use more productive, with subsequent distributed environmental performance increases. The user sends a job by providing a predetermined time limit for running that job. Then, the scheduler gives priority to work according to the request and scheduling policy and places it in the waiting queue. When the resource is released, the scheduler selects the job from the waiting queue with a specific algorithm. Requests will be rejected if the required resources are not available. The user can re-submit a new request by modifying the parameter until available resources can be found. Eventually, there is a decrease in idle resources between work and resource utilization, and the waiting time will increase. An effective scheduling policy is required to improve resource use and reduce waiting times. In this paper, the FCFS-LRH method is proposed, where jobs received will be sorted by arrival time, execution time, and the number of resources needed. After the sorting process, the work will be placed in a logical view, and the job will be sent to the actual resource when it executes. The experimental results show that the proposed model can increase resource utilization by 1.34% and reduce waiting time by 20.47% when compared to existing approaches. This finding could be beneficially implemented in cloud systems resource allocation management.
KeywordsFCFS-LRH, Grid computing, Resource allocation, Resource utilization, Waiting time
|
DOIhttps://doi.org/10.26555/ijain.v6i2.496 |
Article metricsAbstract views : 1051 | PDF views : 246 |
Cite |
Full Text Download
|
References
[1] M. Caramia, S. Giordani, and A. Iovanella, “Grid scheduling by on-line rectangle packing,” Networks, 2004, doi: 10.1002/net.20021.
[2] W. Smith, I. Foster, and V. Taylor, “Scheduling with advanced reservations,” in Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS 2000, pp. 127–132, doi: 10.1109/IPDPS.2000.845974.
[3] I. Foster, C. Kesselman, C. Lee, B. Lindell, K. Nahrstedt, and A. Roy, “A distributed resource management architecture that supports advance reservations and co-allocation,” in IEEE International Workshop on Quality of Service, IWQoS, 1999, doi: 10.1109/IWQOS.1999.766475.
[4] I. Foster and C. Kesselman, The grid 2: Blueprint for a new computing infrastructure, 2004, doi: citeulike-article-id:340626.
[5] K. Czajkowski et al., “A resource management architecture for metacomputing systems,” 1998, pp. 62–82, doi: 10.1007/BFb0053981.
[6] R. Buyya and M. Murshed, “GridSim: a toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computing,” Concurr. Comput. Pract. Exp., vol. 14, no. 13–15, pp. 1175–1220, Nov. 2002, doi: 10.1002/cpe.710.
[7] A. Sulistio, Kyong Hoon Kim, and R. Buyya, “On incorporating an on-line strip packing algorithm into elastic Grid reservation-based systems,” in 2007 International Conference on Parallel and Distributed Systems, 2007, pp. 1–8, doi: 10.1109/ICPADS.2007.4447738.
[8] J. Shi, J. Luo, F. Dong, J. Zhang, and J. Zhang, “Elastic resource provisioning for scientific workflow scheduling in cloud under budget and deadline constraints,” Cluster Comput., vol. 19, no. 1, pp. 167–182, Mar. 2016, doi: 10.1007/s10586-015-0530-0.
[9] A. W. Mu’alem and D. G. Feitelson, “Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling,” IEEE Trans. Parallel Distrib. Syst., vol. 12, no. 6, pp. 529–543, Jun. 2001, doi: 10.1109/71.932708.
[10] C. Castillo, G. N. Rouskas, and K. Harfoush, “On the Design of Online Scheduling Algorithms for Advance Reservations and QoS in Grids,” in 2007 IEEE International Parallel and Distributed Processing Symposium, 2007, pp. 1–10, doi: 10.1109/IPDPS.2007.370226.
[11] P. Xiao, Z. Hu, X. Li, and L. Yang, “A Novel Statistic-based Relaxed Grid Resource Reservation Strategy,” in 2008 The 9th International Conference for Young Computer Scientists, 2008, pp. 703–707, doi: 10.1109/ICYCS.2008.117.
[12] B. S. S. Rani, R. Venkatesan, and R. Ramalakshmi, “Resource reservation in grid computing environments: Design issues,” in 2011 3rd International Conference on Electronics Computer Technology, 2011, pp. 66–70, doi: 10.1109/ICECTECH.2011.5941858.
[13] P. Xiao and Z. Hu, “Relaxed resource advance reservation policy in grid computing,” J. China Univ. Posts Telecommun., vol. 16, no. 2, pp. 108–113, Apr. 2009, doi: 10.1016/S1005-8885(08)60213-7.
[14] 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, Feb. 2019, doi: 10.22266/ijies2019.0228.11.
[15] 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,” in 2016 7th International Conference on the Network of the Future (NOF), 2016, pp. 1–6, doi: 10.1109/NOF.2016.7810118.
[16] M. Barshan, H. Moens, J. Famaey, and F. De Turck, “Deadline-aware advance reservation scheduling algorithms for media production networks,” Comput. Commun., vol. 77, pp. 26–40, Mar. 2016, doi: 10.1016/j.comcom.2015.10.016.
[17] H. R. Moaddeli, G. Dastghaibyfard, and M. R. Moosavi, “Flexible Advance Reservation Impact on Backfilling Scheduling Strategies,” in 2008 Seventh International Conference on Grid and Cooperative Computing, 2008, pp. 151–159, doi: 10.1109/GCC.2008.85.
[18] E. Gomes and M. A. R. Dantas, “Towards a Resource Reservation Approach for an Opportunistic Computing Environment,” J. Phys. Conf. Ser., vol. 540, p. 012002, Oct. 2014, doi: 10.1088/1742-6596/540/1/012002.
[19] A. Mishra, “An enhanced and effective preemption based scheduling for grid computing enabling backfilling technique,” in 2015 International Conference on Advances in Computer Engineering and Applications, 2015, pp. 1015–1018, doi: 10.1109/ICACEA.2015.7164855.
[20] O. Dakkak, S. Awang Nor, and S. Arif, “Scheduling through backfilling technique for HPC applications in grid computing environment,” in 2016 IEEE Conference on Open Systems (ICOS), 2016, pp. 30–35, doi: 10.1109/ICOS.2016.7881984.
[21] S. Leonenkov and S. Zhumatiy, “Introducing New Backfill-based Scheduler for SLURM Resource Manager,” Procedia Comput. Sci., vol. 66, pp. 661–669, 2015, doi: 10.1016/j.procs.2015.11.075.
[22] R. Istrate, A. Poenaru, and F. Pop, “Advance Reservation System for Datacenters,” in 2016 IEEE 30th International Conference on Advanced Information Networking and Applications (AINA), 2016, pp. 637–644, doi: 10.1109/AINA.2016.106.
[23] M. A. S. Netto, K. Bubendorfer, and R. Buyya, “SLA-Based Advance Reservations with Flexible and Adaptive Time QoS Parameters,” 2007, pp. 119–131, doi: 10.1007/978-3-540-74974-5_10.
[24] B. Barzegar, A. M. Rahmani, K. Zamanifar, and A. Divsalar, “Gravitational Emulation Local Search Algorithm for Advanced Reservation and Scheduling in Grid Computing Systems,” in 2009 Fourth International Conference on Computer Sciences and Convergence Information Technology, 2009, pp. 1240–1245, doi: 10.1109/ICCIT.2009.319.
[25] L. Grandinetti, F. Guerriero, L. Di Puglia Pugliese, and M. Sheikhalishahi, “Heuristics for the local grid scheduling problem with processing time constraints,” J. Heuristics, vol. 21, no. 4, pp. 523–547, Aug. 2015, doi: 10.1007/s10732-015-9287-0.
[26] R. Umar, A. Agarwal, and C. R. Rao, “Advance Planning and Reservation in a Grid System,” 2012, pp. 161–173, doi: 10.1007/978-3-642-30507-8_15.
[27] A. Pujiyanta, L. E. Nugroho, and Widyawan, “Planning and Scheduling Jobs on Grid Computing,” in 2018 International Symposium on Advanced Intelligent Informatics (SAIN), 2018, pp. 162–166, doi: 10.1109/SAIN.2018.8673372.
[28] A. Pujiyanta, L. E. Nugroho, and Widyawan, “Advance Reservation for Parametric Job on Grid Computing,” in 2019 Fourth International Conference on Informatics and Computing (ICIC), 2019, pp. 1–5, doi: 10.1109/ICIC47613.2019.8985978.
[29] R. V. Lopes and D. Menasce, “A Taxonomy of Job Scheduling on Distributed Computing Systems,” IEEE Trans. Parallel Distrib. Syst., vol. 27, no. 12, pp. 3412–3428, Dec. 2016, doi: 10.1109/TPDS.2016.2537821.
[30] M. Carvalho and F. Brasileiro, “A User-Based Model of Grid Computing Workloads,” in 2012 ACM/IEEE 13th International Conference on Grid Computing, 2012, pp. 40–48, doi: 10.1109/Grid.2012.13.
[31] U. Lublin and D. G. Feitelson, “The workload on parallel supercomputers: modeling the characteristics of rigid jobs,” J. Parallel Distrib. Comput., vol. 63, no. 11, pp. 1105–1122, Nov. 2003, doi: 10.1016/S0743-7315(03)00108-4.
[32] A. Iosup, D. H. J. Epema, J. Maassen, and R. van Nieuwpoort, “Synthetic Grid Workloads with Ibis, Koala, and Grenchmark,” 2007, pp. 271–283, doi: 10.1007/978-0-387-47658-2_20.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571 (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
andri.pranolo.id@ieee.org (publication issues)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0