Е. Б. Замятина Распределенные системы и алгоритмы Курс лекций

Вид материала

Содержание

Подобный материал:

1 ... 5 6 7 8 9 10 11 12 ... 18

Лекция 9. Балансировка нагрузки в распределенных системах

Балансировка нагрузки (Load Balancing) применяется для оптимизации выполнения распределённых (параллельных) вычислений с помощью распределённой (параллельной) ВС. Балансировка нагрузки предполагает равномерную нагрузку вычислительных узлов (процессора многопроцессорной ЭВМ или компьютера в сети). При появлении новых заданий программное обеспечение, реализующее балансировку, должно принять решение о том, где (на каком вычислительном узле) следует выполнять вычисления, связанные с этим новым заданием. Кроме того, балансировка предполагает перенос (migration – миграция) части вычислений с наиболее загруженных вычислительных узлов на менее загруженные узлы.

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

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

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

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

Балансировка вычислительной нагрузки

Причины возникновения несбалансированной нагрузки

Проблема балансировки вычислительной нагрузки распределённого приложения возникает по той причине, что:

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

Статическая и динамическая балансировки

Следует различать статическую и динамическую балансировки.

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

Это объясняется тем, что:

Может измениться вычислительная среда, в которой происходит выполнение приложения, какой либо вычислительный узел может выйти из строя.
Вычислительный узел, на котором выполняется распределенное приложение, занят ещё и другими вычислениями, доля которых со временем может возрасти.

Так или иначе, выигрыш от распределения логических процессов по компьютерам с целью выполнения параллельной обработки становится неэффективным.

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

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

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

Постановка задачи динамической балансировки

Цель балансировки загрузки может быть сформулирована следующим образом:

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

Представим распределенное приложение в виде графа. Пусть G_p= {V, E}, V –множество вершин (задачи распределенного приложения), E – множество дуг графа – связи между задачами распределенного приложения. Пусть TM – множество моделей распределенных приложений, G_pÎ TM.

Задача балансировки ставится как задача отображения неизоморфных связных графов, B: TM ® NG , где TM – множество графов моделей, NG – множество графов – конфигураций компьютерной сети. Граф G Î NG , G = {C, Ed}, определяется множеством вычислительных узлов C и множеством ребер Ed, обозначающих линии связи. Можно рассматривать NG как суперграф, содержащий все возможные (допустимые) графы G в качестве подграфов.

.

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

Методология практического решения задачи балансировки

Обычно практичное и полное решение задачи балансировки загрузки состоит из четырех шагов:

Оценка загрузки вычислительных узлов.
Инициация балансировки загрузки.
Принятие решений о балансировке.
Перемещение объектов.

В последующих частях конкретизируется каждый шаг балансировки с рассмотрением различных методов решения.

Оценка загрузки

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

В основном такая база данных состоит из двух типов данных:

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

Очень важно владеть такой информацией как коммуникационная модель.

Коммуникационная модель содержит важную информацию для принятия решений о перемещении задач при балансировке загрузки. При необходимости переместить объект с перегруженного процессора A на недогруженный процессор B целесообразно выбрать для перемещения тот объект, который наиболее интенсивно сообщается с задачами, уже расположенными на B.

Необходимо учитывать два типа связей между объектами: двухточечные коммуникации и коллективные коммуникации.

При распределении задач между процессорами производится оценка коммуникаций. Затраты на двухточечную связь между двумя задачами могут быть определены через объем передаваемых данных (b – объём сообщений в байтах) и частоту коммуникации (n – количество сообщений за единицу времени). Используя величины затрат процессора на каждое сообщение и каждый байт, можно оценить общие затраты на коммуникацию между двумя задачами: a * n + b* b, где b – общий объем всех n сообщений.

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

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

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

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

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

Инициализация балансировки загрузки

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

Для этого следует:

Определить момент возникновения дисбаланса загрузки.
Определить степень необходимости балансировки путем сравнения возможной пользы от ее проведения и затрат на нее.

Дисбаланс загрузки может определяться синхронно и асинхронно.

При синхронном определении дисбаланса все процессоры (компьютеры сети) прерывают работу в определенные моменты синхронизации и определяют дисбаланс загрузки путем сравнения загрузки отдельного процессора с общей средней загрузкой.

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

Принятие решений в процессе балансировки

Большинство стратегий динамической балансировки загрузки можно отнести к классу централизованных или к классу полностью распределенных.

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

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

Перемещение объектов

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

Архитектура подсистемы балансировки

Из всего вышесказанного можно сделать вывод о том, что для проведения балансировки во время имитационного моделирования необходимо разработать специальное программное обеспечение. Это программное обеспечение включает:

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

Blog