close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«ЧЕЛЯБИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
КВАЛИФИКАЦИОННАЯ РАБОТА
Параллельное умножение матриц
Факультет
математический
Исполнитель
Харламенков Е.П.
Направление
Информационные
Группа
МТ-401
Вычислительной
Научный
Рудаков С.А.
математики и
руководитель
технологии
Кафедра
информационных
технологий
Дата защиты
Консультант
Оценка
Рецензент
Челябинск 2012
Содержание
СОДЕРЖАНИЕ........................................................................................................................................................ 2
ВВЕДЕНИЕ ............................................................................................................................................................ 3
ГЛАВА 1 ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ ........................................................................................................ 5
1.1 Немного истории ................................................................................................................................. 5
1.2 Архитектура высокопроизводительных ЭВМ ................................................................................. 7
1.3 Параллельные модели программирования ....................................................................................... 9
1.4 Принцип разработки параллельного алгоритма ......................................................................... 11
1.5 Коммуникационные библиотеки ..................................................................................................... 17
1.5.1 Библиотека OpenMP .................................................................................................................................... 17
1.5.2 Библиотека MPI ........................................................................................................................................... 18
1.5.3 Система PVM ................................................................................................................................................ 19
1.5.4 Сравнение MPI и PVM ................................................................................................................................. 21
1.6 Интерфейс передачи сообщений ..................................................................................................... 22
1.6.1 Почему MPI?................................................................................................................................................. 22
1.6.2 Основные функции MPI............................................................................................................................... 23
1.7 Расчет ускорения и эффективности алгоритма. ........................................................................ 25
ГЛАВА 2 РЕАЛИЗАЦИЯ ПРОГРАММЫ УМНОЖЕНИЯ МАТРИЦ ....................................................................................... 27
2.1 Математическая постановка задачи............................................................................................ 27
2.2 Разработка алгоритма .................................................................................................................... 29
2.3 Решение для кластера ...................................................................................................................... 31
2.3.1 Настройка кластера. .................................................................................................................................... 31
2.3.2 Настройка Visual Studio ............................................................................................................................... 31
2.3.3 Создание группового файла ....................................................................................................................... 33
2.3.4 Запуск программы ....................................................................................................................................... 34
2.4 Решение для суперкомпьютера ....................................................................................................... 35
2.4.1 Подключение к суперкомпьютеру. ............................................................................................................ 35
2.4.2 Обмен файлами с суперкомпьютером. ..................................................................................................... 39
2.4.3 Компиляция и запуск программы. ............................................................................................................. 41
2.4.4 Отладка программы .................................................................................................................................... 44
ГЛАВА 3 АНАЛИЗ РЕЗУЛЬТАТОВ. ............................................................................................................................ 49
3.1 Матрицы 500х500 ............................................................................................................................. 49
3.2 Матрицы 1500х1500 ......................................................................................................................... 53
3.3 Матрицы 2500х2500 ......................................................................................................................... 56
ЗАКЛЮЧЕНИЕ. ..................................................................................................................................................... 60
СПИСОК ЛИТЕРАТУРЫ. .......................................................................................................................................... 61
ПРИЛОЖЕНИЕ 1. ПОСЛЕДОВАТЕЛЬНОЕ УМНОЖЕНИЕ МАТРИЦ ................................................................................... 62
ПРИЛОЖЕНИЕ 2. ПАРАЛЛЕЛЬНОЕ УМНОЖЕНИЕ МАТРИЦ ........................................................................................... 63
2
Введение
Актуальность выбранной темы - Мощности современных процессоров
вполне достаточно для решения элементарных шагов большинства задач, а
объединение нескольких десятков таких процессоров позволяет решать многие
поставленные задачи, не прибегая к помощи суперкомпьютеров. Также
построение кластера на основе обычных персональных компьютеров намного
дешевле, чем приобретение суперкомпьютера. Но скорость вычисления
зачастую имеет решающее значение. Эффективность суперкомпьютера в
несколько раз превышает эффективность кластера с распределенной памятью, а
стоимость превышает в десятки раз. В результате возникает вопрос об
оптимальной
вычислительной
архитектуре
для
нашей
задачи.
Этим
определяется актуальность данной темы.
Цель
выпускной
параллельную
квалификационной
программу
быстродействия
этой
умножения
программы
на
работы
матриц.
кластере
–
разработать
Сравнить
результаты
и
суперкомпьютере.
Адаптировать программу для работы с библиотеками WMPI и OpenMPI, а
также с операционными системами Windows и Linux.
Предметная область – технологии и программные библиотеки для
управления кластером. Средства настройки данных библиотек. Средства
отладки параллельных программ.
Постановка задачи –
необходимо получить таблицы и графики,
иллюстрирующие время выполнения поставленных задач на различных
конфигурациях
кластеров,
а
также
при
различных
настройках
суперкомпьютера.
Для достижения поставленной цели в работе поставлены следующие
задачи:
1) изучить теоретические и практические методы организации кластеров.
2) разработать параллельную программу для кластеров с управлением OC
Windows (с помощью библиотек WMPI и OpenMPI)
3
3) перенести полученную программу на суперкомпьютер под управлением
OC Linux
4) провести сравнительный анализ быстродействия данной программы на
различных архитектурах.
Научная новизна – сравнительный анализ быстродействия кластера с
распределенной памятью и
суперкомпьютера, с учетом размерности узлов
суперкомпьютера и процессоров кластера.
Методы исследования и разработки проекта – разработка параллельной
программы, тестирование, анализ результатов, построение таблиц, графиков.
Практическая значимость работы – работа имеет значимость в учебных
целях. Может использоваться для обучения параллельному программированию
с библиотекой MPI, а также отладке параллельных программ и оптимизации их
для использования на кластере с распределенной памятью и суперкомпьютере.
4
Глава 1 Параллельное программирование
1.1 Немного истории
В середине 60-х годов прошлого века появились первые суперкомпьютеры,
это были параллельный 64-процессорный компьютер ILLIAC-IV и векторный
компьютер CDC 6500. Последний стал дебютом легендарного конструктора
высокопроизводительных вычислительных систем Сеймура Крея.
Сеймур Крей основал знаменитую фирму Cray, которая и сейчас выпускает
одноименные суперкомпьютеры.
Из современных проектов следует упомянуть ASCI (Accelerated Strategic
Computer Initiative) — проект, в рамках которого создаются вычислительные
системы с рекордной производительностью. В качестве примера можно
привести суперкомпьютеры ASCI Red и ASCI White, которые вошли в рейтинг
наиболее мощных вычислительных систем мира "Тор 500 Supercomputers".
Суперкомпьютеры являются дорогими, элитными машинами, стоимость
которых может достигать десятков миллионов долларов. Одним из решений
проблемы доступа к дорогостоящим суперкомпьютерным ресурсам является
создание центров, обслуживающих несколько организаций. Так, в США
имеется около десятка крупных суперкомпьютерных центров. Имеются такие
центры и в России, наиболее крупные из них расположены в Москве и СанктПетербурге.
Примерно в середине 80-х годов прошлого века ученые заинтересовались
возможностью использования кластерных систем в качестве относительно
недорогих заменителей суперкомпьютеров. Благодаря развитию сетевых
технологий, появилась возможность соединять вместе несколько рабочих
станций, в качестве которых могут использоваться обычные персональные
компьютеры. Ну а чем такая система не многопроцессорный вычислительный
комплекс? Было разработано необходимое программное обеспечение, которое
стало распространяться бесплатно. Работало это программное обеспечение в
среде операционной системы Linux, которая тоже является бесплатной,
оставаясь в то же время чрезвычайно гибкой и надежной. Таким образом,
5
основная часть программного обеспечения кластера оказывается бесплатной,
что значительно снижает суммарную стоимость всей системы. Оказалось, что в
результате можно построить многопроцессорный комплекс, который лишь в
2—3 раза уступает по быстродействию суперкомпьютеру, но дешевле его в
несколько сотен раз. Такие системы быстро завоевали популярность. [1]
6
1.2 Архитектура высокопроизводительных ЭВМ
Одной из наиболее известных схем классификации компьютерных
архитектур является таксономия Флинна, предложенная Майклом Флинном в
1972 году. В ее основу положено описание работы компьютера с потоками
команд и данных. В классификации Флинна имеется четыре класса архитектур:
1. SISD (Single Instruction Stream — Single Data Stream) — один поток
команд и один поток данных.
2. SIMD (Single Instruction Stream — Multiple Data Stream) — один поток
команд и несколько потоков данных.
3. MISD (Multiple Instruction Stream — Single Data Stream) — несколько
потоков команд и один поток данных.
4. MIMD (Multiple Instruction Stream — Multiple Data Stream) — несколько
потоков команд и несколько потоков данных.
Рассмотрим эту классификацию более подробно.
SISD (single instruction stream / single data stream) - одиночный поток
команд и одиночный поток данных. К этому классу относятся, прежде всего,
классические
последовательные
машины,
или
иначе,
машины
фон-
неймановского типа. В таких машинах есть только один поток команд, все
команды обрабатываются последовательно друг за другом и каждая команда
инициирует одну операцию с одним потоком данных
SIMD (single instruction stream / multiple data stream) - одиночный поток
команд и множественный поток данных. В архитектурах подобного рода
сохраняется один поток команд, включающий, в отличие от предыдущего
класса, векторные команды. Это позволяет выполнять одну арифметическую
операцию сразу над многими данными - элементами вектора.
MISD (multiple instruction stream / single data stream) - множественный
поток команд и одиночный поток данных. Определение подразумевает наличие
в архитектуре многих процессоров, обрабатывающих один и тот же поток
данных. Однако ни Флинн, ни другие специалисты в области архитектуры
компьютеров до сих пор не смогли представить убедительный пример реально
7
существующей вычислительной системы, построенной на данном принципе.
Ряд исследователей относят конвейерные машины к данному классу, однако
это не нашло окончательного признания в научном сообществе. Будем считать,
что пока данный класс пуст.
MIMD (multiple instruction stream / multiple data stream) - множественный
поток команд и множественный поток данных. Этот класс предполагает, что в
вычислительной системе есть несколько устройств обработки команд,
объединенных в единый комплекс и работающих каждое со своим потоком
команд и данных. [2]
8
1.3 Параллельные модели программирования
Рис 1 Модели программирования
Параллелизм данных характеризуется тем что:
1.Одна операция применяется сразу к нескольким элементам массива
данных. Различные фрагменты такого массива обрабатываются на векторном
процессоре или на разных процессорах параллельной машины обработкой
данных управляет одна программа.
2.Пространство имен является глобальным.
3.Параллельные
операции
над
элементами
массива
выполняются
одновременно на всех доступных данной программе процессорах.
Параллелизм задач характеризуется тем что:
1.Вычислительная
самостоятельных
задача
подзадач.
разбивается
Каждая
на
несколько
подзадача
относительно
выполняется
на
своем
процессоре (ориентация на архитектуру MIMD).
2. Для каждой подзадачи пишется своя собственная программа на обычном
языке программирования.
3. Подзадачи должны обмениваться результатами своей работы, получать
исходные данные. Практически такой обмен осуществляется вызовом процедур
специализированной
библиотеки.
Программист
при
этом
может
9
контролировать распределение данных между различными процессорами и
различными подзадачами, а также обмен данными. [3]
10
1.4 Принцип разработки параллельного алгоритма
Важнейшим и одним из наиболее трудоемких этапов создания программы
является разработка алгоритма. Если же речь идет о разработке параллельного
алгоритма,
возникают
дополнительные
проблемы.
Алгоритм
должен
обеспечивать эффективное использование параллельной вычислительной
системы. Следует заботиться и о хорошей масштабируемости алгоритма, а это
не всегда просто.
Процесс разработки параллельного алгоритма можно разбить на четыре
этапа как показано на рисунке 2.
Рис 2 Процесс разработки параллельного алгоритма
1. Декомпозиция. На данном этапе исходная задача анализируется,
оценивается
возможность
ее
распараллеливания.
Иногда
выигрыш
от
распараллеливания может быть незначительным, а трудоемкость разработки
параллельной программы большой. В этом случае первый этап разработки
алгоритма оказывается и последним. Если же "игра стоит свеч", задача и
связанные с ней данные разделяются на более мелкие части — подзадачи и
11
фрагменты
структур
данных.
Особенности
архитектуры
конкретной
вычислительной системы на данном этапе могут не учитываться.
2. Проектирование коммуникаций (обменов данными) между задачами. На
этом этапе определяются коммуникации, необходимые для пересылки
исходных данных, промежуточных результатов выполнения подзадач, а также
коммуникации, необходимые для управления работой подзадач. Выбираются
алгоритмы и методы коммуникации.
3. Укрупнение. Подзадачи могут объединяться в более крупные блоки,
если это позволяет повысить эффективность алгоритма и снизить трудоемкость
разработки. Основными критериями на данном этапе являются эффективность
алгоритма (производительность — в первую очередь) и трудоемкость его
реализации.
4.
Планирование
производится
вычислений.
распределение
подзадач
На
этом
между
заключительном
процессорами.
этапе
Основной
критерий выбора способа размещения подзадач — эффективное использование
процессоров с минимальными затратами времени на обмены данными.[1]
Рассмотрим каждый из этих этапов более подробно.
Декомпозиция
Иногда декомпозиция исходной задачи естественным образом следует из
природы задачи и оказывается очевидной. Иногда это не так. Чем меньше
размер подзадач, получаемых в результате декомпозиции, чем больше их
количество, тем более гибким оказывается параллельный алгоритм, тем легче
обеспечить равномерную загрузку процессоров вычислительной системы.
Впоследствии, возможно, придется "укрупнить" алгоритм, поскольку следует
принять во внимание интенсивность обмена данными и другие факторы.
Сегментироваться могут как вычислительный алгоритм, так и данные.
Применяют разные варианты декомпозиции. В методе декомпозиции данных
сначала сегментируются данные, а затем алгоритм их обработки. Данные
разбиваются
на
фрагменты
приблизительно
одинакового
размера.
С
фрагментами данных связываются операции их обработки, из которых и
12
формируются подзадачи. Определяются необходимые пересылки данных.
Пересечение частей, на которые разбивается задача, должно быть сведено к
минимуму. Это позволяет избежать дублирования вычислений.
При декомпозиции данных сначала анализируются структуры данных
наибольшего размера, либо те, обращение к которым происходит чаще всего.
На разных стадиях расчета могут использоваться различные структуры данных,
поэтому могут потребоваться и динамические, т. е. изменяющиеся со временем,
схемы декомпозиции этих структур.
В
методе
функциональной
декомпозиции
сначала
сегментируется
вычислительный алгоритм, а затем уже под эту схему подгоняется схема
декомпозиции данных. Успех при этом не всегда гарантирован. Схема может
оказаться такой, что потребуются многочисленные дополнительные пересылки
данных. Метод функциональной декомпозиции может оказаться полезным в
ситуации, где нет структур данных, которые очевидно могли бы быть
распараллелены.
Функциональная декомпозиция играет важную роль и как метод
структурирования программ. Он может оказаться полезным, например, при
моделировании сложных систем, которые состоят из множества простых
подсистем, связанных между собой набором интерфейсов.
На практике чаще используется метод декомпозиции данных. Для того
чтобы декомпозиция была эффективной, следует придерживаться следующих
рекомендаций:
1. Количество подзадач после декомпозиции должно примерно на порядок
превосходить количество процессоров. Это позволяет обеспечить большую
гибкость на последующих этапах разработки программы;
2. Следует избегать лишних вычислений и пересылок данных, в противном
случае программа может оказаться плохо масштабируемой и не позволит
достичь высокой эффективности при решении задач большого объема;
3. Подзадачи должны быть примерно одинакового размера, в этом случае
легче обеспечить сбалансированную загрузку процессоров;
13
4. В идеале сегментация должна быть такой, чтобы с увеличением объема
задачи количество подзадач также возрастало (при сохранении постоянным
размера одной подзадачи). Это обеспечит хорошую масштабируемость. [1]
Проектирование коммуникаций
Подзадачи не могут быть абсолютно независимыми, поэтому следующим
этапом разработки алгоритма является проектирование обменов данными
между ними. Проектирование заключается в определении структуры каналов
связи и сообщений, которыми должны обмениваться подзадачи. Каналы связи
могут создаваться неявно, как это происходит, например, в языках
программирования, поддерживающих модель параллелизма данных, а могут
программироваться явно.
Если на первом этапе применяется декомпозиция данных, проектирование
коммуникаций может оказаться непростым делом. Сегментация данных на
непересекающиеся подмножества и связывание с каждым из них своего
множества операций обработки — достаточно очевидный шаг. Однако остается
необходимость обмена данными, а также управления этим обменом. Структура
коммуникаций может оказаться сложной.
В схеме функциональной декомпозиции организация коммуникаций
обычно проще — они соответствуют потокам данных между задачами.
Коммуникации бывают следующих типов:
1. Локальные — каждая подзадача связана с небольшим набором других
подзадач;
2. Глобальные — каждая подзадача связана с большим числом других
подзадач;
3. Структурированные — каждая подзадача и подзадачи, связанные с ней,
образуют регулярную структуру (например, с топологией решетки);
4. Неструктурированные — подзадачи связаны произвольным графом;
5. Статические — схема коммуникаций не изменяется с течением времени;
6. Динамические — схема коммуникаций изменяется в процессе
выполнения программы;
14
7. Синхронные — отправитель и получатель данных координируют обмен;
8. Асинхронные — обмен данными не координируется.
Вот несколько рекомендаций по проектированию коммуникаций:
1. Количество коммуникаций у подзадач должно быть примерно
одинаковым, иначе приложение становится плохо масштабируемым;
2. Там, где это возможно, следует использовать локальные коммуникации;
3. Коммуникации должны быть, по возможности, параллельными.[1]
Укрупнение
Результатом первых двух этапов разработки параллельного алгоритма
является алгоритм, который не ориентирован на конкретную архитектуру
вычислительной системы, поэтому он может оказаться неэффективным. На
этапе укрупнения учитывается архитектура вычислительной системы, при этом
часто приходится объединять (укрупнять) задачи, полученные на первых двух
этапах, для того чтобы их число соответствовало числу процессоров.
Основные требования:
1. Снижение затрат на коммуникации;
2. Если при укрупнении приходится дублировать вычисления или данные,
это 3. Не должно приводить к потере производительности и масштабируемости
программы;
4.
Результирующие
задачи
должны
иметь
примерно
одинаковую
трудоемкость;
5. Сохранение масштабируемости;
6. Сохранение возможности параллельного выполнения;
7. Снижение стоимости и трудоемкости разработки.[1]
Планирование вычислений
На этапе планирования вычислений, заключительном этапе разработки
параллельного алгоритма, необходимо определить, где, на каких процессорах
будут выполняться подзадачи. Основным критерием эффективности здесь
является минимизация времени выполнения программы.
15
Проблема планирования легко решается при использовании систем с
разделяемой памятью, однако не всегда удается найти эффективный способ
укрупнения
и
эвристические
планирования
алгоритмы
вычислений.
динамически
В
этом случае
применяют
сбалансированной
загрузки
процессоров, когда переопределение стратегии укрупнения и планирования
производится периодически во время выполнения программы и иногда с
достаточно большой частотой.
Планирование выполнения задач заключается в организации их доступа к
ресурсам. Порядок предоставления доступа определяется используемым для
этого алгоритмом.
В простой в реализации (эффективной для небольшого числа процессоров)
главная задача отвечает за размещение подчиненных задач.
Подчиненная
задача получает исходные данные для обработки от главной задачи и
возвращает ей результат работы. Эффективность данной схемы зависит от
числа подчиненных задач и относительных затрат на обмены данными между
подчиненной и главной задачами. При использовании централизованной схемы
сбалансированной загрузки главная задача не должна быть "слабым звеном"
программы, т. е. она не должна тормозить выполнение других задач.[1]
Иерархическая схема Big master/slave(master/demon) показана на рисунке 4.
Big master
slave
slave
slave
Рис 3 схема Big master/slave
16
1.5 Коммуникационные библиотеки
Основными
средствами
вычислительных
программирования
систем являются
стандарты: библиотека
три
для многопроцессорных
библиотеки,
оформленные
OpenMP для систем
с
как
общей
памятью (мультипроцессоров) и библиотека MPI(Message Passing Interface)
для систем
с
распределенной
памятью
(мультикомпьютеров).
Для
программирования гетерогенных вычислительных систем с распределенной
памятью используется библиотека PVM. Все указанные библиотеки написаны
на языках высокого уровня и являются в достаточной степени аппаратнонезависимыми. В то же время наблюдается зависимость этих библиотек от
операционной среды. В некоторых случаях библиотеки строятся не из
процедур, а из классов С++.[4]
1.5.1 Библиотека OpenMP
Стандартом OpenMP занимается организация OpenMP ARB (ARchitecture
Board).
В
1997
года
этой
организацией
был
выпущен
стандарт
для языка OpenMP Fortran – расширения языка Фортран 77. Позже вышли
аналогичные стандарты для языков Си и Фортран 90/95.
OpenMP
расширяет
для мультипроцессорных
последовательный язык программирования
систем набором
директив
компилятора и
библиотечных функций. OpenMP-программа начинает свое выполнение как
один процесс,
называемый
главной нитью.
Главная
нить
выполняется
последовательно, пока не встретится первая параллельная область программы.
OpenMP-программа должна
без
всяких
изменений
работать
на
однопроцессорной платформе в качестве последовательной программы.
Директивы OpenMP в этом случае просто игнорируются компилятором, а
вместо вызовов функций OpenMP вставляются "заглушки".[4]
17
1.5.2 Библиотека MPI
Стандарт механизма передачи сообщений MPI (Message Passing Interface)
был принят в 1994 г. Стандарт готовился с 1992 по 1994 годы. группой Message
Passing Interface Forum. Основная цель, которую ставили перед собой
разработчики MPI – обеспечение полной независимости программ, написанных
с использованием библиотеки MPI, от архитектуры многопроцессорной
системы.
Отметим, что интерфейс громоздок и сложен для прикладного
программиста. Интерфейс также сложен для реализации. Поэтому практически
отсутствуют реализации MPI, в которых в полной мере обеспечивается
совмещение обменов с вычислениями.
В 1997 появился проект стандарта MPI-2, который выглядит еще более
громоздким и трудным для полной реализации. Реализацией стандарта MPI-2
является библиотека MPI-2.
Отметим, прежде всего, что стандарт MPI не стандартизует реализацию.
Поставщики многопроцессорных
вычислительных
систем,
как
правило,
предлагают свои реализации стандарта MPI для своих машин. Однако
правильная MPI-программа (программа, написанная с использованием MPI)
должна одинаково выполняться на всех реализациях.
Существуют стандартные "привязки" MPI к языкам С/С++, Fortran 77/90, а
также бесплатные и коммерческие реализации MPI почти для всех
суперкомпьютерных
платформ,
а
также
для
UNIX
и
Windows
NT вычислительных кластеров. Переносимой версией библиотеки МРI является
библиотека МРIСН.
MPI-программа представляет собой набор независимых процессов, каждый
из которых выполняет свою собственную программу, написанную на какомлибо языке высокого уровня. Процессы MPI-программы взаимодействуют друг
с другом посредством передачи сообщений путем вызова коммуникационных
функций MPI-библиотеки. Как правило, каждый процесс выполняется в своем
собственном адресном пространстве, однако допускается и режим разделения
18
памяти. Стандарт MPI не специфицирует модель выполнения процесса — это
может быть как последовательный процесс, так и многопотоковый.
MPI-библиотека реализована в виде примерно 130 функций, в число
которых входят следующие основные наборы функций:
1. функции для работы с группами процессов и коммуникаторами;
2. функции, реализующие коммуникационные операции типа точка-точка;
3. функции, реализующие коллективные коммуникационные операции.
Набор функций библиотеки MPI далеко выходит за рамки набора
функций, минимально необходимого для поддержки механизма передачи
сообщений.
Почти
любая MPI-программа может
быть
написана
с
использованием всего 6 MPI-функций, а достаточно полную и удобную среду
программирования составляет набор из 24 функций.
MPI не обеспечивает механизмов задания начального размещения
процессов по процессорам. Предполагается, что для этого имеются другие
средства. Эти средства должны позволять задать число процессоров и
процессов, разместить процессы и данные на каждом процессоре.
Стандарт MPI требует, чтобы MPI-программы могли выполняться на
гетерогенных многопроцессорных
системах,
в
которых
различные процессоры имеют различные форматы данных одного и того же
типа.
MPI-программа
должна
работать
также
на мультипроцессорных
вычислительных системах.[4]
1.5.3 Система PVM
Система PVM (Parallel Virtual Machine) была создана для объединения
нескольких
связанных
сетью рабочих
параллельную вычислительную
машину.
станций в
Система
единую
виртуальную
представляет
собой
надстройку над операционной системой UNIX и используется на различных
аппаратных платформах, включая и системы с массовым параллелизмом.
Основные принципы PVM:
19
1. Гетерогенность вычислительной системы. Аппаратная среда может
содержать
как
однопроцессорные
машины,
так
и
многопроцессорные
вычислительные системы (как с общей, так и с распределенной памятью).
2. Конфигурируемый пользователем набор вычислительных машин.
Необходимый для решения задачи пользователя набор машин формируется им
из числа любых машин в используемой системе. Набор машин может
изменяться добавлением и удалением машин в процессе работы программы
пользователя.
3. Прозрачность доступа к вычислительным машинам. Прикладные
программы могут "видеть" аппаратную среду как группу виртуальных
вычислительных элементов без атрибутов.
4. Обмен данными меду процессами в соответствии с моделью обмена
сообщениями.
Допускается
обмен
между
машинами
с
различным
представлением данных
Вычислительная модель PVM предполагает, что приложение состоит из
нескольких задач. Задачи могут выполняться параллельно, синхронизуясь и
обмениваясь данными.
Структура PVM. Система PVM состоит из двух частей. Первая часть –
это программа-демон, которая помещается на все компьютеры, создающие
виртуальную машину. Важно, что пользователи могут конфигурировать
перекрывающиеся виртуальные машины. Вторая часть PVM – это библиотека
PVM подпрограмм. Библиотека PVM содержит вызываемые пользователем
подпрограммы
для
обмена
сообщениями,
порождения процессов,
координирования задач и модификации виртуальной машины.
Поддерживаемые
языки
программирования. PVM
поддерживает языки программирования C, C++ и Фортран 77.
Привязка языков C и
C++ к пользовательскому интерфейсу PVM
реализована в виде C-функций. Прикладные C и C++ программы получают
доступ к функциям библиотеки PVM путем присоединения к ним библиотеки
PVM.
20
1.5.4 Сравнение MPI и PVM
MPI и PVM имеют следующие общие характеристики:
1. и MPI и PVM призваны решать одну и ту же задачу обеспечения
межпроцессорной связи,
2. и MPI и PVM ориентированы на одну и туже MPMD парадигму
программирования;
3. и MPI и PVM представляют собой библиотеку программ;
4. и MPI и PVM обеспечивают мобильность создаваемых программ.
MPI и PVM имеют следующие основные отличия:
1. интерфейс программиста PVM проще, чем такой же интерфейс MPI;
2. PVM имеет средства динамического порождения ветвей (в стандарте
MPI-2 такая возможность также имеется);
3. в PVM возможно взаимодействие приложений, запущенных одним и тем
же пользователем (в стандарте MPI-2 такая возможность также имеется).[4]
21
1.6 Интерфейс передачи сообщений
Наиболее
распространены
сейчас
системы
параллельного
программирования на основе MPI (Message Parsing Interface). Идея MPI
исходно проста и очевидна. Она предполагает представление параллельной
программы в виде множества параллельно исполняющихся процессов,
взаимодействующих друг с другом в ходе исполнения передачи данных с
помощью коммуникационных процедур. Они и составляют библиотеку MPI.
Однако надлежащая реализация MPI для обеспечения межпроцессорных
коммуникаций оказалась довольно сложной. Такая сложность связана с
необходимостью
достижения
высокой
производительности
программ,
необходимостью использовать многочисленные ресурсы мультикомпьютера, и,
как следствие большим разнообразием в реализации коммуникационных
процедур в зависимости от режима обработки данных.[5]
1.6.1 Почему MPI?
MPI является на данный момент самой развитой системой параллельного
программирования
с
передачей
сообщений.
MPI
позволяет
создавать
эффективные, надежные и переносимые параллельные программы высокого
уровня.
Эффективность и надежность обеспечиваются:
1. определением MPI операций не процедурно, а логически, т.е.
внутренние механизмы выполнения операций скрыты от пользователя.
2. использованием непрозрачных объектов в MPI (группы, коммутаторы,
типы и т.д.)
3. хорошей реализацией функций передачи данных, адаптирующихся к
структуре физической системы.
Переносимость обеспечивается:
1. тем что тот же самый исходный текст параллельной программы на MPI
может быть выполнен на ряде машин (некоторая настройка необходима, чтобы
использовать преимущества элементов каждой системы). Программный код
может одинаково эффективно выполняться, как на параллельных компьютерах
22
с распределенной памятью, так и на параллельных компьютерах с общей
памятью. Он может выполняться на сети рабочих станций, или на наборе
процессов на отдельной рабочей станции.
2. способностью параллельных программ выполняться на гетерогенных
системах, т.е. на системах, состоящих
из процессоров с различной
архитектурой. MPI обеспечивает вычислительную модель, которая скрывает
много архитектурных различий в работе процессоров. MPI автоматически
делает любое необходимое преобразование данных и использует правильный
протокол
связи,
посылается
ли
код
сообщения
между
одинаковыми
процессорами или между процессорами с разной архитектурой. MPI может
настраиваться как на работу на однородной, так и на работу на гетерогенной
системах.[5]
1.6.2 Основные функции MPI.
Начало работы программы.
Любая прикладная MPI- программа (приложение) должна начинаться с
вызова функции инициализации MPI_Init. В результате выполнения этой
функции создается группа процессов, в которую помещаются все процессы
приложения, и создается область связи, описываемая предопределенным
коммуникатором MPI_COMM_WORLD. Эта область связи объединяет все
процессы-приложения. Процессы в группе упорядочены и пронумерованы от 0
до groupsize-1.
Синтаксис функции инициализации MPI_Init:
Int MPI_Init(int *argc, vhar *argv)
Каждому процессу при инициализации передаются аргументы функции
main, полученные из командной строки.[6]
Завершение работы.
Функция завершения MPI-программ:
Int MPI_Finalaze();
23
Функция закрывает все MPI-процессы и ликвидирует все области связи.
Функция определения числа процессов в области связи.
Int MPI_Comm_size(MPI_Comm MPI_COMM_WORLD, int *size)
Функция
возвращает
количество
процессов
в
области
связи
коммуникатора MPI_COMM_WORLD.
Функция определения номера процесса.
int MPI_Comm_rank(MPI_Comm MPI_COMM_WORLD, int *rank)
Функция возвращает номер процесса, вызвавшего эту функцию.
Функция передачи сообщений.
Int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int tag,
MPI_Comm MPI_COMM_WORLD)
buf – адрес начала расположения пересылаемых данных
count – Число пересылаемых элементов
datatype – тип посылаемых элементов.
Dest – номер процесса-получателя в группе, связанной коммуникатором
MPI_COMM_WORLD
tag – идентификатор сообщения
Функция приема сообщения
Int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int tag,
MPI_Comm MPI_COMM_WORLD, MPI_Status *status)
buf – адрес начала расположения принимаемого сообщения.
count – максимальное число принимаемых элементов.
datatype – тип элементов принимаемого сообщения.
source – номер процесса-отправителя.
tag – идентификатор сообщения.
status – атрибуты принятого сообщения.
24
Функция отсчета времени.
MPI_Wtime
double MPI_Wtime()
Функция возвращает астрономическое время в сеундах, прошедшее с
некоторого момента в прошлом(точки отсчета). Гарантируется, что эта точка
отсчета не будет изменена в течение жизни процесса. Для хронометража
участка программы вызов функции делается в начале и конце участвка и
определяется разница между показаниями таймера.
double starttime, endtime;
starttime = MPI_Wtime();
… хронометрируемый участок …
endtime = MPI_Wtime();
printf(“Выполнение заняло %f секунд”, endtime-starttime);[6]
1.7 Расчет ускорения и эффективности алгоритма.
Ускорение (speedup), получаемое при использовании параллельного
алгоритма для p процессоров, по сравнению с последовательным вариантом
выполнения вычислений определяется величиной
Sp(n)=T1(n)/Tp(n),
т.е. как отношение времени решения задач на скалярной ЭВМ к времени
выполнения
параллельного
алгоритма
(величина
n
применяется
для
параметризации вычислительной сложности решаемой задачи и может
пониматься, например, как количество входных данных задачи).
Эффективность (efficiency) использования параллельным алгоритмом
процессоров при решении задачи определяется соотношением
Ep(n)=T1(n)/(pTp(n))=Sp(n)/p
(величина эффективности определяет среднюю долю времени выполнения
алгоритма, в течение которой процессоры реально задействованы для решения
задачи).
25
При
практическом
применении
данных
показателей
для
оценки
эффективности параллельных вычислений следует учитывать два важных
момента:
При определенных обстоятельствах ускорение может оказаться больше
числа используемых процессоров Sp(n)>p - в этом случае говорят о
существовании
сверхлинейного
(superlinear)
ускорения.
Несмотря
на
парадоксальность таких ситуаций (ускорение превышает число процессоров),
на практике сверхлинейное ускорение может иметь место. Одной из причин
такого
явления
может
быть
неодинаковость
условий
выполнения
последовательной и параллельной программ. Например, при решении задачи на
одном процессоре оказывается недостаточно оперативной памяти для хранения
всех обрабатываемых данных и тогда становится необходимым использование
более медленной внешней памяти (в случае же использования нескольких
процессоров оперативной памяти может оказаться достаточно за счет
разделения данных между процессорами).
При внимательном рассмотрении можно обратить внимание, что попытки
повышения качества параллельных вычислений по одному из показателей
(ускорению или эффективности) могут привести к ухудшению ситуации по
другому показателю, ибо показатели качества параллельных вычислений
являются часто противоречивыми. Так, например, повышение ускорения
обычно может быть обеспечено за счет увеличения числа процессоров, что
приводит, как правило, к падению эффективности. И наоборот, повышение
эффективности достигается во многих случаях при уменьшении числа
процессоров.
26
Глава 2 Реализация программы умножения матриц
2.1 Математическая постановка задачи
Пусть даны две прямоугольные матрицы А с размерностью m x n и В с
размерностью n x q.
[1][1] ⋯ [1][]
⋮
⋱
⋮
A= [
]
[][1] ⋯ [][]
[1][1] ⋯ [1][]
⋱
⋮ ]
B=[ ⋮
[][1] ⋯ [][]
Тогда матрица их произведением будет матрица С с размерностью m x q
С[1][1] ⋯ [1][]
⋮
⋱
⋮
С=[
]
[][1] ⋯ [][]
где C[i][j] = ∑=1 [][] ∗ [][] (i=1,2,…,n; j=1,2,…,q).
При этом необходимо помнить, что Операция умножения двух матриц
выполнима только в том случае, если число столбцов в первом сомножителе
равно числу строк во втором.
[1][1]
⋮
[][]
⋮
[[][1]
⋯ [1][]
⋯
⋯
⋯ [][]
⋯
⋯
⋯ [][]
⋯ [1][]
[1][1]
⋯
⋮
⋮
⋯ [][] X [][1]
⋯
⋮
⋮
⋯ [][]]
[[][1]
[1][1]
⋮
[][1]
⋮
[[][1]
⋯ [1][]
⋯
⋯
⋯ [][]
⋯
⋯
⋯ [][]
⋯ [][] ⋯ [1][]
⋯
⋯
⋯
⋮
⋯ [][] ⋯ [][]
⋯
⋯
⋯
⋮
⋯ [][] ⋯ [][]]
⋯ [1][]
⋯
⋮
⋯ [][]
⋯
⋮
⋯ [][]]
27
Для
получения
элемента
C[i][j]
нужно
сложить
произведения
соответствующих элементов i-ой строки матрицы А и j-го столбца матрицы В.
Следовательно для получения i-ой строки матрицы С, нам понадобятся
следующие исходные данные: i-ая строка матрицы А и вся матрица B.
[1][1]
⋮
[][]
⋮
[[][1]
⋯ [1][]
⋯
⋯
⋯ [][]
⋯
⋯
⋯ [][]
⋯ [1][]
[][]
⋯
⋮
⋮
⋯ [][] X [][]
⋯
⋮
⋮
⋯ [][]] [[][]
[1][1]
⋮
[][]
⋮
[[][1]
В
дальнейшем
этот
⋯ [1][]
⋯
⋯
⋯ [][]
⋯
⋯
⋯ [][]
принцип
⋯ [][] ⋯ [][]
⋯
⋯
⋯
⋮
⋯ [][] ⋯ [][]
⋯
⋯
⋯
⋮
⋯ [][] ⋯ [][]]
⋯ [1][]
⋯
⋮
⋯ [][]
⋯
⋮
⋯ [][]]
будет
являться основой
в нашем
параллельном алгоритме.
28
2.2 Разработка алгоритма
Рассмотрим нашу задачу, опираясь на сведения, описанные ранее.
Нам необходимо произвести умножение двух матриц. Исходные матрицы
записаны в файлах. Результат необходимо будет сохранить в файл.
Алгоритм работы программы:
BM(Big Master)
считывание
исходных данных
из файлов
декомпозиция
данных, планирование распределения
по процессорам
Daemon_1
Daemon_2
Daemon_3
передача данных
процессорам
ожидание
завершения
вычисления
получение
данных
получение
данных
получение
данных
вычисление
вычисление
вычисление
передача
данных Big
Master’у
передача
данных Big
Master’у
передача
данных Big
Master’у
получение данных
от процессоров
сохранение
полученных данных
в файл
Рис 4 алгоритм параллельного умножения матриц
29
1. Исходные матрицы А и В хранятся в файлах 1 и 2 соответственно. На
первом этапе Big Master считывает данные матрицы из файлов в оперативную
память.
2.
После завершения считывания инициализируем MPI с помощью функции
MPI_Init(), и получаем информацию о количестве используемых процессоров и
о номере текущего процессора (функции MPI_Comm_size и MPI_Comm_rank
соответственно).
Далее реализуем декомпозицию в соответствии с выбранным алгоритмом
(Глава математическая постановка задачи)
Big Master отправляет матрицу B всем процессорам, а также каждому
процессору отправляет по s-строк матрицы A. Число s рассчитывается как
s=
_
_
где rows_A - количество строк матрицы А, process_count - количество
процессов. Таким образом, отправляем каждому процессу одинаковое число
строк. Если же после деления получился остаток n, то первым n-процессам
передаем s+1 строк матрицы А, а оставшимся процессам передаем s строк.
3.
После отправки последнего сообщения Big Master переходит в режим
получения сообщений.
Каждый daemon после инициализации ожидает получения исходных
данных, затем производит вычисления и отправляет результат обратно Big
Master’у.
4. Big Master, получив все сообщения, сохраняет результаты в файл в виде
матрицы.
30
2.3 Решение для кластера
2.3.1 Настройка кластера.
Скачиваем и устанавливаем WMPI на каждый компьютер в сети. После
выполнения программы SETUP.EXE на каждом компьютере кластера в
корневом каталоге (по умолчанию) создается папка wmpi1.3.
Устанавливаем и запускаем мастера (Big Master). Для этого на главном
компьютере запускаем файл
install_service.bat. Затем запускаем файл
start_service.bat. На остальных компьютерах кластера нужно запустить
wmpi_daemon.exe.
Для
выполнения
прикладной
параллельной
программы
создается
групповой файл, где все процессы, которые принадлежат приложению,
статически определены. Первый процесс, так называемый большой мастер
(bm), затем стартуют другие процессы (рабы) и конфигурируют виртуальную
параллельную машину. [7]
2.3.2 Настройка Visual Studio
Заходим в Visual Studio Tools -> Options, выбираем вкладку "Projects and
Solutions" внутри нее выбираем пункт "VC++ Directories". В выпадающем меню
Show directories for выбираем пункт "Library files". Нажимаем на иконку с
изображением папки (New Line). В появившейся строчке прописываем путь до
необходимых библиотек C:\WMPI1.3\lib (рис 5).
31
Рис 5
Нужно прописать в настройках путь до файла "mpi.h". Заходим в Visual
Studio Tools -> Options, выбираем вкладку "Projects and Solutions" внутри нее
выбираем пункт "VC++ Directories". В выпадающем меню Show directories for
выбираем пункт "Include files"(рис 6).
Рис 6
32
Затем нужно подключить указать каталог с библиотечными файлами.
Заходим Project -> Properties выбираем вкладку "Configuration Properties ->
General".
Добавляем
в
Additional
Library
Directories
путь
к
файлам
"С:\WMPI1.3\lib\Console"(рис 7).
Рис 7
2.3.3 Создание группового файла
В групповом файле статически описываются
все процессы, которые
принадлежат приложению. Первый процесс, так называемый большой мастер
(bm), затем стартуют другие процессы (рабы) и конфигурируют виртуальную
параллельную машину.
Групповой файл имеет расширение .pg и должен иметь имя, совпадающее
с именем исполняемого файла нашей программы. Также он должен находиться
в одном каталоге с программой. Этот файл должен быть создан только на
главном компьютере, который будет управлять остальными.
В групповой файле прописываются ip адреса рабов, кол-во процессов на
каждом и путь до исполняемого файла.
33
Пример содержания группового файла(рис 8)
local 4
192.168.86.162 4 C:\WMPI\Ref\test.exe
192.168.86.163 4 C:\WMPI\Ref\test.exe
Рис 8
Таким образом мы запускаем нашу программу(test.exe), находящуюся в
каталоге С:\WMPI\Ref\. На трех компьютерах, по 4 процесса на каждом.
2.3.4 Запуск программы
Запуск программы осуществляется через консоль (cmd). Пусть файл нашей
программы имеет имя test.exe. Для запуска достаточно в консоли написать
"test.exe" и нажать Enter.
Если наш .pg файл и исполняемый файл программы имеют разные имена,
то запуск будет выглядеть так "test.exe –p4pg <имя pg файла>".
34
2.4 Решение для суперкомпьютера
2.4.1 Подключение к суперкомпьютеру.
Для подключения к суперкомпьютеру нам необходима программа PuTTY
Скачиваем программу, устанавливаем, запускаем.
Так выглядит главное меню программы (рис 9)
Рис 9
В
поле
"Имя
хоста"
прописываем
IP
адрес
суперкомпьютера:
195.54.14.162(рис 10)
Для подключения к нашему суперкомпьютеру необходимо установить тип
соединения SSH. (рис 10)
SSH (англ. Secure Shell — «безопасная оболочка») — сетевой протокол
прикладного
уровня,
позволяющий
производить
удалённое
управление
операционной системой и передачу файлов. Сходен по функциональности с
протоколами Telnet и rlogin, но, в отличие от них, шифрует весь трафик,
включая и передаваемые пароли.
35
Можно прописать название сеанса в поле "Сохраненные сеансы" и нажать
кнопку "Сохранить". Тогда при следующем запуске программы не придется
снова прописывать IP адрес суперкомпьютера, а достаточно будет просто
выбрать сеанс и нажать кнопку "Загрузить".(рис 10)
Рис 10
Нажимаем кнопку "Соединение".
На экране появится консоль, запрашивающая логин и пароль.(рис 11)
36
Рис 11
Вводим логин и пароль, проходим авторизацию. Теперь мы получили
доступ к суперкомпьютеру. Он управляется операционной системой Linux. Для
удобства навигации и работы с файловой системой рекомендуется использовать
файловый менеджер Midnight Commander. Для его запуска в командной строке
вводим команду "mc" и нажимаем Enter.
Примерно так выглядит интерфейс Midnight Commander(рис 12)
Рис 12
37
Возможно, в различных ОС Windows бывают проблемы с правильным
отображением символов, например, так (рис 13)
Рис 13
Чтобы это исправить, необходимо в настройках PuTTY установить
кодировку UTF-8(рис 14 и 15)
Рис 14
38
Рис 15
Для выхода из Midnight Commander нужно нажать комбинацию клавиш
CTRL+F10.
Все, мы подключились к суперкомпьютеру. Для отключения достаточно в
командной строке ввести команду exit.
2.4.2 Обмен файлами с суперкомпьютером.
Если у нас появляется необходимость скопировать файлы с Windows
машины на суперкомпьютер, или наоборот, скачать результат выполнения
программы с суперкомпьютера, то нам необходима еще одна программа,
которая позволяет осуществлять обмен файлами.
Скачиваем программу WinSCP, устанавливаем и запускаем.
Появляется главное окно программы, вводим логин, пароль и IP адрес
суперкомпьютера(рис 16)
39
Рис 16
Появляется окно файлового менеджера (рис 17)
Рис 17
Слева мы видим содержимое жесткого диска нашего компьютера, а справа
содержимое нашей директории на суперкомпьютере. Теперь можно свободно
обмениваться
файлами
и
папками
между
Windows
машиной
и
суперкомпьютером.
40
2.4.3 Компиляция и запуск программы.
Чтобы откомпилировать файл на нашем суперкомпьютере, нужно
воспользоваться командой, которая имеет следующий синтаксис:
mpiCC [имя файла] –o [имя выходного файла]
Команда компиляции для нашей тестовой программы (Console_pi.c)
получилась такая:
mpiCC Console_pi.c –o cons
Рис 18
После выполнения этой команды у нас появился файл *cons
Теперь можно поставить нашу программу в очередь на выполнение. Как
только освободится, необходимое нам количество ядер, программа запустится.
Синтаксис постановки в очередь такой:
runjob -pr <Профиль> -np <Число процессов> <Описание> <Путь к
программе> [Аргументы]
41
Доступные профили: openmpi, openfoam171, openfoam16ext, single
Описание задачи - произвольное наименование задачи, которое будет
отображаться в очереди задач.
Для нашей программы команда постановки в очередь выглядит так:
runjob –pr openmpi –np 5 test_pi ./cons
Рис 19
Теперь программа поставлена в очередь.
42
Рис 20
На рисунке 20 видно, что программа запущена на 1 узле с 5 процессорами.
Также нашей программе присвоен номер запущенного процесса – 1380.
По этому номеру мы можем следить за ходом выполнения программы с
помощью команды qstat.
Рис 21
В нашей директории появился файл log.test_pi.txt. В нем записываются
результаты выполнения программы, а также ошибки, возникшие в процессе
работы программы.
43
2.4.4 Отладка программы
Для
отладки
OpenMPI
программы
можно
использовать
Windows
компьютер. Но предварительно необходимо его настроить.
1) Для установки и настройки OpenMPI нам необходимо скачать программу
CMake (cmake.org), архив с библиотекой OpenMPI.
2) Устанавливаем CMake.
3) Распаковываем архив с библиотекой OpenMPI.
4) Запускаем CMake.
Нам необходимо заполнить следующие поля(рис 22)
"Where is the source code" – Сюда прописываем путь до папки, в которую
распаковали архив OpenMPI.
"Where to build the binaries" – Указываем путь до папки, в которую будет
сохранен результат работы обработки программой CMake(по умолчанию лучше
указать
C:\ResCMake)
Рис 22
44
Затем наживаем кнопку "Configure". В выпадающем меню выбираем версию
Visual Studio, которую собираемся использовать(рис 23). Нажимаем кнопку
"Finish"
Рис 23
Нажимаем "Generate" и ждем пока программа выполнит свою работу.
Закрываем CMake.
5) С помощью Visual Studio открываем OpenMPI.sln, который находится в
папке C:\ResCMake\ .
Теперь нужно собрать проект, для этого в Visual Studio нажимаем Build -> Build
Solution.
Закрываем Visual Studio.Теперь OpenMPI готов к работе.
Запуск параллельной программы в ОС Windows используя библиотеку
OpenMPI
Для тестирования будем использовать простую программу Console_pi.
45
В код программы нужно добавить #include "mpi.h". А также нужно
прописать в настройках путь до него. Заходим в Visual Studio Tools -> Options,
выбираем вкладку "Projects and Solutions" внутри нее выбираем пункт "VC++
Directories". В выпадающем меню Show directories for выбираем пункт "Include
files"(рис 24)
Рис 24
Если сейчас попробовать откомпилировать программу, то мы получим
ошибки линкования. Чтобы их исправить нужно подключить файлы
библиотеки OpenMPI.
Заходим в Visual Studio Tools -> Options, выбираем вкладку "Projects and
Solutions" внутри нее выбираем пункт "VC++ Directories". В выпадающем меню
Show directories for выбираем пункт "Library files". Нажимаем на иконку с
изображением папки (New Line). В появившейся строчке прописываем путь до
необходимых библиотек C:\ResCMake\Debug.(рис 25)
46
Рис 25
Затем нужно подключить библиотеку libmpid.lib. Заходим Project ->
Properties выбираем вкладку "Configuration Properties -> Linker -> Input".
Добавляем
в
Additional
Dependencies
название
файла
библиотеки
libmpid.lib.(рис 26)
Рис 26
47
Теперь можно откомпилировать наш проект. Нажимаем Build -> Build
Solution.
Если все успешно, то прежде чем запустить программу, нужно создать
отдельную папку (назовем её C:\test) и скопируем в нее следующие файлы:
mpirun.exe (C:\ResCMake\orte\)
libmpid.dll (C:\ResCMake\Debug\)
libopen_pald.dll (C:\ResCMake\Debug\)
libopen_rted.dll (C:\ResCMake\Debug\)
Console_pi.exe (находится в папке Debug с нашего проекта)
Теперь открываем консоль Пуск -> Все программы -> Стандартные ->
Командная строка
В командной строке нужно зайти в директорию test, выполняем команду
cd C:\test.
Запускаем нашу программу (на пяти процессах) с помощью команды mpirun –n
5 Console_pi.exe
Рис 27
48
Глава 3 Анализ результатов.
В этой главе мы будем опираться на книгу В.П.Гергеля [7] и результаты
собственных экспериментов.
Для тестирования будем использовать кластер и суперкомпьютер. Кластер
состоит из компьютеров под управлением OC Windows, соединенных в сеть. На
каждом из компьютеров установлен 4х ядерный процессор. Таким образом для
максимальной производительности будем запускать по 4 процесса на каждом
компьютере. Суперкомпьютер состоит из 12 вычислительных узлов и хостмашины. Во все (включая хост-машину) установлено по 2 процессора, с 6
ядрами каждый. Итого мы имеем 156 ядер. Таким образом для наилучшей
производительности запускаем по 6 или 12 процессов на каждом узле.
3.1 Матрицы 500х500
Для первого тестирования возьмем две матрицы размерами 500x500,
заполненные случайными числами типа double. Нужно получить время
выполнения последовательного алгоритма и параллельного алгоритма, с
различными конфигурациями кластера. Результаты можно увидеть в таблице 1.
время
выполнения
программы
среднее время
расчета
демоном
среднее время
передачи
между
процессами
ускорение
эффективность
последовательный
алгоритм
1 процессор
(4 ядра)
4 процесса
WMPI
3
процессора
(по 4 ядра)
12
процессов
WMPI
5 процессоров
(по 4 ядра)
20 процессов
WMPI
7 процессоров
(по 4 ядра)
28 процессов
WMPI
2,160177
2,074677
3,209718
3,322700
3,645200
0,236468
0,090492
0,053524
0,033722
0,016970
0,320667
0,388901
0,606623
1,04
0,26
0,67
0,056
0,65
0,0325
0,59
0,021
Таблица 1 Кластер: матрицы 500х500
Из результатов можно видеть, что большая часть времени уходит на
коммуникации. По эффективности выигрывает только параллельное решение
на одном процессоре с 4мя ядрами. Все коммуникации "внутренние", поэтому
49
нет больших затрат на межсетевое взаимодействие. Таким образом можно
сделать вывод, что для матриц размерности 500x500 эффективным будет
распараллеливание только на одном многоядерном процессоре.
t секунд
время выполнения на кластере
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
время выполнения
Рис 28 Время выполнения на кластере(матрицы 500х500)
Теперь проведем тесты тех же матриц, на супер компьютере. В результате
получаем следующую таблицу 2.
последовательный
алгоритм
суперкомпьютер
6 процессов
OpenMPI
суперкомпьютер
12
процессов
OpenMPI
суперкомпьютер
18
процессов
OpenMPI
суперкомпьютер
24 процесса
OpenMPI
суперкомпьютер
32 процесса
OpenMPI
1,110083
0,349008
0,307470
0,385201
0,424037
0,495098
0,152894
0,105005
0,121365
0,039210
0,028578
среднее
время
передачи между
процессами
0,004376
0,018847
0,062169
0,108247
0,127455
ускорение
3,18
3,61
2,88
2,62
2,24
эффективность
0,53
0,3
0,16
0,11
0,07
время выполнения
программы
среднее
время
расчета демоном
Таблица 2 Суперкомпьютер: матрицы 500х500
На суперкомпьютере время коммуникаций намного меньше, чем на
кластере, в результате чего заметно уменьшение времени вычислений.
Наилучший результат получился при вычислении на 2х процессорах (12
процессов), однако показатель эффективности уступает , по сравнению с 6
50
процессами (1 процессором). Это закономерно, т.к. зачастую, показатели
эффективности и ускорения противоречивы.
время выполнения на
суперкомпьютере
Основной
t секунд
Основной
Основной
Основной
время выполнения
Основной
Основной
Основной
6 process
12
18
24
32
(1 node) processes processes processes processes
(1 nodes) (2 nodes) (2 nodes) (3 nodes)
Рис 29 Время выполнения на суперкомпьютере (матрицы 500х500)
сравнение времени выполнения
Основной
Основной
t секунд
Основной
Основной
Основной
на кластере
Основной
на суперкомпьютере
Основной
Основной
Основной
6 process
12
18
24
32
(1 node) processes processes processes processes
(1 nodes) (2 nodes) (2 nodes) (3 nodes)
Рис 30 Сравнение времени выполнения на кластере и суперкомпьютере
(матрицы 500х500)
51
Сравнение ускорения и эффективности.
Основной
Основной
Основной
Основной
ускорение
эффективность
Основной
Основной
Основной
4 process
12
20
28
(1 com) processes processes processes
(3 com)
(5 com)
(7 com)
Рис 31 Ускорение и эффективность на кластере (матрицы 500х500)
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
ускорение
эффективность
Основной
Рис 32 Ускорение и эффективность на суперкомпьютере (матрицы 500х500)
52
3.2 Матрицы 1500х1500
Теперь проведем те же самые тесты для матриц размерности 1500x1500.
время
выполнения
программы
среднее время
расчета
демоном
среднее время
передачи
между
процессами
ускорение
последователь
ный алгоритм
1 процессор
(4 ядра)
4 процесса
WMPI
3 процессора
(по 4 ядра)
12 процессов
WMPI
5 процессоров
(по 4 ядра)
20 процессов
WMPI
7 процессоров
(по 4 ядра)
28 процессов
WMPI
48,593148
35,651193
33,675174
33,756784
36,467611
15,423669
5,683095
3,381528
2,217660
3,994406
3,596013
4,089683
4,398110
1,36
1,44
1,44
1,33
0,34
0,12
0,072
0,048
эффективность
Таблица 3 Кластер: матрицы 1500х1500
t секунд
время выполнения на кластере
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
время выполнения
4 process
12
20
28
(1 com) processes processes processes
(3 com) (5 com) (7 com)
Рис 33 Время выполнения на кластере (матрицы 1500х1500)
По результатам тестирования на кластере с матрицами размерностью
1500x1500 можно увидеть, что наилучшие результаты получаются при
вычислениях на 3 и 5 процессорах, но на 3 процессорах коэффициенты
ускорения и эффективности превышают соответствующие коэффициенты при
выполнении на 5 компьютерах.
Выполним тот же тест на суперкомпьютере.
53
время
выполнения
программы
последовательный
алгоритм
суперкомпьютер
6 процессов
OpenMPI
суперкомпьютер
12 процессов
OpenMPI
суперкомпьютер
18 процессов
OpenMPI
суперкомпьютер
24 процесса
OpenMPI
суперкомпьютер
32 процесса
OpenMPI
44,564870
9,047838
5,562706
4,926660
4,127737
4,084823
7,185554
3,685521
2,440488
1,821858
1,359205
0,058115
0,011391
0,653908
0,711749
0,884602
4,93
8,01
9,05
10,8
10,91
0,82
0,67
0,5
0,45
0,34
среднее время
расчета
демоном
среднее время
передачи
между
процессами
ускорение
эффективность
Таблица 4 Суперкомпьютер: матрицы 1500х1500
Ускорение на суперкомпьютере заметно выше, однако с ростом ускорения
падает эффективность. Больше времени затрачивается на коммуникации, а
время использования процессоров уменьшается.
t секунд
время выполнения на
суперкомпьютере
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
время выполнения
6 process
12
18
24
32
(1 node) processes processes processes processes
(1 nodes) (2 nodes) (2 nodes) (3 nodes)
Рис 34 Время выполнения на суперкомпьютере (матрицы 1500х1500)
54
сравнение времени выполнения
Основной
Основной
t секунд
Основной
Основной
Основной
на кластере
Основной
на суперкомпьютере
Основной
Основной
Основной
6 process (1 12 processes 18 processes 24 processes 32 processes
node)
(1 nodes)
(2 nodes)
(2 nodes)
(3 nodes)
Рис 35 36 Сравнение времени выполнения на кластере и суперкомпьютере
(матрицы 1500х1500)
Сравнение ускорения и эффективности.
Основной
Основной
Основной
Основной
Основной
ускорение
Основной
эффективность
Основной
Основной
Основной
4 process
12
20
28
(1 com) processes processes processes
(3 com)
(5 com)
(7 com)
Рис 37 Ускорение и эффективность на кластере (матрицы 1500х1500)
55
Основной
Основной
Основной
Основной
Основной
ускорение
эффективность
Основной
Основной
Рис 38 Ускорение и эффективность на суперкомпьютере (матрицы
1500х1500)
3.3 Матрицы 2500х2500
Теперь выполним тестирование на матрицах размерностью 2500x2500.
время
выполнения
программы
среднее время
расчета
демоном
среднее время
передачи
между
процессами
ускорение
эффективность
последовательный
алгоритм
1 процессор
(4 ядра)
4 процесса
WMPI
3 процессора (по
4 ядра)
12
процессов
WMPI
5
процессоров
(по 4 ядра)
20 процессов
WMPI
7
процессоров (по
4 ядра)
28 процессов
WMPI
204,051787
138,282129
104,256304
100,398433
105,684734
74,227252
28,492439
15,608230
10,739235
20,540173
10,656562
7,813668
11,819882
1,46
1,96
2,03
1,93
0,37
0,16
0,1
0,07
Таблица 5 Кластер: матрицы 2500х2500
56
время выполнения на кластере
Основной
Основной
t секунд
Основной
Основной
Основной
Основной
время выполнения
Основной
Основной
Основной
4 process
12
20
28
(1 com) processes processes processes
(3 com) (5 com) (7 com)
Рис 39 Время выполнения на кластере (матрицы 2500х2500)
последовательный
алгоритм
суперкомпьютер
6 процессов
OpenMPI
суперкомпьютер
12 процессов
OpenMPI
суперкомпьютер
18 процессов
OpenMPI
суперкомпьютер
24 процесса
OpenMPI
суперкомпьютер
32 процесса
OpenMPI
228,731690
43,687715
24,435294
18,285426
16,278644
14,024881
среднее время
расчета
демоном
37,901145
19,295975
12,821543
9,900662
7,203445
среднее время
передачи
между
процессами
ускорение
эффективность
0,979718
0,225219
0,845334
2,010950
1,950573
5,24
0,87
9,36
0,78
12,51
0.7
14,05
0,59
16,31
0,51
время
выполнения
программы
Таблица 6 Суперкомпьютер: матрицы 2500х2500
57
t секунд
время выполнения на
суперкомпьютере
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
Основной
время выполнения
6 process
12
18
24
32
(1 node) processes processes processes processes
(1 nodes) (2 nodes) (2 nodes) (3 nodes)
Рис 40 Время выполнения на суперкомпьютере (матрицы 2500х2500)
сравнение времени выполнения
Основной
Основной
t секунд
Основной
Основной
Основной
на кластере
Основной
на суперкомпьютере
Основной
Основной
Основной
6 process
12
18
24
32
(1 node) processes processes processes processes
(1 nodes) (2 nodes) (2 nodes) (3 nodes)
Рис 41 Сравнение времени выполнения на кластере и суперкомпьютере
(матрицы 2500х2500)
58
Сравнение ускорения и эффективности.
Основной
Основной
Основной
ускорение
Основной
эффективность
Основной
Основной
4 process
12
20
28
(1 com) processes processes processes
(3 com)
(5 com)
(7 com)
Рис 42 Ускорение и эффективность на кластере (матрицы 1500х1500)
Основной
Основной
Основной
Основной
Основной
Основной
Основной
ускорение
Основной
эффективность
Основной
Основной
Рис 43 Ускорение и эффективность на суперкомпьютере (матрицы
2500х2500)
59
Заключение.
В ходе выполнения квалификационной работы были получены следующие
результаты:
1) Разработана параллельная программа умножения матриц.
2) Полученная программа адаптирована для использования на кластерах с
разделяемой памятью и на суперкомпьютере с общей памятью, под
управлением OC Linux или OC Windows.
3) Проведен
сравнительный
анализ
результатов
быстродействия
программы на разных архитектурах, составлены сравнительные
таблицы и графики.
60
Список литературы.
1.
С.Немнюгин,
О.Стесик.
Параллельное
программирование
для
многопроцессорных вычислительных систем – СПб 2002
2. [Электронный ресурс] http://parallel.ru/computers/taxonomy/flynn.html
3. С.Немнюгин Технологии параллельного программирования: MPI –
СпбГУ 2009
4. [Электронный ресурс] http://bigor.bmstu.ru/?cnt/?doc=Parallel/base.cou
5. В.Д.Кореев Параллельное программирование в MPI. 2-е издание. –
Новосибирск 2002
6.
А.А.Букатов,
В.Н.Дацюк,
А.И.Жегуло
Программирование
многопроцессорных вычислительных систем Ростов-на-Дону 2003
7. Рудаков С.А., Руководство по запуску параллельной программы на
кластере WMPI 1.3, http://csu.ac.ru/~rusear/
8. В.П.Гергель, Теория и практика параллельных вычислений.
61
Приложение 1. Последовательное умножение матриц
62
Приложение 2. Параллельное умножение матриц
В разработке…(дорабатывается)
63
1/--страниц
Пожаловаться на содержимое документа