1 Много ли надо знать о параллельных вычислениях? 1 Часть I. Параллельные вычислительные системы 11



Дата07.07.2016
өлшемі161.91 Kb.
#182497

Содержание

Внимание - местами могут быть неверно распознанные слова. А английские слова могут стать русскими: Open = Орет. (такое нашел и поправил уже).


Предисловие 1

Много ли надо знать о параллельных вычислениях? 1


Часть I. Параллельные вычислительные системы 11

Глава 1. Что скрывают "обыкновенные" компьютеры 13

§ 1.1. Немного об устройстве компьютера 14

Представление информации. Общее устройство компьютера. Операции и операн-
ды. Команды. Управление. Арифметико-логическое устройство. Память. Устройст-
во ввода/вывода. Центральный процессор. Вопросы и задания.

§ 1.2. Операции с числами 19

Двоичное представление чисел. Разряды. Фиксированная и плавающая запятая.
Округление чисел. Ошибка округления. Сравнение представлений чисел. Вопросы
и задания.

§ 1.3. Иерархия памяти 25

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

§ 1.4. Языки программирования и программы 31

Языки низкого и высокого уровня. Проблемно-ориентированные языки. Контроль
эффективности программ. Компьютерная зависимость. Портабельность программ.
Компиляторы и эффективность программ. Необходимость привлечения дополни-
тельной информации. Вопросы и задания.

§ 1.5. Узкие места 37

Иллюстративная модель компьютера. Пиковая и реальная производительность.
Взаимодействие отдельных узлов компьютера. Эффективность. Узкие места. Во-
просы и задания.

Глава 2. Как повышают производительность компьютеров 42

§ 2.1. Усложнение и наращивание аппаратных средств 43

Уменьшение размеров. Скалярная, конвейерная и параллельная обработка. Иерар-
хия памяти. Опережающий просмотр команд. Локальность вычислений и исполь-
зования данных. Примеры. Вопросы и задания.

§ 2.2. Повышение интеллектуальности управления компьютером 60

Закон Мура. Спецпроцессоры. Суперскалярные и VLIW-архитектуры. Коммутацион-
ные схемы. Топологии связей процессоров. SMP-компьютеры. Архитектуры NUMA и
ccNUMA. Развитие программного обеспечения. Примеры. Вопросы и задания.


Содержание
§ 2.3. Система функциональных устройств _ 78

Простые и конвейерные устройства. Стоимость работы. Загруженность. Пиковая и


реальная производительность. Эффективность. Различные соотношения. Законы
Амдала и Густавсона—Барсиса. Взаимосвязь законов. Вопросы и задания.

Глава 3. Архитектура параллельных вычислительных систем 94

§ 3.1. Классификация параллельных компьютеров и систем 96

Классификация Флинна, Хокни, Фенга, Хендлера, Шнайдера, Скилликорна.
Взаимосвязь классификаций. Архитектура компьютеров и структура задач. Вопро-
сы и задания.

§ 3.2. Векторно-конвейерные компьютеры 114

Детальное рассмотрение компьютера Cray С90. Структура оперативной памяти.
Регистровая структура. Функциональные устройства. Пиковая и реальная произво-
дительность. Вопросы и задания.

§ 3.3. Параллельные компьютеры с общей памятью 134

Детальное рассмотрение компьютера HP Superdome. Ячейка компьютера. Локальные
и удаленные ячейки. Процессор PA-8700. Работа с памятью. Вопросы и задания.

§ 3.4. Вычислительные системы с распределенной памятью 142

Детальное рассмотрение компьютеров Cray T3D/T3E. Управляющие и вычисли-
тельные узлы. Процессорный элемент. Сетевой интерфейс. Сетевой маршрутиза-
тор. Коммуникационная сеть. Память. Кластерные проекты. Вопросы и задания.

§ 3.5. Концепция GRID и метакомпьютинг 154

