Содержание к диссертации
Введение
Глава 1. Обзор существующих архитектурных и программных платформ 11
1.1 Использование комбинаторных алгоритмов 11
1.2 Способы реализации алгоритмов 12
1.3 Существующие архитектуры параллельных компьютеров 16
1.3.1 SMP (Symmetric Multiprocessing) 17
1.3.2 МРР (Massive Parallel Processing) 19
1.3.3 NUMA (неоднородный доступ к памяти) 20
1.3.4 cc-NUMA (неоднородный доступ к памяти с поддержкой когерентности кэшей) 21
1.3.5 PVP (параллельно-векторные системы) 22
1.3.6 Кластеры 23
1.3.7 GRID (вычислительная сеть) 26
1.3.8 Выводы 27
1.4 Способы организации взаимодействия процессов 28
1.4.1 Стандарты 28
1.4.2 Технологии 33
1.4.3 Высокоуровневые средства разработки 34
1.4.4 Выводы 36
Выводы по главе 1 37
Глава 2. Создание высокоэффективных реализаций параллельных комбинаторных алгоритмов генерации комбинаторных объектов 39
2.1 Эффективная реализация параллельной генерации перестановок N-элементного множества 40
2.2 Эффективная реализация параллельной генерации всех подмножеств TV-элементного множества 48
2.3 Эффективная реализация параллельной генерации элементных подмножеств 56
2.4 Генерация комбинаторных объектов в гетерогенной кластерной среде 69
2.4.1 Учет производительности узлов кластера при распараллеливании алгоритма 70
2.4.2 Использование средств администрирования МРІ для балансировки вычислительной нагрузки 72
2.5 Вычислительный эксперимент. Генерация комбинаторных объектов в гетерогенной среде 75
2.6 Метаалгоритм генерации комбинаторных объектов 83
2.6.1 Фаза сбора данных 86
2.6.2 Эффективное распределение задач 88
2.6.3 Конструирование метаалгоритма управления распараллеливанием генерации комбинаторных объектов 90
Выводы по главе 2 93
Глава 3. Эффективные реализации параллельных алгоритмов на графах и матроидах 95
3.1 Эффективная реализация параллельного алгоритма Флойда 95
3.1.1 Метод распараллеливания 97
3.1.2 Вычисление оптимального кол-ва узлов для параллельного выполнения алгоритма Флойда 100
3.1.3 Вычислительный эксперимент 105
3.2 Эффективная реализация параллельного жадного алгоритма на матроидах 108
3.2.1 Метод распараллеливания 113
3.2.2 Вычисление оптимального количества узлов для параллельного выполнения жадного алгоритма на матричном матроиде 115
3.2.3 Вычислительный эксперимент 121
3.3 Выполнение параллельных алгоритмов Флойда и жадного алгоритма на матричном матроиде в гетерогенной кластерной среде 124
Выводы по главе 3 133
Глава 4. Библиотека параллельных реализаций комбинаторных алгоритмов 135
4.1 Общее назначение библиотеки 135
4.2 Требования, предъявляемые к библиотеке 135
4.3 Выбор языка реализации 138
4.4 Особенности проектирования и реализации программ в среде стандарта МИ и MPI-2 ..139
4.4.1 Программа конфигурирования гетерогенной кластерной среды с использованием средств MPI 140
4.4.2 Реализация метаалгоритма генерации комбинаторных объектов 141
4.4.3 Реализация распараллеливания алгоритма Флойда в среде MPI 153
4.4.4 Реализация распараллеливания жадного алгоритма на матричных матроидах в среде MPI 161
4.4.5 Тестирование реализаций параллельных алгоритмов 164
4.5 Общая структура библиотеки эффективных параллельных реализаций комбинаторных алгоритмов 167
Выводы по главе 4 180
Заключение 181
Литература
- cc-NUMA (неоднородный доступ к памяти с поддержкой когерентности кэшей)
- Эффективная реализация параллельной генерации элементных подмножеств
- Вычисление оптимального кол-ва узлов для параллельного выполнения алгоритма Флойда
- Особенности проектирования и реализации программ в среде стандарта МИ и MPI-2
Введение к работе
В последние десятилетия получены теоретические результаты, свидетельствующие о том, что для широкого класса задач не существует достаточно «эффективных алгоритмов», и способ их решения носит комбинаторный характер. С другой стороны, налицо - возрастающая с каждым годом потребность решения задач в областях: дискретной оптимизации, исследования операций, моделирования процессов и систем в экономике, физике, химии и т.д. [1,2,3]
Центральными в решении данных задач являются комбинаторные объекты, которые можно условно разделить на несколько классов:
элементарные комбинаторные объекты (перестановки множества, подмножества множества, k-элементные подмножества, разбиения множества, разбиения чисел);
графы;
матроиды.
Использование комбинаторных объектов в решении задач подразумевает их создание и обработку. Проблема заключается в том, что комбинаторные алгоритмы часто характеризуются большим объемом производимых вычислений, поэтому эффективность используемых алгоритмов уже давно находится в центре внимания ученых.
Чтобы усилить эффективность комбинаторных алгоритмов и сделать время их выполнения приемлемым для конечного потребителя (исследовательских институтов, военных ведомств, правительств) в мире разрабатываются все более мощные вычислительные комплексы, отличающиеся друг от друга типом архитектуры, что является следствием их ориентации на решение конкретных задачи (обработки векторов, больших объемов данных, хранения данных и т.д.).
Применение суперЭВМ налагает особые требования на вновь
создаваемые программные средства, обеспечивающие надежную и
экономичную реализацию алгоритма при решении прикладных задач. Эффективность использования суперЭВМ проявляется при создании сложных исследовательских комплексов и экспертных систем. Однако, написание эффективной параллельной программы намного труднее, чем написание последовательной.
Таким образом, создание программного обеспечения для параллельных компьютеров является центральной проблемой суперкомпьютерных вычислений [4], поэтому разработанные ранее последовательные комбинаторные алгоритмы и их реализации требуют переосмысления и переработки с учетом архитектур современных вычислительных комплексов для построения их эффективных параллельных форм.
Указанные выше обстоятельства обусловливают выбор в качестве объекта исследования алгоритмы генерации и обработки комбинаторных объектов. Данная работа направлена на решение проблемы параллельной генерации и обработки комбинаторных объектов с использованием современных вычислительных комплексов.
В качестве предмета исследования были выбраны методы распараллеливания последовательных форм алгоритмов генерации и обработки комбинаторных объектов для их выполнения в гомогенных и гетерогенных кластерах.
Цель работы - повышение эффективности алгоритмов генерации и обработки комбинаторных объектов за счет использования их параллельных форм в кластерных системах
Задачи исследования. Для достижения поставленной цели были решены следующие задачи:
Обзор существующих библиотек параллельных реализаций алгоритмов и анализ архитектур, позволяющих производить параллельные вычисления;
Анализ существующих алгоритмов генерации и обработки комбинаторных объектов, разработка их эффективных последовательных реализаций;
Разработка методов распараллеливания последовательных алгоритмов
7 генерации и обработки комбинаторных объектов в гомогенных и гетерогенных кластерах;
Решение задачи выбора оптимального количества узлов кластера для выполнения параллельных алгоритмов: Флойда и "жадного" алгоритма на матричном матроиде;
Проектирование и реализация библиотеки эффективных параллельных комбинаторных алгоритмов;
Методы исследования. При выполнении диссертационной работы использовались: теория множеств, теория графов, теория матроидов, линейная алгебра, технологии программирования.
Для оценки производительности полученных реализаций последовательных и параллельных алгоритмов использовалась РТ-метрика. При проектировании и реализации библиотеки эффективных реализаций использовался язык моделирования UML, объектно-ориентированный подход.
Научная новизна работы состоит в следующем:
Предложен обобщенный метод распараллеливания алгоритмов генерации комбинаторных объектов (подмножеств n-элементного множества, к-подмножеств, перестановок), дающий возможность повысить эффективность использования узлов гомогенного и гетерогенного кластеров;
Предложен способ учета производительности узлов гетерогенного кластера при выполнении параллельных алгоритмов генерации комбинаторных объектов, позволяющий сбалансированно распределять задачи между узлами данного кластера;
Разработаны методы распараллеливания на основе параллелизма данных алгоритмов: Флойда и жадного алгоритма на матричном матроиде,-обеспечивающие эффективность реализаций за счет оптимальной загрузки узлов гомогенного и гетерогенного кластеров;
Разработан метод определения оптимального количества узлов кластера для выполнения параллельных алгоритмов: Флойда и жадного алгоритма на матричном матроиде, дающий возможность учесть такие параметры
8 кластера как пропускная способность коммуникационной сети, производительность отдельных узлов кластера.
Практическая значимость работы заключается в следующем:
Разработана объектно-ориентированная библиотека параллельных алгоритмов генерации и обработки комбинаторных объектов, позволяющая ускорить процесс разработки использующих генерацию и обработку комбинаторных объектов программ, программных комплексов и пакетов прикладных программ для гомогенных и гетерогенных кластеров;
С использованием разработанной библиотеки проведена экспериментальная оценка эффективности предложенных методов распараллеливания комбинаторных алгоритмов, показавшая почти линейный рост ускорения параллельных комбинаторных алгоритмов с увеличением числа используемых узлов кластера (в случае алгоритмов, работающих с матрицами, такой рост наблюдается при количестве узлов не больше расчетного).
Реализация и внедрение результатов работы. Результаты работы внедрены в НПФ «КРУГ» г. Пенза.
Основные положения, выносимые на защиту:
Методы распараллеливания алгоритмов генерации комбинаторных объектов: перестановок, подмножеств n-элементного множества, к-подмножеств - на основе параллелизма данных;
Методы учета производительности узлов гетерогенного кластера для выполнения алгоритмов генерации;
Методы распараллеливания алгоритмов Флойда и жадного алгоритма на матричном матроиде на основе параллелизма данных для выполнения в гомогенных и гетерогенных кластерах;
Методы расчета оптимального числа используемых узлов кластера для работы параллельных алгоритмов: Флойда и жадного алгоритма на матричном матроиде;
5. Программные инструментальные средства, позволяющие ускорить процесс разработки программ, программных комплексов и пакетов прикладных программ, использующих генерацию и обработку комбинаторных объектов.
Содержание работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка используемой литературы и четырех приложений.
В первой главе анализируются существующие способы выполнения алгоритмов. Делается вывод о целесообразности использования параллельных алгоритмов генерации и обработки комбинаторных объектов. Рассматриваются существующие архитектуры многопроцессорных систем и сред исполнения параллельных программ. Показывается, что наиболее перспективной архитектурой можно считать кластерную архитектуру и среду исполнения MPI. Производится анализ существующих библиотек параллельных реализаций алгоритмов.
Во второй главе анализируются существующие последовательные алгоритмы генерации комбинаторных объектов. Предлагаются методы распараллеливания процесса генерации: подмножеств п-элементного множества, k-подмножеств, перестановок. Предлагается обобщенный алгоритм генерации данных комбинаторных объектов, позволяющий в качестве основы использовать произвольный последовательный алгоритм генерации. Предлагаются методы учета производительности узлов гетерогенного кластера для выполнения алгоритмов генерации комбинаторных объектов.
В третьей главе предлагаются методы распараллеливания алгоритмов: Флойда, жадного алгоритма на матричном матроиде, предлагается общий для данных алгоритмов метод распределенного хранения матрицы для выполнения алгоритмов в гомогенной и гетерогенной средах. Исследуется вопрос выбора оптимального количества узлов для выполнения описанных алгоритмов.
В четвертой главе описываются основные аспекты проектирования и реализации: библиотеки эффективных реализаций параллельных алгоритмов, предложенных во второй и третьей главах.
10 В заключении приводятся основные результаты работы.
В приложениях приводятся: описание существующих последовательных алгоритмов генерации комбинаторных объектов, характеристики использовавшихся для практических экспериментов кластеров, результаты тестирования параллельных реализаций комбинаторных алгоритмов, копиа акта внедрения, копии свидетельств регистрации разработанных программных средств в Отраслевом фонде алгоритмов и программ.
Апробация работы. Основные положения и результаты работы
докладывались на:
VI международной научно-технической конференции "Новые информационные технологии и системы", г. Пенза, 2004 г.;
XI Всероссийской научно-технической конференции, г. Н. Новгород, 2004г.
Публикации. По теме диссертации опубликовано 15 печатных работ, из них 6 статей и 9 тезисов. Список публикаций приведен в разделе Литература.
Результаты работы зарегистрированы в Отраслевом фонде алгоритмов и программ. Копии полученных свидетельств приведены в приложении Г.
cc-NUMA (неоднородный доступ к памяти с поддержкой когерентности кэшей)
cc-NUMA (неоднородный доступ к памяти с поддержкой когерентности кэшей) Логически память NUMA системы представляется единым сплошным массивом, но распределена между узлами. Любые изменения сделанные каким-либо процессором в памяти становятся доступны всем процессорам благодаря механизму поддержания когерентности кэшей. Архитектура cc-NUMA предполагает кэширование как вертикальных (процессор - локальная память) так и горизонтальных (узел - узел) связей. Кэширование вертикальных связей позволяет организовать каждый узел как UMA компьютер, позволяя получить преимущества UMA архитектуры, используя небольшое количество процессоров (обычно 2 или 4) над общей памятью и увеличивая тем самым производительность до 4 раз. В тоже время, возможность комбинирования в одной вычислительной системе множества узлов UMA данной архитектуры позволяет наращивать мощность, не увеличивая слишком количества процессоров в каждом узле. А это позволяет использовать преимущества UMA архитектур, и одновременно имея большое количество процессоров в одной вычислительной системе.
В системе cc-NUMA физически распределенная память объединяется, как в любой другой SMP-архитектуре, в единый массив. Не происходит никакого копирования страниц или данных между ячейками памяти. Адресное пространство в данных архитектурах делится между узлами. Данные, хранящиеся в адресном пространстве некоторого узла, физически хранятся в этом же узле. Нет никакой программно - реализованной передачи сообщений. Существует просто одна карта памяти, с частями, физически связанными медным кабелем, и очень умные (в большей степени, чем объединительная плата) аппаратные средства. Аппаратно - реализованная кэш-когерентность означает, что не требуется какого-либо программного обеспечения для сохранения множества копий обновленных данных или для передачи их между множеством экземпляров ОС и приложений. Со всем этим справляется аппаратный уровень точно так же, как в любом SMP-узле, с одной копией ОС и несколькими процессорами [11].
Программное обеспечение для NUMA архитектур не использует коммуникационные операции явно. Все процессоры разделяют общее адресное пространство. Копирование данных, из одного адреса в другой, может фактически повлечь пересылку данных из одного узла в другой, если целевой адрес принадлежит адресному диапазону другого узла. В этом состоит ещё одно сходство cc-NUMA и UMA архитектур, и эта особенность позволяет использовать в cc-NUMA программное обеспечение для UMA архитектур с незначительными изменениями. PVP (параллельно-векторные системы) Основным признаком PVP-систем является наличие специальных векторно-конвеиерных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных, эффективно выполняющиеся на конвейерных функциональных устройствах. Как правило, несколько таких процессоров (1-16) работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций. Несколько таких узлов могут быть объединены с помощью коммутатора (аналогично МРР). Достоинства: Если алгоритм представлен в форме операций над векторами, то вероятно производительность PVP-системы будет очень высокой; Нет необходимости в описании и реализации взаимодействий разных узлов. Недостатки: Высокая стоимость; Невозможность представления многих алгоритмов в форме операций над векторами.
Кластерные системы представляют собой некоторое число рабочих станций или персональных компьютеров (каждый из которых называется узлом кластера), объединенных высокоскоростной сетью, например: Gigabit Ethernet или ATM [13]. Для простоты управления кластерами, используется специальное ПО, помогающее управлять загруженностью узлов и координировать их работу.
Одним из примеров реализации кластерной системы является кластеры Beowulf. Beowulf - это собственное имя первого кластера, созданного в GSFC (Goddard Space Flight Center), на основе компьютеров Intel архитектуры под ОС Linux. Проект Beowulf начался летом 1994 года в научно-космическом центре NASA. Первым кластером Beowulf была система, состоящая из 16 узлов (486DX4/100Mhz). В настоящее время термин Beowulf применяется ко всем аналогичным кластерным системам.
Эффективная реализация параллельной генерации элементных подмножеств
Кластерные системы представляют собой некоторое число рабочих станций или персональных компьютеров (каждый из которых называется узлом кластера), объединенных высокоскоростной сетью, например: Gigabit Ethernet или ATM [13]. Для простоты управления кластерами, используется специальное ПО, помогающее управлять загруженностью узлов и координировать их работу.
Одним из примеров реализации кластерной системы является кластеры Beowulf. Beowulf - это собственное имя первого кластера, созданного в GSFC (Goddard Space Flight Center), на основе компьютеров Intel архитектуры под ОС Linux. Проект Beowulf начался летом 1994 года в научно-космическом центре NASA. Первым кластером Beowulf была система, состоящая из 16 узлов (486DX4/100Mhz). В настоящее время термин Beowulf применяется ко всем аналогичным кластерным системам.
Кластер Beowulf состоит из нескольких отдельных узлов, объединенных в общую сеть. Оптимальным считается построение кластеров на базе двухпроцессорных компьютеров. Для уменьшения накладных расходов на взаимодействие между узлами применяют полнодуплексный 100 MB Fast Ethernet (реже используют SCI), создают несколько сетевых сегментов или соединяют узлы кластера через коммутатор. В качестве программного обеспечения применяют ОС Linux, бесплатные реализации MPI и пр.
Кластеры в настоящее время находят самое широкое применение [14]. В качестве примера приведем несколько реально работающих кластеров:
1. Locus Supercluster - система используется для создания формул фармацевтических препаратов. Применяемая технология Locus Discovery использует методы химии и биоинформатики. Новые математические методы моделирования и использование кластерной системы позволяют сократить срок открытия препарата, ранее измеряемый годами, до нескольких недель;
2. Biopendium - самый большой коммерческий вычислительный ресурс Европы в области биотехнологий. На данный момент результатом использования системы Biopendium является создание нового препарата Nicastrin, использующегося в настоящее время для лечения болезни Альцгеймера (Alzheimer);
3. CBRC Magi System - на данной системе проходят проверку а затем используются новые методы биологических исследований. В частности, исследуются и применяются методы: для предсказания функций генов и белка; для анализа и предсказания трехмерных структур и функциональных компонентов белка;
4. Incyte Genomics - компания, владеющая данным кластером, предлагает услуги по выполнению работ, связанных с генными технологиями и требующих больших вычислений. Предоставляется доступ к базам данным (БД) с информацией.
Таким образом, можно назвать следующие типы кластеров, по задачам, которые им приходится решать [15]: Кластеры высокой надежности (highly-available clusters). Для выполнения этой задачи (можно ее сформулировать и как "горячее резервирование") настройка кластера осуществляется таким образом, что в любой момент времени каждый узел кластера является точной копией любого другого узла. В этом случае выход из строя одного из узлов никак не влияет на доступность информации всего кластера - это необходимо для того, чтобы выполнение некоторых работ (на основе данных кластера) не прерывалось;
Равномерно-загруженные KJiacTepbi(load-balancing clusters) обрабатывают огромный объем транзакций схожего типа (web-серверы, серверы баз данных);
Кластеры для научных расчетов используются также как и обычные МРР-системы, но кластеры обладают одним существенным достоинством - они легко расширяются дополнительными узлами. Кроме того, при разработке ПО для таких кластеров, стараются предоставить как можно большую масштабируемость, что дает возможность добавления узлов в кластер во время работы ПО при минимальной реконфигурации.
Кроме научных экспериментов, кластеры применяются в компьютерной графике для генерации сложных сцен с максимальной скоростью,- это необходимо, например, при создании фильма, где количество кадров выходит за тысячи и десятки тысяч. Находят свое использование кластеры и в области прогнозирования тенденций и моделирования ситуаций в природе, экономике и других областях.
Основными достоинствами кластерной архитектуры являются: низкая стоимость (как и у МРР-архитектуры); естественная распределенность узлов; простота расширения, а, следовательно, и легкость наращиваемости производительности; надежность.
Среди недостатков кластерной архитектуры можно выделить следующие: большое время доступа процесса узла к памяти других узлов; необходимо специальным образом проектировать программу, используя операции: пересылки данных между узлами, синхронизации доступа к ресурсам и т.д.
Вычисление оптимального кол-ва узлов для параллельного выполнения алгоритма Флойда
В существующих работах много внимания уделяется проблемам повышения теоретической эффективности алгоритмов. Однако эффективность алгоритма зависит и от того, на какой платформе и как реализуется алгоритм.
Обратим свое внимание на некоторые проблемы, которые могут возникнуть при работе распараллеленного указанным выше способом алгоритма Флойда в кластерной среде на базе сети ЭВМ.
Если представить себе, что кластер, в котором будет выполняться алгоритм Флойда, содержит около тысячи ЭВМ, а количество вершин в графе не превышает, скажем, 2000, то кажется очевидным, что, в таком случае, нагрузка на сеть будет велика, в то время как нагрузка на каждый из узлов ничтожна. Таким образом, можно сказать, что одной из проблем, возникающей при распараллеливании алгоритма Флойда, является проблема определения оптимального количества узлов кластера, которые должны участвовать в вычислительном процессе [92].
Договоримся использовать в рассуждении следующие обозначения: N - количество вершин в графе Г- Время пересылки одной строки матрицы смежности (Nэлементов) Z - Время просчета одной строки матрицы смежности (внутренний цикл) К - оптимальное количество узлов для распределенного выполнения алгоритма Флойда FK- время выполнения алгоритма Флойда с использованием К узлов. Общее время выполнения алгоритма Флойда на одном узле: F(\) = N2Z
При распараллеливании алгоритма на К узлов данное время сократится в К раз. Однако, возникнут затраты времени, связанные с передачей данных по сети. В соответствии с алгоритмом распараллеливания, общее количество строк, которое передается от каждого узла всем остальным, равно N(K-l). Тогда время FK параллельного выполнения алгоритма Флойда на К узлах запишется как: N2Z F(K) = -=- + TN(K-\) К
Таким образом, задача определения оптимального количества узлов для выполнения алгоритма сводится к минимизации данной функции по К: FK - min Выполним это стандартным методом: NZ Щ + Т(К-\)) тт Для поиска экстремумов функции решаем уравнение: F K=Q (N( + T(K-\))) = 0 к. щЩ- + Т(К-1)У = 0 к 2 ZN к1 = если требуется найти только длину кратчайших путей, и если требуется найти и сами пути, так как в этом случае приходится передавать два вектора (из матрицы D и матрицы W). Обозначим, два этих значения К как KD и Kw, соответственно, и примем во внимание ограничение, накладываемое на значения К, вследствие его натуральной природы, тогда оптимальное количество узлов кластера для выполнения на нем алгоритма Флойда запишется следующим образом: KD = \ZN (3.1.2.1) Kw л/2 (3.1.2.2) Оператор [_ J означает взятие целой части, или округление вниз.
Размер одной строки матрицы смежности - (4iV) байт, так как каждый элемент матрицы смежности имеет тип unsigned long.
Допустим, скорость локальной вычислительной сети S - ЮОМбит, тогда теоретическая скорость передачи будет (100 000 000/8) байт/с, что составляет 12 500 000 байт/с. Учтем накладные расходы на пересылку сетевых пакетов. Чтобы выяснить величину накладных расходов проведем эксперимент, измеряя время передачи по сети 100 000 000 байт с помощью функций MPI: MPI_Send, MPI_Recv. Результаты эксперимента приведены в таблице 3.1.2.
Учитывая, что передача данных может осуществляться по разным протоколам с использованием разного количества промежуточных звеньев (что может влиять на конечную производительность сети), примем теоретический процент накладных расходов равным 10-20%. Введем коэффициент ВЭфф, показывающий долю реальной пропускной способности сети от теоретической. Тогда итоговая эффективная скорость передачи данных в сети будет: Speedб = S Вэфф байт/с
Так как основной единицей в наших расчетах выступает строка, состоящая из N элементов, размер каждого из которых составляет 4 баша, то выразим скорость Speed в строках в секунду: Speed, ї спрок/с 125000- S-BM Speedy строк/с соответственно, время Т: Speed с 125000-5-5 / С учетом произведенных расчетов формула (3.1.2.1) запишется следующим образом: К0 125000- SZ -Вофф (3.1.2.3) и формула (3.1.2.2), соответственно: 125000-Ж-i Klv = 00-S7-R .. (3.1.2.4)
В формулах (3.1.2.3) и (3.1.2.4) осталась одна неопределенная переменная - Z Если предположить, что кластер содержит однотипные ЭВМ, то можно предложить определять Z путем предварительного замера времени выполнения элементов алгоритма Флойда на одном из вычислительных узлов.
Особенности проектирования и реализации программ в среде стандарта МИ и MPI-2
Так как описанные в главах 2 и 3 алгоритмы сформулированы в терминах C++, то основная проблема при реализации алгоритмов связана не с языком программирования, а со средой их выполнения MPI. Структура среды выполнения и коммуникативные функции среды неизбежно накладывают некоторые ограничения и дают определенные возможности для реализации параллельных программ. Рассмотрим структуру MPI-среды и МР1-программы. Так как MPI является стандартом, то рассматриваемые структуры являются общими для всех реализаций MPI.
Изучив структуру среды MPI и структуру MPI-программы, мы можем конкретизировать реализации алгоритмов с учетом их особенностей.
Программа конфигурирования гетерогенной кластерной среды с использованием средств MPI
В соответствии с описанными в главе 2 принципами учета производительности узлов кластера была спроектирована и реализована программа MPIHeterogeneousConfig, формирующая конфигурационную строку для запуска МРІ-приложения в гетерогенной среде.[101]
Выбор типа генерируемых во время теста комбинаторных объектов (для наиболее точного соответствия задачи и производительности узлов при ее выполнении) осуществляется указанием одного из ключей (-р), приведенных в таблице 4.4.1. Кроме того, существует возможность: задать максимально допустимое число запускаемых на одном узле процессов (ключ -mt); задать приблизительное количество подзадач, на которое может быть разбита целевая задача (ключ -astc).
Общий вид строки запуска программы выглядит следующим образом: MPIHeterogeneousConfig Ключи Программа работает по следующему алгоритму: 1. запуск на каждом узле кластера замера времени генерации выбранного комбинаторного объекта; 2. нормирование полученных результатов по описанному выше методу С. = - .. к, где К - уточняющий коэффициент, предварительно К=\ .0; 3. вычисление общего количество полученных потоков Р = ] ][с,.J; 4. вычисление уточняющего коэффициента по первому методу (учитывая параметр —mt - максимальное количество потоков на одном узле): Кх = t М- тш , где М- значение параметра -mt; 5. вычисление уточняющего коэффициента по второму методу (учитывая параметр -astc - приблизительно количество подзадач, на которое можно разбить исходную задачу): К2 = где А - значение параметра -astc; 6. Применение наиболее сильного ограничения: K=min(Ki,K2); 7. Если К \, повторить шаг 2; 8. формирование запускного bat-файла, учитывающего производительность узлов при запуске МРІ-приложения: на і-м узле запускается \_C.j потоков.
В результате работы программа выводит в файл Имя_МРІ_приложения.Ьаі командную строку для запуска программы Имя_МР1_приложения с учетом производительности узлов средствами МРІ и дублирует эту строку, выводя ее в выходной поток.
Опишем подробнее методы определенного в параграфе 2.6 интерфейса, который должен поддерживаться всеми классами, инкапсулирующими алгоритмы генерации комбинаторных объектов:
1) PTASKDATA GetTaskData(PTASKDATA plnitData);
Входные данные - область памяти, содержащая последовательно расположенные данные, описывающие свойства класса комбинаторных объектов. Для рассмотренных выше комбинаторных объектов входные данные
Выходные данные - набор данных, который можно использовать как исходный для создания экземпляра реализации
2) ulong GetSubTaskCount(PTASKDATA pTaskData); Входные данные: pTaskData - область памяти, полученная из функции GetTaskData или GetSubTaskData
Выходные данные - количество наборов данных, на которые можно разбить исходный набор. При реализации данной функции стоит обратить внимание на то, что разбиение некоторого небольшого набора данных на более мелкие не является эффективным, так как при этом время генерации комбинаторных объектов становится меньше времени установки коммуникаций между процессами. При возникновении указанной ситуации целесообразно возвращать 0, не разбивая задачу на подзадачи.
3) PTASKDATA GetSubTaskData(PTASKDATA pTaskData, ulong nSubTaskNo); Входные данные: pTaskData - область памяти, полученная из функции GetTaskData или GetSubTaskData nSubTaskNo - номер набора данных, 0 =nSubTaskNo GetSubTaskCount(pTaskData) Выходные данные - набор данных, который можно использовать как исходный для создания экземпляра реализации.
