В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления.

В октябре 2002 года в издательстве БХВ-Петербург вышла в свет книга
В.В.Воеводин, Вл.В.Воеводин "Параллельные вычисления"-СПб.: БХВ-Петербург, 2002.-608 с.: ил. (тираж - 3000 экземпляров).
ISBN 5-94157-160-7

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

В области параллельных вычислений данная монография является первой книгой, рекомендованной Министерством образования РФ в качестве учебного пособия для обучения по направлению "Прикладная математика и информатика".

Книга уже поступила в продажу и доступна во всех центральных книжных магазинах, а также в Интернет-магазинах, например Озон или Books.Ru.

Заказать книгу можно в отделе "книга-почтой" издательства "БХВ". Контактное лицо - Пименова Наталья, e-mail: trade@bhv.spb.su

Все вопросы, связанные с поставкой книги в Ваш город, магазин, университет, библиотеку и т.д. можно решить с коммерческим директором издательства "БХВ" Коноваловым Андреем Михайловичем, тел. (812) 541-8551, 541-8461, root@bhv.spb.su.

Книга издана при поддержке компании Hewlett-Packard.

---

Оглавление:

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

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

• Глава 1. Что скрывают обыкновенные компьютеры
  • 1.1. Немного об устройстве компьютера
    Представление информации. Общее устройство компьютера. Операции и операнды. Команды. Управление. Арифметико-логическое устройство. Память. Устройство ввода-вывода. Центральный процессор. Вопросы и задания.
  • 1.2. Операции с числами
    Двоичное представление чисел. Разряды. Фиксированная и плавающая запятая. Округление чисел. Ошибка округления. Сравнение представлений чисел. Вопросы и задания.
  • 1.3. Иерархия памяти
    Различные виды памяти. Время доступа. Виртуальная память. Влияние на время решения задачи. Трудности работы с медленной памятью. Вопросы и задания.
  • 1.4. Языки программирования и программы
    Языки низкого и высокого уровня. Проблемно ориентированные языки. Контроль эффективности программ. Компьютерная зависимость. Портабельность программ. Компиляторы и эффективность программ. Необходимость привлечения дополнительной информации. Вопросы и задания.
  • 1.5. Узкие места
    Иллюстративная модель компьютера. Пиковая и реальная производительность. Взаимодействие отдельных узлов компьютера. Эффективность. Узкие места. Вопросы и задания.
• Глава 2. Как повышают производительность компьютеров
  • 2.1. Усложнение и наращивание аппаратных средств
    Уменьшение размеров. Скалярная, конвейерная и параллельная обработка. Иерархия памяти. Опережающий просмотр команд. Локальность вычислений и использования данных. Примеры. Вопросы и задания.
  • 2.2. Повышение интеллектуальности управления компьютером
    Закон Мура. Спецпроцессоры. Суперскалярные и VLIW архитектуры. Коммутационные схемы. Топологии связей процессоров. SMP компьютеры. Архитектуры NUMA и ccNUMA. Развитие программного обеспечения. Примеры. Вопросы и задания.
  • 2.3. Система функциональных устройств
    Простые и конвейерные устройства. Стоимость работы. Загруженность. Пиковая и реальная производительность. Эффективность. Различные соотношения. Законы Амдала и Густавсона-Барсиса. Взаимосвязь законов. Вопросы и задания.
• Глава 3. Параллельные вычислительные системы
  • 3.1. Классификация параллельных компьютеров и систем
    Классификация Флинна, Хокни, Фенга, Хендлера, Шнайдера, Скилликорна. Взаимосвязь классификаций. Архитектура компьютеров и структура задач. Вопросы и задания.
  • 3.2. Векторно-конвейерные компьютеры
    Детальное рассмотрение компьютера Cray C90. Структура оперативной памяти. Регистровая структура. Функциональные устройства. Пиковая и реальная производительность. Вопросы и задания.
  • 3.3. Параллельные компьютеры с общей памятью
    Детальное рассмотрение компьютера HP Superdome. Ячейка компьютера. Локальные и удаленные ячейки. Процессор PA-8700. Работа с памятью. Вопросы и задания.
  • 3.4. Вычислительные системы с распределенной памятью
    Детальное рассмотрение компьютеров Cray T3D/T3E. Управляющие и вычислительные узлы. Процессорный элемент. Сетевой интерфейс. Сетевой маршрутизатор. Коммуникационная сеть. Память. Кластерные проекты. Вопросы и задания.
  • 3.5. Концепция GRID и метакомпьютинг
    Метакомпьютер как огромная распределенная система. Особенности распределения задач и передачи данных. Различные проекты. Концепция GRID. Проблемы пользователей. Вопросы и задания.
  • 3.6. Производительность параллельных компьютеров
    Сравнение вычислительных систем. Пиковая производительность и формат данных. Вычислительные и коммуникационные ядра. Тесты. Вопросы и задания.

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

