Оптимальная балансировка нагрузки в Grid-системах

Введение. Рост потребностей в компьютерных ресурсах для решения крупномасштабных вычислительных задач явился причиной создания концепции GRID. Глобальные вычислительные сети GRID объединяют разнородные вычислительные ресурсы: персональные компьютеры, вычислительные кластеры, суперкомпьютеры. Вследствие этого имеет место разнородный характер выполняемых приложений, начиная от распределенных супервычислений до высокопоточных вычислений, позволяющих организовать эффективное использование ресурсов для небольших задач, занимая временно простаивающие компьютерные ресурсы.

Главной задачей разработчиков GRID является превращение вычислительной сети, состоящей из тысяч разнообразных элементов, в единое целое, работающее и управляемое как многопроцессорный компьютер. Чтобы поддерживать такую распределенную среду, необходимо решить широкий круг проблем, который можно разделить на две основные группы в соответствии с теорией распределенных вычислений: разработка программного обеспечения глобальной распределенной сетевой операционной системы и разработка эффективных методов планирования и распределения поступающих заданий по имеющимся вычислительным ресурсам. Предлагаемый способ балансировки нагрузки в Grid-системах относится именно ко второй группе.

Принципы функционирования системы GRID. Рассмотрим в общем виде структуру и схему функционирования GRID-систем [1], с тем, чтобы уяснить механизм выполнения задачи от формирования заявки до получения результата вычислений и определить совокупность требований, предъявляемых к задачам, поступающим на обработку.

Основными компонентами в системе GRID являются:

• 1.    Потребитель GRID: пользователь GRID и приложения (последовательные, параллельные).

• 2.    Промежуточное программное обеспечение (ПО) сервисов GRID: интерфейсное ПО уровня пользователя; интерфейсное ПО ядра GRID.

• 3.    Брокер ресурсов GRID: система управления задачами; система составления расписаний (поиск и выбор ресурсов с использованием системы исследования GRID, генерация расписания); система исследования GRID (обнаружение ресурсов во взаимодействии с информационным сервером GRID); система установки задачи (активация выполнения задачи).

• 4.    Поставщики ресурсов и услуг GRID: предоставляют в пользование свои вычислительные средства, с целью максимизации использования простаивающих ресурсов и получения прибыли от вложенных средств.

В рассматриваемой системе Брокер ресурсов выступает в роли соединительного звена между Потребителями и Поставщиками ресурсов GRID, используя интерфейсное ПО ядра для обеспечения услуг. Брокер получает задания от пользователей и распределяет задачи между узлами, учитывая информацию о задачах и текущем состоянии узлов. Брокер анализирует запрос на выполнение задачи и рассылает его всем узлам, которые могут его выполнить. Каждый узел возвращает время, до которого задача может быть выполнена. Брокер принимает решение на основе этой информации и выбирает узел или кластер, который удовлетворяет предельному времени выполнения задачи и имеет наименьшую стоимость, или использует другой критерий: например, минимальное время выполнения.

Таким образом, выполнение функций Брокера ресурсов основывается на информации двух видов:

• 1.    Характеристики узлов или кластеров: количество процессоров т,; объем памяти каждого процессора S_t ; производительность процессоров гр, стоимость К, каждого кластера или узла. Эту информацию предоставляют Поставщики ресурсов и услуг Grid.

• 2.    Характеристики задач, поступающих в систему: количество требуемых процессоров Pj для решения задачи; максимальное время выполнения tj (на pj процессорах); требования к памяти Мр предельное время, до которого задача должна быть выполнена. Эту информацию предоставляют Потребители GRID.

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

Метод распределения задач по вычислительным узлам. Задача планирования вычислительного процесса состоит в построении оптимальных расписаний выполнения распределенных программ. Большинство задач составления расписания являются NP-полными. В конкретных постановках задач составления расписаний свойства ресурсов и заданий задаются по-разному, в результате чего известно большое число постановок и результатов, полученных для них.

