Параллельные вычисления. — СПб.: БХВ-Петербург, 2004. — 608 с.: ил.
ISBN 5-94157-160-7
Книга известных российских ученых посвящена обсуждению ключевых проблем современных параллельных вычислений. С единых позиций рассматриваются архитектуры параллельных вычислительных систем, технологии параллельного программирования, численные методы решения задач. Вместе со строгим описанием основных положений теории информационной структуры программ и алгоритмов, книга содержит богатый справочный материал, необходимый для организации эффективного решения больших задач на компьютерах с параллельной архитектурой.
Содержание
Предисловие.....................................................................................................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
Закон Мура. Спецпроцессоры. Суперскалярные и VLlW-архитектуры. Коммутационные схемы. Топологии связей процессоров. SMP-компьютеры. Архитектуры NUMA и ccNUMA, Развитие программного обеспечения. Примеры. Вопросы и задания.
§ 2.3. Система функциональных устройств............_............................................78
Простые и конвейерные устройства. Стоимость работы. Загруженность. Пиковая и реальная производительность. Эффективность. Различные соотношения. Законы Амдала и Густавсона—Барсиса. Взаимосвязь законов. Вопросы и задания.
Глава 3. Архитектура параллельных вычислительных систем............................94
§ 3.1. Классификация параллельных компьютеров и систем............................96
Классификация Флинна, Хокни, Фенга, Хендлера, Шнайдера, Скилликорна. Взаимосвязь классификаций. Архитектура компьютеров и структура задач. Вопросы и задания.
§ 3.2. Векторно-конвейерные компьютеры.........................................................114
Детальное рассмотрение компьютера Cray C90. Структура оперативной памяти. Регистровая структура. Функциональные устройства. Пиковая и реальная производительность. Вопросы и задания.
§ 3.3. Параллельные компьютеры с общей памятью.........................................134
Детальное рассмотрение компьютера HP Superdome. Ячейка компьютера. Локальные и удаленные ячейки. Процессор РА-8700. Работа с памятью. Вопросы и задания.
§ 3.4. Вычислительные системы с распределенной памятью............................142
Детальное рассмотрение компьютеров Cray T3D/T3E. Управляющие и вычислительные узлы. Процессорный элемент. Сетевой интерфейс. Сетевой маршрутизатор. Коммуникационная сеть. Память. Кластерные проекты. Вопросы и задания.
§ 3.5. Концепция GRID и метакомпьютинг.......................................................154
Метакомпьютер как огромная распределенная система. Особенности распределения задач и передачи данных. Различные проекты. Концепция GRID. Проблемы пользователей. Вопросы и задания.
§ 3.6. Производительность параллельных компьютеров....................................162
Сравнение вычислительных систем. Пиковая производительность и формат данных. Вычислительные и коммуникационные ядра. Тесты. Вопросы и задания.
ЧАСТЬ II. ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ........................................179
Глава 4. Большие задачи и параллельные вычисления.....................................181
§ 4.1. Большие задачи и большие компьютеры..................................................183
Моделирование климатической системы. Обтекание летательных аппаратов. Математические модели и вычислительная техника. Огромные объемы вычислений и размеры памяти. Вопросы и задания.
§ 4.2. Граф алгоритма и параллельные вычисления...........................................191
Порядок вычислений. Граф алгоритма. Параллельные формы графа. Ярус и высота. Инвариантность к ошибкам округления. Граф алгоритма и информационное ядро. Параметризация в графе. Вопросы и задания.
§ 4.3. Концепция неограниченного параллелизма.............................................198
Параллельные алгоритмы. Принцип сдваивания. Примеры алгоритмов малой высоты. Ограниченность концепции. Новые алгоритмы — новые свойства. Трудности в проблеме портабельности. Вопросы и задания.
§ 4.4. Внутренний параллелизм............................................................................206
Преимущества внутреннего параллелизма. Примеры. Обнаружение новых свойств. Декомпозиция алгоритмов. Использование медленной памяти. Структура алгоритмов и программ. Вопросы и задания.
Содержание_________________________________________V
Глава 5. Технологии параллельного программирования....................................219
§ 5.1. Использование традиционных последовательных языков......................221
Обилие средств параллельного программирования. Трудности применения. Необходимость дополнительной информации. Системы программирования ОрепМР, DVM, mpC. Примеры использования. Вопросы и задания.
§ 5.2. Системы программирования на основе передачи сообщений................268
Системы параллельного программирования Linda, MPI, MPI-2. Интерфейсы для последовательных языков Fortran, С, C++. Примеры использования. Вопросы и задания.
§ 5.3. Другие языки и системы программирования...........................................301
Т-система. Система программирования НОРМА. Приближенность к математическим записям. Примеры использования. Вопросы и задания.
Глава 6. Тонкая информационная структура программ.....................................320
§ 6.1. Графовые модели программ........................................................................324
Информационная структура программы. Операционная и информационная связь. Графы управления, операционно-логической истории, информационный, истории реализации, зависимостей, влияния. Минимальные графы зависимостей. Снова граф алгоритма. Примеры графов. Вопросы и задания.
§ 6.2. Выбор класса программ...............................................................................337
Статический анализ структуры программ. Статистическая значимость отдельных операторов. Линейный класс программ. Вопросы и задания.
§ 6.3. Графы зависимостей и минимальные графы............................................342
Опорные оператор, гнездо циклов, область. Пространства итераций. Лексикографический порядок. Типы зависимостей. Максимальный и минимальный графы зависимостей и их свойства. Теорема об информационном покрытии. Вопросы и задания.
§ 6.4. Простые и элементарные графы................................................................351
Простые и элементарные графы и программы. Расщепление минимальных графов на простые. Погружение минимального графа в объединение элементарных. Сведение к анализу элементарных программ. Вопросы и задания.
§ 6.5. Лексикографический порядок и /--свойство матриц...............................355
Лексикографический максимум в многограннике. L-свойство матриц. Критерий лексикографического максимума. Дополнительные свойства матриц с i-свойством. Вопросы и задания.
§ 6.6. Построение минимальных графов зависимостей.....................................363
Основная задача. Конструктивные алгоритмы построения элементарных, простых и минимальных графов зависимостей для программ из линейного класса. Вопросы и задания.
§ 6.7. Циклы ParDOvi избыточные вычисления.................................................373
Лексикографически правильные графы. Параллельные множества. Параллельная структура программ. Критерий цикла ParDO. Избыточные вычисления и критерий их обнаружения. Вопросы и задания.
§6.8. Примеры.......................................................................................................378
Формализованное построение графов алгоритмов для конкретных программ. Сложнейшие графы алгоритмов для простейших программ. Зависимость параллельной структуры от порядка выполнения операций.
Глава 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. Вычисляемые ветвления. Нелинейные индексные выражения. Уточнение описания внешних переменных. Подпрограммы и функции. Функции mm и max. Прямое вычисление графов. Вопросы и задания.
§ 8.2. Граф-машина................................................................................................459
Локальность управления. Свойства различных реализаций. Гомоморфная свертка. Граф-машина и граф вычислительной системы. Сохранение временных режимов. Вопросы и задания.
§ 8.3. Регулярные и направленные графы...........................................................471
Итерационные процессы и регулярные графы. Расщепление бесконечного регулярного графа. Главный регулярный подграф. Критерий отсутствия контуров. Линейные развертки регулярного графа. Гомоморфная свертка регулярных графов. Вопросы и задания.
§ 8.4. Математические модели систолических массивов...................................482
Систолические массивы как вычислительные системы. Локальность управления. Минимальные коммуникационные связи. Реализация регулярных графов алгоритмов. Примеры построения систолических массивов для заданных алгоритмов. Вопросы и задания.
§ 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
Цена: 300руб.
