malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

Новосибирский государственный технический университет

В.Э.Малышкин, В.Д.Корнеев

ПАРАЛЛЕЛЬНОЕ

ПРОГРАММИРОВАНИЕ

МУЛЬТИКОМПЬЮТЕРОВ

Новосибирск – 2006

ББК 32.973-018.1 УДК 681.3.06

Рецензенты Кафедра Вычислительных систем

Новосибирского государственного университета

Б.Г.Глинский, д.т.н., профессор

Кафедра Параллельных вычислительных технологий Новосибирского государственного университета

В.А.Вшивков, д.ф.-м.н., профессор

В книге рассмотрены основные понятия параллельного программирования мультикомпьютеров, приведены краткие обзоры основного на текущий момент инструмента параллельного программирования мультикомпьютеров – библиотеку MPI, и архитектур современных микропроцессоров и вычислительных систем. Книга содержит материалы курсов по параллельному программированию, которые в течении 10 лет читаются в Новосибирском государственном техническом университете для студентов факультета Прикладной математики и информатики и в Новосибирском государственном университете для студентов факультета Информационных технологий.

Для студентов, магистрантов и аспирантов вузов, для научных сотрудников и практикующих программистов, для всех желающих изучить параллельное программирование с самого начала.

Подготовка книги поддержана из средств программы Рособразования "Развитие научного потенциала ВШ", проект РНП.2.2.1.1.3653.

ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ

ВВЕДЕНИЕ

1.ПОНЯТИЕ ВЫЧИСЛИМОЙ ФУНКЦИИ

1.1.Неформальные соображения 1.2.Основные предварительные понятия

1.2.1.Алфавит 1.2.2.Кодирование 1.2.3.Бесконечный алфавит 1.2.4.Наборы (кортежи) 1.2.5.Термы

1.3.Понятие рекурсивной функции 1.3.1.Простейшие вычислимые функции 1.3.2.Суперпозиция частичных функции 1.3.3.Оператор примитивной рекурсии 1.3.4.Оператор минимизации

1.4.Детерминант вычислимой функции

2.ЗАДАЧА КОНСТРУИРОВАНИЯ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ

2.1.Представление алгоритма 2.2.Требования к представлению параллельного алгоритма

2.3. Простейшая программа, реализующая алгоритм 2.4.Сравнительная непроцедурность языков

программирования

3.ВЗАИМОДЕЙСТВУЮЩИЕ ПРОЦЕССЫ

3.1.Последовательные процессы. 3.2.Выполнение системы процессов 3.3.Сети Петри.

3.3.1.Определение сети Петри. 3.3.2.Разметка сети 3.3.3.Граф достижимости

3.4.Задача взаимного исключения 3.5.Дедлоки

3.5.1.Определение дедлока 3.5.2.Необходимые условия дедлока

3.5.3.Борьба с дедлоками

3.6.Задача о пяти обедающих философах

3.7.Задача производитель/потребитель 3.8.Реализация управления взаимодействующими процессами

3.8.1.Семафоры 3.8.2.Задача взаимного исключения.

3.8.3.Задача производитель/потребитель с ограниченным буфером 3.8.4.Задача читатели-писатели

3.8.5.Критические интервал

4.ПРОГРАММИРОВАНИЕ ВЗАИМОДЕЙСТВУЮЩИХ ПРОЦЕССОВ

4.1.Асинхронное программирование 4.1.1.Понятие асинхронной программы 4.1.2.Некорректное вычисление данных 4.1.3.Некорректное считывание данных

4.2.Message passing interface (MPI) 4.2.1.Определение MPI

4.2.2.Параллельная программа разделения множеств 4.2.3.Коммуникационно-замкнутые слои параллельной программы 4.2.4.Когерентность параллельных программ 4.2.5.Анализ программы разделения множеств

5.ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В КРУПНОБЛОЧНЫХ ИЕРАРХИЧЕСКИХ МУЛЬТИКОМПЬЮТЕРАХ

5.1.Введение 5.2.Линейные иерархические мультикомпьютеры 5.3.Линейные алгоритмы

5.4.Отображение алгоритма на ресурсы мультикомпьютера 5.5.Система параллельного сборочного программирования Иня

5.5.1.Основные компоненты СПП 5.5.2.Децентрализованное управление. 5.5.3.Централизованное управление.

5.5.4.Язык и система параллельного программирования

Иня.

6.ОТОБРАЖЕНИЕ АЛГОРИТМОВ НА РЕСУРСЫ МУЛЬТИКОМПЬЮТЕРА

6.1.Статическая постановка задачи 6.2.Идеи параллельной реализация PIC

6.2.1.Краткое описание метода 6.2.2.Особенности параллельной реализации метода

частиц 6.2.3.Сборочный подход к конструированию программы

6.3.Распараллеливание метода частиц 6.3.1.Распараллеливание метода частиц для линейки ПЭ

(линеаризация PIC)

6.3.2.Отображение линеаризованного PIC на 2D решетку ПЭ

6.3.3.Отображение 2D решетки ПЭ на гиперкуб 6.4.Централизованные алгоритмы балансировки загрузки

6.4.1.Начальная балансировка загрузки ПЭ 6.4.2.Динамическая балансировка загрузки 6.4.3.Виртуальные слои ПМ 6.4.4.Централизованный алгоритм балансировки

загрузки при реализации PIC на решетке ПЭ 6.5.Децентрализованные алгоритмы динамической балансировки загрузки

