Dispatching of arrays with requests of equal non-Euclidean heuristic measure in Grid systems

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.