Assessment of the impact of the distributed computing complex parameters of on the performance of load balancing algorithms.

Введение

В результате проведённого анализа ряда публикаций ^[1,2,3] выявлено, что на производительность алгоритмов балансировки вычислительной нагрузки и, в целом, всей распределённой системы сильное влияние оказывает её конфигурация. В работе ^[3] автором показано, что подбор правильных параметров распределённого вычислительного комплекса (РВК) позволяет повысить его пропускную способность на 24,5%, а также снизить время отклика системы на 28,1%. Однако основной проблематикой в данном вопросе является то, что большинство современных РВК строится в условиях гетерогенности среды, что приводит к необходимости выбора и последующей фиксации этих параметров на глобальном уровне. Стоит отметить, что в зависимости от целевого назначения вычислительного комплекса и в зависимости от требуемого уровня детализации, набор фиксируемых параметров может разниться. В частности, рассматривая организацию вычислений для локальной многопроцессорной системы, для обеспечения корректного описания модели системы, нас, в первую очередь интересуют соответствующие атрибуты вычислительного задания, такие как их размер, максимальное время ожидания в очереди на обработку, а также время обработки задания. Соответственно, ряд существующих подходов к управлению вычислительной нагрузкой были разработаны с учётом данных атрибутов. Например, одним из возможных вариантов решения задачи балансировки вычислительной нагрузки является её рассмотрение в рамках задачи ортогональной упаковки ^[5,6]. При данном подходе каждая вычислительная задача представляется прямоугольником, где ширина может быть представлена, например, требуемым вычислительным ресурсом процессора, а высота может быть представлена временем выполнения задачи.

Современный же этап развития вычислительной техники характеризуется повсеместным внедрением распределённых систем, построенных с использованием технологии Grid Computing. Учитывая все недостатки первых систем, а именно невозможность реализации данных систем в гетерогенной среде, I. Foster и C. Kesselman предложили ^[4] новый подход к организации глобально-распределённых комплексов и систем^[5], что позволило решить данную задачу. Данный подход позволил объединить глобально рассредоточенные вычислительные узлы, посредством сети Интернет, в некоторую абстрактную решётку ^[5], где каждый узел системы выделяется для выполнения конкретного вычислительного задания. Дальнейшее развитие данной технологии привело к созданию и повсеместному развитию концепции добровольных вычислений, что позволило объединить не только крупные вычислительные центры, но и обычные персональные компьютеры пользователей в единую Grid среду. Соответственно, для глобально распределённых вычислительных комплексов, построенных на основе добровольных вычислений при создании её модели, а также организации системы балансировки заданиями, необходимо учитывать ряд дополнительных параметров системы, в частности, модель нагрузки для рабочих мест, характер использования памяти, тип файловой системы и т.д.

Далее, дадим описание разработанной имитационной модели РВК и рассмотрим вопрос оценки степени влияния таких параметров, как структура файловой системы и тип сетевого протокола на эффективность работы алгоритмов балансировки нагрузки.

Разработка имитационной модели распределённого вычислительного комплекса

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

Имитационная модель, по сравнению с аналитической, обладает рядом преимуществ. Имитационное моделирование, для нашей задачи, позволяет ^[8]:

- производить многократное измерение интересующих нас параметров;

- осуществлять полный контроль всех параметров исследуемой системы, с возможностью текущей модификации алгоритма поведения исследуемой системы.

Так как построение имитационной модели сложного комплекса основывается на принципах иерархического многоуровневого моделирования ^[9], необходимо определить базовую модель, которая будет проста в реализации. Соответственно, выделим следующие модели РВК:

1. Базовая модель – распределённый вычислительный комплекс с гомогенным составом узлов, линий связи.

2. Глобальная модель (3-го уровня) – распределённый вычислительный комплекс с гетерогенным составом узлов, линий связи.

Одним из важнейших параметров, учёт которых необходим в разрабатываемой системе, является модель загрузки вычислительного узла комплекса. В данном эксперименте узловая нагрузка была представлена в виде однородного гомогенного потока событий (распределение Пуассона) и нелинейной кусочно-стационарной модели, описанной в виде уравнения:

Под кусочной стационарностью здесь понимается модель, выходная переменная которой является стационарной на некоторых отрезках времени эксплуатации.

На рисунке 1 показан подход к балансировке нагрузки на основе динамических моделей загрузки узлов ^[10].

Рисунок 1 —Балансировка нагрузки с использованием динамических моделей загрузки узлов ^[10]

