Введение
Глава 1 Проблема архитектурно-зависимой декомпозиции графа данных программы и ее место в области высокопроизводительных вычислений 18
1.1. Проблемы управления данными параллельной программы в высокопроизводительной вычислительной среде 18
1.2. Содержательная постановка задачи архитектурно-зависимой декомпозиции
1.2.1. Граф данных параллельной программы 22
1.2.2. Архитектура вычислительной сети 25
1.2.3. Проблема архитектурно-зависимой декомпозиции графа данных программы 28
1.3. Задачи и методы их решения в проблематике повышения эффективности высокопроизводительных вычислений 29
1.3.1. Задачи, связанные с повышением эффективности высокопроизводительных вычислений 29
1.3.2. Методы решения задач, связанных с повышением эффективности высокопроизводительных вычислений 31
1.4. Итоги главы 1 43
Глава 2 Формализация задачи архитектурно-зависимой декомпозиции 44
2.1. Обобщенная математическая модель архитектурно-зависимой декомпозиции 44
2.1.1. Графовая модель исходной структуры данных параллельной программы 44
2.1.2. Гиперграфовая модель структуры вычислительной сети 45
2.1.3. Матричное представление структуры вычислительной сети 48
2.1.4. Пространство решений задачи архитектурно-зависимой декомпозиции 48
2.2. Критерии задачи архитектурно-зависимой декомпозиции 50
2.2.1. Балансировка загрузки вычислительных ресурсов 50
2.2.2. Минимизация загрузки коммуникационной среды 51
2.3. Частные случаи задачи архитектурно-зависимой декомпозиции 52
2.3.1. Задачи разбиения графа 52
2.3.2. Задачи о назначениях 53
2.4. Итоги главы 2 56
Глава 3 Многоуровневые методы архитектурно-зависимой декомпозиции 57
3.1. Многоуровневая схема решения задачи АЗД 57
3.2. Метод редукции исходной задачи к квадратичной задаче о назначениях
3.2.1. Группировка элементов задачи методом решения задачи разбиение графа 60
3.2.2. Технология перехода к квадратичной задачи о назначениях 61
3.2.3. Многоуровневый метод снижения размерности квадратичной задачи о назначениях 62
3.3. Алгоритмы решения квадратичной задачи о назначениях 63
3.3.1. Алгоритм ветвей и границ 64
3.3.2. Гибридный генетический алгоритм на порядковом представлении решений 71
3.3.3. Улучшающий гибридный генетический алгоритм на бинарном представлении решений.. 77
3.4. Восстановление решений задач архитектурно-зависимой декомпозиции 83
3.4.1. Проекция решения редуцированной задачи в пространство решений исходной задачи 83
3.4.2. Уточнение решения методом локальной оптимизации 85
3.5. Итоги главы 3 88
Глава 4 Программная реализация, её апробация и эксплуатация 90
4.1. Аспекты программной реализации системы архитектурно-зависимой декомпозиции 90
4.1.1. Программная модель исходных данных задачи 90
4.1.2. Основные программные интерфейсы 92
4.1.3. Примеры использования системы для решения задач архитектурно-зависимой декомпозиции 94
4.2. Тестовые задачи и вычислительный эксперимент 95
4.2.1. Тестовые задачи 95
4.2.1.1. Тестовые исходные данные в терминах квадратичной задачи о назначениях 96
4.2.1.2. Тестовые исходные данные для задачи архитектурно-зависимой декомпозиции 96
4.2.2. Вычислительный эксперимент 100
4.2.2.1. Сравнение алгоритмов решения редуцированных задач 100
4.2.2.2. Настройка алгоритмов и выбор режимов работы 114
4.2.2.3. Апробация многоуровневого алгоритма 121
4.2.2.4. Выводы 123
4.3. Особенности эксплуатации программы архитектурно-зависимой декомпозиции 123
4.3.1. Проблема эффективного извлечения исходных данных 123
4.3.2. Иерархическое представление архитектуры вычислительной системы 125
4.4. Итоги главы 4 127
Заключение 127
Литература 129