Метакомпьютер как огромная распределенная система. Особенности распределе-
ния задач и передачи данных. Различные проекты. Концепция GRID. Проблемы
пользователей. Вопросы и задания.

§ 3.6. Производительность параллельных компьютеров 162

Сравнение вычислительных систем. Пиковая производительность и формат дан-
ных. Вычислительные и коммуникационные ядра. Тесты. Вопросы и задания.

Часть П. Параллельное программирование 179

Глава 4. Большие задачи и параллельные вычисления 181

§ 4.1. Большие задачи и большие компьютеры 183

Моделирование климатической системы. Обтекание летательных аппаратов. Ма-
тематические модели и вычислительная техника. Огромные объемы вычислений и
размеры памяти. Вопросы и задания.

§ 4.2. Граф алгоритма и параллельные вычисления 191

Порядок вычислений. Граф алгоритма. Параллельные формы графа. Ярус и высо-
та. Инвариантность к ошибкам округления. Граф алгоритма и информационное
ядро. Параметризация в графе. Вопросы и задания.

§ 4.3. Концепция неограниченного параллелизма 198

Параллельные алгоритмы. Принцип сдваивания. Примеры алгоритмов малой вы-
соты. Ограниченность концепции. Новые алгоритмы — новые свойства. Трудности
в проблеме портабсльности. Вопросы и задания.

§ 4.4. Внутренний параллелизм 206

Преимущества внутреннего параллелизма. Примеры. Обнаружение новых свойств.
Декомпозиция алгоритмов. Использование мешенной памяти. Структура алгорит-
мов и программ. Вопросы и задания.

Содержание

V



Глава 5. Технологии параллельного программирования 219

§ 5.1. Использование традиционных последовательных языков 221

Обилие средств параллельного программирования. Трудности применения. Необ-
ходимость дополнительной информации. Системы программирования OpenМР,
DVM, mpC. Примеры использования. Вопросы и задания.

§ 5.2. Системы программирования на основе передачи сообщений 268

Системы параллельного программирования Linda, MPI, MPI-2. Интерфейсы для
последовательных языков Fortran, С, С++. Примеры использования. Вопросы и
задания.

§ 5.3. Другие языки и системы программирования 301

Т-система. Система программирования НОРМА. Приближенность к математиче-
ским записям. Примеры использования. Вопросы и задания.

Глава 6. Тонкая информационная структура программ 320

§ 6.1. Графовые модели программ 324

Информационная структура программы. Операционная и информационная связь.
Графы управления, операционно-логической истории, информационный, истории
реализации, зависимостей, влияния. Минимальные графы зависимостей. Снова
граф алгоритма. Примеры графов. Вопросы и задания.

§ 6.2. Выбор класса программ 337

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

§ 6.3. Графы зависимостей и минимальные графы 342

Опорные оператор, гнездо циклов, область. Пространства итераций. Лексикографи-
ческий порядок. Типы зависимостей. Максимальный и минимальный графы зависи-
мостей и их свойства. Теорема об информационном покрытии. Вопросы и задания.

§ 6.4. Простые и элементарные графы 351

Простые и элементарные графы и программы. Расщепление минимальных графов
на простые. Погружение минимального графа в объединение элементарных. Све-
дение к анализу элементарных программ. Вопросы и задания.

§ 6.5. Лексикографический порядок и L-свойство матриц 355

Лексикографический максимум в многограннике, L-свойство матриц. Критерий лек-
сикографического максимума. Дополнительные свойства матриц с L-свойством.
Вопросы и задания.

§ 6.6. Построение минимальных графов зависимостей 363

Основная задача. Конструктивные алгоритмы построения элементарных, простых
и минимальных графов зависимостей для программ из линейного класса. Вопросы
и задания.

§ 6.7. Циклы ParDO и избыточные вычисления 373

Лексикографически правильные графы. Параллельные множества. Параллельная
структура программ. Критерий цикла ParDO. Избыточные вычисления и критерий
их обнаружения. Вопросы и задания.

§ 6.8. Примеры 378

