Параллельное программирование мультикомпьютеров (200,00 руб.)

Стр.1

Стр.2

Стр.10

Стр.11

Стр.12

Стр.13

В.Э. Малышкин, В.Д. Корнеев ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ МУЛЬТИКОМПЬЮТЕРОВ НОВОСИБИРСК 2006

Стр.1

УДК 004.272 М 209 Подготовка книги поддержана из средств программы Рособразования “Развитие научного потенциала ВШ”, проект РНП.2.2.1.1.3653 Рецензенты: д-р техн. наук, проф., зав. кафедрой вычислительных систем механико-математического ф-та НГУ Б.М. Глинский, д-р физ.-мат наук, проф. НГУ В.А. Вшивков Малышкин, В.Э. М 209 Параллельное программирование мультикомпьютеров : учебник / В.Э. Малышкин, В.Д. Корнеев. – Новосибирск : Изд-во НГТУ, 2006. – 296 с. – (“Учебники НГТУ”). ISBN 5-7782-0702-6 Рассмотрены основные понятия параллельного программирования мультикомпьютеров, приведены краткие обзоры основного на текущий момент инструмента параллельного программирования мультикомпьютеров – библиотеки MPI и архитектур современных микропроцессоров и вычислительных систем. Содержатся материалы курсов по параллельному программированию, которые в течение 10 лет читаются в Новосибирском государственном техническом университете для студентов факультета прикладной математики и информатики и в Новосибирском государственном университете для студентов факультета информационных технологий. Книга предназначена для студентов, магистрантов и аспирантов вузов, для научных сотрудников и практикующих программистов, а также для всех желающих изучить параллельное программирование. УДК 004.272 ISBN 5-7782-0702-6  В.Э. Малышкин, В.Д. Корнеев, 2006  Новосибирский государственный

Стр.2

ОГЛАВЛЕНИЕ ПРЕДИСЛОВИЕ ................................................................................................. 9 ВВЕДЕНИЕ ....................................................................................................... 12 Г л а в а 1. ПОНЯТИЕ ВЫЧИСЛИМОЙ ФУНКЦИИ................................. 15 1.1. Неформальное введение .............................................................. 15 1.2. Основные предварительные понятия ......................................... 19 1.2.1. Алфавит ................................................................................ 19 1.2.2. Кодирование ........................................................................ 19 1.2.3. Бесконечный алфавит ......................................................... 20 1.2.4. Наборы (кортежи) ............................................................... 21 1.2.5. Термы ................................................................................... 21 1.3. Понятие рекурсивной функции .................................................. 23 1.3.1. Простейшие вычислимые функции ................................... 23 1.3.2. Суперпозиция вычислимых функций ................................ 23 1.3.3. Оператор примитивной рекурсии ...................................... 26 1.3.4. Оператор минимизации ...................................................... 31 1.4. Детерминант вычислимой функции ........................................... 33 Г л а в а 2. ЗАДАЧА КОНСТРУИРОВАНИЯ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ ............................................................................. 37 2.1. Представление алгоритма ........................................................... 37 2.2. Требования к представлению параллельного алгоритма ......... 47 2.3. Простейшая программа, реализующая алгоритм ...................... 49 2.4. Сравнительная непроцедурность языков программирования .................................................................................... 50 Г л а в а 3. ВЗАИМОДЕЙСТВУЮЩИЕ ПРОЦЕССЫ ............................... 53 3.1. Последовательные процессы ...................................................... 53 3.2. Выполнение системы процессов ................................................ 58 3.3. Сети Петри.................................................................................... 60 3.3.1. Определение сети Петри..................................................... 60 3.3.2. Разметка сети ....................................................................... 61 3.3.3. Граф достижимости ............................................................ 64

Стр.10

6 ОГЛАВЛЕНИЕ 3.4. Задача взаимного исключения .................................................... 66 3.5. Дедлоки ......................................................................................... 65 3.5.1. Определение дедлока .......................................................... 65 3.5.2. Необходимые условия возникновения дедлока................ 69 3.5.3. Борьба с дедлоками ............................................................. 70 3.6. Задача о пяти обедающих философах ........................................ 72 3.7. Задача производитель/потребитель ............................................ 75 3.8. Реализация управления взаимодействующими процессами .... 77 3.8.1. Семафоры ............................................................................. 78 3.8.2. Задача взаимного исключения ........................................... 79 3.8.3. Задача производитель/потребитель с ограниченным буфером ................................................................................ 80 3.8.4. Задача читатели-писатели .................................................. 81 3.8.5. Критические интервалы ...................................................... 84 Г л а в а 4. ПРОГРАММИРОВАНИЕ ВЗАИМОДЕЙСТВУЮЩИХ ПРОЦЕССОВ .............................................................................. 85 4.1. Асинхронное программирование ............................................... 85 4.1.1. Понятие асинхронной программы ..................................... 85 4.1.2. Некорректное вычисление данных .................................... 89 4.1.3. Некорректное считывание данных .................................... 89 4.2. Message passing interface (MPI) ................................................... 90 4.2.1. Определение MPI ................................................................ 91 4.2.2. Параллельная программа разделения множеств .............. 93 4.2.3. Коммуникационно-замкнутые слои параллельной программы............................................................................ 96 4.2.4. Когерентность параллельных программ ........................... 98 4.2.5. Анализ программы разделения множеств ....................... 100 Г л а в а 5. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В КРУПНОБЛОЧНЫХ ИЕРАРХИЧЕСКИХ МУЛЬТИКОМПЬЮТЕРАХ ..................................................... 103 5.1. Введение .................................................................................... 103 5.2. Иерархические мультикомпьютеры ........................................ 106 5.3. Линейные алгоритмы................................................................. 110 5.4. Динамическое отображение алгоритма на ресурсы мультикомпьютера..................................................................... 113 5.5. Система параллельного сборочного программирования Иня .... 118 5.5.1. Основные компоненты СПП ............................................ 119 5.5.2. Децентрализованное управление ..................................... 119 5.5.3. Централизованное управление ......................................... 123 5.5.4. Язык и система параллельного программирования Иня ... 123

