Реферат по теме магистерской работы
Содержание
1.1 Общие сведения о балансировке нагрузки1.2 Этапы создания распределенного приложения 2.1 Статическая балансировка
2.2 Динамическая балансировка
3.1 Описание RCL–cтратегии переноса нагрузки
3.1.1 Действия первого уровня
3.1.2 Действия второго уровня
3.1.3 Случайный алгоритм
3.1.4 Алгоритм, основанный на коммуникациях
3.1.5 Алгоритм, основанный на вычислении нагрузки
3.2 Реализация RCL–алгоритма
Введение
Использование распределенных вычислений при решении сложных задач позволяет снизить временные затраты в значительной мере. Важнейшей задачей, возникающей при создании параллельной вычислительной системы, является сбалансированность нагрузки компьютеров.
1. Особенности распределенной системы
1.1 Общие сведения о балансировке нагрузки
Балансировка нагрузки (Load Balancing) применяется для оптимизации
выполнения параллельных вычислений с помощью параллельной
вычислительной системы, она предполагает равномерную нагрузку
процессоров многопроцессорной ЭВМ. При появлении новых задач
программное обеспечение, реализующее балансировку, должно принять
решение о том, на каком процессоре (вычислительном узле) следует
выполнять вычисления, связанные с этой новой задачей. Балансировка
нагрузки также предполагает перенос части вычислений с наиболее
загруженных процессоров на менее загруженные [1].
1.2 Этапы создания распределенного приложения
Одним из этапов процесса создания параллельной программы является декомпозиция. Она предназначена для разбиения приложения на задачи, которые будут исполняться на отдельных процессорах. В результате такой декомпозиции создается набор задач, которые параллельно (одновременно) занимаются задачей. Эти задачи могут быть как независимыми, так и связанными между собой посредством обмена данными. Распределение задач происходит отдельным этапом, позволяющим распределить модули, полученные на этапе декомпозиции, между процессорами.
Рисунок 1 — Пример распределенного приложения
Распределенное приложение представляет собой совокупность логических процессов, которые взаимодействуют друг с другом, обмениваясь друг с другом сообщениями. Логические процессы распределяются по разным вычислительным узлам и функционируют параллельно. Распределяются логические процессы по вычислительным узлам таким образом, чтобы загрузка вычислительных узлов была равномерной.
Однако при выполнении параллельного приложения может возникнуть конфликт между сбалансированным распределением объектов по процессорам и низкой скоростью обменов данными между этими процессорами. Некоторые процессоры могут простаивать, в то время как остальные будут перегружены, если коммуникация между процессорами ведется на низкой скорости [3]. С другой стороны, затраты на коммуникацию могут быть велики для сбалансированной системы. Именно поэтому метод балансировки должен быть подобран таким образом, чтобы вычислительные узлы были загружены равномерно, а скорость обмена данными между процессорами была оптимальной.
Реализация такой параллельной вычислительной системы требует разработки алгоритмов синхронизации объектов, которые функционируют на различных узлах вычислительной системы. И наоборот, эффективность реализации алгоритмов синхронизации зависит от сбалансированности нагрузки по узлам вычислительной системы.
Рисунок 2 — Расределение процессов по вычислительным узлам
Дисбаланс нагрузки может возникнуть по нескольким причинам:
- неоднородность структуры параллельного приложения, т.е. различные логические процессы требуют разных вычислительных мощностей;
- неоднородность структуры вычислительного комплекса, т.е. различные вычислительные узлы обладают разной производительностью;
- неоднородность структуры взаимодействия между узлами вычислительной сети, т.е. линии связи между узлами могут иметь разные характеристики пропускной способности [4].
На сегодняшний день универсального метода борьбы с дисбалансом нагрузки не существует.
2. Методы балансировки
Методы балансировки разделяют на статические и динамические.
2.1 Статическая балансировка
Статическая балансировка
выполняется до начала выполнения параллельного приложения. При
распределении логических процессов по процессорам используется опыт
предыдущих выполнений (так называемое обучение
на исторических данных
). Однако
размещение логических процессов по узлам вычислительной сети
предварительно может не дать положительных результатов.
Это объясняется тем, что:
- вычислительная среда, в которой происходит выполнение приложения, может измениться, т.е. один или несколько вычислительных узлов могут выйти из строя;
- вычислительный узел, на котором выполняется параллельное приложение, может быть занят другими вычислениями.
2.2 Динамическая балансировка
Динамическая балансировка предусматривает перераспределение нагрузки на вычислительные узлы во время исполнения приложения. Для такой балансировки используют программное обеспечение, которое определяет:
- загрузку процессоров;
- пропускную способность линий связи между узлами;
- частоту обмена данными между логическими процессами параллельного приложения и др.
Динамические методы обычно применяют, если время, необходимое на балансировку, намного меньше времени выполнения задачи [2]. Динамическая задача балансировки обычно включает в себя не только распределение нагрузки по вычислительным узлам, но и, учитывая особенности вычислительно алгоритма, выбор оптимального числа процессоров. Балансировка нагрузки может выполняться программно или аппаратно, централизованно или децентрализовано.
3 Динамическая балансировка и перенос нагрузки
Алгоритм динамической балансировки определяет с какого вычислительного узла и на какой следует перенести задачу во время работы системы. Такой подход позволяет реагировать на изменение состояния вычислительной системы. Однако динамическая балансировка влечёт за собой дополнительные расходы времени на сбор статистических данных о состоянии вычислительной среды, на анализ данных и на принятие решений.
Перенос нагрузки — это механизм, который используется для переноса задачи с одного процессора на другой. Балансировку и перенос нагрузки используют для повышения производительности параллельной системы [8]. Из–за неоднородности вычислительной среды, один алгоритм может хорошо работать в одной параллельной системе и плохо в другой.
3.1 Описание RCL–cтратегии переноса нагрузки
Рассмотрим три алгоритма динамического переноса нагрузки:
- случайный алгоритм (random, R);
- алгоритм, основанный на коммуникациях (communication, С);
- алгоритм, основанный на вычислении нагрузки (load, L).
Будем в дальнейшем называть эти алгоритмы балансировки RCL–стратегией.
Алгоритм переноса объекта или процесса с одного вычислительного узла достаточно сложен. Однако введение некоторых допущений может снизить сложность этого алгоритма. Пусть:
- распределённая система объединяет несколько различных типов данных (является гетерогенной);
- пользователь может интерактивно взаимодействовать с машиной в любой момент времени;
- количество вычислительных узлов в сети ограничено;
- возможно изменение вычислительной сети;
- задержки на обмен данными между узлами остаются неизменными;
- издержки на перенос нагрузки с одного на другой процессор соизмерим с физическими размерами этой нагрузки.
RCL стратегия использует двухуровневый процесс принятия решений (централизованный и децентрализованный подходы), который предполагает:
- центральный процесс–координатор принимает решение о переносе нагрузки;
- каждый отсылающий сообщения процесс выбирает нагрузку, которую следует перенести [10].
3.1.1 Действия первого уровня
Выбирается центральный координатор, который сможет принимать решения. В начале действий по переносу нагрузки информации все рабочие узлы приостанавливают свою работу на некоторое время и каждый получает информацию о локальной нагрузке в текущий момент времени.
Координатор анализирует эти данные и на их основании определяет, нужно ли совершать перенос нагрузки с одного узла на другой. Если перенос нагрузки необходим, то центральный координатор совершает процедуру перераспределения нагрузки, на основании скорости работы узлов.
Если в переносе нагрузки нет необходимости, процессор посылает сообщения об этом другим узлам и каждый узел продолжает обрабатывать свои задачи.
3.1.2 Действия второго уровня
Если, находясь на втором уровне, посылающие данные узлы получат от центрального координатора сигнал о необходимости перераспределения нагрузки, они начинают процесс выбора части нагрузки для переноса её на другой процессор. При этом используется RCL стратегия. После этого начинается процесс переноса. Он включает упаковку данных и их отправку с посылающего узла, и приём и распаковку на принимающем. В конце каждого шага миграции адресат рассылает всем остальным сообщение о завершении процедуры переноса и о новом размещении данных. Далее каждый процессор продолжает выполнение задач [6].
Перенос нагрузки предполагает перенос объектов с одного узла на другой. Для выбора объектов, которые следует перенести на другой компьютер, используют один из трёх алгоритмов.
3.1.3 Случайный алгоритм
Случайный алгоритм заключается в случайном выборе объектов моделирования на посылающем узле. Выбор продолжается до тех пор, пока количество выбранных объектов не будет соответствовать заданному числу.
К преимуществам случайного алгоритма можно отнести: лёгкость реализации и сравнительно небольшое время выбора объектов для переноса.
3.1.4 Алгоритм, основанный на коммуникациях
Посылающий узел выбирает локальные объекты, которые наиболее часто обмениваются информацией с принимающим. Этот метод помогает сократить время на обмен данными между двумя логическими процессами. Однако, в таком случае, на каждом узле должна быть таблица коммуникаций, в которой фиксируется частота обменов каждого объекта, находящегося на посылающем узле, с другими узлами, и эта таблица должна регулярно обновляться [5]. Также, для выбора объекта для переноса нужно использовать алгоритмы сортировки и поиска, а при большом количестве объектов время выполнения алгоритмов линейного поиска и сортировки может быть значительным.
3.1.5 Алгоритм, основанный на вычислении нагрузки
Этот алгоритм ставит для себя целью минимизацию количества выбранных для переноса объектов. Во время миграции объекты моделирования сортируются по показателям их нагрузки (количество событий каждого типа, умноженное на коэффициент их сложности). Первым выбирают объект с максимальной нагрузкой [9].
В сравнении с алгоритмом, основанным на коммуникациях, данным алгоритм требует меньших временных затрат, а, следовательно, является более предпочтительным.
3.2 Реализация RCL–алгоритма
Стратегия динамического перераспределения нагрузки RCL была реализована в системе SPEEDES (Synchronous Parallel Environment for Emulation and Discrete–Event Simulation — синхронная параллельная среда для эмуляции и моделирования дискретных событий) с целью повышения её производительности.
Каждый из алгоритмов был протестирован на трёх наборах входных данных. При этом внешняя нагрузка изменялась. Результаты экспериментов показали, что процедуры миграции могут дать хорошие результаты в различных условиях моделирования — при различных нагрузках [7].
Рисунок
3 — Пример миграции нагрузки между вычислительными узлами
(анимация: 7 кадров, 3 цикла повторения, 200 килобайт)
(голубым на рисунке отмечен координатор, оранжевым —
процессоры,
занятые работой над задачами, зеленым — свободные узлы,
красным
— перегруженные узлы)
Заключение
В заключении можно сказать, что для всех трёх стратегий время выполнения сокращается, если интервал между процедурами перераспределения нагрузки невелик.
Частота выполнения процедуры перераспределения влияет на время моделирования существенным образом.
При сравнении параллельного выполнения с переносом нагрузки и без него видно, что процедура переноса существенно влияет на скорость выполнения эксперимента.
При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2012 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.
Список источников
- Замятина
Е.
Б., Ефимов А. Ю., Козлов А. А., Усынин А. С.
Оптимизация времени выполнения параллельных вычислений
— Пермь, 2009. - Немнюгин С.А., Средства программирования для многопроцессорных вычислительных систем — Санкт–Петербург, 2007.
- Миков
А.И., Замятина Е.Б., Козлов А.А.
Оптимизация параллельных вычислений с применением мультиагентной балансировки
— Пермь, 2007. - Load Balancing in Parallel Computers. Электронный ресурс. Режим доступа: http://www.inspirenignite.com/load-balancing-in-parallel-computers/
- Бельков Д.В., Алгоритмы балансировки загрузки процессоров параллельной вычислительной системы. Электронный ресурс. Режим доступа: http://ea.donntu.ru:8080/jspui/bitstream/123456789/6282/1/belkov.pdf
- Афраймович
Л.Г.
Модели и методы эффективного использования распределенных вычислительных систем
— Нижний Новгород, 2012 - Ardhendu Mandal and Subhas Chandra Pal, An Empirical Study and Analysis of the Dynamic Load Balancing Techniques Used in Parallel Computing Systems. Электронный ресурс. Режим доступа http://arxiv.org/ftp/arxiv/papers/1109/1109.1650.pdf
- Marc H. Willebeek–LeMair, Anthony P. Reeves, Transactions on parallel and distributed systems, vol.4, # 9 — 1993, c. 979
- Балансировка нагрузки в распределенных системах. Электронный ресурс. Режим доступа http://intuit4.intuit.ru/studies/courses/1146/238/lecture/3287?page=1
- Принципы построения параллельных вычислительных систем. Электронный ресурс. Режим доступа http://wiki.auditory.ru/Принципы_построения_параллельных_вычислительных_систем