УДК 004.272.43

А. Э. Саак

Полиномиальные алгоритмы распределения ресурсов в Grid-системах на основе квадратичной типизации массивов заявок

Массив заявок пользователей на компьютерное обслуживание в Grid-системах, многопроцессорных вычислительных системах моделируется протяженной линейной полиэдралью координатных ресурсных прямоугольников. Диспетчирование реализуется путем локализации линейной полиэдрали в оболочке области вычислительно-временных ресурсов системы согласно многоцелевому критерию качества назначения заявок на обслуживание. Вводится среда диспетчирования с неэвклидовой мерой ресурсных прямоугольников в качестве элементов и действиями над элементами, отвечающими задаче диспетчирования. В среде ресурсных прямоугольников определяются круговой, гиперболический и параболический квадратичные типы массивов прямоугольников. Рассматривается выбор алгоритма локализации, адаптированного к квадратичному типу перераспределяемого массива, с оценкой качества обслуживания эвристической мерой. Устанавливается полиномиальная трудоемкость разработанных алгоритмов распределения процессорно-временных ресурсов, даются рекомендации о возможности их использования в диспетчере как многопроцессорных вычислительных систем, так и центра Grid-технологий.
Ключевые слова: Grid-система, многопроцессорная вычислительная система, диспетчирование, квадратичный тип массива заявок пользователей, полиномиальный алгоритм диспетчирования

Saak A. E. Polynomial Algorithms of Task Scheduling in Grid Systems Based on Quadratic Typification of a Task Queue

A multiprocessor task queue waiting for execution by a Grid system or multiprocessor computer system is modeled as an extended linear polyhedral of coordinate resource rectangles. A process of scheduling is presented as a localization of a linear polyhedral in an enclosure of an area of a system computational and time resources, in accordance with a multipurpose quality criterion used for multiprocessor tasks assignment. It is proposed an environment of scheduling with a non-Euclidean measure of resource rectangles as elements and operations on elements which meet the requirements of a problem of scheduling. In the environment of resource rectangles there are denoted circular, hyperbolic and parabolic quadratic type of a sequence of rectangles. It is proposed an heuristics principle with selection of a localization algorithm which is adapted to the quadratic type of a sequence of rectangles which are subject for allocation. The quality of such allocation is measured by a heuristic measure. The algorithms for processor and time resources distribution proposed in the paper could be implemented in polynomial time. The proposed algorithms can be used by a scheduler of MCS or Grid technology center.
Keywords: Grid system, multiprocessorcomputer system, scheduling, quadratic type of a multiprocessor tasks queue, polynomial algorithm of scheduling

СОДЕРЖАНИЕ

Введение

1. Модель массива заявок пользователей
2. Модель функционирования Grid-системы
3. Постановка задачи диспетчирования в Grid-системах
4. Формальный аппарат среды диспетчирования
5. Классификация массивов заявок по трем квадратичным типам
6. Массивы заявок кругового типа
7. Массивы заявок гиперболического типа
8. Массивы заявок параболического типа

Заключение