С целью приближенности к реальным условиям эксплуатации, тестирование разработанного алгоритма производилось на глобальной модели, с различным набором параметров, описанных выше. В качестве основных алгоритмов балансировки нагрузки были выбраны следующие алгоритмы: алгоритм балансировки со случайным распределением задач (англ. randomized load balancing algorithm), циклический алгоритм (англ. Round-Robin), алгоритм наименьшего количества соединений (англ. Least-Connection), прогностический алгоритм на основе метода экспоненциального сглаживания (exponential smoothing) и прогностический алгоритм на основе метода квазилинеаризации.

После описания основных требований к имитационной модели была произведена её разработка. Структура разработанной системы представлена на рисунке 2.

Рисунок 2 — Функциональная схема разработанной системы

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

На рисунке 3 приведены параметры эксперимента исследуемого РВК с различными характеристиками.

Рисунок 3 — Фиксируемые параметры распределённого вычислительного комплекса

Анализ влияния структуры файловой системы на эффективность работы алгоритмов балансировки

В результате анализа полученных экспериментальных данных было выявлено, что структура файловой системы оказывает существенное влияние на производительность алгоритмов балансировки нагрузки. Так, при загрузке системы, стремящейся к 1, резко (см. рисунок 5) ухудшалась работа системы, построенной на основе бездисковой модели структуры файловой системы. Разработанный прогностический алгоритм на основе метода квазилинеаризации, так же как и метод на основе экспоненциального сглаживания, показали наилучшие результаты (см. рисунок 4 и рисунок 5). Данный эффект можно объяснить тем, что при больших нагрузках, а именно при больших количествах операций ввода/вывода, общий файловый сервер становится «узким» местом всего вычислительного комплекса. Особо остро данный проблема встаёт на тех узлах, на которых используется файл подкачки (англ. paging).

Рисунок 4 — Производительность различных алгоритмов при файловой структуре с локальными дисками

Рисунок 5 — Производительность различных алгоритмов при файловой структуре с общим файловым сервером

Анализ влияния протокола передачи данных

Для оценки влияния выбора коммуникационного протокола, было произведено сравнение двух протоколов передачи данных TCP и UDP. Предполагалось оценить влияние коммуникационного протокола для дисковых и бездисковых рабочих станций. Особое внимание было уделено бездисковым рабочим станциям с общим файловым сервером, так как предполагалось, что при больших нагрузках на систему, происходит большое число обращений к файловому серверу, что может приводить к флуктуациям сетевого трафика.

Результаты эксперимента для протокола TCP приведены на рисунке 6 и рисунке 7. Результаты для бездисковых и систем с локальными дисками с протоколом UDP представлены, соответственно, на рисунке 8 и рисунке 9.

Рисунок 6 — Производительность алгоритмов для протокола TCP (бездисковые системы)

Рисунок 7 — Производительность алгоритмов для протокола TCP (локальная структура)

Рисунок 8 — Производительность алгоритмов для протокола TCP (бездисковые системы)

Рисунок 9 — Производительность алгоритмов для протокола UDP (локальная структура файловой системы)

Как видно из графиков, уменьшение времени отклика, как для дисковых, так и бездисковых систем произошло при использовании сетевого протокола UDP. Данный факт объясняется тем, что протокол UDP организует передачу пакетов без предварительного установления соединения, что приводит к снижению объёма передаваемых данных. Однако стоит проявлять осторожность при интерпретации полученных результатов. Так, при построении модели не учитывалась внутренняя структура сетей передачи данных, а именно наличие активного сетевого оборудования (коммутаторы, прокси-серверы и т.д.) в её составе и надёжность данного оборудования. Однако полученные результаты могут быть применены для локальных комплексов, таких как университетские вычислительные центры.

Заключение

Полученные в ходе анализа результатов эксперимента данные, позволили отметить важность учёта, при создании адекватной модели современного распределённого вычислительного комплекса, таких параметров как модель вычислительной нагрузки, структура файловой системы комплекса и тип сетевого протокола. Однако, как отмечено в данной работе сетевая составляющая в полной мере не учитывается, что поднимает ряд проблем для дальнейших исследований. Связано это, прежде всего, со сложностью построения адекватной модели, учитывающие все свойства сетевого трафика и промежуточных передающих узлов, между сервером и хостом, а также все возможные варианты передачи пакета данных. Для решения данной задачи, в дальнейшем, планируется рассмотреть древовидную структуру представления grid архитектуры, с целью построения более адекватной модели.