Система GRID характеризуется различными производительностями вычислительных узлов, а полученные задания могут существенно различаться по объему операций. Эффективное выполнение различных программ на неоднородных распределенных системах в большой степени зависит от правильного размещения задач по процессорам, учитывающим как специфику вычислительной системы (количество процессоров, их производительность, латентность и пропускная способность коммуникационных каналов), так и конкретного программного приложения (объем кода, длительность исполнения программ).

Постановку задачи оптимального распределения заданий по вычислительным узлам распределенной системы сформулируем в следующем виде:

Пусть имеется п узлов pi,... ,р_п вычислительной системы и т задач Wi,... w_m, при чем т <п. Числа Су>0 (/= 1,2,..., т, j=l,2,... ,п) определяют меру эффективности задачи w, на узле p_j; и определяются из информации о вычислительном ресурсе, предоставляемой Поставщиком услуг GRID, и информации о характеристиках задачи, предоставляемой Потребителем GRID. Назовем матрицу С=||Су||, i=l, ...,т, j=l, ...,п матрицей эффективности.

Тот факт, что при некотором распределении на процессоры программа му попадает на узел рц можно описать подстановкой:

• ( 1 2 ... к ... т )

• V? *2 ••• *к ••• *п)

Требуется найти ^ - такое распределение задач Wi,... w_m по вычислительным узлам pi,... ,р_п, чтобы величина минимальной производительности Су была максимальной по всем подстановкам ^ i

S(cr) = mine, „

=1, ...,L. В качестве оптимизационного параметра выбирается величина ^ieL ’ ', где ^и - некоторая подстановка, и ставится вопрос о нахождении оптимального параметра $° ” тах^^) Иными словами, имея способ ^ назначения на процессоры, можно найти конкретную для этого способа ми-

S(a)=Cki                                        S(o-)

нимальную производительность         ’ « . Именно эта минимальная производительность v 7

определяет скорость и производительность решения всей совокупности задач. Тот процессор, на котором реализуется минимальная производительность, называется узким местом в назначении. В под становке ^° самое узкое место будет наибольшим среди всех возможных назначений.

Решение поставленной задачи сводится к нахождению наибольшего паросочетания в двудольном графе. Представим множество вершин А графа Г=[А, В], как объединение двух его непустых непере- секающихся подмножеств Аь А2 так, что любое ребро из В будет иметь один конец в 1, а другой конец - в 2 . Подмножество вершин Aj={wb... ,wm} - есть множество заданий, а подмножество вершин А2={рь... ,рп} - есть множество узлов. Алгоритм выбора наибольших паросочетаний в двудольном графе позволит найти распределение ст° задач по процессорам. При построении алгоритма для отыскания оптимального распределения программ, с использованием заданной матрицы эффективности С, выделяется последовательность наборов распределений, т.е. подстановок ^^ i =1, ...,L , с каждым шагом приближающих к максимальной эффективности.

Алгоритм решения задачи:

Шаг 1. Фиксируем матрицу производительностей С= || Су || и любое назначение на процессоры - о. Пусть 5 - минимальная производительность при этом назначении. Построим рабочую таблицу по С--

Шаг 2. Рассматривая рабочую таблицу, построенную на предыдущем шаге, как рабочую таблицу в алгоритме для выбора наибольшего паросочетания в двудольном графе [2], найдем соответствующее наибольшее паросочетание. Если в нем окажется п ребер, то по ним восстанавливается новое назначение на процессоры с новой, более высокой, минимальной производительностью. Обозначим ее снова через s и вернемся к шагу 1. Если же число ребер окажется меньше п, то имеющееся назначение на процессоры уже оптимально.

В. Д. Анахин. Графоаналитический метод моделирования динамики систем с асимметричными колебаниями

Заключение. Постановка задачи оптимальной балансировки нагрузки для системы управления GRID в таком виде позволяет свести задачу к относительно простой. Алгоритм сходится очень быстро, за малое число шагов, тогда как полный перебор всех возможностей распределения заданий по вычислительным узлам потребовал бы для расчета т! вариантов. По сравнению с известными методами математического программирования для решения задач такого рода отпадают трудности формального описания большого количества ограничений, ведущих к возрастанию трудоемкости математического решения задачи распределения нагрузки.