Введение
ГЛАВА 1. Анализ реализуемости итерационных алгоритмов на параллельных вычислительных системах 9
1.1 Понятие итерационных алгоритмов 9
1.2 Анализ параллельных алгоритмов 11
1.3 Классификация параллельных итерационных алгоритмов 13
1.3.1 Алгоритм с синхронными итерациями и коммуникациями 14
1.3.2 Алгоритм с синхронными итерациями и асинхронными коммуникациями ,15
1.3.3 Алгоритм с асинхронными итерациями и коммуникациями 16
1.4 Параллельные асинхронные итерационные алгоритмы 17
1.5 Проблема переносимости прикладных программ в среде параллельных ЭВМ 20
1.5.1 Прикладные задачи, требующие больших компьютерных ресурсов 21
1.5.2 Основные виды суперкомпьютерных сред 21
1.5.3 Стандартизованное описание супер-ЭВМ среды 23
1.5.4 Особенности функционирования программ на аппаратных платформах MIMD 25
1.6 Современные среды параллельного программирования 28
1.6.1 Средства коммуникации для систем с распределенной памятью 28
1.6.2 MPI 29
1.6.3 PVM 30
1.7 Выводы 32
ГЛАВА 2. Распараллеливание программ для многопроцессорных вычислительных систем с распределенной памятью 33
2.1 Архитектура высокопроизводительных ЭВМ 33
2.1.1 SIMD - суперЭВМ 33
2.1.2 Многопроцессорные ЭВМ 36
2.1.2.1 Массивно-параллельные ЭВМ с распределенной памятью 37
2.1.2.2 Параллельные компьютеры с общей памятью 38
2.1.2.3 Векторно-конвейерные ЭВМ 38
2.1.2.4 Многопроцессорные ЭВМ с архитектурой комбинированного типа... 39
2.2 Методы распараллеливания программ 40
2.2.1 Ручное распараллеливание 40
2.2.2 Полуавтоматическое распараллеливание 43
2.2.3 Автоматическое распараллеливание 43
2.3 Основные проблемы управления параллелизмом на кластере 44
2.3.1 Параллельные программы на основе SPMD 44
2.3.2 Кластеры рабочих станции 47
2.3.3 Выполнение параллельных SPMD программ на кластерах 49
2.3.4 Проблемы управления параллелизмом 54
2.4 Высокая производительность коммуникаций 55
2.4.1 Myrinet 55
2.4.2 SCI 56
2.4.3 QSNET 56
2.5 Отношение стоимости вычислений и коммуникаций 57
2.6 Накладные расходы на поддержание параллелизма 61
2.6.1 Накладные расходы на коммуникацию 61
2.6.2 Накладные расходы на синхронизацию 63
2.7 Выводы 64
ГЛАВА 3. Анализ методов распределения вычислительной нагрузки при решении оптимизационных задач 66
3.1 Распределение задач при параллельных вычислениях 66
3.1.1 Количество подзадач 67
3.1.2 Количество процессоров и время вычисления 67
3.2 Способы распределения вычислительной нагрузки 68
3.2.1 Порядок распределения нагрузки 69
3.3 Постановка задачи квадратичного назначения 70
3.3.1 Классификация алгоритмов размещения 73
3.3.2 Итерационные алгоритмы улучшения размещения 74
3.4 Решение задачи квадратичного назначения на параллельной платформе
75
3.4.1 Методы распределения нагрузки при решении задачи квадратичного назначения 76
3.4.2 Ускорение генерации случайного вектора 79
3.5 Выводы 86
CLASS ГЛАВА 4. Результаты экспериментальных исследований и испытаний CLASS 88
4.1 Решение задачи квадратичного назначения на кластере 88
4.1.1 Архитектура экспериментальных систем 88
4.1.2 Параметры системы 91
4.1.3 Механизм распределения нагрузки для задачи квадратичного назначения 92
4.2 Результаты последовательного решения тестовой задачи 92
4.2.1 Алгоритм случайного поиска 93
4.2.2 Алгоритмы парных перестановок 104
4.2.3 Алгоритмы групповых перестановок 107
4.3 Параллельные алгоритмы решения оптимизационных задач 110
4.3.1 Параллельная реализация алгоритмов случайного поиска 112
4.3.2 Параллельная реализация алгоритма парных перестановок 113
4.3.3 Параллельная реализация алгоритма групповых перестановок 115
4.3.4 Эффективность параллельных алгоритмов 116
4.4 Выводы 117
Заключение 118