Формализованное построение графов алгоритмов для конкретных программ.
Сложнейшие графы алгоритмов для простейших программ. Зависимость парал-
лельной структуры от порядка выполнения операций.


VI

Содержание


Глава 7. Эквивалентные преобразования программ 393

§ 7.1. Развертки графа 394

Строгая и обобщенная развертки. Свойства разверток. Развертки и параллельные
множества. Конструктивный алгоритм построения кусочно-линейных разверток.
Выделение в графах строгих и нестрогих зависимостей. Вопросы и задания.

§ 7.2. Макрографы зависимостей 404

Макровершины и макродуги. Укрупненное представление зависимостей. Разверт-
ки и декомпозиция алгоритмов. Распределенные вычисления. Работа с медленной
памятью. Вопросы и задания.

§ 7.3. Эквивалентные программы 408

Эквивалентные преобразования программ. Эквивалентные по вычислениям про-
граммы. Преобразования, гарантирующие эквивалентность. Вопросы и задания.

§ 7.4. Наиболее распространенные преобразования программ 415

Перестановка циклов. Слияние циклов. Переупорядочивание операторов. Распре-
деление цикла. Скашивание цикла. Расщепление пространства итераций. Выпол-
нение итераций цикла в обратном порядке. Треугольные преобразования. Вопросы
и задания.

§ 7.5. Две сопутствующие задачи 421

Оценивание длины критического пути графа зависимостей. Распределение масси-
вов по модулям памяти.

§ 7.6. Примеры 426

Формализованное построение разверток и макрографов для конкретных программ.
Определение циклов ParDO. Распределение массивов по модулям памяти. Эквива-
лентное преобразование подпрограммы OLDA из пакета тестов Perfect Club
Benchmarks. Самые лучшие результаты. Система V-Ray.
Часть III. Смежные проблемы и применение 441

Глава 8. Вычислительные системы и алгоритмы 443

§ 8.1. Расширение и уточнение линейного класса 448

Прямая подстановка. Вычисляемый цикл go to. Вычисляемые ветвления. Нелиней-
ные индексные выражения. Уточнение описания внешних переменных. Подпро-
граммы и функции. Функции min и max. Прямое вычисление графов. Вопросы и
задания.

§ 8.2. Граф-машина 459

Локальность управления. Свойства различных реализаций. Гомоморфная свертка.
Граф-машина и граф вычислительной системы. Сохранение временных режимов.
Вопросы и задания.

§ 8.3. Регулярные и направленные графы 471

Итерационные процессы и регулярные графы. Расщепление бесконечного регу-
лярного графа. Главный регулярный подграф. Критерий отсутствия контуров. Ли-
нейные развертки регулярного графа. Гомоморфная свертка регулярных графов.
Вопросы и задания.

§ 8.4. Математические модели систолических массивов 482

Систолические массивы как вычислительные системы. Локальность управления.
Минимальные коммуникационные связи. Реализация регулярных графов алгорит-
мов. Примеры построения систолических массивов для заданных алгоритмов. Во-
просы и задания.


Содержание

VII

§ 8.5. Математическая модель алгебраического вычислителя 499

Структура алгебраических задач. Спецпроцессор для алгебраических задач. Ис-
пользование систолического массива для матричной операции А + ВС. Вопросы и
задания.

§ 8.6. Матрицы и структура алгоритмов 503

Общие вычислительные процессы. Вариационная матрица алгоритма. Матрицы
смежностей и инциденций. Критерий развертки. Уравновешенные графы. Крите-
рий уравновешенности. Вопросы и задания.

§ 8.7. Новое применение сведений о структуре 511

Восстановление линейного функционала. Вычисление градиента. Анализ ошибок
округления. Всюду вариационная матрица алгоритма. Вопросы и задания.

§ 8.8. Примеры 528

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

Глава 9. Пользователь в среде параллелизма 533

§ 9.1. Типичные ситуации в вопросах и ответах 534

