Содержание к диссертации
Введение
ГЛАВА 1. Анализ реализуемости итерационных алгоритмов на параллельных вычислительных системах 9
1.1 Понятие итерационных алгоритмов 9
1.2 Анализ параллельных алгоритмов 11
1.3 Классификация параллельных итерационных алгоритмов 13
1.3.1 Алгоритм с синхронными итерациями и коммуникациями 14
1.3.2 Алгоритм с синхронными итерациями и асинхронными коммуникациями ,15
1.3.3 'Алгоритм с асинхронными итерациями и коммуникациями 16
1.4 Параллельные асинхронные итерационные алгоритмы 17
1.5 Проблема переносимости прикладных программ в среде параллельных ЭВМ 20
1.5.1 Прикладные задачи, требующие больших компьютерных ресурсов 21
1.5.2 Основные виды суперкомпьютерных сред 21
1.5.3 Стандартизованное описание супер-ЭВМ среды 23
1.5.4 Особенности функционирования программ на аппаратных платформах MIMD 25
1.6 Современные среды параллельного программирования 28
1.6.1 Средства коммуникации для систем с распределенной памятью 28
1.6.2 MPI 29
1.6.3 PVM 30
1.7 Выводы 32
ГЛАВА 2. Распараллеливание программ для многопроцессорных вычислительных систем с распределенной памятью 33
2.1 Архитектура высокопроизводительных ЭВМ 33
2.1.1 SIMD - суперЭВМ 33
2.1.2 Многопроцессорные ЭВМ 36
2.1.2.1 Массивно-параллельные ЭВМ с распределенной памятью 37
2.1.2.2 Параллельные компьютеры с общей памятью 38
2.1.2.3 Векторно-конвейерные ЭВМ 38
2.1.2.4 Многопроцессорные ЭВМ с архитектурой комбинированного типа... 39
2.2 Методы распараллеливания программ 40
2.2.1 Ручное распараллеливание 40
2.2.2 Полуавтоматическое распараллеливание 43
2.2.3 Автоматическое распараллеливание 43
2.3 Основные проблемы управления параллелизмом на кластере 44
2.3.1 Параллельные программы на основе SPMD 44
2.3.2 Кластеры рабочих станции 47
2.3.3 Выполнение параллельных SPMD программ на кластерах 49
2.3.4 Проблемы управления параллелизмом 54
2.4 Высокая производительность коммуникаций 55
2.4.1 Myrinet 55
2.4.2 SCI 56
2.4.3 QSNET 56
2.5 Отношение стоимости вычислений и коммуникаций 57
2.6 Накладные расходы на поддержание параллелизма 61
2.6.1 Накладные расходы на коммуникацию 61
2.6.2 Накладные расходы на синхронизацию 63
2.7 Выводы 64
ГЛАВА 3. Анализ методов распределения вычислительной нагрузки при решении оптимизационных задач 66
3.1 Распределение задач при параллельных вычислениях 66
3.1.1 Количество подзадач 67
3.1.2 Количество процессоров и время вычисления 67
3.2 Способы распределения вычислительной нагрузки 68
3.2.1 Порядок распределения нагрузки 69
3.3 Постановка задачи квадратичного назначения 70
3.3.1 Классификация алгоритмов размещения 73
3.3.2 Итерационные алгоритмы улучшения размещения 74
3.4 Решение задачи квадратичного назначения на параллельной платформе
75
3.4.1 Методы распределения нагрузки при решении задачи квадратичного назначения 76
3.4.2 Ускорение генерации случайного вектора 79
3.5 Выводы 86
CLASS ГЛАВА 4. Результаты экспериментальных исследований и испытаний CLASS 88
4.1 Решение задачи квадратичного назначения на кластере 88
4.1.1 Архитектура экспериментальных систем 88
4.1.2 Параметры системы 91
4.1.3 Механизм распределения нагрузки для задачи квадратичного назначения 92
4.2 Результаты последовательного решения тестовой задачи 92
4.2.1 Алгоритм случайного поиска 93
4.2.2 Алгоритмы парных перестановок 104
4.2.3 Алгоритмы групповых перестановок 107
4.3 Параллельные алгоритмы решения оптимизационных задач 110
4.3.1 Параллельная реализация алгоритмов случайного поиска 112
4.3.2 Параллельная реализация алгоритма парных перестановок 113
4.3.3 Параллельная реализация алгоритма групповых перестановок 115
4.3.4 Эффективность параллельных алгоритмов 116
4.4 Выводы 117
Заключение 118
- Алгоритм с синхронными итерациями и асинхронными коммуникациями
- Ручное распараллеливание
- Количество процессоров и время вычисления
- Алгоритм случайного поиска
Введение к работе
Актуальность проблемы. Как один из молодых разделов науки системный анализ занимается установлением взаимосвязи между отдельными параметрами сложных агрегированных комплексов, поиском оптимальных решений многокритериальных задач. По мере усложнения анализируемых систем, ростом числа параметров, определяющих их состав и функционирование, возрастает вычислительная сложность алгоритмов и методов анализа. Если при небольшой мощности систем для поиска оптимума мы можем использовать даже алгоритмы, основанные на переборе всех возможных состояний системы, то при увеличении размерности практический интерес представляют итерационные алгоритмы. Они широко используются в различных приложениях, ориентированных на задачи оптимизации, теоретически обоснованы. Однако качество или точность получаемых ими решений определяется числом итераций. Следовательно, получение высокой точности решения при большой размерности задач становится вычислительно сложной процедурой. Сегодня в качестве платформ для создания ресурсоемких приложений используются параллельные вычислители, что делает актуальным задачу реализации на них алгоритмов и методов системного анализа.
В качестве оптимизационных приложений, требующих больших
вычислительных ресурсов, можно рассматривать задачу распределения
заказов между обрабатывающими центрами, планирование размещения
производственного оборудования, размещение компонентов
телекоммуникационных систем и элементов на коммутационных платах. Математической моделью подобных задач является задача квадратичного назначения.
В работе рассматриваются различные аспекты реализации на параллельных вычислителях итерационных алгоритмов решения задачи квадратичного назначения. Расширение сферы использования компьютеров, основанных на новых микропроцессорных архитектурах, является также актуальной научной проблематикой.
Цель работы и задачи исследования. Цель работы: повышение эффективности параллельных вычислительных систем с распределенной памятью при решении оптимизационных задач методами квадратичного назначения.
Для достижения поставленной цели в работе решаются следующие основные задачи:
1. Анализ архитектурных особенностей высокопроизводительных вычислителей с распределенной памятью.
Анализ методов распределения нагрузки для ресурсоемких приложений.
Разработка метода распределения нагрузки для решения задачи квадратичного назначения.
Разработка параллельного алгоритма решения задачи квадратичного назначения.
Разработка параллельной программы, адаптированной для вычислителей с распределенной памятью.
Экспериментальное исследование эффективности предложенных алгоритмов.
Методы исследования. При решении указанных задач были использованы положения теории графов, методы системного анализа, схемотехника многопроцессорных вычислительных систем и языки параллельного программирования.
Научная новизна. Разработка и исследование новых алгоритмов решения задач системного анализа с целью повышения эффективности работы параллельных вычислительных систем с распределенной памятью. Алгоритмы позволяют повысить эффективность использования узлов и общую производительность параллельной вычислительной системы при решении оптимизационных задач, основанных на квадратичном назначении.
Практическая значимость. Предложенный способ распределения вычислительной нагрузки и параллельный алгоритм адаптированы для систем с распределенной памятью. Эффективность способа распределения нагрузки зависит как от архитектуры системы, так и от способа реализации алгоритма.
Поскольку основной проблемой, влияющей на производительность параллельных систем с распределенной памятью, является пересылка данных между узлами, то сокращение коммуникационных накладных расходов приводит к повышению эффективности вычислений, что позволяет расширить область практического использования ресурсоемких оптимизационных методов системного анализа, основанных на квадратичном назначении.
Положения, выносимые на защиту.
Обзор методов распределения вычислительной нагрузки для программ решения задачи квадратичного назначения на параллельных вычислительных системах.
Эффективный метод распределения вычислительной нагрузки при решении задачи квадратичного назначения на параллельных вычислительных системах.
Итерационный параллельный алгоритм решения задачи квадратичного назначения.
Параллельная программа автоматического решения задачи квадратичного назначения.
Результаты практического исследования эффективности предложенных алгоритмов.
Внедрение результатов. Результаты диссертационной работы используются на кафедре вьгаислительной техники МИЭТ при проведении лабораторных работ по курсу «Высокопроизводительные вычислительные системы».
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов "Микроэлектроника и информатика - 2005, 2006, 2007, 2008", Международной школе-конференции - 2005, научной сессии МИФИ - 2007, Всероссийской межвузовской научно-практической конференции молодых ученых, специалистов, преподавателей, аспирантов и студентов "Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем - 2007".
Публикации. По материалам диссертации опубликовано шесть тезисов докладов и три статьи. Получено свидетельство РФ на программу для ЭВМ.
Структура и объём диссертационной работы. Рукопись диссертационной работы состоит из введения, четырех глав, заключения, списка литературы и приложения.
Алгоритм с синхронными итерациями и асинхронными коммуникациями
Если узлы начинают выполнение очередной итерации только после получения необходимых данных, а операции обмена они инициируют по мере их необходимости, не дожидаясь окончания собственных вычислений, то можно говорить об алгоритмах синхронных итераций и асинхронных коммуникаций. В алгоритмах этого класса сделана попытка уменьшить простой процессоров за счет совмещения по времени операций счета и пересылки. Для начала следующей итерации узел должен получить от остальных узлов не сами данные, а только сообщений о завершении расчетов. В такой схеме вычислений (рис. 1.2) все необходимые данные собираются в узле до начала очередной итерации. Точностные характеристики параллельных реализаций и этих алгоритмов будут аналогичны последовательным при равном числе шагов.
Алгоритм с асинхронными коммуникациями К недостаткам алгоритмов этого класса относится то, что при небольших объемах, передаваемых на каждой итерации данных, они будут вырождаться в полностью синхронные алгоритмы, т.к. время пересылки сигналов о завершении итерации не будет отличаться от времени пересылки данных.
При значительных объемах итерационных коммуникаций эти алгоритмы эффективнее полностью синхронных и снижают простой узлов системы.
Особый интерес для параллельных реализаций представляют асинхронные итерационные алгоритмы (рис. 1.3). Теоретически они позволяют устранить простой узлов из-за ожидания синхросообщений, но на практике операции приема данных могут блокировать процесс вычислений. При этом узлы начинают выполнение очередной итерации сразу после окончания предыдущей, не дожидаясь получения дополнительных данных от других узлов. Данные, поступающие в процессе выполнения очередной итерации, могут быть учтены как на следующей стадии, так и на текущей. Однако последний вариант алгоритмически сложнее. Алгоритмы, реализующие описанную стратегию, являются полностью асинхронными. время Необходимо отметить, что точностные характеристики параллельных асинхронных алгоритмов могут отличаться от последовательных реализаций. В литературе отсутствуют данные, посвященные исследованию этого вопроса.
В целом, можно считать, что для систем с распределенной памятью наибольшую эффективность использования узлов можно получить при использовании асинхронных алгоритмов с большим интервалом асинхронности.
Достоинство асинхронных алгоритмов заключается в том, что они позволяют снизить затраты на синхронизацию, что особенно важно для масштабируемых приложений. Это позволяет узлам выполнить больше итераций в единицу времени, что проводит к более быстрому решению. Им не нужно ждать сообщений от других узлов, а именно эта задержка передачи сообщения препятствует конвергенции. Таким образом, чем дольше временная задержка между созданием сообщения и его приемом в пункте назначения, тем меньше она способствует конвергенции.
Согласно A. Heddaya и К. Park [7], прямой путь распределения нагрузки в итерационных алгоритмах с числом шагов т по п узлам состоит в равномерном распределении переменных к = т/ между узлами. Где т
представляет размерность задачи, и п обозначает количество узлов в параллельной системе. Генетический параллельный итерационный алгоритм может описан следующим образом.
Во всех узлах системы на каждой итерации, выполняется следующая последовательность операций: Iterative fixed-point algorithm: repeat receive xx,x2,...,xn update хік,хІШ,...,хіШ_х send хік,хік+1,...,хік+к_} until termination condition Где оба send и receive являются асинхронными. Общая стоимость итерации, измеренная в единицах времени, даётся C = Cr+Cu+Cs (1.1) где С, стоимость «receive», Си стоимость «update», и С, стоимость «send». Пусть М — общее количество сообщений, произведенных на итерации в каждом узле. Для любого узла і, его скорость генерации сообщения Л, = М/ а общая скорость генерации сообщения для всей системы — Л = Л, =пЛ. Затраты, выраженные как функции тип зависят от того какие сообщения используются: точечные обмены (pointo-point) или широковещательная рассылка (broadcast). При передаче данных позиционирования (pointo-point) мы имеем: М а пк = т; Cr а пк = т; Cs а пк = т. (1 2) При ретрансляции на все терминалы (broadcast), М и Сд. меняются на: М а к = т/; С а к = т/. (1.3) М а т/ — это самый оптимальный случай, например, когда все узлы подсоединены к единой сети Ethernet. Для обычных сетей с маршрутизацией (routing networks), М пропорциональна т. Для положительных констант К}, К2 и Кг мы имеем а —-г, и, Л,а рг-7, (1.4) K.+W K n + K.+nW 1 /т - 3 /т а для случаев передачи от прямой связи (pointo-point) и широковещательной рассылки (broadcast), С„ является функцией, как размера задачи, т, так и количества узлов п, соответственно. Для наших целей достаточно отметить, что наименьшие расчёты итерации на одном узле должны включать поверку значений т, которую он получает. Тогда, Cu = Q(w). Следует отметить, что значение п т и самая точная степень детализации достигаются при п = т. Отсюда для случая передачи от прямой связи (pointo-point) мы имеем = ОД = Л, =0(1) = Я = 0(п), (1.5) а для широковещательной рассылки (broadcast), пС/ = П(п) = Л =7 -7 = 1 = (1)- (L6) Из этого анализа приходим к следующему заключению: - при передаче точка-точка увеличение количества узлов с целью ускорения вычислений до п приводит к повышению нагрузки сети в пропорции у . Когда Л превышает /л — скорость обслуживания сети, это приводит к перегрузке сети и очень сильной задержке сообщений и замедлению работы алгоритма. Для алгоритмов в распределенных системах считается, что п — большая величина, следовательно, мы работаем в режиме /л Л. И главная цель состоит, чтобы отрегулировать Л до значения Л «/и; - при всех других одинаковых параметрах, ретрансляция (broadcast) лучше, чем передача точка-точка, что касается уменьшения перегрузки сети. В самом оптимистичном случае, когда М а щ/, увеличение количества узлов, участвующих в асинхронном итеративном вычислении не увеличивает входную скорость сети. Дисбаланс, вызванный механизмом ретрансляции на стоимость приёма, приводит к тому, что узлы тратят гораздо больше времени на обработку поступающих пакетов; - временная сложность стоимости Си определяет отношение вычисления и коммуникации и непосредственно влияет на скорость с которой данные загружаются в сеть. В частном случае, когда все структурные аспекты благоприятно сочетаются, управление коммуникацией не является сложной задачей. Проблемы, связанные с уменьшением времени переключения между процессами receive, send, и update решаются путём упаковки адекватного количества сообщений в пакет, который надо контролировать как системную переменную.
Ручное распараллеливание
При распараллеливании программы необходимо выделить участки возможного параллелизма в коде и реализовать их параллельное исполнение. Известны несколько методов для создания параллельных программ:
ручное распараллеливание — программист самостоятельно выделяет блоки параллелизма, организует синхронизацию вычислений и обработку критических ситуаций;
полуавтоматическое распараллеливание — компилятор при трансляции кода руководствуется директивами программиста, но вопросы синхронизации решаются автоматически;
автоматическое распараллеливание — компилятор выполняет все этапы распараллеливания самостоятельно, учитывая конфигурацию аппаратных ресурсов системы.
Полный обзор этих трёх методов распараллеливания представлен в работе Goscinski [54] and [55]. В следующих разделах диссертации выделены те языки параллельного программирования, пакеты и системы работы Goscinski, которые относятся к распараллеливанию программы для выполнения на кластерах.
Ручное распараллеливание программы требует от программиста не только тонкого понимания языков параллельного программирования и используемых библиотек, но и знания архитектуры машины. Методы программирования для скалярных, векторных и параллельных ЭВМ существенно отличаются друг от друга. Эти условия делают процесс ручного распараллеливания весьма трудоемким.
Языки параллельного программирования, такие как Emerald [56], Linda [57, 58] и Orca [59], обеспечивают более высокий уровень абстрагирования, уменьшают трудоемкость программирования и увеличивают уровень читаемости и портативности программ [54]. При этом языки параллельного программирования ограничиваются специфическими моделями параллелизма, не всегда подходящими для создаваемой программы. Параллельные пакеты, такие как PVM [39, 60], р4 [61] и MPI [62, 63], хотя и не идентифицируют блоки параллелизма, предоставляя это программисту, реально поддерживают представление параллелизма посредством многих специализированных примитивов для выполнения, коммуникации и координации параллельных процессов. Современные параллельные пакеты в основном ориентированы на реализацию различных коммуникаций, и их эффективность сильно зависит от искусства программиста. При ручном распараллеливании можно добиться самой эффективно работающей программы, но вместе с тем, сам процесс ручного распараллеливания является очень трудоёмким.
При ручном распараллеливании главной задачей является оценка времени, которое затрачивается разными частями программы, и выделение ресурсопотребляющих частей. Затем необходимо провести анализ возможности параллельного исполнения этих частей и выбрать необходимые коммуникации.
Диагностика компилятора поможет установить причины, мешающие векторизовать и распараллелить циклы. Возможно, что простыми действиями удастся устранить эти причины. Это может быть простое исправление стиля программы, перестановка местами операторов (цикла и условных), разделение одного цикла на несколько, удаление из критических частей программы лишних операторов (типа операторов отладочной печати). Небольшие усилия могут дать здесь весьма существенный выигрыш в быстродействии.
Второй этап - замена алгоритма вычислений в наиболее критичных частях программы. Способы написания оптимальных (с точки зрения быстродействия) программ существенно отличаются в двух парадигмах программирования - в последовательной и в параллельной (векторной). Поэтому программа, оптимальная для скалярного процессора, с большой вероятностью не может быть векторизована или распараллелена. В то же время специальным образом написанная программа для векторных или параллельных ЭВМ будет исполняться на скалярных машинах довольно медленно. Замена алгоритма в наиболее критических частях программы может привести к серьезному ускорению программы при относительно небольших потраченных усилиях. Дополнительные возможности предоставляют специальные векторные и параллельные библиотеки подпрограмм. Используя библиотечные функции, которые оптимизированы для конкретной ЭВМ, можно упростить себе задачу по написанию и отладке программы. Единственный недостаток данного подхода состоит в том, что программа может стать не переносимой на другие машины (даже того же класса), если на них не окажется аналогичной библиотеки.
Написание программы "с нуля" одинаково сложно (или одинаково просто) для машин любых типов. Этот способ является идеальным для разработки эффективных, высокопроизводительных векторных или параллельных программ. Начинать надо с изучения специфики программирования для векторных и параллельных ЭВМ, изучения алгоритмов, которые наиболее эффективно реализуются на ЭВМ данных типов. После этого надо проанализировать поставленную задачу и определить возможность применения векторизуемых и распараллеливаемых алгоритмов для решения конкретной задачи. Возможно, что придется переформулировать какие-то части задачи, чтобы они решались с применением векторных или параллельных алгоритмов. Программа, специально написанная для векторных или параллельных ЭВМ, даст наибольшее ускорение при ее векторизации и распараллеливании.
Следует отметить и такое направление распараллеливания, как создание специализированных пакетов прикладных программ (ППП), реализованных на различных ЭВМ с параллельной архитектурой. К этому же направлению можно отнести модификацию существующих пакетов, их пополнение программами для параллельных численных методов. В работе [46] была высказана следующая идея организации программного обеспечения для решения широкого круга задач линейной алгебры:
пакет первого уровня - элементарные клеточные задачи на параллельной ЭВМ;
пакет второго уровня - матричные задачи произвольной размерности;
пакет третьего уровня - мониторные программы для различных матричных задач.
Параллельной реализации различных подпрограмм из таких пакетов как PBLAS и P_ARPACK посвящены несколько глав книги [64]. Разработка ГШП РАСЕРАСК для решения эллиптических краевых задач на ЭВМ с параллельной архитектурой описана в работе [65, 66]. Решению сеточных уравнений на многопроцессорных вычислительных комплексах посвящены работы [67, 68, 69].
Полуавтоматические методы распараллеливания требуют
взаимодействия между программистом и распараллеливающим компилятором. В таких методах программист обязан указывать области в пределах программы, которые являются потенциально параллелизуемыми. Компилятор использует эту информацию, чтобы выделить и представить параллелизм. ParaScope [70] является примером такой системы, которая объединяет компилятор, редактор и систему отладки, чтобы сформировать интегрированную распараллеливающую среду. Эти компоненты также поддерживают и визуальное представление параллелизма, для того чтобы облегчить его идентификацию.
Методы полного автоматического распараллеливания включают компиляторы распараллеливания, которые преобразовывают стандартные последовательные программы в параллельные программы. Преимуществами компиляторов распараллеливания, таких как Paradigm [71], SUIF [72] и RHODOS [73], [74] является то, что пользователи могут разрабатывать программы на языках, которые они знают, стандартным последовательным способом, а компилятор в состоянии обнаружить и извлечь параллелизм, который содержится в пределах программы. Использование автоматических методов уменьшает время распараллеливания и вероятность ошибки, но не всегда обеспечивает необходимую эффективность параллельных программ. Кроме того, компиляторы распараллеливания для наиболее популярных платформ - кластеров только начинают разрабатываться [55].
Количество процессоров и время вычисления
Размер и сложность задач влияют на время параллельного вычисления программ приложения. Когда программа приложения распределяется на задачи, то главным вопросом является — достаточно ли большой объем вычислений заключен в одной подзадаче, чтобы была необходимость передавать её для решения отдельному процессору. Гранулярность задач определяется как отношение времени выполнения задачи во времени коммуникации [93]. Задачи считается мелкозернистой (fine-grain), если это отношение сравнительно низкое, и значит, что вычисления занимают меньше времени, чем коммуникации. Мелкозернистая задача (fine-gpain task) подразумевает высокую степень параллелизма и высокое количество накладных расходов на коммуникации. С другой стороны, задача будет крупнозернистой (coarse-grain), если отношение сравнительно высоко. Согласно Cosnard и Trystram [94] термин мелкозернистость (fine granularity) используется, если количество процессоров больше или равно количеству фрагментов данных, в противном случае используется термин крупнозернистость (coarse granularity). Связь между количеством процессоров и количеством задач тоже важна.
Число используемых процессоров - также важный фактор. Максимальная производительность будет получена, если все процессоры (PEs) будут заняты все время вычисления, то есть, в течение процесса вычислений нет бездействующих процессоров. Увеличение количества процессоров не всегда обеспечивает рост производительности из-за увеличения накладных расходов. Данную проблему можно решить, если использовать различное количество процессоров. Большое количество процессоров необходимо тогда, когда требуется решить задачу как можно быстрее. Эффективность увеличивается, когда число используемых процессоров и время выполнения минимальны. Возникает вопрос, как можно решить проблему с оптимальным количеством процессоров и за минимальное время вычисления. Задача может быть решена за минимальное время, если уменьшить накладные расходы коммуникаций и загрузить все процессоры производительными задачами в течение всего времени вычисления.
Распределение вычислительной нагрузки направлено на улучшение производительности системы, обычно выраженное во временной характеристике или доступности ресурсов, путём размещения нагрузки среди набора узлов. Проблема распределения вычислительной нагрузки возникает по ряду причин [95]:
- структура распределенного приложения неоднородна, различные логические процессы требуют различных вычислительных мощностей;
- структура вычислительного комплекса (например, кластера), также неоднородна, т.е. разные вычислительные узлы обладают разной производительностью;
- структура межсоединений неоднородна, т.к. линии связи, соединяющие узлы, могут иметь различные характеристики и пропускную способность.
Методы распределения нагрузки системы можно разделить на два класса [96]: статические или динамические.
При статическом методе распределение нагрузки на узлы выполняется априорно или детерминировано (deterministically) без учёта реального хода выполнения программы. Такой подход и прост, и эффективен, когда нагрузку можно точно рассчитать и планировщик может управлять всеми узлами или, по крайней мере, осведомлён об их текущей загрузке при решении задачи распределения вычислений. Проблемы возникают, когда фоновая нагрузка склонна к изменениям, или не все процессы находятся в пределах управления статического распределителя нагрузки.
Динамическое распределение нагрузки предусматривает перераспределение вычислительной нагрузки на узлы во время вычисления. Программное обеспечение, реализующее динамическую балансировку, определяет:
- загрузку вычислительных узлов;
- пропускную способность линий связи;
- частоту обменов сообщениями между узлами распределенного приложения и др.
Системы динамического распределения нагрузки обычно управляют нагрузкой узлов в тех случаях, когда во время работы приложения возникают события, которые могут влиять на эффективность работы системы. Именно это различие между статической и динамической формами распределения нагрузки является основным предметом интереса к динамическому распределению нагрузки.
Главная цель распределения нагрузки — это разделение вычислений между узлами системы. Этой цели можно достичь изменяя порядок приоритетности, точный выбор которого зависит от обстановки и архитектуры конкретной системы. Распределение нагрузки обычно описывается в литературе как балансировка нагрузки или разделение нагрузки. Эти термины иногда заменяют друг друга, но у них есть и вполне чёткие определения. Разделение нагрузки это самая грубая форма распределения вычислений. Нагрузка может размещаться только на бездействующих узлах и может рассматриваться как бинарная, т.е. узел либо бездействует, либо занят.
Балансировка нагрузки является утончённой формой по сравнению с разделением только в том случае, если она производится динамически. Динамическая балансировка пытается обеспечить загрузку всех узлов системы, перераспределяя нагрузку на те узлы, которые простаивают в момент принятия решения.
Алгоритм случайного поиска
Итерационные алгоритмы применяются для решения задачи размещения с различными критериями оптимизации F(p): суммарная длина соединений, суммарное число пересечений соединений и т. д. В любом итерационном алгоритме исследуется некоторое подмножество размещений, в некотором смысле близких к начальному, для выделения в нем размещения с меньшим значением функции-критерия.
В настоящее время имеется ограниченное число тестовых задач, по которым известны оценки эффективности различных алгоритмов. Одной из них является тест-задача Штейнберга [113], состоящая- в минимизации суммарной длины соединений 36 элементов, размещаемых на поле размером 4x9 (рис. 4.3). С точки зрения оптимизации это задача квадратичного назначения. Матрица соединений элементов представлена в приложении 1.
Тест-задача Штейнберга (расположение позиций) Сначала проведем исследование эффективности последовательной реализации различных алгоритмов. Для экспериментальных исследований использовались различные последовательные итерационные алгоритмы, которые можно разделить на:
- алгоритмы случайного поиска;
- алгоритмы парных перестановок;
- алгоритмы групповых перестановок.
Подробное их описание представлено ниже.
Итерационные алгоритмы используют для улучшения исходного размещения элементов на плате некоторый процесс перестановки местами элементов. В случае минимизации суммарной длины соединений оптимизируется величина (3.2).
В качестве начального может быть взято решение, полученное одним из конструктивных алгоритмов, либо с помощью генератора случайных чисел, или заданное вручную.
Основная идея алгоритма случайного поиска заключается в том, что с помощью генератора случайных чисел определяются позиции всех 36 элементов и, получается некоторое размещение р с оценкой F(p). Результат первой итерации используется в качестве эталона. Повторим процедуру и получим новое размещение. Если оценка F для этого размещения лучше эталона, то заменим его и продолжим работу. Программа будет работать до тех пор, пока не выполнит заданное число итераций.
Для нахождения точного решения необходимо произвести перебор п! различных вариантов размещения элементов, что при п 15 становится трудновыполнимой задачей. В алгоритмах случайного поиска решение получается путем выбора лучшего варианта из некоторого ограниченного набора случайно сгенерированных размещений. Очевидно, что с увеличением числа перебираемых вариантов будет повышаться и точность решения. Одной из основных проблем при реализации алгоритма является быстрое получение случайного размещения. Если мы начнем заполнять элементы вектора р случайными числами и при этом проверять, чтобы элементы не повторялись, то чем больше будет заполненных элементов, тем чаще будут выпадать повторяющиеся цифры. В результате мы будем тратить много времени на генерацию каждого нового размещения. Для сокращения времени генерации предлагается использовать разбиение вектора Р на части, что снизит вероятность повторов, рассмотрены ранее (в разделе 3.4.2). Блок-схема алгоритма представлена на рис. 4.4.
Алгоритмы парных перестановок являются простейшими в рассматриваемом классе алгоритмов. Различные варианты алгоритмов отличаются правилами выбора переставляемых элементов, а также глубиной поиска локального экстремума.
Рассмотрим один из вариантов алгоритма. Пусть имеется некоторое начальное размещение. Оно может быть задано вручную или получено конструктивным алгоритмом. С помощью генератора случайных чисел выбираются два элемента е, и е}, и меняются местами. Рассчитывается новое значение F{p); если оно меньше исходного, то производится перестановка, а если нет, то выбирается другая пара элементов и осуществляется аналогичная процедура. Процесс продолжается до тех пор, пока не выполнит заданное число итераций. Алгоритмы парных перестановок минимизируют функционал (3.2).
Блок схема алгоритма парных перестановок представлена на рис. 4.10. Приращение значения функции length (3.2) при перестановке местами элементов е, и Cj, находящихся первоначально в позициях first и second вектора р соответственно, рассчитывается с учетом симметрии матриц [R] и [D].