• Глава 4. Большие задачи и параллельные вычисления
  • 4.1. Большие задачи и большие компьютеры
    Моделирование климатической системы. Обтекание летательных аппаратов. Математические модели и вычислительная техника. Огромные объемы вычислений и размеры памяти. Вопросы и задания
  • 4.2. Граф алгоритма и параллельные вычисления
    Порядок вычислений. Граф алгоритма. Параллельные формы графа. Ярус и высота. Инвариантность к ошибкам округления. Граф алгоритма и информационное ядро. Параметризация в графе. Вопросы и задания.
  • 4.3. Концепция неограниченного параллелизма
    Параллельные алгоритмы. Принцип сдваивания. Примеры алгоритмов малой высоты. Ограниченность концепции. Новые алгоритмы - новые свойства. Трудности в проблеме портабельности. Вопросы и задания.
  • 4.4. Внутренний параллелизм
    Преимущества внутреннего параллелизма. Примеры. Обнаружение новых свойств. Декомпозиция алгоритмов. Использование медленной памяти. Структура алгоритмов и программ. Вопросы и задания.
• Глава 5. Технологии параллельного программирования
  • 5.1. Использование традиционных последовательных языков
    Обилие средств параллельного программирования. Трудности применения. Необходимость дополнительной информации. Системы программирования Open MP, DVM, mpC. Примеры использования. Вопросы и задания.
  • 5.2. Системы программирования на основе передачи сообщений
    Системы параллельного программирования Линда, MPI, MPI-2. Интерфейсы для последовательных языков Фортран, Си, С++. Примеры использования. Вопросы и задания.
  • 5.3. Другие языки и системы программирования
    Т-система. Система программирования Норма. Приближенность к математическим записям. Примеры использования. Вопросы и задания.
• Глава 6. Тонкая информационная структура программ
  • 6.1. Графовые модели программ
    Информационная структура программы. Операционная и информационная связь. Графы управления, операционно-логической истории, информационный, истории реализации, зависимостей, влияния. Минимальные графы зависимостей. Снова граф алгоритма. Примеры графов. Вопросы и задания.
  • 6.2. Выбор класса программ
    Статический анализ структуры программ. Статистическая значимость отдельных операторов. Линейный класс программ. Вопросы и задания.
  • 6.3. Графы зависимостей и минимальные графы
    Опорные оператор, гнездо циклов, область. Пространства итераций. Лексикографический порядок. Типы зависимостей. Максимальный и минимальный графы зависимостей и их свойства. Теорема об информационном покрытии. Вопросы и задания.
  • 6.4. Простые и элементарные графы
    Простые и элементарные графы и программы. Расщепление минимальных графов на простые. Погружение минимального графа в объединение элементарных. Сведение к анализу элементарных программ. Вопросы и задания.
  • 6.5. Лексикографический порядок и L-свойство матриц
    Лексикографический максимум в многограннике. L-свойство матриц. Критерий лексикографического максимума. Дополнительные свойства матриц с L-свойством. Вопросы и задания.
  • 6.6. Построение минимальных графов зависимостей
    Основная задача. Конструктивные алгоритмы построения элементарных, простых и минимальных графов зависимостей для программ из линейного класса. Вопросы и задания.
  • 6.7. Циклы ParDO и избыточные вычисления
    Лексикографически правильные графы. Параллельные множества. Параллельная структура программ. Критерий цикла ParDO. Избыточные вычисления и критерий их обнаружения. Вопросы и задания.
  • 6.8. Примеры
    Формализованное построение графов алгоритмов для конкретных программ. Сложнейшие графы алгоритмов для простейших программ. Зависимость параллельной структуры от порядка выполнения операций.