Конкретные вопросы из практики параллельного программирования. Исследова-
ние возникших ситуаций. Возможные идеи и пути решения. Что следует из пере-
численных примеров? Вопросы и задания.

§ 9.2. Программный сервис в параллельных вычислениях 558

Почему в программе что-то не так? Компиляторы, отладчики, профилировщики,
анализаторы, конверторы. Система V-Ray. Статические и динамические характе-
ристики параллельных программ. Анализ структуры программ. Графовые структу-
ры программ на практике. Вопросы и задания.

§ 9.3. Организационная поддержка пользователя 581

Инфраструктура поддержки работы пользователей. Информационно-аналитический
центр по параллельным вычислениям Parallel.ru. Вопросы и задания.

Заключение. Параллельные вычисления: интеграция от А до Я 585

Список литературы 588

Интернет-ресурсы 592

Предметный указатель 593


Предметный указатель

L

L-свойство матрицы 362


А

Автокод 31

Автоматическое распараллеливание

программ 222


Автономная программная система 323

V-Ray 436


Адрес слова 15

физический 27


Алгоритм:

детерминированный 193

линейный 349

недетерминированный 193

параллельный 199

Штрассена 206


Альтернативные многогранники 365
Анализ ошибок:

обратный 521

прямой 520
Арифметика:

разрядно-параллельная 51

разрядно-последовательная 51
Арифметико-логическое устройство 16
Архитектура:

ccNUMA 73

NUMA71

UMA71


Б

Байт 15


Барьерная синхронизация 144
Бенчмарк 166

Банк памяти 53


Бит 14

В

Вектор:


данных 124

граничных значений 462

задержек 462

реализации 462


Величина, заданная на области 313
Вершина:

входная 192

выходная 192
Взаимодействие процессов:

Put/Get 299

Send/Receive 299
Внутренний код 16
Волновой фронт 406
Время разгона конвейера 125
Выделение стандартных операций 419
Выражение индексное нелинейное 450
Вычисления избыточные 376
Вычислительное ядро 36
Вычислительный кластер 146
Вычисляемые ветвления 449

Г

Гиперкуб 69

Гомоморфизм простой 467
Гомоморфная свертка 467
Гомоморфный:

образ 467

прообраз 467

594

Предметный указатель


Граф:

алгоритма 192

влияния 334

вызовов процедур 561

вызовов процедур расширенный 563

зависимостей 333

максимальный 346

минимальный сверху 347

минимальный снизу 346

обратный 347

простой 353

элементарный 354

покрытие 348
информационный 329
использования общей памяти 566
лексикографически правильный 373
направленный 478

направляющий вектор 478


параллельная форма 194

каноническая 194

линейная 195

максимальная 194

обобщенная 195

строгая 194


параметризованный 193
передач управления 327
плоский 488
программы 327

простой канонический вид 371


расширенный 450
регулярный 472

бесконечный 472

базовые векторы 472

базовый многогранник 474

главный регулярный подграф 473

опорные вершины 474


решетчатый 336
сильно связанный 405
системы 84
управления 327

процедурный 569


управляющий 327
эквивалентности 409
элементарный канонический

вид 371
Граф-машина 459


Графовая модель программы 326

д

Денотационный подход 325


Динамическое порождение

процессов 298


Дискретное неравенство Беллмана 466
Дискретное уравнение Беллмана 466
Дистрибутивная решетка 403
Доля последовательных вычислений 87
3

Зависимость 345

data-flow 346

анти 346


истинная 346

по входу 346

по выходу 346
Зависимые точки графа 345
Загруженность:

системы 82

устройства 80
Закон:

Амдала 1-й 86

Амдала 2-й 87

Густавсона—Барсиса 89

Мура 43
Запятая:

плавающая 21

фиксированная 21
Значение неготовое 302
И

Иерархия памяти 58


Иллюстративная модель компьютера 38
Информационная структура
программы 324
тонкая 324
Информационное ядро 197
Информационные типовые
структуры 446
гипотеза 446
История реализации программы 329
Итерация 343
цикла 343

