| Глава 1. Введение | 11 |
| |
| 1.1. Современный компьютер — инструмент параллельной обработки данных | 11 |
| 1.2. Области применения многопроцессорных систем | 16 |
| 1.3. Рассматриваемые параллельные архитектуры | 19 |
| 1.4. Пример параллельного алгоритма | 20 |
 1.4.1. Последовательный рекурсивный алгоритм | 21 |
| 1.4.2. Параллельный рекурсивный алгоритм | 21 |
| 1.4.3. Последовательное вычисление членов ряда | 22 |
| 1.4.4. Последовательный матричный алгоритм | 23 |
| 1.4.5. Параллельный матричный алгоритм | 24 |
| |
| Глава 2. Основные понятия | 28 |
| |
| 2.1. Параллельная программа как ансамбль взаимодействующих |
| последовательных процессов | 28 |
| 2.2. Внутренний параллелизм | 29 |
| 2.2.1. Сложение многоразрядных чисел | 30 |
| 2.3. Ускорение и эффективность параллельных алгоритмов | 38 |
| 2.4. Ускорение и эффективность относительно наилучшего |
| последовательного алгоритма | 41 |
| 2.4.1. Неравноправность условий выполнения — первая причина |
| сверхлинейного ускорения | 43 |
| 2.4.2. Алгоритмическая причина сверхлинейного ускорения | 44 |
| 2.4.3. Формальное преобразование параллельного алгоритма |
| в «наилучший» последовательный | 47 |
| 2.5. Априорная оценка эффективности параллельного алгоритма | 49 |
| |
| Глава 3. Модели параллельных программ | 53 |
| |
| 3.1. Вычислительные системы с распределённой памятью | 54 |
| 3.2. Вычислительные системы с общей памятью | 56 |
| 3.3. Гибридные архитектуры | 58 |
| 3.4. Модель выполнения параллельной программы на распределённой |
| памяти | 59 |
| 3.5. Модель выполнения параллельной программы на обшей памяти | 60 |
| 3.6. Средства взаимодействия последовательных процессов | 62 |
| 3.6.1. Свойства канала передачи данных | 62 |
| 3.6.2. Методы передачи данных | 63 |
| 3.6.3. Семафор | 72 |
| 3.6.4. Барьерная синхронизация | 75 |
| |
| Глава 4. Базовые параллельные методы | 77 |
| |
| 4.1. Метод сдваивания | 78 |
| 4.1.1. Быстрый алгоритм выбора частичных сумм | 84 |
| 4.1.2. Барьерная синхронизация на основе синхронных обменов | 86 |
| 4.1.3. Стена Фокса | 88 |
| 4.2. Метод геометрического параллелизма | 88 |
| 4.3. Метод конвейерного параллелизма | 98 |
| 4.4. Метод коллективного решения | 107 |
| 4.5. Причины потери эффективности | 114 |
| |
| Глава 5. Сортировка данных | 117 |
| |
| 5.1. Постановка задачи | 117 |
| 5.2. Последовательные алгоритмы сортировки | 120 |
| 5.2.1. Быстрая сортировка (runtime qsort, wsort) | 123 |
| 5.2.2. Простое двухпутевое слияние (dsort) и слияние списков |
| (lsort) | 124 |
| 5.2.3. Пирамидальная сортировка (hsort) | 126 |
| 5.3 Свойства последовательных алгоритмов | 128 |
| 5.3.1. Сортировка методом простого двухпутевого слияния | 128 |
| 5.3.2. Пирамидальная сортировка | 135 |
| 5.3.3. Наилучший последовательный алгоритм сортировки dhsort | 139 |
| 5.4. Масштабируемые алгоритмы сортировки | 141 |
| 5.4.1. Сети сортировки | 141 |
| 5.4.2. Сеть чётно-нечётной сортировки | 144 |
| 5.4.3. Сеть обменной сортировки со слиянием Бэтчера | 145 |
| 5.4.4. Сортировка больших массивов | 150 |
| 5.4.5. Сравнение алгоритмов сортировки | 153 |
| 5.5. Результаты численных экспериментов | 157 |
| |
| Глава 6. Генерация псевдослучайных чисел | 161 |
| |
| 6.1. Требования к генераторам псевдослучайных чисел для МВС | 162 |
| 6.2. Линейно-конгруэнтные генераторы | 168 |
| 6.3. M-последовательности | 170 |
| 6.4. Проверка примитивности полиномов | 176 |
| 6.5. Тестирование генераторов | 177 |
| |
| Глава 7. Декомпозиция сеточных графов | 180 |
| |
| 7.1. Пример двумерной сетки | 180 |
| 7.2. Критерии декомпозиции графов | 182 |
| 7.2.1. Критерий 1: классический критерий декомпозиции графа | 183 |
| 7.2.2. Критерий 2: выделение обособленных доменов | 184 |
| 7.2.3. Критерий 3: минимизация максимальной степени домена | 185 |
| 7.2.4. Критерий 4: обеспечение связности графов каждого |
| из доменов | 186 |
| 7.3. Декомпозиция на основе исходной нумерации узлов | 189 |
| 7.4. Рекурсивная бисекция | 191 |
| 7.5. Декомпозиция регулярных графов | 192 |
| 7.6. Методы декомпозиции произвольных графов | 196 |
| 7.6.1. Иерархическая декомпозиция | 196 |
| 7.6.2. Спектральная бисекция | 205 |
| 7.6.3. Алгоритм инкрементного роста | 210 |
| 7.7. Декомпозиция больших сеток | 217 |
| 7.7.1. Координатная рекурсивная бисекция | 218 |
| 7.7.2. Двухуровневая стратегия обработки и хранения сеток | 220 |
| |
| Глава 8. Динамическая балансировка загрузки процессоров | 223 |
| |
| 8.1. Стратегии балансировки загрузки | 223 |
| 8.2. Метод диффузной балансировки | 224 |
| 8.3. Моделирование горения метанового факела | 229 |
| 8.3.1. Постановка задачи динамической балансировки | 235 |
| 8.3.2. Алгоритм серверного параллелизма | 236 |
| 8.4. Адаптивное интегрирование | 248 |
| 8.4.1. Последовательные алгоритмы | 249 |
| 8.4.2. Параллельные алгоритмы | 256 |
| |
| Глава 9. Визуализация сеточных данных | 278 |
| |
| 9.1. Клиент-серверная технология | 280 |
| 9.2. Online или Offline-визуализация: плюсы и минусы | 281 |
| 9.2.1. Online-визуализация Offline-визуализация | 281 |
| 9.3. Этапы визуализации | 285 |
| 9.4. Визуализация изоповерхностей | 290 |
| 9.4.1. Аппроксимация изоповерхности | 293 |
| 9.4.2. Виды данных, описывающих триангуляцию | 296 |
| 9.4.3. Метод редукции | 299 |
| 9.4.4. Заполняющие пространство триангуляции | 302 |
| 9.4.5. Параллельные алгоритмы построения аппроксимирующих |
| триангуляций | 303 |
| 9.4.6. Многоуровневое огрубление больших сеток | 304 |
| 9.4.7. Примеры визуализации | 306 |
| 9.5. Ввод-вывод сеточных данных | 308 |
| 9.5.1. Соотношение времени чтения данных и времени их обработки | 308 |
| 9.5.2. Распределённый ввод-вывод | 309 |
| 9.5.3. Огрубление и сжатие скалярных сеточных функций | 310 |
| |
| Список ссылок | 317 |
| Предметный указатель | 323 |
