Эмпирическое исследование и анализ методов динамической балансировки нагрузки, используемых в параллельных вычислительных системах

Аннотация

Ardhendu Mandal, Subhas Chandra Pal Эмпирическое исследование и анализ методов динамической балансировки нагрузки, используемых в параллельных вычислительных системах Рассмотрены системы блочного моделирования. Исследовано моделирование уравнения гармонического осциллятора. Проведено сравнение моделирующих сред.

Введение

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

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

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

Цели балансировки нагрузки

Балансировка нагрузки приложения оказывает прямое влияние на достигаемое ускорение, а также на производительность параллельной системы [1 , 2].

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

Некоторые из основных целей алгоритма балансировки нагрузки, как указано в [3], заключаются в следующем:

• Улучшение производительности:Достичь большего общего улучшения производительности системы при разумных затратах, например, сократить время отклика задачи при сохранении приемлемых задержек;
• Равенство должностей:Одинаково относиться ко всем компонентам в системе, независимо от их происхождения;
• Отказоустойчивость:Чтобы иметь работоспособность при частичном отказе в системе;
• Возможность модификации:Иметь возможность модифицировать себя в соответствии с любыми изменениями и расширением конфигурации распределенной системы;
• Стабильность системы:Способность учитывать чрезвычайные ситуации, например, внезапный всплеск приходов, так что производительность системы не ухудшается сверх определенного порога, в то же время предотвращая при этом узлы распределенной системы тратить слишком много времени на переход между собой вместо выполнения этих задач.

Типы стратегий балансировки нагрузки

Различные стратегии и алгоритмы были предложены, реализованы и классифицированы в ряде исследований [4 , 5 , 6]. В целом балансировка нагрузки - это своего рода проблема оптимизации расписания.

Стратегия балансировки нагрузки может быть определена проверкой, например, прямоугольная решетка точек сетки, разбитая на более мелкие прямоугольники, так что проблема балансировки нагрузки решается до написания программы. В зависимости от информации, используемой при решении о балансировке нагрузки, ее можно разделить на две широкие категории: глобальные или локальные политики [6]. В глобальных политиках балансировщик нагрузки использует профили производительности всех доступных рабочих станций. Рабочие станции с локальными политиками разделены на разные группы. Преимущество локальной схемы заключается в том, что информация о профиле производительности обменивается только внутри локальной группы. Выбор глобальной или локальной политики зависит от поведения, которое приложение запрещает. В зависимости от времени, необходимого для привязки задач к обрабатывающим элементам, алгоритмы балансировки нагрузки могут быть далее классифицированы как статико-динамические [7]. Нетривиальные алгоритмы статической балансировки нагрузки распределяют задачи по обрабатывающим элементам во время компиляции, в то время как динамические алгоритмы связывают задачи с обрабатывающими элементами во время выполнения. Алгоритмы статической балансировки нагрузки основываются на оценке время выполнения задач и требования к межпроцессному взаимодействию. Разница классифицируется как статическая динамика [7]. Нетривиальные алгоритмы статической балансировки нагрузки распределяют задачи по элементам обработки во время компиляции, в то время как динамические алгоритмы связывают задачи с элементами обработки во время выполнения.

Рисунок 1 – Различные типы методов балансировки нагрузки

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

Методы динамической балансировки нагрузки: краткое обсуждение

Обстоятельства, определяющие оптимальный баланс, часто или непрерывно меняются во время выполнения, так что затраты на расчет балансировки нагрузки после каждого изменения должны быть минимизированы в дополнение к оптимизации разделения фактического расчета. Это означает, что необходимо время от времени принимать решения, чтобы решить, нужна ли балансировка нагрузки и сколько времени нужно на нее потратить. С другой стороны, динамические (или адаптивные) политики полагаются на актуальную информацию о состоянии системы и определяют назначение задач процессорам во время выполнения [8 , 9 , 10]. Следовательно, они более привлекательны с точки зрения производительности [11 , 12].

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