К

Каскадный переключатель 66


Классификация:

В. Хендлера 103

Д. Скилликорна 110

Л. Шнайдера 107

М. Флинна 97

М. Флинна MIMD 98

М. Флинна MISD 98

М. Флинна SIMD 98

М. Флинна SISD 97

Р. Хокни 100

Т. Фенга 101
Когерентность кэш-памяти 72
Код:

внутренний 16

машинный 16
Команда:

векторная 48

машинная 16

скалярная 48


Коммуникационный профиль

приложений 175


Коммутатор матричный 66
Компилятор 16
Компьютер:

ATLAS 53


BBN Butterfly 72

Beowulf-кластеры 147

CDC-6600 53

CDC-7600 53

Cm* 71

Connection Machine 70


Cray C90 116
Cray T3D/T3E 142
Cray-1 57

Hewlett-Packard Superdome 135

IBM 701 51

IBM 704 51

IBM 709 51

ILLIAC IV 54

STRETCH 52

БЭСМ-6 29

M-20 29

MBC-1000M 150


Сетунь 24

Стрела 56


SMP 64

с архитектурой ccNUMA 73

с архитектурой NUMA 71

с архитектурой UMA 71

с общей памятью 63

с распределенной памятью 64


Конвейер:

длина 47


команд 53

ступень 47


Концепция неограниченного

параллелизма 199


Кортеж система Linda 268
Критическая секция программы 233
Л

Лексикографически:

неупорядоченные функции 370

упорядоченные функции 370


Лексикографический порядок:

в линейном пространстве


итераций 344

в программе 344

в пространстве итераций 345
Линейные фрагменты 341
Линейный класс алгоритмов 349
Локальность:

вычислений 57

использования данных 57

м

Макровершина 405


Макрограф 405
Макродуга 405
Макропараллелизм 374
Массивов:

выравнивание 239

распределение 238
Матрица:

алгоритма вариационная 505

информационной связности 506
взвешенная 506

инциденций 507

смежностей 507

596

Предметный указатель


Машинный нуль 22
Метакомпьютинг 155

Condor 155

GIMPS 156

Globus 156

PACX-MPI 155

SETI@home 156


Микропараллелизм 374
Модель программирования:

master/slaves 274

SPMD 275

н

Норма 403


О

Область 311


Обработка:

конвейерная 46

параллельная 44
Обратное выполнение цикла 418
Общая шина 65
Общие данные DVM 242
Операнд 15

Операционная система 17


Операционно-логическая история 328
Операционный подход 325
Операция 15

коллективная 293

произведения областей 311
Опорная область 343
Опорное:

гнездо циклов 342

пространство 342
Опорный многогранник 342
Отношение:

влияния 335

зависимости 333

п

Память 15

адресуемая 26
быстрая 26

виртуальная 28


время доступа 25
конфликты 117
кэш 26
медленная 26
неадресуемая 26
оперативная 26
постоянная 26

проблема когерентности кэш 72

разрядно-параллельная 51

разрядно-последовательная 51

регистровая 26

сверхбыстрая 26


Параллелизм:

внутренний 207

координатный 396

массовый 421

скошенный 396
Параллельная форма графа 194

высота 194

каноническая 194

линейная 195

обобщенная 195

строгая 194

ширина 194

ширина яруса 194

ярус 194
Параллельные множества 373
Параллельный алгоритм 199
Передача сообщений:

асинхронная 285

синхронная 280
Переменная:

координатная 252

локальная 226

неготовая 303

общая 226

размазанная 251

распределенная по сети 250
Перестановка циклов 416
Переупорядочивание операторов 417
Покрытие графа 348
Полукольцо разверток 465
Портабельность программ 33
Порядок:

линейный 195

частичный 192

Правило собственных вычислений 237
Принцип близкодействия 488
Проблема отображения 444
Программа 31

иерархическое представление

структуры 567
история операционно-

логическая 328


