Содержание к диссертации
Введение
Глава 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
Литература
- Приближенные схемы решения графовых проблем
- Декомпозиция расчетных сеток в терминах задач разбиения графов
- Концепция обобщенного многоуровневого алгоритма
- Многоуровневый итерационный алгоритм раскраски графа
Приближенные схемы решения графовых проблем
Проблемы принятия оптимальных и оптимально-компромиссных решений на графах требуют своего решения в различных сферах научной и практической деятельности человека. Общим в этих проблемах является математическая модель, основанная на графовых структурах, абстрагирующих объекты и системы предметной области. При этом основные трудности численного решения подобных задач связаны с большой размерностью, различного рода модельными ограничениями, обусловленными проблемной спецификой, а также видом оптимизируемой функции, которая на практике, как правило, оказывается многоэкстремальной. Нередко подобные задачи квалифицируются как NP-трудные, что в практической точки зрения означает возможность поиска точного решения только с использованием комбинаторных методов, которые в общем случае не исключают перебор всего множества допустимых решений задачи. В итоге гарантированные экспоненциальные затраты на поиск оптимальных решений определили вектор исследований прикладных математиков, связанный с развитием альтернативных подходов, способных находить практические пригодные решения, затрачивая при этом приемлемые вычислительные ресурсы.
Научно-технический и технологический прогресс в конце 20 и начале 21 века, бурная эволюция вычислительной техники придали мощный толчок к развитию новых приближенных и эвристических подходов к решению экстремальных задач на графовых структурах больших порядков. Графовые задачи, возникающие и требующие своего решения в таких областях, как численное физико-математическое моделирование, управление сложными процессами, конструкторское проектирование сложных устройств и систем эволюционируют в сторону увеличения размеров, детализации модельных абстракций, усложнения математических моделей и целевых функций. Эти изменения обусловлены в первую очередь практической необходимостью более точно и полно описывать явления, происходящие в проблемном домене.
В результате подобных процессов расширялась систематика графовых методов, развивались технологии и подходы к решению не только классических задач, но и практически значимых проблем. Подходы, которые с успехом справлялись с решением относительно небольших задач, естественным образом изымались из технологических и производственных процессов. Им на замену приходили новые методы, основанные на более эффективных принципах анализа сложных моделей. Качественный скачек в методах решения трудных графовых задач произошел с появлением так называемых гибридных схем, которые позволяли интегрировать в некоторую общую базовую структуру разные алгоритмы. Принципы, на основании которых формировались подобные схемы, базировались на наблюдаемых явлениях и установленных закономерностях в физических, биологических и социальных системах.
Однако в гонке с «проклятием размерности» эти методы уступили первенство принципиально новым многоуровневым подходам, которые основывали поиск решения на технологиях редукции (упрощения, огрубления) исходных данных задачи и рекурсивном переходе к новой более простой задаче или серии задач, для решения которых требуется значительно меньше вычислительных ресурсов чем для решения исходной. Многоуровневый алгоритм как и гибридная схема позволял с успехом эксплуатировать ранее полученные «решатели» более простых задач в своей структуре, обеспечивая необходимый компромисс между качеством генерируемых решений и накладными расходами, требующимися на их поиск.
На практике разработка и реализация многоуровневых алгоритмов оказалась далеко непростым делом, успех которого сильно зависит от массы субъективных факторов, включая наличие опыта исследователя в области дискретной оптимизации и целого спектра навыков в сфере информационных технологий. С другой стороны объективно математическая модель может оказаться непростой для ее исследования при помощи многоуровневой оптимизации. В результате многоуровневые алгоритмы, переживаемые уже более 20 лет период интенсивного развития, так и не достигли той степени популярности, как, например, алгоритмы основанные на эволюционно-популяционных принципах. В современных научных работах, посвященной многоуровневой оптимизации, практически не поднимаются вопросы, связанные с системным анализом в области разработки и реализации многоуровневых схем. Зачастую авторы приводят конечные результаты, не обсуждая технологию получения той или иной успешной стратегии редукции и эффективного восстановления решения исходной задачи. В открытой печати практически не раскрываются аспекты процесса создания и настройки многоуровневого алгоритма для решения той или иной классической задачи, не говоря уже а прикладных проблемах. Цель данной диссертационной работы состоит не только в развитии теории многоуровневой оптимизации, но и в создании методики практической реализации многоуровневых алгоритмов для решения сложных большеразмерных задач на графах.
В данной главе дается обзор ряда практически значимых задач на графах с учетом их прикладной специфики, приводится классификация методов сквозь эволюцию их развития, нацеленную на повышение эффективности экстремальных большеразмерных труднорешаемых задач. Обозначаются тенденции в становлении методов многоуровневой оптимизации. Формулируются цели и задачи исследования.
Мощный импульс к развитию математического моделирования как нового способа исследования теоретических и практических задач естествознания в конце XX в. обусловлен появлением электронно-вычислительных машин, способных производить арифметические и логические вычисления со скоростью, недоступной для человека. Необходимость в решении все более сложных актуальных научных, технических и организационных задач потребовала создания и обоснования математических моделей, отражающих основные закономерности исследуемых явлений, а также создания экономичных численных алгоритмов их решения. За почти трехсотлетнюю историю развития теории графов несколькими поколениями математиков исследованы актуальные графовые проблемы, созданы и развиты разнообразные методы их решения. За последние полвека реализован широкий спектр программных средств, в основе которых положены теоретические и практические результаты на графах. Все это в совокупности оказывало и оказывает в настоящее время значимое влияние на выбор математического аппарата при построении абстрактных моделей объектов, процессов и систем. Графовые структуры оказываются очень удобным инструментом для описания структур данных, различных видов связей, информационных потоков. Графы активно используются при описании сложных систем и процессов. Без них не обойтись, когда требуется наглядно представить зависимости в сложных технических объектах, при описании на разных уровнях моделей программных систем и разнообразных производственных процессов. Собственно содержание научного направления математического моделирования находится в тесном симбиозе с графами, включая весь процесс от разработки математических моделей и алгоритмов до создания комплексов и пакетов программ для решения классов задач, анализа результатов, вывода, хранения [97,122,123].
Стремление к описанию более полных математических моделей, способных адекватно описывать более сложные исследуемые процессы, разработка более точных и эффективных алгоритмов стимулировало развитие вычислительной техники. Это обеспечивалось не только за счет совершенствования элементной базы, но и главным образом за счет новых архитектур ЭВМ, использующих принципы многопроцессорности и параллельности вычислений. Без эволюции математических моделей и алгоритмов, которые являлись неотъемлемой частью маршрутов проектирования и процессов производства сложного электронного оборудования, прогресс в развитии высокопроизводительной вычислительной техники был бы невозможен. С другой стороны новые принципы организации вычислительных систем предопределяют новые требования к моделям и алгоритмам, вызывая тем самым очередной виток в эволюции инструментов математического моделирования. Научно-техническая эволюция породила тенденции к усложнению программных решений в области математического моделирования и проектирования сложных систем. В 90-е годы прошлого возникли устойчивые понятия CAD (с англ. Computer Aided Design), CAM (с англ. Computer Aided Manufacturing) и CAE (с англ. Computer Aided Engineering), описывавшие комплекс программных средств автоматизированного проектирования, подготовки производства и инженерных расчетов. В это период произошло становление стандартов, определивших требования к данным системам на два десятилетия [188].
Декомпозиция расчетных сеток в терминах задач разбиения графов
Главной особенностью динамической балансировки является требование, связанное с минимальными затратами на реализацию перехода от начальной к новой декомпозиции. Затраты, связанные на реализацию такого перехода зависят от структуры и распределения начальной декомпозиции по процессорам ВС, от коммуникационных свойств и топологических аспектов ВС, от структуры и распределения финальной декомпозиции. Кроме этого на практике имеют место неконтролируемые и непрогнозируемые явления, связанные состоянием компонент среды и протекающих в ВС процессов, которые в итоге могут оказывать значительное влияние на коммуникационные издержки.
В результате имеет смысл оперировать только обобщенными показателями, оказывающими влияние на продолжительность этапа реализации перехода к новой декомпозиции. Рассмотрим некоторые из них.
Для оценки времени реализации всей совокупности обменов Q.(f,f) можно воспользоваться интервальной моделью (2.14),(2.15). Нижняя граница (2.28) достигается, когда все обмены происходят одновременно и друг с другом не конфликтуют. Верхняя граница (2.29) Более точная оценка связана с оценкой времени работы тактовой схемы реализации системы транзакций Q.(f,f) в коммуникационной среде H(Y,A,p,r). Рассмотрим ее детально.
Задача построения расписания для системы конфликтующих транзакций в коммуникационной среде Для исходных данных задачи балансировки (G,#,/) и некоторого решения / однозначно определяется граф конфликтующих пересылок где Q = Q(/0,/) совокупность пересылок Q = т, с издержками ребер, связывающих конфликтующие пересылки (г/г ,иФ0 следует понимать как невозможность выполнить одновременно транзакции г/ и ju).
В результате задачу построения расписания для системы конфликтующих транзакций можно сформулировать в терминах задачи планирования конкурирующих пересылок в параллельных расчетах на распределенных данных (см. 2.3.2). Решения (ni5...Pm) задач (2.16), (2.17) можно использовать для оценки числа тактов (2.30) и обобщенных издержек (2.31) выполнения всех пересылок Q.
Задачи (2.30) и (2.31) обобщают класс задач нахождения хроматического числа графа, которые в свою очередь NP-трудны. Следует отметить, что декомпозиция системы транзакций Q на группы независимых транзакций (Q1,...,QJ естественно транслируется в синхронную модель параллельной программы - внешний цикл по группам /: = 1,т, для каждой группы Q. каждый процессор независимо от остальных реализует свои транзакции, ожидает завершения работы остальных процессоров и так далее пока не будет рассмотрены все группы.
Теоретически задачу построения расписания для системы конфликтующих транзакций в коммуникационной среде можно сформулировать в терминах планирования операций [117]. В такой модели решением является вектор, который указывает для каждой операции транзакции (межпроцессорная пересылка) время начала её выполнения. В итоге подобная модель предполагает асинхронную схему организации процедуры процесса межпроцессорных пересылок. Однако на сегодняшний день нет технической возможности обеспечить на программном уровне такую асинхронную схему работы программы, которая была бы адекватна найденному графику выполнения операций. В силу этого, подобные модели можно использовать для построения теоретических оценок, но практическое их использование для реализации расписания системы транзакций Q сопряжено с серьезными технологическим ограничениями.
Маршруты проектирования электронных систем представляют собой сложную многостадийную технологию, архитектура которой сильно зависят от технологического процесса производства, структуры изделия и функциональных, параметрических и других требований заказчика. Процесс разработки электронной системы начинается с подготовки требований и системной спецификации, включает этапы функционального и логического проектирования (для интегральных схем). Непосредственно перед производством следует этапы конструкторского (физического) и технологического проектирования. Если второй сосредоточен на возможности и способах изготовления изделия в заданных условиях, то первый характеризует структуру, расположение в пространстве и форму составных частей объекта.
Концепция обобщенного многоуровневого алгоритма
Многослойная трассировка цепей интегральной схемы имеет ряд нюансов. Рассмотрим их детальнее. Как и в случае общей задачей трассировки (2.37), (2.38), (2.39), (2.40) требуется построить систему непересекающихся связных трасс минимальной длины. Структура трассируемого пространства описывается так называемой сеткой трассировки, которая обеспечивает ортогональную прокладка всех трасс (под углами 90 градусов) строго по регулярной системе узлов. В ИС нередко при присутствует два (и более) слоя металлизации, которые служат для проведения трасс. Переход со слоя на слой осуществляется посредством контактных окон. Положение контактных окон не фиксировано и допускается в любом месте кристалла, за исключением областей запрета для металлизации. Области запрета с точки зрения общей модели задачи трассировки описываются через исключение соответствующих узлов из множества допустимых для металлизации узлов V. Для каждого слоя указывается приоритетное направление для трасс, которое в терминах модели выражается в виде функции u:E Z+, которая искусственно увеличивает длину ребер, направление которых не совпадает с приоритетным.
На практике при решении задач трассировки (особенно для интегральных схем субмикронными топологическими нормами) требуется учитывать множество физических эффектов, возникающих в металлических проводниках. Например, негативное влияние на качество сигнала в проводнике оказывают изломы металлической трассы, множественные переходы с слоя на слой; циклические конфигурации трассы генерируют магнитные помехи, которые отражаются на качестве сигнала трасс, пролегающих в соседних слоях. Учесть все физические эффекты в алгоритме трассировки зачастую просто невозможно. В силу этого данная задача решается в несколько этапов.
На первом этапе рассматривается задача глобальной трассировки. Его суть в огрублении коммутационной модели и переходе к более простой задаче. Вначале все трассируемое пространство разбивается на относительно крупные фрагменты (блоки, области, регионы) - главное условие чтобы в них были сосредоточены связные между собой элементы, в этом случае трассы в этих участках будут носить локальный характер. Далее относительно мелкими фрагментами (макродискреты) покрывают оставшиеся области сетки трассировки. Сетка макродискретов служит для реализации транзитных цепей между блоками. На этапе глобальной трассировки реализуются только транзитные цепи. Подобная технология допускает сокрытие той части исходной сетки трассировки, которая соответствует блокам, тем самым уменьшая размер задачи. Рассматриваема общая модель трассировки естественно вписывается в этап глобальной трассировки и может быть использована при решении проблемы трассировки транзитных цепей.
На втором этапе рассматривается задача детальной трассировки. Задача этого этапа реализовать трассы, локализованные в рамках блоков. При этом данная проблема также естественно формулируется в терминах общей модели трассировки.
На третьем этапе проводится анализ построенных трасс, выявляются и оцениваются негативные эффекты, связанные с физическими явлениями в проводниках со сложной геометрией. Затем проблемные трассы корректируются или принимается решение о перетрассировке отдельного участка.
Как уже отмечалось проектирование радиоэлектронной системы из функционально законченных блоков (типовых блоков) предполагает решение задач компоновки, размещения и трассировки. Задача компоновки заключается в распределении типовых блоков по монтажным шкафам. В задаче размещения требуется найти такое расположение типовых блоков в пространстве монтажного шкафа. К типовым блокам внутри монтажного шкафа подходит множество кабелей. Одни кабели подводят питание, другие являются заземляющими. Есть кабели, которые связывают блоки, расположенные в пространстве одного монтажного шкафа, а есть которые связывают блоки с клеммами внешней шины. Если не прикладывать никаких усилий по прокладке кабелей внутри монтажного шкафа, то получится паутина из электрических соединений, которая не позволит ни получить доступ к типовым блокам, ни устранить проблему влияние помех, исходящих от силовых кабелей внутри шкафа. Для компактной и аккуратной прокладки кабелей применяются кабельные каналы – это полые короба с регулярной структурой отверстий. Предварительная топология расположения коробов и их габариты проектируется на предыдущих этапах. Задача трассировки (трехмерной трассировки) заключается в нахождении трасс кабелей по кабельным каналам в пространстве монтажного шкафа. Требуется, во-первых, минимизировать влияние помех, исходящих от силовых кабелей, во-вторых, минимизировать суммарную длину соединений. В задаче имеется одно ограничение, связанное с заполненностью кабельных каналов: кабели могут входить в кабельный канал в любое регулярное отверстие, но пиковая загрузка по длине кабельного канала по возможности не должна превышать определенного порога - максимальное количество кабелей, проходящих через сечение короба.
Задача трассировки особенно остро встает в случае вывода на лицевую сторону монтажного шкафа множества индикаторов, общее число которых может достигать несколько сотен. В этом случае порядок общего числа кабелей может исчисляться тысячами.
Сформулируем проблему трассировки кабелей монтажного шкафа в терминах общей задачи трассировки (2.37), (2.38), (2.39), (2.40). Для этого внутренне пространство всей системы коробов покроем регулярной сеткой с шагом в диаметр типового кабеля и = const. В результате построенная сетка будет соответствовать графу G(V,E,w,u) структуры трассируемого пространства. Зная координаты коннекторов и клемм размещенного оборудования монтажного шкафа можно их отождествить по некоторому правилу с узлом регулярной сетки. Например, выбирать ближайший незанятый узел.
Многоуровневый итерационный алгоритм раскраски графа
Для решения задачи динамической балансировки предлагается следующая схема решения (см. рис. 4.17). На этапе 1 формируется орграф для потоковой балансирующей модели (см. 4.2.1) и решается задача поиска максимального балансирующего потока. При отсутствии требований на связную декомпозицию (2.6),(2.9) или (2.10) число пограничных слоев, которое допустимо переносить из доменов исходного разбиения, может быть произвольным. Решение потоковой задачи описывается в виде списка трансферов {т15...,тД где каждый трансфер определяет тройку ti=(ii,Ji,yVj), где /,ЄЇД показывает номер домена декомпозиции источника вершин для переноса в трансфере tl; j) є\,к соответствует номеру домена декомпозиции получателя вершин для переноса tl; w: є N - суммарный вес вершин для переноса tl. В принципе последовательная реализация топологически отсортированных пересылок {т1,...,тг} от "исток" до "стока" позволит в итоге получить сбалансированную декомпозицию. Однако затраты на такой переход от исходной к новой декомпозиции могут оказаться значительными, так как не предполагают параллельности в её реализации. Для сокращения подобных издержек, формализованных в виде критериев (2.30) и (2.31), предназначен этап 2.
На этапе 2 для списка трансферов {т,,...,тг} формируется граф конфликтующих пересылок (вершины пересылки, а ребра конфликты) и решается задача нахождения правильной вершинной раскраски с лексикографической сверткой критериев ((2.16),(2.17)). Для решения этой задачи используется многоуровневый алгоритм планирования конкурирующих процессов (см. 4.2.2). Результатом работы алгоритмов на этапе 2 есть классы независимых трансферов
Цель такого переноса - получить сечение между доменами il и j) с минимальным сечением (см. рис. 4.18). В результате эта задача также может быть сформулирована в терминах задачи (2.4),(2.5) 2-разбиения графа, который получается как подграф исходного графа G, индуцированный множеством Vh LJ Vh. Для решения данной задачи можно использовать многоуровневый итерационный алгоритма -разбиения графа (см. 4.1.1). Последний этап 4 предназначен для физического переноса данных между процессорами.
Этапы от 1 до 4 могут выполняться в общем цикле (см. рис. 4.17, отмечен пунктиром), каждый такой цикл будем называть итерацией алгоритма динамической балансировки.
Предлагаемый алгоритм балансировки, будем называть BALANCE, апробировался на тестовых данных, сформированных из реальных задач физико-математического моделирования в РФЯЦ-ВНИИЭФ. В таблице 4.13 приведены описания 5 задач. Начальная декомпозиция (на 20 и на 100 подграфов) графов 800835.graph и 515.sarov формировалась исходя из предположения, что веса всех вершин и ребер графа равны единице. Балансировка осуществлялась в условиях изменения весов вершин, что моделируется файлами .weights.
Тестовые задачи решались с варьируемыми настройками: число многоуровневых итераций алгоритма 2-разбиения графа; общее число итераций цикла балансировки. В сводной таблице 4.14 представлены на примере задачи 3 результаты, которые отражают типовую картину. С ростом числа итераций (как для общих, та и для MLI) пропорционально возрастают временные издержки алгоритма. Но при этом сечение (2.5) и общий объём пересылок (2.27) заметно уменьшаются с ростом итераций MLI, и не в целом не меняются с ростом общих итераций. Дисбаланс и число тактов пересылок (2.30) напротив уменьшаются с ростом общих итераций, и слабо зависят от числа итераций MLI.
В следующей таблице 4.15 приведены результаты решения всех тестовых задач. Алгоритм BALANCE имел следующие параметры: общие итераций осуществлялись до достижения оптимального баланса (результаты каждой итерации фиксировались в таблице), число итераций MLI для алгоритма бисекции выбрано 10.
Результаты, представленные в таблице 4.15 демонстрируют, что на алгоритм балансировки в зависимости от степени разбалансированности решения требует от 2 до 3 общих итераций. При этом академическая реализация алгоритма BALANCE на языке C# при решении тестовых задач потребляла не больше 15 секунд на одну итерацию. В задачах архитектурно-зависимой декомпозиции расчетной сетки домены декомпозиции ассоциируются конкретным процессорам. В задаче требуется распределить узлы сетку по k доменам с учетом их производительности соответствующих процессоров (2.4) или (2.7) и (2.8), с учетом коммутационных показателей и структуры топологии ВС (2.14) и (2.15).
С практической точки зрения интересны два частных случая этой задачи. Первый случай, когда имеет место гомогенная вычислительная система с равномощными процессорами и одинаковыми затратами на передачу данных между любой парой вычислителей:
При этом задачу архитектурно-зависимой декомпозиции можно сформулировать в терминах задачи сбалансированного -разбиения графа - требуется распределить параллельные части программы по к равновзвешенным подграфам (соответствуют процессорам) так, чтобы связи между подграфами были минимальные.
Другой частный случай имеет место, когда число частей параллельной программы и число вычислителей одинаково, при этом процессоры равномощны, но затраты на передачу данных различаются: п = к; P = 1,T(i,i) = 0,Vi = 1,tT(i,i) 0,ViJ = 1J, іФ]. Тогда требования (2.7) и (2.8) сбалансированной загрузки вычислителей вырождаются в требование взаимно-однозначного соответствия между частями параллельной программы и процессорами, и общая задача архитектурно-зависимой декомпозиции формулируется в терминах размещения распределенных данных по узлам топологии ВС (см. 2.2.3.4), которая в свою очередь формулируется в терминах (2.24),(2.25) квадратичной задачи о назначениях.
С учетом описанных выше двух частных случаев предлагается эвристическая технология решения общей задачи, основанная на концепции многоуровневости. Основная идея состоит в том, что на первом этапе (см.рис. 4.19) производится сбалансированное -разбиение (2.4),(2.5) графа параллельной программы, где к - количество процессоров. Решение этой частной задачи группирует элементы графа параллельной программы по доменам. Такая группировка минимизирует связи между доменами разбиения и тем самым локализует интенсивные обмены данными в рамках одного процессора. На втором этапе решается одна из задач размещения (назначения) распределенных данных по узлам топологии ВС (2.24) или (2.25). Цель алгоритмов решения этой задачи состоит в попытке отобразить связанные друг с другом домены на "близкие" процессоры в рамках физической топологии вычислительной сети, тем самым снижая обобщенные издержки на межпроцессорные коммуникации. На первом и втором этапах не учитывался такой аспект вычислительных систем, как различная производительность вычислительных узлов. В результате синтезированное решение задачи отображения графа может не удовлетворять ограничению (2.4), и третий этап предназначен для балансировки найденного решения задачи отображения графа.