Введение
Глава 1. Обзор существующих архитектурных и программных платформ 11
1.1 Использование комбинаторных алгоритмов 11
1.2 Способы реализации алгоритмов 12
1.3 Существующие архитектуры параллельных компьютеров 16
1.3.1 SMP (Symmetric Multiprocessing) 17
1.3.2 МРР (Massive Parallel Processing) 19
1.3.3 NUMA (неоднородный доступ к памяти) 20
1.3.4 cc-NUMA (неоднородный доступ к памяти с поддержкой когерентности кэшей) 21
1.3.5 PVP (параллельно-векторные системы) 22
1.3.6 Кластеры 23
1.3.7 GRID (вычислительная сеть) 26
1.3.8 Выводы 27
1.4 Способы организации взаимодействия процессов 28
1.4.1 Стандарты 28
1.4.2 Технологии 33
1.4.3 Высокоуровневые средства разработки 34
1.4.4 Выводы 36
Выводы по главе 1 37
Глава 2. Создание высокоэффективных реализаций параллельных комбинаторных алгоритмов генерации комбинаторных объектов 39
2.1 Эффективная реализация параллельной генерации перестановок N-элементного множества 40
2.2 Эффективная реализация параллельной генерации всех подмножеств TV-элементного множества 48
2.3 Эффективная реализация параллельной генерации элементных подмножеств 56
2.4 Генерация комбинаторных объектов в гетерогенной кластерной среде 69
2.4.1 Учет производительности узлов кластера при распараллеливании алгоритма 70
2.4.2 Использование средств администрирования МРІ для балансировки вычислительной нагрузки 72
2.5 Вычислительный эксперимент. Генерация комбинаторных объектов в гетерогенной среде 75
2.6 Метаалгоритм генерации комбинаторных объектов 83
2.6.1 Фаза сбора данных 86
2.6.2 Эффективное распределение задач 88
2.6.3 Конструирование метаалгоритма управления распараллеливанием генерации комбинаторных объектов 90
Выводы по главе 2 93
Глава 3. Эффективные реализации параллельных алгоритмов на графах и матроидах 95
3.1 Эффективная реализация параллельного алгоритма Флойда 95
3.1.1 Метод распараллеливания 97
3.1.2 Вычисление оптимального кол-ва узлов для параллельного выполнения алгоритма Флойда 100
3.1.3 Вычислительный эксперимент 105
3.2 Эффективная реализация параллельного жадного алгоритма на матроидах 108
3.2.1 Метод распараллеливания 113
3.2.2 Вычисление оптимального количества узлов для параллельного выполнения жадного алгоритма на матричном матроиде 115
3.2.3 Вычислительный эксперимент 121
3.3 Выполнение параллельных алгоритмов Флойда и жадного алгоритма на матричном матроиде в гетерогенной кластерной среде 124
Выводы по главе 3 133
Глава 4. Библиотека параллельных реализаций комбинаторных алгоритмов 135
4.1 Общее назначение библиотеки 135
4.2 Требования, предъявляемые к библиотеке 135
4.3 Выбор языка реализации 138
4.4 Особенности проектирования и реализации программ в среде стандарта МИ и MPI-2 ..139
4.4.1 Программа конфигурирования гетерогенной кластерной среды с использованием средств MPI 140
4.4.2 Реализация метаалгоритма генерации комбинаторных объектов 141
4.4.3 Реализация распараллеливания алгоритма Флойда в среде MPI 153
4.4.4 Реализация распараллеливания жадного алгоритма на матричных матроидах в среде MPI 161
4.4.5 Тестирование реализаций параллельных алгоритмов 164
4.5 Общая структура библиотеки эффективных параллельных реализаций комбинаторных алгоритмов 167
Выводы по главе 4 180
Заключение 181
Литература