история реализации 329
канонизация 448
линейный участок 567
нелинейность устранимая 448
преобразование:

специальное 411

треугольное 419

элементарное 413


L-дерево 567
векторизация 123
графовая модель 326
детерминированная 193
исследование:

динамическое 571

статическое 341
линейная 340
линейный класс 340
недетерминированная 193
параллельная структура 373
параметр:

младший 342

старший 342
портабельность 33
преобразователь 326
простая 353
распознаватель 326
элементарная 354
Производительность:
Flops 165
MIPS 164

асимптотическая 86

пиковая 80

реальная 80


Пространство:

кортежей 268

итераций 343

переупорядочивание 411

расщепление 418
линейное 343
Процесс сдваивания 200

рекуррентный 203

Процессор 17

матричный 54

с архитектурой VLIW 62

суперскалярный 62

центральный 17
Процессы параллельные

FORK/JOIN 226


Прямая подстановка 448
Р

Развертка 394


вектор:
граничных значений 462
задержек 462
реализации 462
кусочно-линейная 397

направляющий вектор 399


минимальная 464
нулевая 403
обобщенная 394
обобщенная самая строгая 423
основная 395
расщепляющая 395
с ограничениями 463
строгая 394
Раскрутка цикла 131
Распределение цикла 417
Расслоение памяти 52
Рекуррентные соотношения 471
С

Свойства метакомпьютера 157


Связи фиктивные 450
Связь:

информационная 327

операционная 327

по управлению 327

транспортная 488

шинная 488


Сдваивания рекуррентного процесса 203
Сеть:

каскадная перестраиваемая 41


латентность 151
пропускная способность 151

598

Предметный указатель


Синхронизация барьерная 144
Система коммутации 65
Система программирования:

DVM 235


Linda 268

mpC 248


MPI 275

MPI-2 298

OpenMP 225

НОРМА 309

Т-система 301
Систолическая:

система 483

ячейка 483
Систолический массив 482
Скалярное произведение 403
Скашивание цикла 418
Слияние циклов 416
Слово 15

адрес 15


длина 15

содержимое 15


Спецпроцессор 61
Список Тор500 167
Срабатывание оператора 343
Стоимость:

операции 80

работы 80
Сумматор 24

т

Теневые грани массива 242


Теорема об информационном

покрытии 348


Тестирование компьютеров:

HINT 176


LINPACK 166

NPB 172


PERFECT Club Benchmarks 171
SPEC 175
STREAM 168
Top500 167
бенчмарк 166
Ливерморские циклы 170
Технологии параллельного
программирования 220

Топология:

гиперкуба 69

связи процессоров 68


Точка лексикографического
максимума 356

У

Укладка графа 481


Умножитель 24
Ускорение 83
Устройство 16

ввода/вывода 16

арифметико-логическое 16

загруженность 80

конвейерное 79
время разгона 125
длина 79
ступень 79

оперативное запоминающее 26

простое 79

управления 17


Уточнение внешних переменных 453

Ф

Формула Эйлера 499


Фронт:

волновой 406

вычислений 406
Функции:

базовые 249

лексикографически
неупорядоченные 370

лексикографически


упорядоченные 370

покрывающие 348

сетевые 254

узловые 249

чистые 302
ц

Центральный процессор 17


Цикл:

ParDo 374

TrueParDo 578

Циклический профиль:
путей 566
фрагмента 569

Эквивалентные:


возмущения 521
выражения 408
программы 409

Эффективность 83


Число:

двоичные разряды 19


мантисса 22
машинный нуль 22
округление 19
ошибка округления 19
порядок 22

с плавающей запятой 22


с фиксированной запятой 21

э

Эквивалентное преобразование


программы 409

Я

Ядро:


вычислительное 36

информационное 197


Язык программирования 31

высокого уровня 31

машинно-независимый 32

низкого уровня 31

однократного присваивания 310

проблемно-ориентированный 31



универсальный 32


Достарыңызбен бөлісу:




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет