ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 6. Vol. 31. 2025

DOI: 10.17587/it.31.317-321

A. E. Saak, Dr. of Eng. Sc., Professor,
HSE University, Moscow, 109028, Russian Federation

Dispatching of Arrays with Requests of Equal Non-Euclidian Heuristic Measure in Grid Systems

Received on 02.07.24
Accepted on 24.07.24

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 1x 23, 2x22, to 2 x S1 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 of dynamic 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 H-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 H-level algorithm for length with minimal deviation which is introduced in the paper.
Keywords: Grid system of centralized architecture, multisite mode of request servicing, non-Euclidean heuristic measure, polynomial complexity of the algorithm, level algorithms by height, level algorithms by length, non-Euclidean heuristic measure of the request, arrays of requests of growing non-Euclidean heuristic measure

P. 317-321

Full text on eLIBRARY

References

1. 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.
2. 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.
3. Caramia M., Giordani S., Iovanella A. Grid scheduling by on-line rectangle packing, Networks, 2004, vol. 44, no. 2, pp. 106—119.
4. Huang E., Korf R. Optimal rectangle packing: an absolute placement approach, Journal of Artificial Intelligence Research, 2013, vol. 46, pp. 47—87.
5. 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).
6. 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).
7. 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.
8. 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).
9. Saak A. Eh. Circular-typed multiprocessor tasks scheduling in grid systems, Informacionnye tehnologii, 2016, vol. 22, no. 1, pp. 37—41 (in Russian).
   

To the contents