Программирование для многопроцессорных систем в стандарте MPI - Шпаковский Г.И., Серикова Н.В.. Программирование для многопроцессорных систем в стандарте MPI -. Организация вычислений в многопроцессорных системах
 Скачать 1.61 Mb.
|
|
МИНСК БГУ 2002 2 Настоящее пособие предназначено для практического обучения параллельному программированию в стандарте MPI (The Message Passing Interface). В пособии содержатся: общие сведения по парал- лельным системам и их программированию; полные справочные дан- ные по библиотеке функций MPI; примеры программирования при- ложений (матричные задачи, решение ДУЧП, СЛАУ, криптоанализ); сведения по организации вычислений в различных исполнительных средах. Имеется большой объем приложений, включающий справоч- ные материалы и примеры MPI программ. Издание предназначено студентам естественнонаучных направле- ний, специалистам и научным работникам, заинтересованным в реше- нии прикладных задач с большим объемом вычислений. 3 ОГЛАВЛЕНИЕ ПРЕДИСЛОВИЕ ................................................................................................. 7 Р а з д е л 1. ВВЕДЕНИЕ..................................................................................... 9 Глава 1. Организация вычислений в многопроцессорных системах .... 9 1.1. Классификация многопроцессорных систем ................................. 9 1.2. Сетевой закон Амдала ...................................................................... 12 1.3. Техническая реализация многопроцессорных систем .................. 14 1.4. Программирование для систем с разделяемой памятью .............. 15 1.5. Программирование для систем спередачей сообщений ............. 21 Контрольные вопросы и задания к главе 1 .................................... 27 Глава 2. Реализации интерфейса программирования MPI .................... 28 2.1. MPICH – основная реализация MPI ............................................... 28 2.2. Способы запуска приложений в MPICH ........................................ 33 2.2.1. Запуск с помощью MPIRun.exe ................................................. 33 2.2.2. Процедура MPIConfig.exe ......................................................... 34 2.2.3. Процедура MPIRegister.exe ....................................................... 35 2.3. Библиотека MPE и логфайлы .......................................................... 36 2.4. Средства просмотра логфайлов ....................................................... 42 Контрольные вопросы и задания к главе 2 .................................... 43 Р а з д е л 2. БИБЛИОТЕКА ФУНКЦИЙ MPI .............................................. 45 Глава 3. Парные межпроцессные обмены .................................................. 45 3.1. Введение ............................................................................................ 45 3.2. Операции блокирующей передачи и блокирующего приема ...... 46 3.2.1. Блокирующая передача ............................................................. 46 3.2.2. Данные в сообщении .................................................................. 47 3.2.3. Атрибуты сообщения ............................................................... 48 3.2.4. Блокирующий прием .................................................................. 48 3.2.5. Возвращаемая статусная информация .................................. 50 3.3. Соответствие типов данных и преобразование данных ............... 51 3.3.1. Правила соответствия типов данных .................................. 51 3.3.2. Преобразование данных ............................................................ 53 3.4. Коммуникационные режимы ........................................................... 54 3.5. Семантика парного обмена между процессами ............................. 58 3.6. Распределение и использование буферов ...................................... 62 3.7. Неблокирующий обмен .................................................................... 63 3.7.1. Коммуникационные объекты ................................................... 64 3.7.2. Инициация обмена ..................................................................... 65 3.7.3. Завершение обмена .................................................................... 67 3.7.4. Семантика неблокирующих коммуникаций ........................... 69 3.7.5. Множественные завершения ................................................... 71 3.8. Проба и отмена ................................................................................. 77 3.9. Совмещенные прием и передача сообщений ................................. 81 3.10. Производные типы данных .............................................................. 84 3.10.1. Конструкторы типа данных ................................................. 85 4 3.10.2. Адресные функции и функции экстентов ............................. 88 3.10.3. Маркеры нижней и верхней границ ....................................... 89 3.10.4. Объявление и удаление объектов типа данных ................... 90 3.10.5. Использование универсальных типов данных ...................... 91 3.10.6. Примеры ................................................................................... 93 3.11. Упаковка и распаковка ..................................................................... 96 Контрольные вопросы и задания к главе 3 .................................... 101 Глава 4. Коллективные взаимодействия процессов ................................. 107 4.1. Введение ............................................................................................ 107 4.2. Коллективные операции .................................................................. 109 4.2.1. Барьерная синхронизация ......................................................... 109 4.2.2. Широковещательный обмен .................................................... 109 4.2.3. Сбор данных ............................................................................... 110 4.2.4. Рассылка ..................................................................................... 119 4.2.5. Сбор для всех процессов ............................................................ 124 4.2.6. Функция all-to-all Scatter/Gather .............................................. 126 4.3. Глобальные операции редукции ..................................................... 128 4.3.1. Функция Reduce .......................................................................... 128 4.3.2. Предопределенные операции редукции .................................... 129 4.3.3. MINLOС и MAXLOС .................................................................. 131 4.3.4. Функция All-Reduce .................................................................... 133 4.3.5. Функция Reduce-Scatter ............................................................. 134 4.3.6. Функция Scan .............................................................................. 135 4.4. Корректность ..................................................................................... 136 Контрольные вопросы и задания к главе 4 .................................... 138 Глава 5. Группы и коммуникаторы ............................................................. 143 5.1. Введение ............................................................................................ 143 5.2. Базовые концепции ........................................................................... 144 5.3. Управление группой ......................................................................... 145 5.3.1. Средства доступа в группу ...................................................... 145 5.3.2. Конструкторы групп ................................................................ 147 5.3.3. Деструкторы групп ................................................................... 150 5.4. Управление коммуникаторами ........................................................ 150 5.4.1. Доступ к коммуникаторам ...................................................... 150 5.4.2. Конструкторы коммуникаторов ............................................ 151 5.4.3. Деструкторы коммуникаторов ............................................... 153 5.5. Примеры ............................................................................................ 154 Контрольные вопросы и задания к главе 5 .................................... 155 Глава 6. Топологии процессов ....................................................................... 158 6.1. Виртуальная топология .................................................................... 158 6.2. Топологические конструкторы ........................................................ 160 6.2.1. Конструктор декартовой топологии ..................................... 160 6.2.2. Декартова функция MPI_DIMS_CREATE ............................... 161 6.2.3. Конструктор универсальной (графовой) топологии ............. 162 6.2.4. Топологические функции запроса ............................................. 163 6.2.5. Сдвиг в декартовых координатах .......................................... 168 5 6.2.6. Декомпозиция декартовых структур .................................... 169 Контрольные вопросы к главе 6 ...................................................... 171 Р а з д е л 3. ПРОГРАММИРОВАНИЕ ПРИЛОЖЕНИЙ ........................... 173 Глава 7. Матричные задачи ........................................................................... 173 7.1. Самопланирующий алгоритм умножения матриц ........................ 173 7.2. Клеточный алгоритм умножения матриц ....................................... 179 7.2.1. Клеточный алгоритм ................................................................. 179 7.2.2. Способы создания коммуникаторов ........................................ 181 7.2.3. Параллельная программа для клеточного алгоритма ............ 184 Контрольные вопросы и задания к главе 7 .................................... 186 Глава 8. Решение дифференциальных уравнений в частных производных .................................................................................... 187 8.1. Задача Пуассона ................................................................................ 187 8.2. Параллельные алгоритмы для метода итераций Якоби ............... 188 8.2.1. Параллельный алгоритм для 1D композиции ......................... 188 8.2.2. Параллельный алгоритм для 2D композиции ......................... 192 8.2.3. Способы межпроцессного обмена ........................................... 194 Контрольные вопросы и задания к главе 8 .................................... 200 Глава 9. Параллелизм в решении задач криптоанализа ....................... 201 9.1. Криптология и криптоанализ .......................................................... 201 9.2. Криптосистема DES .......................................................................... 203 9.3. Параллельная реализация DES алгоритма ..................................... 207 Контрольные вопросы к главе 9 ..................................................... 212 Глава 10. Системы линейных алгебраических уравнений ...................... 213 10.1. Методы решения СЛАУ ................................................................... 213 10.2. Параллельные алгоритмы решения СЛАУ ................................... 216 10.2.1. Последовательный алгоритм метода простой итерации . 216 10.2.2. Параллельный алгоритм метода простой итерации ........ 217 10.2.3. Параллельный алгоритм метода Гаусса-Зейделя .............. 222 Контрольные вопросы и задания к главе 10 .................................. 224 Р а з д е л 4. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ....... 225 Глава 11. Обработка исключений и отладка ............................................. 225 11.1. Обработка исключений .................................................................... 225 11.2. Отладка параллельных приложений ............................................... 229 11.2.1. Трассировка ............................................................................. 230 11.2.2. Использование последовательных отладчиков .................... 231 11.2.3. Псевдопараллельный отладчик .............................................. 232 11.2.3. Отладка программ MPI с помощью TotalView .................... 234 Контрольные вопросы к главе 11 ................................................... 235 Глава 12. Эффективность параллельных вычислений ............................ 236 12.1. Аналитическая оценка эффективности вычислений ..................... 236 12.2. Способы измерения эффективности вычислений ......................... 240 12.3. Интерфейс профилирования ............................................................ 241 Контрольные вопросы к главе 12 .................................................... 244 6 Глава 13. Параллельные библиотеки .......................................................... 245 13.1. Библиотека ScaLAPACK .................................................................. 245 13.2. Библиотека PETSc ............................................................................ 251 13.3. Примеры ............................................................................................ 258 Контрольные вопросы к главе 13 ................................................... 268 ПРИЛОЖЕНИЯ .................................................................................................. 269 Приложение 1. Константы для языков С и Fortran ........................................ 269 Приложение 2. Перечень функций MPI-1.1 ................................................... 272 Приложение 3. Организации параллельных вычислений в сети под управлением Windows NT 277 Приложение 4. Характеристики коммуникационных сетей для кластеров ................................................................................. 282 Приложение 5. Варианты решения заданий для самостоятельной работы ...................................................................................... 284 ИСТОЧНИКИ ИНФОРМАЦИИ ...................................................................... 319 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ......................................................................... 321 УКАЗАТЕЛЬ ФУНКЦИЙ .................................................................................. 323 7 ПРЕДИСЛОВИЕ Настоящее пособие предназначено для практического обучения параллельному программированию в стандарте MPI (The Message Passing Interface). В пособии содержатся: общие сведения по парал- лельным системам и их программированию; полные справочные дан- ные по библиотеке функций MPI; примеры программирования при- ложений, важных для многих областей науки и техники; сведения по организации вычислений в различных исполнительных средах. MPI является библиотекой функций обмена данными между про- цессами, реализованная для языков С и Fortran. Головной организа- цией проекта MPI является Аргоннская национальная лаборатория США [1]. После появления первой версии стандарта MPI в мае 1994 года MPI получил широкое распространение. В настоящее время стандарт MPI адаптирован для большинства суперЭВМ и кластеров, в том числе и в России [2]. Благодаря простоте технической реализации кластеров на базе локальных сетей сотни университетов используют MPI для учебных и научных целей. Стандарт MPI-1 использует статическое размещение процессов и данных по процессорам, а стандарт MPI-2 предназначен для динами- ческого распределения работ. В настоящее время стандарт MPI-2 пол- ностью не реализован и в основном используется стандарт MPI-1. На- стоящее пособие построено на версии стандарта MPI-1.2 с до- бавлением привязок для языка С++. Все ошибки предыдущих версий исключены. При создании пособия использовались следующие источники ин- формации: • Материалы сайта Аргоннской национальной лаборатории [1], где размещены: различные версии стандартов MPI-1 и MPI-2, доку- ментация и дистрибутивы для различных версий MPICH, парал- лельные библиотеки и много других материалов справочного и учебного характера. • Материалы сайта Научно-исследовательского вычислительного центра МГУ [3]. • Книги и руководства, авторами которых являются основные разра- ботчики библиотеки интерфейса MPI и его реализаций [4,5,6,7,8]. • Переводы, выполненные в 2001 году, в рамках программы Союзно- го государства СКИФ по разработке кластерных систем [9,10,11]. 8 Все разделы пособия сопровождаются большим количеством при- меров, контрольными вопросами, заданиями для самостоятельной ра- боты. Поскольку MPI используется для программирования на языках С и Fortran, то и примеры даются попеременно на обоих языках. Для большинства заданий в приложении приведены готовые и протести- рованные программы-ответы на языке С. В приложении содержится только часть программ-ответов, это вызвано ограниченным объемом книги. Остальные ответы и многие другие материалы (дистрибутивы MPICH, параллельных библиотек, руководства по инсталляции и мно- го другой документации) содержатся на сайте Белорусского госу- дарственного университета [12] или могут быть получены по элек- тронной почте, адрес которой указан ниже. Предполагается, что на начальном уровне обучение будет прово- дится на сетях персональных ЭВМ под управлением операционной системы Windows NT с использованием языка С, поэтому в приложе- нии рассмотрены вопросы создания и настройки локальной сети на базе Windows NT (настройка сети, MPICH, среды языка С) для на- писания приложений. Настоящее пособие увидело свет благодаря помощи многих лю- дей. Постоянную поддержку в издании пособия оказывали А. Н. Кур- бацкий и С. Г. Мулярчик, много советов по содержанию книги дал М. К. Буза. Практическая проверка некоторых примеров выполнена студентами А. Е. Верхотуровым, А. Н. Гришановичем и А. В. Орло- вым. Глава 10 написана с участием Г. Ф. Астапенко. В обсуждении работы принимали участие А. С. Липницкий, В. Ф. Ранчинский, Г. К. Афанасьев и многие другие сотрудники кафедры информатики. Авторы будут признательны всем, кто поделится своими сообра- жениями по совершенствованию данного пособия. Русскоязычная тер- минология по MPI еще не устоялась, поэтому некоторые термины, ис- пользованные в пособии, могут оказаться не совсем удачными. Воз- можные предложения и замечания по этим и другим вопросам просим присылать по адресу: Республика Беларусь 220050, Минск, проспект Франциска Скорины, 4 Белорусский государственный университет Факультет радиофизики и электроники, кафедра информатики E-mail: Serikova@bsu.by, Shpakovski@bsu.by 9 Р А З Д Е Л 1. ВВЕДЕНИЕ |