Введение
Глава 1. Место многоуровневой оптимизации в решении экстремальных большеразмерных задач на графах 22
1.1. Актуальные проблемы в процессах моделирования и проектирования сложных систем 24
1.2. Эволюция методов решения прикладных задач на графовых структурах 31
1.2.1. Точные методы решения графовых задач 31
1.2.2. Приближенные схемы решения графовых проблем 32
1.2.2. Эвристические методы на графах 36
1.3. Многоуровневая оптимизации для решения большеразмерных задач на графах 45
1.4. Итоги главы 1. Место многоуровневой оптимизации в решении экстремальных большеразмерных задач на графах 50
Глава 2. Математические модели и экстремальные задачи на графах 52
2.1. Обобщенная математическая модель 52
2.1.1. Исходные данные обобщенной модели 52
2.1.2. Решение обобщенной модели 53
2.1.3. Параметры и ограничения обобщенной модели 54
2.1.4. Сложность задачи выбора обобщенного решения 55
2.2. Оптимизационные задачи на графах в процессах физико-математического моделирования 56
2.2.1. Декомпозиция расчетных сеток в терминах задач разбиения графов 57
2.2.2. Задачи планирования конфликтующих вычислений и коммуникаций 67
2.2.3. Задачи упорядочения разреженных структур 70
2.2.4. Задачи балансировки вычислительных ресурсов на распределенных данных 80
2.3. Задачи проектирования электронных систем 86
2.3.1. Компоновка электронных схем 87
2.3.2. Планирование шин земли и питания 89
2.3.3. Размещение компонент электронных систем 90
2.3.4. Трассировка цепей электронных систем 93
2.8. Итоги главы 2. Математические модели и экстремальные задачи на графах 98
Глава 3. Концепция многоуровневого итерационного алгоритма 100
3.1. Общая концепция многоуровневого алгоритма 101
3.1.1. Традиционный многоуровневый алгоритм 101
3.1.2. Многоуровневый итерационный алгоритм 104
3.1.3. Концепция обобщенного многоуровневого алгоритма 107
3.2. Основные процедуры многоуровневого алгоритма 109
3.2.1. Методы построения огрубленных моделей 109
3.2.1. Редукция исходных данных 111
3.2.3. Поиск решений редуцированных задач 121
3.2.4. Восстановление решений
3.3.1. Адаптивный каркас многоуровневого алгоритма 130
3.3.2. Процесс создания многоуровневого алгоритма 134
3.4. Итоги главы 3. Концепция многоуровневого итерационного алгоритма 141
Глава 4. Реализация многоуровневых итерационных алгоритмов 143
4.1. Многоуровневые итерационные алгоритмы решения классических задач на графах 143
4.1.1. Многоуровневый итерационный алгоритм k-разбиения графа 144
4.1.2. Многоуровневый итерационный алгоритм раскраски графа 152
4.1.3. Многоуровневый итерационный алгоритм сужения ширины графа 161
4.1.4. Многоуровневый итерационный алгоритм коммивояжера. 169
4.2. Многоуровневые итерационная алгоритмы для решения прикладных задач на графах в процессах физико-математического моделирования 175
4.2.1. Многоуровневый алгоритм декомпозиции расчетной сетки 175
4.2.2. Многоуровневый алгоритм планирования конфликтующих процессов 183
4.2.3. Многоуровневый алгоритм упорядочения разреженных структур 183
4.2.4. Многоуровневый алгоритм балансировки декомпозиции расчетной сетки 187
4.2.5. Многоуровневый алгоритм архитектурно-зависимой декомпозиции сетки 191
4.3. Многоуровневые алгоритмы для решения прикладных задач на графах в процессах конструкторского проектирования электронных систем 197
4.3.1. Многоуровневый алгоритм компоновки интегральных схем 197
4.3.2. Многоуровневый алгоритм размещения компонент интегральных схем 197
4.3.3. Многоуровневый алгоритм трассировки цепей интегральных схем 205
4.3.4. Результаты испытаний многоуровневой схемы синтеза топологии интегральных схем 213
4.3.5. Многоуровневые технологии в конструкторском проектировании монтажных шкафов 214
4.4. Итоги главы 4. Реализация многоуровневых итерационных алгоритмов 216
Глава 5. Адаптация многоуровневых итерационных алгоритмов к современным высокопроизводительным вычислительным системам 218
5.1. Концепция построения параллельных многоуровневых алгоритмов на системах с общей и распределенной памятью 218
5.1.1. Графовые модели на системах с общей и распределенной памятью 218
5.1.2. Концепция гибридных многоуровневых схем для высокопроизводительных вычислительных систем 220
5.1.3. Технология параллельной редукции графа 222
5.2. Аспекты параллельной реализации многоуровневых итерационных алгоритмов декомпозиции 224
5.2.1. Параллельная рекурсивная бисекция графа 225
5.2.2. Параллельная локальная оптимизация на распределенных данных 226
5.2.3. Вычислительный эксперимент 228
5.3. Аспекты параллельной реализации многоуровневых итерационных алгоритмов упорядочения 230
5.3.1. Параллельная локальная оптимизация 230
5.3.2 Схема работы итерационного алгоритма на распределенных данных 233
5.3.3. Вычислительный эксперимент 234
5.4. Итоги главы 5. Адаптация многоуровневых итерационных алгоритмов к современным высокопроизводительным системам 236
Глава 6. Программная библиотека матруз и её приложения 237
6.1. Описание программной библиотеки МАТРУЗ 237
6.1.1. Структура библиотеки МАТРУЗ 237
6.1.2. Сборка библиотеки 242
6.1.3. Основные интерфейсы и функции библиотеки 243
6.1.3. Примеры использования библиотеки МАТРУЗ 250
6.2. Программное обеспечение используемое в процессах физико математического моделирования 252
6.2.1. Программное обеспечение для декомпозиции сеток 252
6.2.2. Программное обеспечение для решения задач планирования параллельных процессов 256
6.2.3. Программное обеспечение для упорядочения разреженных матриц 257
6.2.4. Программное обеспечение для решения задач балансировки 260
6.2.5. Результаты внедрения библиотеки МАТРУЗ в пакеты численного физико-математического моделирования 260
6.3. Программное обеспечение используемое в процессах моделирования и создания сложных систем 261
6.3.1. Программное обеспечение топологического синтеза интегральных схем 261
6.3.2. Программное обеспечение конструкторского проектирования монтажных шкафов 270
6.3.3. Программные системы, использующие функции МАТРУЗ при решении задач моделирования и планирования сложных процессов 273
6.4. Итоги главы 6. Программная библиотека МАТРУЗ и её приложения 282
Заключение 284
Литература
