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

Авторы статьи: Ardhendu Mandal и Subhas Chandra Pal

Автор перевода: Волохова Г.В.

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

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

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

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

I. Введение

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

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

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

Балансировки нагрузки имеет непосредственное влияние на скорость работы системы [1, 2]. Основной целью оптимизации распределения нагрузки является перераспределение сбалансированной рабочей нагрузки с помощью задач и сведение к минимуму процесса коммуникации с оптимальным использованием ресурсов и времени работы реагирования. Таким образом, повышение производительности параллельных компьютеров выравнивания нагрузки обработки элементов является целью балансировки нагрузки. Некоторые из основных целей алгоритма балансировки нагрузки, как указано в [3] являются:

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

(2) Равенство задач: решение всех задач в системе на одном уровне, независимо от их происхождения;

(3) Отказоустойчивость;

(4) Модифицируемость: Есть возможность изменять вносить изменения или расширить в распределенной конфигурации системы;

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

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

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

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

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

IV. Динамическая балансировка нагрузки Техника: Краткое обсуждение

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

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

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

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

II) Запуск политики: определяет соответствующий период, чтобы начать операцию балансировки нагрузки.

III) Ресурс типа политики: классификация ресурсов в качестве сервера или приемник задач в соответствии с его состояние доступности.

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

V) Выбор политики: определяет задачи, которые должны быть перенесены из перегруженных ресурсов (источник) в наиболее свободных денежных средств.

VI. Проблемы в оценке эффективности

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

(I) Как измерить загрузки ресурсов?

(II) Какие критерии сохранения определить эту нагрузку?

(III) Как избежать негативных последствий ресурсов динамичность от объема работы, и

(IV) Как учитывать неоднородность ресурсов для того, чтобы получить мгновенный средний представитель нагрузку на систему?

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

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

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

VIII. Заключение

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

IX. План будущей работы

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

Список литературы

[1] Donaldson, V., Berman. F., and Paturi, R., Program Speedup in a Heterogeneous Computing Network, Journal of Parallel and Distributed Computing, 21, 3, 316-322, (6/1994).

[2] Leopold, C., Parallel and Distributed Computing. A survey of Models, Paradigms, and Approaches, Wiley Series on Parallel and Distributed Computing. Albert Zomaya Series Editor, 2001.

[3] Goscinski, A., Distributed Operating Systems, Addison-Wesley, Sydney, 1991.

[4] Casavant, T. L. and Kuhl, J. G., A taxonomy of scheduling in general purpose distributed computing systems, IEEE Transactions on Software Engineering,

[5] Xu, C. Z. and Lau, F. C. M., Load Balancing in Parallel Computers: Theory and Practice, Kluwer, Boston, MA, 1997.

[6] Zaki, M. J., Li , W. and Parthasarathy, S., Customized dynamic load balancing for a network of workstations, Proc. of the 5th IEEE Int. Symp. HDPC, 282–291, 1996.

[7] Qian, X. and Yang, Q., An analytical model for load balancing on symmetric multiprocessor systems, Journal of Parallel and Distributed Computing, Vol. 20, 198-211, 1994.

[8] Mirchandaney, R., Towsley, D. and Stankovic, J., Adaptive load sharing in heterogeneous systems, Proc. International Conference on Distributed Computing Systems”, 298-306, 1989.

[9] Shin, K. G. and Hou, C. J., Analytic models of adaptive load sharing schemes in distributed realtime systems, IEEE Transactions on Parallel and Distributed Systems, 4, 9, 740-761, July 1993.

[10] Willebeek-LeMair, M. H. and Reeves, A. P. , Strategies for dynamic load balancing on highly parallel computers, IEEE Transactions on Parallel 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 Transactions on Software Engineering, 12, 5, 662-675, May 1986.

[12] Williams, R. D., Performance of Dynamic Load Balancing Algorithms for Unstructured Mesh Calculations, C3 P 913,June 1990.

[13] Karatza, H. D., Job scheduling in heterogeneous distributed systems, Journal. of Systems and Software, 56, 203-212, 1994.

[14] Eager, D. L., Lazowska, E. D. and Zahorjan, J., Adaptive load sharing in homogeneous distributed systems, IEEE Trans. on Soft. Engg., 12, 5, 662-675, 1986.