Abstract
In this work, we introduce and study a set of tree-based algorithms for resources allocation considering group dependencies between their parameters. Real world distributed and high-performance computing systems often operate under conditions of the resources availability uncertainty caused by uncertainties of jobs execution, inaccuracies in runtime predictions and other global and local utilization events. In this way we can observe an availability over time function for each resource and use it as a scheduling parameter. As a single parallel job usually occupies a set of resources, they shape groups with common probabilities of usage and release events. The novelty of the proposed approach is an efficient algorithm considering groupings of resources by the common availability probability for the resources’ co-allocation. The proposed algorithm combines dynamic programming and greedy methods for the probability-based multiplicative knapsack problem with a tree-based branch and bounds approach. Simulation results and analysis are provided to compare different approaches, including greedy and brute force solution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Lee, Y.C., Wang, C., Zomaya, A.Y., Zhou, B.B.: Profit-driven scheduling for cloud services with data access awareness. J. Parall. Distrib. Comput. 72(4), 591–602 (2012)
Garg, S.K., Konugurthi, P., Buyya, R.: A linear programming-driven genetic algorithm for meta-scheduling on utility grids. Int. J. Parall. Emerg. Distrib. Syst. 26, 493–517 (2011)
Buyya, R., Abramson, D., Giddy, J.: Economic models for resource management and scheduling in grid computing. J. Concurren. Comput.: Pract. Exp. 5(14), 1507–1542 (2002)
Ernemann, C., Hamscher, V., Yahyapour, R.: Economic scheduling in grid computing. In: Feitelson, D.G., Rudolph, L., Schwiegelshohn, U. (eds.) JSSPP 2002. LNCS, vol. 2537, pp. 128–152. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36180-4_8
Kurowski, K., Nabrzyski, J., Oleksiak, A., Weglarz, J.: Multicriteria aspects of grid re-source management. In: Nabrzyski, J., Schopf, J.M., Weglarz, J. (eds.) Grid Resource Management, pp. 271–293. Kluwer Academic Publishers, State of the Art and Future Trends (2003)
Toporkov, V., Toporkova, A., Bobchenkov, A., Yemelyanov, D.: Resource selection algorithms for economic scheduling in distributed systems. In: ICCS 2011, June 1–3, 2011, Singapore, Procedia Computer Science, vol. 4. pp. 2267–2276. Elsevier (2011)
Netto, M.A.S., Buyya, R.: A flexible resource co-allocation model based on advance reservations with rescheduling support. In: Technical Report, GRIDSTR-2007-17, Grid Computing and Distributed Systems Laboratory, The University of Melbourne, Australia, October 9 (2007)
Jackson, D., Snell, Q., Clement, M.: Core algorithms of the Maui scheduler. In: Feitelson, D.G., Rudolph, L. (eds.) JSSPP 2001. LNCS, vol. 2221, pp. 87–102. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45540-X_6
Javadi, B., Kondo, D., Vincent, J., Anderson, D.: Discovering statistical models of availability in large distributed systems: An empirical study of SETI@home. IEEE Trans. Parall. Distrib. Syst. 22(11), 1896–1903 (2011)
Rood, B., Lewis, M.J.: Grid resource availability prediction-based scheduling and task replication. J. Grid Comput. 7, 479 (2009)
Tchernykh, A., Schwiegelsohn, U., El-ghazali, T., Babenko, M.: Towards understanding uncertainty in cloud computing with risks of confidentiality, integrity, and availability. J. Comput. Sci. 36 (2016)
Chaari, T., Chaabane, S., Aissani, N., Trentesaux, D.: Scheduling under uncertainty: Survey and research directions. In: 2014 International Conference on Advanced Logistics and Transport (ICALT), pp. 229–234 (2014)
Calheiros, R.N., Ranjan, R., Beloglazov, A., De Rose, C.A.F., Buyya, R.: CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. J. Softw. Pract. Exp. 41(1), 23–50 (2011)
Toporkov, V., Yemelyanov, D.: Availability-based resources allocation algorithms in distributed computing. In: Voevodin, V., Sobolev, S. (eds.) RuSCDays 2020. CCIS, vol. 1331, pp. 551–562. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64616-5_47
Toporkov, V., Yemelyanov, D., Grigorenko, M.: Optimization of resources allocation in high performance computing under utilization uncertainty. In: Paszynski, M., Kranzlmüller, D., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds.) ICCS 2021. LNCS, vol. 12747, pp. 540–553. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77980-1_41
Toporkov, V., Yemelyanov, D., Bulkhak, A.: Machine learning-based scheduling and resources allocation in distributed computing. In: Groen, D., et al. (eds.) Computational Science – ICCS 2022. ICCS 2022. Lecture Notes in Computer Science, vol. 13353, pp. 3–16. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-08760-8_1
Acknowledgments
This work was supported by the Russian Science Foundation (project No. 22-21-00372, https://rscf.ru/en/project/22-21-00372/).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Toporkov, V., Yemelyanov, D., Tselishchev, A. (2023). Allocation of Distributed Resources with Group Dependencies and Availability Uncertainties. In: Mikyška, J., de Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M. (eds) Computational Science – ICCS 2023. ICCS 2023. Lecture Notes in Computer Science, vol 14077. Springer, Cham. https://doi.org/10.1007/978-3-031-36030-5_48
Download citation
DOI: https://doi.org/10.1007/978-3-031-36030-5_48
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-36029-9
Online ISBN: 978-3-031-36030-5
eBook Packages: Computer ScienceComputer Science (R0)