Политики в алгоритмах балансировки нагрузки

Алгоритмы балансировки нагрузки могут быть определены путем реализации следующих политик[13]:

• Информационная политика:указывает, какую информацию о рабочей нагрузке следует собирать, когда и откуда;
• Политика срабатывания:определяет подходящий период для начала операции балансировки нагрузки;
• Политика типа ресурса:классифицирует ресурс как сервер или получатель программ в соответствии с его статусом доступности;
• Политика расположения:использует результаты политики типа ресурса для поиска подходящего сервера-партнера или получателя;
• Политика выбора:defines the tasks that shouldbemigrated from overloaded resources (source) to most idleresources.

Проблемы при оценке производительности

Основная цель методов балансировки нагрузки - ускорить выполнение приложений на ресурсах, рабочая нагрузка которых изменяется во время выполнения непредсказуемым образом [14]. Следовательно, важно определить метрики для измерения нагрузки на ресурсы:

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

Сравнительный анализ различных методов динамической балансировки нагрузки

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

Централизованные методы динамической балансировки нагрузки

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

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

Распределенная некооперативная методика динамической балансировки нагрузки

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

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

Распределенная кооперативная оптимальная динамическая балансировка нагрузки

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

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

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

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

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

Выводы

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

Список использованной литературы

1. Donaldson, V., Berman. F., and Paturi, R.,ProgramSpeedup in a Heterogeneous Computing Network, JournalofParallel and Distributed Computing, 21,3,316-322,(6/1994).
2. Leopold, C.,Parallel and Distributed Computing. AsurveyofModels, Paradigms, and Approaches, Wiley SeriesonParallel and Distributed Computing. AlbertZomayaSeries Editor,2001.
3. Goscinski, A.,Distributed Operating Systems, Addison-Wesley, Sydney,1991.
4. Casavant, T.L.and Kuhl,J.G.,A taxonomyofscheduling in general purpose distributed computing systems, IEEE TransactionsonSoftware Engineering, 14, 2, 141–153,1994.
5. Xu,C.Z. and Lau,F.C.M.,Load Balancing inParallel Computers: Theory and Practice, Kluwer, Boston,MA,1997.
6. Zaki, M. J., Li , W. and Parthasarathy, S.,Customizeddynamic load balancing for anetworkof workstations,Proc. ofthe5thIEEE Int.Symp.HDPC, 282–291, 1996.
7. Qian, X. andYang,Q.,An analytical model for loadbalancing on symmetric multiprocessor systems, JournalofParallel and Distributed Computing, Vol. 20, 198-211, 1994.
8. Mirchandaney, R., Towsley, D. and Stankovic, J.,Adaptive load sharing in heterogeneous systems,Proc. International ConferenceonDistributed Computing Systems”, 298-306,1989.
9. Shin,K.G. andHou,C. J.,Analytic modelsofadaptive load sharing schemes in distributed real- time systems, IEEE TransactionsonParallel and DistributedSystems,4,9,740-761, July1993.
10. Willebeek-LeMair, M.H.and Reeves, A. P. ,Strategies for dynamic load balancingonhighlyparallel computers, IEEE TransactionsonParallel and Distributed Systems,4, 9,979-993, Sept.1993.
11. Eager,D.L.,Lazowska,E. D. and Zahorjan, J.,Adaptive load sharing in homogeneous systems, IEEE TransactionsonSoftware Engineering, 12,5,662- 675, May1986.
12. Williams,R.D.,PerformanceofDynamic LoadBalancing Algorithms for Unstructured Mesh Calculations,C3P 913,June1990.
13. Karatza,H.D.,Job scheduling in heterogeneousdistributed systems, Journal.ofSystems and Software, 56, 203-212, 1994.
14. Eager,D.L.,Lazowska,E. D. and Zahorjan, J.,Adaptive load sharing in homogeneous distributedsystems, IEEE Trans.on Soft.Engg., 12, 5, 662-675, 1986.