Бурова И.Г., Демьянович Ю.К. Алгоритмы параллельных вычислений и программирование
Подождите немного. Документ загружается.
Регулярный решетчатый граф 120
Режим максимального быстродействия 80
Решетчатый граф 53
Связный гомоморфизм 48
Связный граф 42
Синхронизированная система 79
Синхронный режим 79
Систолические массивы 112
Систолические ячейки 112
Смежные вершины 41
Собственные переменные 136
События в CSP 191
Составная цепь 41
Стабильная работа 57
Степень вершины 41
Стоимость операции 56
Стоимость работы 56
Схема сдваивания 21
Такт 55
Технология Open MP 135
Управляющий процесс в Linda 197
Уравновешенная базовая система 79
Ускорение 62
Условное функциональное устройство 65
Функции одинакового порядка 27
Функциональное устройство 55
Характеристика Эйлера 117
Частично упорядоченный граф 43
Шаблон в Linda 192
Ширина параллельной формы 19
Цепь 41
Цикл 42
Эквивалентные функции 27
Элементарный цикл 42
202
Литература
1 . Воеводин В.В. Математические модели и методы в парал-
лельных процессах. М., 1986. 296 с.
2 . Корнеев В.В. Параллельные вычислительные системы. М.,
1999. 320 с.
3 . Yukiya Aoyama, Jun Nakano. RS/6000 SP:Practical MPI
Programming. IBM. Technical Support Organization., 2000. 221 p.
www.redbook.ibm.com
4 . Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.
СПб., 2002. 608 с.
203
О Г Л А В Л Е Н И Е
ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
Глава 1. О ПОСТАНОВКЕ ЗАДАЧИ
РАСПАРАЛЛЕЛИВАНИЯ . . . . . . . . . . . . . . . . . . . . . . . . 5
§ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
§ 2. О некоторых вычислительных задачах . . . . . . . . . . . . . . . . . . . 7
§ 3. Численный эксперимент и его целесообразность . . . . . . . . . 9
§ 4. Об архитектуре вычислительных систем . . . . . . . . . . . . . . . . 11
4.1. Однопроцессорные системы . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2. Многопроцессорные системы . . . . . . . . . . . . . . . . . . . . . . . 12
4.3. Трудности использования многопроцессорных ВС .14
4.4. Идея конвейерных вычислений . . . . . . . . . . . . . . . . . . . . 14
4.5. О классификации многопроцессорных систем . . . . . 15
4.6. Примеры высокопроизводительных ВС . . . . . . . . . . . . 16
§ 5. О понятии "алгоритм" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
§ 6. Параллельная форма алгоритма. . . . . . . . . . . . . . . . . . . . . . . . .19
§ 7. О концепции неограниченного параллелизма . . . . . . . . . . . 21
§ 8. О схеме сдваивания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
§ 9. О вычислении степени на параллельной системе . . . . . . . 23
§ 10. О взаимоотношении числа данных и высоты
параллельной формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Глава 2. О НЕКОТОРЫХ МЕТОДАХ
ЛИНЕЙНОЙ АЛГЕБРЫ В КОНЦЕПЦИИ
НЕОГРАНИЧЕННОГО ПАРАЛЛЕЛИЗМА . . . . . . 27
§ 1. Предварительные соглашения . . . . . . . . . . . . . . . . . . . . . . . . . . 27
§ 2. Распараллеливание умножения матрицы на вектор . . . . 28
§ 3. Распараллеливание перемножения матриц . . . . . . . . . . . . . 28
§ 4. О распараллеливании одного рекуррентного процесса . .29
§ 5. Об LU-разложении . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
§ 6. Распараллеливание LU-разложения трехдиагональной
матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34
§ 7. О распараллеливании процесса отыскания обратной
матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38
204
Глава 3. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ГРАФОВ
В СВЯЗИ С РАСПАРАЛЛЕЛИВАНИЕМ . . . . . . . 41
§ 1. О понятии графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41
§ 2. Ориентированный граф . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
§ 3. Топологическая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
§ 4. Примеры графов параллельных форм . . . . . . . . . . . . . . . . . . 45
§ 5. Изоморфизм графов. Операции гомоморфизма . . . . . . . . 47
§ 6. Построение графов параллельных форм . . . . . . . . . . . . . . . .49
§ 7. Направленные графы и параллельные формы . . . . . . . . . .51
Глава 4. ФУНКЦИОНАЛЬНЫЕ УСТРОЙСТВА . . . . . . . . . 55
§ 1. Некоторые определения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
§ 2. Свойства простых и конвейерных функциональных
устройств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
§ 3. О времени реализации алгоритма . . . . . . . . . . . . . . . . . . . . . . . 60
§ 4. Ускорение при распараллеливании . . . . . . . . . . . . . . . . . . . . . . 62
Глава 5. АЛГОРИТМЫ И ВЫЧИСЛИТЕЛЬНЫЕ
СИСТЕМЫ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
§ 1. О соотношении графов алгоритма
и вычислительной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
§ 2. Базовая вычислительная система. . . . . . . . . . . . . . . . . . . . . . . .68
§ 3. К построению графа вычислительной системы. . . . . . . . . .70
Глава 6. ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ
АЛГОРИТМОВ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
§ 1. Программы реализации алгоритмов . . . . . . . . . . . . . . . . . . . . 75
1.1. Условия реализуемости алгоритмов . . . . . . . . . . . . . . . .75
1.2. О времени выполнения алгоритмов . . . . . . . . . . . . . . . . 78
1.3. Уравновешенность базовой системы.
Режим максимального быстродействия . . . . . . . . . . . 79
§ 2. Матричные представления графов алгоритмов . . . . . . . . . 82
2.1. Матрицы инциденций и смежности . . . . . . . . . . . . . . . . 82
2.2. О реализации алгоритма с данной
матрицей инциденций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.3. Об использовании памяти для хранения
промежуточных результатов . . . . . . . . . . . . . . . . . . . . . . 85
2.4. Задача отображения алгоритмов
на вычислительные системы как задача
минимизации функционала . . . . . . . . . . . . . . . . . . . . . . . 86
205
2.5. О представлении графа алгоритма
в пространстве R
n
. Условия существования
циклов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .89
§ 3. Об N P -сложности задачи отыскания
графа вычислительной системы из графа
алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.1. Метод перебора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.2. О сужении класса задач . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Глава 7. ПАРАЛЛЕЛИЗМ ПРИ ОБРАБОТКЕ
ИНФОРМАЦИИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
§ 1. Конвейерные вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
1.1. Безусловные конвейерные вычислители . . . . . . . . . . . 97
1.2. Развертка безусловного конвейерного
вычислителя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
§ 2. Векторные вычислительные машины . . . . . . . . . . . . . . . . . . 104
2.1. Векторные операции и векторная память . . . . . . . . .104
2.2. О зацеплении конвейерных устройств . . . . . . . . . . . . 107
§ 3. Систолические массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.1. Понятие о системах с жестко заданной
конфигурацией. Систолические ячейки
и систолические массивы . . . . . . . . . . . . . . . . . . . . . . . . .111
3.2. Исходные предположения. Принцип
близкодействия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .115
3.3. Клеточные подразделения. Характеристика
Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.4. Систолические массивы и регулярные
графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
§ 4. Об архитектуре параллельных суперкомпьютеров . . . . .122
4.1. О наиболее мощных современных
компьютерах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.2. О сложных вычислительных задачах . . . . . . . . . . . . . 123
4.3. Виды обработки данных . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.4. Об истории развития параллелелизма . . . . . . . . . . . . 126
4.5. Об архитектуре векторно-конвейерной
супер-ЭВМ CRAY C90 . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
206
Глава 8. О ТЕХНОЛОГИИ
ПРОГРАММИРОВАНИЯ OPEN MP . . . . . . . . . . .130
§ 1. Трудности перехода от последовательных программ
к параллельным . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
§ 2. Введение в технологию Open MP. . . . . . . . . . . . . . . . . . . . . . .135
§ 3. Директивы Open MP. Описание
параллельных областей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
§ 4. Параллельные секции и их вложенность . . . . . . . . . . . . . . . 137
§ 5. Распределение работы. Программирование
на низком уровне . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
§ 6. Выполнение операторов цикла . . . . . . . . . . . . . . . . . . . . . . . . . 139
§ 7. Параллелизм независимых фрагментов . . . . . . . . . . . . . . . . 141
§ 8. Классы переменных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
§ 9. Критические секции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
§ 10. Другие возможности Open MP . . . . . . . . . . . . . . . . . . . . . . . . 145
10.1. Синхронизация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
10.2. Участок нити-мастера . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
10.3. Последовательное выполнение
отдельного оператора . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
10.4. Гарантированное поддержание когерентности . . . 146
§ 11. Привлекательные черты технологии Open MP . . . . . . . 146
Глава 9. О ПАРАЛЛЕЛЬНОМ ПРОГРАММИРОВАНИИ
С ИСПОЛЬЗОВАНИЕМ СТАНДАРТА MPI . . . 148
§ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
§ 2. Элементы идеологии стандарта MPI . . . . . . . . . . . . . . . . . . .149
§ 3. О реализации разветвлений на параллельной системе .152
§ 4. О программировании вычислений на параллельной
системе. Процедура MPI_REDUCE . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
§ 5. Перечень основных процедур стандарта MPI . . . . . . . . . .155
Глава 10. ТЕХНОЛОГИЯ
ПРОГРАММИРОВАНИЯ DVM. . . . . . . . . . . . . . . . 162
§ 1. Основные принципы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
§ 2. Распределение массивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
§ 3. Выравнивание массивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
§ 4. Параллельное выполнение циклов . . . . . . . . . . . . . . . . . . . . . .165
§ 5. Отображение задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
§ 6. Соседние общие данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
207
§ 7. Удаленные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .169
§ 8. Редукционные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
§ 9. Пересеченные данные. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .170
§ 10. Пример программы. Отладка. Заключительные
замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Глава 11. ПРОГРАММИРОВАНИЕ НА mpC . . . . . . . . . . . . . 174
§ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
§ 2. Базовые и узловые функции. . . . . . . . . . . . . . . . . . . . . . . . . . . .174
§ 3. Автоматические сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
§ 4. Статическая сеть . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
§ 5. Тип сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
§ 6. Родитель виртуалььной сети. Виртуальный
хост-компьютер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
§ 7. Синхронизация работы сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
§ 8. Подсети в языке mpC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
§ 9. Управление отображением виртуальных процессоров
на реальные процессы параллельной программы. . . . . . . . . . .182
§ 10. Учет затрат на передачу данных . . . . . . . . . . . . . . . . . . . . . . 185
Глава 12. О НЕКОТОРЫХ ДРУГИХ ЯЗЫКАХ
ПРОГРАММИРОВАНИЯ . . . . . . . . . . . . . . . . . . . . . . 188
§ 1. О языке Occam (“Бритва Оккама”). . . . . . . . . . . . . . . . . . .188
§ 2. О языке CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
§ 3. О языке Linda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
§ 4. Портфель задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ . . . . . . . . . . . . . . . . . . . . . . . . . . . .200
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
208