6.5.1.Основной диффузионный алгоритм 6.5.2.Модифицированный диффузионный алгоритм 6.5.3.Децентрализованный алгоритм динамической балансировки

6.6.Заключительные замечания 6.7.Принципы сборочной технологии параллельного

программирования

7.СИНТЕЗ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

7.1.Простые вычислительные модели 7.1.1. Исходные соображения 7.1.2.Основные определения

7.1.3.Оптимизация при планировании вычислений

7.1.4.Генерация параллельных программ 7.2.Алгоритмы синтеза параллельных программ

7.2.1.Общая схема синтеза параллельной программы 7.2.2.Планирование алгоритма 7.2.3.Выбор алгоритма

7.2.4.Структурированные операции и их преобразования 7.2.5.Проблема компиляции параллельной программы

7.3.Вычислительные модели с массивами

8.ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ В СИСТЕМАХ MPI и OpenMP

8.1.Введение 8.1.1.Модели параллельного программирования

8.1.2.Модель передачи сообщений 8.1.3.Модель с общей памятью 8.1.4.Модель параллелизма по данным.

8.1.5.В чем особенность и сложность параллельного программирования

8.1.6. Почему выбраны MPI, OpenMP и HPF ?

8.2.Программирование на распределенных мультикомпьютерах и примеры параллельных программ в

MPI

8.2.1.Умножение матрицы на матрицу.

8.2.1.1Алгоритм 1.

8.2.1.2Алгоритм 2.

8.2.2.Параллельные алгоритмы решения систем линейных алгебраических уравнений методом Гаусса.

8.2.2.1.Первый алгоритм решения СЛАУ методом Гаусса

8.2.2.2.Второй алгоритм решения СЛАУ методом Гаусса.

8.2.3.Параллельные алгоритмы решения СЛАУ итерационными методами.

8.2.3.1Параллельный алгоритм решения СЛАУ методом простой итерации.

8.2.3.2Параллельный алгоритм решения СЛАУ методом сопряженных градиентов.

8.3.Программирование на суперкомпьютерах с общей памятью и примеры параллельных программ в OpenMP 8.3.1. Умножение матрицы на матрицу. 8.3.2.Параллельный алгоритм решения СЛАУ методом

Гаусса 8.3.3.Параллельный алгоритм решения СЛАУ методом

сопряженных градиентов

ПРЕДИСЛОВИЕ

В книге приводятся и обсуждаются базисные понятия из области параллельных вычислений и параллельного программирования мультикомпьютеров.

Суперкомпьютеры позволили начать решать новые задачи большого размера, приступить к реализации реалистических математических моделей сложных физических явлений и технических устройств, которые раньше нельзя было решать на маломощных последовательных компьютерах. В этой области суперкомпьютеры являются незаменимым и универсальным технологическим инструментом как в изучении природы, так и в практической деятельности. Понятна привлекательность изучения ядерного взрыва на модели, а не в натуре.

Использование суперкомпьютеров наталкивается на большие трудности. Очень сложно создавать и отлаживать параллельные программы, гораздо сложнее последовательных. В

самых простых с виду параллельных программах обнаруживаются иной раз фатальные ошибки. Известны программы, содержащие буквально десяток операторов, которые долгое время считались правильными. И тем не менее со временем в них обнаруживали тяжелые ошибки! А ведь среди приложений суперкомпьютеров есть много и таких, которые очень чувствительны к ошибкам. Даже незначительные ошибки в программе могут приводить к тяжелым последствиям. Отсюда

значительно бó льший, чем в последовательном

программировании, интерес к автоматизации конструирования параллельных программ, к строгим математическим методам конструирования и анализа правильности программ.

Профессия программиста требует основательного знания математики. Незнание математики существенно ограничивает возможности понимания сложного поведения системы параллельно протекающих и взаимодействующих вычислительных процессов. Инженеры, не имеющие подготовки в математике, быстро оказываются в состоянии не полного понимания устройства параллельного программного обеспечения.

Теория параллельных вычислений характеризуется большим разнообразием идей, подходов к решению задач, к

разработке параллельных программ. Часто задачи требуют учета их особенностей для разработки эффективных программ решения. Это в свою очередь приводит к разработке разнообразных и многочисленных специализированных средств параллельного программирования. Все средства невозможно (да и не нужно) изучить. По этой причине более продуктивно начать с изучения общих моделей и методов параллельного программирования, нежели с конкретных систем программирования

Чтобы избежать рассмотрения множества не существенных на первых порах деталей и освоить идеи параллельного программирования в достаточно общем виде,

изучение предмета начнется на довольно высоком уровне абстракции. Это, конечно, потребует немалых усилий при изучении, но окупится со временем более глубоким пониманием природы параллельных вычислений. А потому здесь не будет рассматриваться все разнообразие идей параллельного программирования, а выбран путь, который быстро приведет к пониманию сути параллельного программирования. А это и есть основная цель книги – правильно сформировать исходную точку зрения на предмет.

Для лучшего понимания и усвоения теоретического материала необходимо, конечно, и знакомство с нынешними вычислительными реалиями. Потому в книге кратко рассматриваются и основные на сегодняшний день средства задания множества параллельно исполняющихся и взаимодействующих процессов (системы MPI и OpenMP), а

также приводится обзор архитектур современных микропроцессоров и вычислительных систем.

Книга трактует вопросы именно параллельного программирования (в узком смысле). Имеется ввиду, что процесс решения задачи разбивается (довольно условно) на несколько крупных этапов: «физическая» формулировка задачи →