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

Глава 1. Введение
1.1. Современный компьютер - инструмент
параллельной обработки данных
1.2. Области применения многопроцессорных
систем
1.3. Рассматриваемые параллельные архитектуры
1.4. Пример параллельного алгоритма
1.4.1. Последовательный рекурсивный алгоритм
1.4.2. Параллельный рекурсивный алгоритм
1.4.3. Последовательное вычисление членов ряда
1.4.4. Последовательный матричный алгоритм
1.4.5. Параллельный матричный алгоритм
Глава 2. Основные понятия
2.1. Параллельная программа как ансамбль
взаимодействующих последовательных процессов
2.2. Внутренний параллелизм
2.2.1. Сложение многоразрядных чисел
2.3. Ускорение и эффективность параллельных
алгоритмов
2.4. Ускорение и эффективность относительно
наилучшего последовательного алгоритма
2.4.1. Неравноправность условий выполнения -
первая причина сверхлинейного ускорения
2.4.2. Алгоритмическая причина сверхлинейного
ускорения
2.4.3. Формальное преобразование параллельного
алгоритма в "наилучший" последовательный
2.5. Априорная оценка эффективности
параллельного алгоритма
Глава 3. Модели параллельных программ
3.1. Вычислительные системы с распределенной
памятью
3.2. Вычислительные системы с общей памятью
3.3. Гибридные архитектуры
3.4. Модель выполнения параллельной программы
на распределенной памяти
3.5. Модель выполнения параллельной программы
на общей памяти
3.6. Средства взаимодействия последовательных
процессов
¦Д.6.1. Свойства канала передачи данных
3.6.2. Методы передачи данных
3.6.3. Семафор
3.6.4. Барьерная синхронизация
Глава 4. Базовые параллельные методы
4.1. Метод сдваивания
4.1.1. Быстрый алгоритм выбора частичных сумм
4.1.2. Барьерная синхронизация на основе
синхронных обменов
4.1.3. Стена Фокса
4.2. Метод геометрического параллелизма
4.3. Метод конвейерного параллелизма
4.4. Метод коллективного решения
4.5. Причины потери эффективности
Глава 5. Сортировка данных
5.1. Постановка задачи
5.2. Последовательные алгоритмы сортировки
5.2.1. Быстрая сортировка (runtime qsort, wsort)
5.2.2. Простое двухпутевое слияние (dsort)
и слияние списков (Isort)
5.2.3. Пирамидальная сортировка (hsort)
5.3 Свойства последовательных алгоритмов
5.3.1. Сортировка методом простого двухпутевого
слияния
5.3.2. Пирамидальная сортировка
5.3.3. Наилучший последовательный алгоритм
сортировки dhsort
5.4. Масштабируемые алгоритмы сортировки
5.4.1. Сети сортировки
5.4.2. Сеть четно-нечетной сортировки
5.4.3. Сеть обменной сортировки со слиянием
Бэтчера
5.4.4. Сортировка больших массивов
5.4.5. Сравнение алгоритмов сортировки
5.5. Результаты численных экспериментов
Глава 6. Генерация псевдослучайных чисел
6.1. Требования к генераторам псевдослучайных
чисел для МВС
6.2. Линейно-конгруэнтные генераторы
6.3. М-последовательности
6.4. Проверка примитивности полиномов
6.5. Тестирование генераторов
Глава 7. Декомпозиция сеточных графов
7.1. Пример двумерной сетки
7.2. Критерии декомпозиции графов
7.2.1. Критерий 1: классический критерий
декомпозиции графа
7.2.2. Критерий 2: выделение обособленных
доменов
7.2.3. Критерий 3: минимизация максимальной
степени домена
7.2.4. Критерий 4: обеспечение связности графов
каждого из доменов
7.3. Декомпозиция на основе исходной нумерации
узлов
7.4. Рекурсивная бисекция
7.5. Декомпозиция регулярных графов
7.6. Методы декомпозиции произвольных графов
7.6.1. Иерархическая декомпозиция
7.6.2. Спектральная бисекция
7.6.3. Алгоритм инкрементного роста
7.7. Декомпозиция больших сеток
7.7.1. Координатная рекурсивная бисекция
7.7.2. Двухуровневая стратегия обработки и
хранения сеток
Глава 8. Динамическая балансировка загрузки
процессоров
8.1. Стратегии балансировки загрузки
8.2. Метод диффузной балансировки
8.3. Моделирование горения метанового факела
8.3.1. Постановка задачи динамической
балансировки
8.3.2. Алгоритм серверного параллелизма
8.4. Адаптивное интегрирование
8.4.1. Последовательные алгоритмы
8.4.2. Параллельные алгоритмы
Глава 9. Визуализация сеточных данных
9.1. Клиент-серверная технология
9.2. Online или Offline-визуализация: плюсы и
минусы
9.2.1. Online-визуализация Offline-визуализация
9.3. Этапы визуализации
9.4. Визуализация изоповерхностей
9.4.1. Аппроксимация изоповерхности
9.4.2. Виды данных, описывающих триангуляцию
9.4.3. Метод редукции
9.4.4. Заполняющие пространство триангуляции
9.4.5. Параллельные алгоритмы построения
аппроксимирующих триангуляции
9.4.6. Многоуровневое огрубление больших сеток
9.4.7. Примеры визуализации
9.5. Ввод-вывод сеточных данных
9.5.1. Соотношение времени чтения данных и
времени их обработки
9.5.2. Распределенный ввод-вывод
9.5.3. Огрубление и сжатие скалярных сеточных
функций
Список ссылок
Предметный указатель