Диссертация (Математическое и программное обеспечение балансировки вычислительных заданий для распределенных вычислительных комплексов на основе прогнозных моделей), страница 6

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

Так в [51] рассматривается способ планированиядля максимизации минимального времени выполнения задачи. Данныйнестандартный критерий оптимизации предназначен, прежде всего, длявыравниванияи калибровкипроцессабалансировки вычислительнойнагрузки.Особое внимание следует уделить исследованиям, направленным наразработку новых подходов к решению задачи балансировки нагрузки. Встатье [52] задача распределения задач в системе распределённых кластероврассматриваетсяполубесконечныхкакзадачаполос.двумернойАвторыстатьиупаковкиврассматриваютнесколькооднуизразновидностей двумерной задачи упаковки (англ. 2-Dimensional BinPacking), а именно двумерной упаковки в полубесконечную полосу (англ.

2Dimensional Strip Packing, 2-SP). Главное различие 2-Dimensional Bin Packingот 2-Dimensional Strip Packing заключается в том, что в 2-SP идётминимизация высоты контейнера, а в 2-BP идёт минимизация количестваконтейнеров.Каждая вычислительная задача представляется прямоугольником, гдеширина может быть представлена, например, требуемым вычислительнымресурсом процессора, а высота может быть представлена временемвыполнения задачи. Прямоугольники (задачи) должны быть размещены внесколько полубесконечных полос (вычислительные узлы), при этом,каждый прямоугольник не должен вращаться, а также пересекаться с34другими, уже размещёнными прямоугольниками [53].

На рисунке 1.4,вкачестве примера, показаны возможные варианты размещений 7 заданий(прямоугольников) в полубесконечную полосу. При этом, этом первыйвариант более предпочтителен, так как высота контейнера в данном случаеменьше.Рисунок 1.4 — Решение упаковки прямоугольников в полубесконечнуюполосу:количество заданий i=7Для данной постановки задачи, разработано множество методов, средикоторых наибольший интерес представляет рассмотрение так называемых«онлайн» методов. В [54, 55] даётся подробное описание основныхалгоритмов для решения задачи и их классификация, а также предлагаетсяряд улучшений для известных эвристик.В [56] предложен подход к балансировке вычислительной нагрузки,основанный на концепции теории игр.

Особенностью данного подходаявляется, то обстоятельство, что данный метод способен успешно работать вРВК,состоящейизгетерогенныхвычислительныхузлов.Задачабалансировки нагрузки рассматривается авторами, как кооперативная игра35между компьютерами. Каждый вычислительный узел рассматривается какигроккооперативнойигры,цельюкоторогоявляетсяминимизацияожидаемого времени выполнения задания. Для решения данной задачиприменяется подход, предложенный Дж. Ф. Нэшем. Показано, что решениеНэша задачи о сделках, обеспечивает оптимальное распределение Парето длясоответствующихвычислительныхузловРВК,чтогарантируетоптимальность распределения заданий по узлам РВК [56].

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

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

Dinda в своей работе [58] показал,что узловая нагрузка, при определённых условиях, может проявлятьфрактальные свойства. Так, в результате проведённого им эксперимента посбору статистики с более чем 35 узлов научно-исследовательского кластера,было обнаружено, что узловая нагрузка обладает свойствами самоподобия сосреднимпоказателемХёрста 0,73…0,99.Данныйэффект позволяетосуществить кратковременное прогнозирование сетевой и вычислительнойнагрузки, что можно использовать при создании алгоритмов балансировкивычислительной нагрузки в РВК.361.3.

Анализ и классификация методов балансировки нагрузкиузлов распределённого вычислительного комплексаКак было показано ранее [38], «в общем случае, можно выделитьобобщённуюклассификациюметодовбалансировкизагрузкивычислительных узлов» [41, 42, 43, 45].Выделяют локальную и глобальную балансировку. Под локальнойбалансировкой понимается назначение, с помощью соответствующихмеханизмов операционной системы, задач на временные срезы работыпроцессора.

Глобальная процедура балансировки заключается в решениизадачипланированияназначениясоответствующегозаданиянасоответствующий вычислительный узел в соответствующий временной срезпроцессора [45].«По характеру распределения нагрузки на вычислительные узлыразличают: динамическую балансировку (перераспределение); статическую балансировку» [38].Ранее было показано [38], «что статическая балансировка частовыполняется по результатам априорного анализа.

Приресурсовповычислительнымраспределенииузлам анализируется модельраспределённого комплекса, с целью выявления наилучшей стратегиибалансировки. При этом необходимо учитывать структуру распределённогокомплекса, а также конфигурацию вычислительных узлов. Основнойнедостаток данного метода балансирования нагрузки заключается внеобходимости ассоциации узлов с различной конфигурацией оборудованияс вычислительной сложностью конкретного задания, что не всегдапредставляется возможным» [38].37Вработе[46]статическиеметодыбалансировкинагрузкиподразделяются на оптимальные и субоптимальные.Оптимальные статические методы балансировки нагрузки реализуетсяна основе выбора некоторого критерия оптимальности.

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

Результаты исследований[44] показывают, что динамические стратегии обеспечивают более высокуюпроизводительность, по сравнению со статическими методами. Наибольшеераспространениеданнаястратегияполучиладлясовременныхвысоконагруженных гетерогенных РВК.Динамические методы балансировки подразделяются [42]: По принципам администрирования балансировки загрузки узловРВКнацентрализованныеидецентрализованныеметодыбалансировки. По степени адаптации нагрузки, возникающей в ходе работыРВК, на адаптивные и неадаптивные методы.38Централизованные методы основаны на модели ведущий/ведомый(master/slave).В данной модели предполагается наличие центральногосервера-планировщика, который имеет некоторое множество задач дляпередачи их на ведомые узлы системы. Существенным недостатком данногоподхода к организации балансировки потоков является ограниченнаявозможность масштабируемости комплекса, вследствие наличия такогоузкого места, как сервера-планировщика.

На рисунке 1.5 представленамодель централизованного метода балансирования потоками.Рисунок 1.5 — Централизованный метод балансировки нагрузки [111]Как было показано ранее [111], при децентрализованном подходе всеили часть узлов, входящие в систему, участвуют в процессе распределениянагрузки. Децентрализованные методы позволяют преодолевать проблемуналичия узкого места, однако имеют существенный недостаток в видеповышенных накладных расходов на организацию передачи данных.Возможный подход к организации динамической децентрализованной39балансировки, в виде организации совместного пула, представлен на рисунке1.6.Рисунок 1.6 — Пример организации децентрализованной динамическойбалансировки [111]Особо следует остановиться на динамических методах балансировкинагрузки,применяемыхдлябалансировкипотоковвполностьюдецентрализованных распределённых комплексах, например в пиринговыхP2P сетях [111]. Так как данные системы полностью децентрализованы,предполагается отсутствие управляющего сервера, который осуществляетбалансировку потоками запросов в системе.

Одним из возможных вариантоврешения данной задачи является концепция виртуальных серверов [47].На рисунке 1.7 показана данная концепция.Процесс балансировкинагрузки осуществляется виртуальным сервером, которыйреализован нареальном узле системы. При этом каждый реальный узел системы можетсодержать несколько виртуальных серверов.40Рисунок 1.7 — Концепция виртуального сервера в структуре P2P [47]В статье [49] даётся ещё одна возможная классификация алгоритмовбалансировки.