Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70226910.17587/it.31.317-321Computing systems and networksВычислительные системы и сетиResearch ArticleDispatching of arrays with requests of equal non-Euclidean heuristic measure in Grid systemsДиспетчеризация массивов с заявками равной неэвклидовой эвристической меры в Grid-системахSaakA. E.СаакА. Э.
Russian Federation

Dr. of Eng. Sc., Professor

д-p техн. наук, проф.

asaak@hse.ruHSE UniversityНИУ "Высшая школа экономики"1506202531631732106022026Copyright ©; 2025, Informacionnye TehnologiiCopyright ©; 2025, Информационные технологии2025Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/702269

Abstract of the article: Grid systems of centralized architecture, with multisite dispatching, characterized by the ability to fulfill a multiprocessor request on several parallel systems simultaneously, are modeled by the resource quadrant. A user request when served by a Grid system dispatcher is modeled by a resource rectangle with horizontal and vertical dimensions respectively equal to the number of time resource units and processors required to complete the request. An illustration of the exponential complexity of dispatching resource rectangles is the placement of successive resource rectangles of equal perimeter from 1*23, 2*22, to 23*1 into an enclosing rectangle of the minimum area, which took more than three days. The exponential complexity of the optimal distribution of resource rectangles determines the practical value of heuristic algorithms of polynomial complexity, which are based on the operations ofdynamic integration of resource rectangles in the resource rectangles environment. To assess the quality of dispatching, a non-Euclidean heuristic measure is used. It takes in consideration the area and shape of the occupied resource area. The quality of dispatching of arrays with requests equal to the non-Euclidean heuristic measure is analyzed. This paper considers the quality of six polynomial level algorithms in terms of height and length (with a disadvantage, with an excess and with a minimum deviation) when dispatching arrays with requests of equal non-Euclidean heuristic measure. The quality of six polynomial algorithms for dispatching arrays with requests of a growing non-Euclidean heuristic measure is investigated. Using five test arrays of resource rectangles with an increasing non-Euclidean heuristic measure, it is shown that Д-level algorithms in terms of length with a minimum deviation have the smallest maximum value of the heuristic measure of 0.7. When servicing arrays with requests of a growing non-Euclidean heuristic measure in Grid systems, it is recommended to use the polynomial Д-level algorithm for length with minimal deviation which is introduced in the paper.

Исследуется качество диспетчеризации массивов с заявками равной неэвклидовой эвристической меры в Grid-системах централизованной архитектуры с мультисайтным режимом обслуживания. Анализируются три уровневых алгоритма по высоте и три уровневых алгоритма по протяженности. Анализ эффективности шести эвристических полиномиальных уровневых алгоритмов управления вычислительно-временными ресурсами проведен на пяти тестовых массивах.

Grid system of centralized architecturemultisite mode of request servicingnon-Euclidean heuristic measurepolynomial complexity of the algorithmlevel algorithms by heightlevel algorithms by lengthnon-Euclidean heuristic measure of the requestarrays of requests of growing non-Euclidean heuristic measureGrid-система централизованной архитектурымультисайтный режим обслуживания заявкинеэвклидова эвристическая мераполиномиальная трудоемкость алгоритмауровневые алгоритмы по высотеуровневые алгоритмыпо протяженностинеэвклидова эвристическая мера заявкимассивызаявок растущей неэвклидовой эвристической мерыDe Freitas Cunha R., Chaimowicz L. An SMDP approach for Reinforcement Learning in HPC cluster schedulers, Future Generation Computer Systems, 2023, vol. 139, pp. 239—252.De Freitas Cunha R., Chaimowicz L. An SMDP approach for Reinforcement Learning in HPC cluster schedulers // Future Generation Computer Systems. 2023. Vol. 139. P. 239-252.Tang X., Liu Y., Deng T. et al. A job scheduling algorithm based on parallel workload prediction on computational grid, Journal of Parallel and Distributed Computing, 2023, vol. 171, pp. 88—97.Tang X., Liu Y., Deng T. et al. A job scheduling algorithm based on parallel workload prediction on computational grid // Journal of Parallel and Distributed Computing. 2023. Vol. 171. P. 88-97.Caramia M., Giordani S., Iovanella A. Grid scheduling by online rectangle packing, Networks, 2004, vol. 44, no. 2, pp. 106—119.Caramia M., Giordani S., Iovanella A. Grid scheduling by online rectangle packing // Networks. 2004. Vol. 44, N. 2. P. 106—119.Huang E., Korf R. Optimal rectangle packing: an absolute placement approach, Journal of Artificial Intelligence Research, 2013, vol. 46, pp. 47—87.Huang E., Korf R. Optimal rectangle packing: an absolute placement approach // Journal of Artificial Intelligence Research. 2013. Vol. 46. P. 47—87.Saak A. Eh. Polynomial algorithms for resource allocation in Grid-based systems for quadratic typing, Informacionnye tehnologii, 2013, no. 7, Prilozhenie, 32 p. (in Russian).Саак А. Э. Полиномиальные алгоритмы распределения ресурсов в Grid-системах на основе квадратичной типизации массивов заявок // Информационные технологии. 2013. № 7. Приложение. 32 с.Saak A. Eh. Scheduling of sets of circular-type and hyperbolic-type tasks in grid-systems, Informacionnye tehnologii, 2016, vol. 22, no. 5, pp. 323—332 (in Russian).Саак А. Э. Диспетчеризация массивов заявок кругового и гиперболического типа в Grid-системах // Информационные технологии. 2016. Т. 22, № 5. С. 323—332.Zrigui S., Camargo R., Legrand A., Trystram D. Improving the performance of batch schedulers using online job run time classification, Journal of Parallel and Distributed Computing, 2022, vol. 164, pp. 83—95.Zrigui S., Camargo R., Legrand A., Trystram D. Improving the performance of batch schedulers using online job run time classification // Journal of Parallel and Distributed Computing. 2022. Vol. 164. P. 83—95.Saak A. Eh., Kureichik V. V. Dispatching arrays with tasks of equal resource measure in grid systems, Informacionnye tehnologii, 2022, vol. 28, no. 12, pp. 663—669 (in Russian).Саак А. Э., Курейчик В. В. Диспетчеризация массивов с заявками равной ресурсной меры в Grid-системах // Информационные технологии. 2022. Т. 28, № 12. С. 663—669.Saak A. Eh. Circular-typed multiprocessor tasks scheduling in grid systems, Informacionnye tehnologii, 2016, vol. 22, no. 1, pp. 37—41 (in Russian).Саак А. Э. Диспетчеризация заявок кругового типа в Grid-системах // Информационные технологии. 2016. Т. 22, № 1. С. 37—41.