Стр.11

7 Г л а в а 6. ОТОБРАЖЕНИЕ АЛГОРИТМОВ НА РЕСУРСЫ МУЛЬТИКОМПЬЮТЕРА ........................................................ 133 6.1. Статическая постановка задачи ................................................ 133 6.2. Идеи параллельной реализация PIC ......................................... 142 6.2.1. Краткое описание метода ................................................. 142 6.2.2. Особенности параллельной реализации метода частиц ................................................................................. 144 6.2.3. Сборочный подход к конструированию программы...... 146 6.3. Распараллеливание метода частиц ........................................... 147 6.3.1. Распараллеливание метода частиц для линейки ПЭ (линеаризация PIC)............................................................ 148 6.3.2. Отображение линеаризованного PIC на 2D решетку ПЭ ........................................................................ 148 6.3.3. Отображение 2D решетки ПЭ на гиперкуб ..................... 149 6.4. Централизованные алгоритмы балансировки загрузки .......... 150 6.4.1. Начальная балансировка загрузки ПЭ ............................. 151 6.4.2. Динамическая балансировка загрузки ............................. 152 6.4.3. Виртуальные слои ПМ ...................................................... 155 6.4.4. Централизованный алгоритм балансировки загрузки при реализации PIC на решетке ПЭ................................. 156 6.5. Децентрализованные алгоритмы динамической балансировки загрузки .............................................................. 157 6.5.1. Основной диффузионный алгоритм ................................ 157 6.5.2. Модифицированный диффузионный алгоритм .............. 158 6.5.3. Децентрализованный алгоритм динамической балансировки ..................................................................... 158 6.6. Заключительные замечания к реализации PIC ........................ 159 6.7. Общие принципы сборочной технологии параллельного программирования ..................................................................... 160 6.7.1. Собирать или делить? ....................................................... 160 6.7.2. Двухуровневая система программирования ................... 161 6.7.3. Разделение семантики и схемы вычислений .................. 163 6.7.4. Динамическая балансировка загрузки ............................. 163 6.7.5. Требования к представлению массовых алгоритмов для их параллельной реализации ..................................... 163 Г л а в а 7. СИНТЕЗ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ НА ВЫЧИСЛИТЕЛЬНЫХ МОДЕЛЯХ .................................. 165 7.1. Простые вычислительные модели ............................................ 165 7.1.1. Исходные соображения .................................................... 165 7.1.2. Основные определения ..................................................... 170 7.1.3. Оптимизация при планировании вычислений ................ 179 7.1.4. Генерация параллельных программ................................. 182

Стр.12

8 ОГЛАВЛЕНИЕ 7.2. Алгоритмы синтеза параллельных программ .......................... 185 7.2.1. Общая схема синтеза параллельной программы ............ 185 7.2.2. Планирование алгоритма .................................................. 190 7.2.3. Выбор алгоритма ............................................................... 195 7.2.4. Структурированные операции и их преобразования ..... 199 7.2.5. Проблема компиляции параллельной программы ......... 210 7.3. Вычислительные модели с массивами ..................................... 213 7.3.1. Упрощенные вычислительные модели с массивами...... 213 7.3.2. Динамические вычислительные модели с массивами ... 216 7.3.3. Итеративные вычислительные модели с массивами...... 217 7.3.4. Синтез максимально асинхронной программы .............. 219 7.4. Модификации и приложения метода ....................................... 220 7.4.1. Интеллектуализация модульного программирования ... 221 7.4.2. Моделирование дискретных систем ................................ 225 Г л а в а 8. ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ В СИСТЕМАХ MPI и OpenMP ................................................ 229 8.1. Модели параллельного программирования ............................. 230 8.2. Программирование на распределенных мультикомпьютерах и примеры параллельных программ в MPI.................... 237 8.2.1. Умножение матрицы на матрицу ..................................... 239 8.2.2. Параллельные алгоритмы решения систем линейных алгебраических уравнений методом Гаусса ................... 254 8.2.3. Параллельные алгоритмы решения СЛАУ итерационными методами ................................................ 265 8.3. Программирование на суперкомпьютерах с общей памятью и примеры параллельных программ в OpenMP ....... 274 8.3.1. Умножение матрицы на матрицу ..................................... 276 8.3.2. Параллельный алгоритм решения СЛАУ методом Гаусса ................................................................................. 278 8.3.3. Параллельный алгоритм решения СЛАУ методом сопряженных градиентов.................................................. 282 Библиографический список ........................................................................... 287 Словарь терминов ........................................................................................... 289

Стр.13