• Глава 7. Эквивалентные преобразования программ
  • 7.1. Развертки графа
    Строгая и обобщенная развертки. Свойства разверток. Развертки и параллельные множества. Конструктивный алгоритм построения кусочно-линейных разверток. Выделение в графах строгих и не строгих зависимостей. Вопросы и задания.
  • 7.2. Макрографы зависимостей
    Макровершины и макродуги. Укрупненное представление зависимостей. Развертки и декомпозиция алгоритмов. Распределенные вычисления. Работа с медленной памятью. Вопросы и задания.
  • 7.3. Эквивалентные программы
    Эквивалентные преобразования программ. Эквивалентные по вычислениям программы. Преобразования, гарантирующие эквивалентность. Вопросы и задания.
  • 7.4. Наиболее распространенные преобразования
    Перестановка циклов. Слияние циклов. Переупорядочивание операторов. Распределение цикла. Скашивание цикла. Расщепление пространства итераций. Выполнение итераций цикла в обратном порядке. Треугольные преобразования. Вопросы и задания.
  • 7.5. Две сопутствующие задачи
    Оценивание длины критического пути графа зависимостей. Распределение массивов по модулям памяти.
  • 7.6. Примеры
    Формализованное построение разверток и макрографов для конкретных программ. Определение циклов ParDO. Распределение массивов по модулям памяти. Эквивалентное преобразование подпрограммы OLDA из пакета тестов Perfect Club Benchmarks. Самые лучшие результаты. Система V-Ray.

Часть 3. Смежные проблемы и применение

• Глава 8. Вычислительные системы и алгоритмы
  • 8.1. Расширение и уточнение линейного класса
    Прямая подстановка. Вычисляемый цикл go to. Вычисляемые ветвления. Нелинейные индексные выражения. Уточнение описания внешних переменных. Подпрограммы и функции. Функции min и max. Прямое вычисление графов. Вопросы и задания.
  • 8.2. Граф-машина
    Локальность управления. Свойства различных реализаций. Гомоморфная свертка. Граф-машина и граф вычислительной системы. Сохранение временных режимов. Вопросы и задания.
  • 8.3. Регулярные и направленные графы
    Итерационные процессы и регулярные графы. Расщепление бесконечного регулярного графа. Главный регулярный подграф. Критерий отсутствия контуров. Линейные развертки регулярного графа. Гомоморфная свертка регулярных графов. Вопросы и задания.
  • 8.4. Математические модели систолических массивов
    Систолические массивы как вычислительные системы. Локальность управления. Минимальные коммуникационные связи. Реализация регулярных графов алгоритмов. Примеры построения систолических массивов для заданных алгоритмов. Вопросы и задания.
  • 8.5. Математическая модель алгебраического вычислителя
    Структура алгебраических задач. Спецпроцессор для алгебраических задач. Использование систолического массива для матричной операции A + BC. Вопросы и задания
  • 8.6. Матрицы и структура алгоритмов
    Общие вычислительные процессы. Вариационная матрица алгоритма. Матрицы смежностей и инциденций. Критерий развертки. Уравновешенные графы. Критерий уравновешенности. Вопросы и задания.
  • 8.7. Новое применение сведений о структуре
    Восстановление линейного функционала. Быстрое вычисление градиента. Анализ ошибок округления. Всюду вариационная матрица алгоритма. Вопросы и задания.
• Глава 9. Пользователь в среде параллелизма
  • 9.1. Типичные ситуации в вопросах и ответах
    Конкретные вопросы из практики параллельного программирования. Исследование возникших ситуаций. Возможные идеи и пути решения. Что следует из перечисленных примеров? Вопросы и задания.
  • 9.2. Программный сервис в параллельных вычислениях
    Почему в программе что-то не так? Компиляторы, отладчики, профилировщики, анализаторы, конверторы. Система V-Ray. Статические и динамические характеристики параллельных программ. Анализ структуры программ. Графовые структуры программ на практике. Вопросы и задания.
  • 9.3. Организационная поддержка пользователя
    Инфраструктура поддержки работы пользователей. Информационно-аналитический Центр по параллельным вычислениям Parallel.ru. Вопросы и задания.

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

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

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

---

© Лаборатория Параллельных информационных технологий НИВЦ МГУ