автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка и реализация многоуровневых алгоритмов декомпозиции гиперграфовых моделей

На правах рукописи

и0344СЬ 1Ь

ФНЛИМОНОВ АНДРЕЙ ВИКТОРОВИЧ

РАЗРАБОТКА И РЕАЛИЗАЦИЯ МНОГОУРОВНЕВЫХ АЛГОРИТМОВ ДЕКОМПОЗИЦИИ ГИПЕРГРАФОВЫХ МОДЕЛЕЙ

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Н.Новгород 2 2 СЕН 2008

2008

003446515

Работа выполнена в Федеральном Агентстве по Образованию «Нижсго-родский Государственный Университет им. Н.И.Лобачевского»

Научный руководитель доктор технических наук,

профессор Батищев Дмитрий Иванович

Официальные оппоненты

доктор технических наук, профессор Гергель Виктор Павлович,

доктор технических наук, доцент

Хранилов Валерий Павлович

Ведущая организация ФГУП ФНПЦ «НИИИС

им. Ю.Е. Седакова»

Защита состоите*

Диссертационного Совета Д 212.166.13 при Нижегородском Государственном Университете им. Н.И.Лобачевского по адресу: 603950, Н.Новгород, пр.Гагарина, д. 23.

С диссертацией можно ознакомиться в библиотеке Нижегородского Государственного Университета им. Н.И.Лобачевского.

Лъ ?:

Автореферат разослшр^^» СлАХ^/ С^г у 2008 г.

Ученый секретарь диссертационного совета кандидат

физико-математических наук

Савельев Владимир Петрович

Актуальность темы исследований

Проектирование современной радиоэлектронной аппаратуры (РЭЛ), программных систем и вычислительных комплексов предполагает решение большого количества различных математических задач. Естественно, способность решать такие задачи предполагает наличие соответствующих алгоритмов решения. Однако, зачастую размерности и сложность таких задач настолько велики, что делают невозможным их решение, даже с использованием мощнейшей вычислительной техники. В связи с этим возникла проблема практической разрешимости задач: найти реализуемый, эффективный или хотя бы достаточно про-сюй в практически важных случаях алгоритм ее решения. Подходы, относящиеся к этой категории применимы исключительно к оптимизационным задачам (однако это обстоятельство не является сильным ограничением, поскольку огромное количество прикладных задач естественно формулируются как оптимизационные) и включают прием, который заключается в отказе от поиска оптимального решения и нахождении вместо этого "приемлемого" решения за обозримое время. Методы, применяемые для построения алгоритмов такого типа, сильно зависят от специфики задачи, и хотя на практике оказываются весьма неплохими, для получения удовлетворительных характеристик алгоритма обычно требуется довольно большая работа по его "доводке". В результате удается только в очень редких случаях предсказать и оценить поведение таких алгоритмов.

Конечно, термин "приемлемые" не строг в математическом смысле. Под "приемлемыми" решениями нами понимаются решения, которые удовлетворяют исследователя. Ведь в большинстве реальных задач нет особой необходимости находить именно глобальный оптимум. Чаще всего целью поисков являются решения, удовлетворяющих определенным ограничениям. Например, электрические цепи принципиальной схемы некоторого электронного устройства требуется распределить в непересекающихся слоях, а число таких слоев не должно превышать заданной величины. В этом смысле достаточно найти именно "приемлемые", т.е. разумные решения.

Традиционно, решения задач проектирования РЭА, программных систем и вычислительных комплексов связывают с решением графовых задач. Так, например, при производстве современного электронного оборудования особое место занимает разработка печатных плат и микроэлектронных схем большой плотности. Одной из задач, которая требует решения при их конструировании, является задача разбиения принципиальных схем устройств на составные части (подсхемы, функциональные блоки). Типовые элементы принципиальной схемы должны таким образом быть распределены по отдельным подсхемам, чтобы число внешних соединений было как можно меньше. Это необходимо с целыо повышения надежности схемы, уменьшения влияния наводок, повышения технологичности и простоты конструктивного оформления.

При разработке топологии многослойных схем возникает задача распределения "конфликтующих" соединений по отдельным слоям (задача расслоения цепей). Расслоение до трассировки основано на анализе схемы соединений для выявления тех соединений или их групп, которые не могут быть расположены на одной плоскости из-за неизбежности "сложных" ситуаций трассировки. В частности, усложняется форма соединений, увеличивается их длина, растет время поиска трасс при реализации алгоритма трассировки на ЭВМ.

Использование графов при решении такого рода задач часто налагает существенные ограничения, как на математические модели, так и на решающие алгоритмы, что, в конечном итоге, отрицательно сказывается на качестве получаемых решений. Часто более предпочтительным с точки зрения точности моделирования является использование обобщения графов - гиперграфов, поскольку они не только более естественно описывают названные выше инженерные задачи, но и позволяют решать некоторые задачи линейной алгебры и дискретной математики, сведение которых к классическим графам либо невозможно, либо порождает очень сложные модели. Однако, несмотря на значительно более широкие возможности, предоставляемые гиперграфовыми моделями, сложность машинной реализации самих моделей и алгоритмов, работающих над ними, также выше. В этой ситуации особенно остро встает проблема построения алгоритмов, осуществляющий поиск приближенных решений.

Можно выделить два класса подходов решения задач высокой сложности - это упрощение алгоритмов: снижение их математической и инженерной сложности, применение различного вида эвристик, и упрощение решаемых задач. Часто для решения задачи создается метод, который сочетает в себе два этих подхода. К таким методам можно отнести целый класс алгоритмов, получающий широкое распространение в последнее время - многоуровневые алгоритмы. Ключевая идея многоуровневого алгоритма состоит следующем: размерность задачи редуцируется путем удаления наименее существенной информации, затем производится поиск решения редуцированной задачи, после этого производится ряд улучшений полученного решения на основе добавления в модель задачи ранее удаленной информации.

Многоуровневые алгоритмы предполагают широкие возможности по настройке алгоритма, поскольку позволяют достаточно легко интегрировать в структуру алгоритма различные эвристики, направленные на улучшение получаемого решения. Не смотря на очевидные достоинства многоуровневых методов, разработка и исследование этого класса алгоритмов применительно к графовым и гиперграфовым моделям у нас в стране - редкое явление. За рубежом такого рода методами занимаются G.Karypis, V.Kumar, B.Hendrickson, R.Leland, S. Barnard, H. Simon и др.

Еще одним примером способа сокращения вычислительной сложности решающих алгоритмов может служить введение элементов рандомизации. Данное направление дало толчок к развитию методов эволюционных вычислений

(подкласс методов случайного поиска), что позволило построить универсальные и достаточно мощные алгоритмы для широкого класса задач. У нас в стране разработкой такого типа алгоритмов занимались Д.И. Батищев, J1.C. Бернштейн, И.Л. Букатова, Я.Г. Дорфман, Б.П. Коробков, В.М. Курейчик, A.M. Мелихов, Ю.И. Неймарк, Г.И. Орлова, Л.А. Растригип, А.П. Рыжков, Д.Б. Юдин и другие. Методы эволюционных вычислений не гарантируют обнаружения оптимального решения. Однако практический интерес к ним не ослабевает, а наоборот усиливается. Объяснить это можно тем обстоятельством, что эти методы позволяют исследовать и находить приемлемые решения таких задач, решение которых при помощи традиционных методов оказывается затруднительным, а в некоторых случаях и просто невозможным.

Синтез многоуровневых и эволюционно-генетических алгоритмов позволяет получать гибкие, легко настраиваемые под каждую конкретную задачу методы, которые позволяют контролировать баланс между качеством решения и вычислительным ресурсом, потраченным на его получение.

Цель работы

Цель работы заключается в:

1) разработке и реализации многоуровневого алгоритма поиска решения задачи k-декомпозиции гиперграфов большой размерности.

2) разработке и реализации ряда эвристик, входящих в состав многоуровневого алгоритма.

3) разработке и реализации алгоритма улучшения k-разбиения гиперграфа, основанного на принципах эволюционно-генетического поиска.

4) разработке методологии работы с атрибутированными гиперграфами и ее реализации в виде программной среды.

5) разработке способа формализации задачи компоновки радиоэлектронной схемы на основе БМК и решении конкретной задачи компоновки

6) проведении ряда вычислительных экспериментов с целью выяснения эффективности работы алгоритма.

Научная новизна

Разработана концепция «фильтр-вид», предполагающая построение специального вида иерархий гиперграфов на основе атрибутивной информации, содержащейся в них, правила изменения и передачи этой атрибутивной информации, а также методы построения и управления такими иерархиями на основе специальных операторов - фильтров.

Разработана гибридная схема решения задачи k-декомпозиции графа на основе многоуровневого и генетического алгоритма. Предложена методика работы и принципы построения улучшающего ГА в структуре многоуровневого алгоритма. Использование ГА в качестве улучшающего алгоритма, позволяет значительно повысить качество получаемого разбиения вследствие значительно

более детального исследования области поиска на каждой из стадий многоуровневого алгоритма.

Предложен метод реализации многоуровневого алгоритма декомпозиции гиперграфа на основе концепции «фильтр-вид», позволяющей автоматизировать общие для многоуровневой парадигмы процессы и сосредоточиться непосредственно на логике решающего алгоритма. Алгоритм позволяет решать задачи достаточно большой размерности за счет ее редуцирования, исследовать обширные области поиска и получать приемлемые результаты за счет применения ГА в сочетании с различными эвристиками, направленными на улучшение качества решения.

Разработана и реализована система машинного представления гиперграфовых структур, а также логика наиболее употребимых при работе с гиперграфами операций. Это позволяет значительно сэкономить время при разработке алгоритмов. Система оформлена в виде библиотеки классов, что делает возможным использовать ее при решении практических и академических задач сторонними исследователями. Исследованы и реализованы различные методики ускорения работы системы представления гиперграфов. Проведены вычислительные эксперименты, подтверждающие эффективность разработанных методов.

Предложен метод сведения экстремальной задачи компоновки БИС на основе БМК к задаче к-декомпозиции гиперграфа. Выполнена компоновка конкретного радиоэлектронного устройства.

Теоретическая и практическая ценность работы

В качестве технических приложений класса задач декомпозиции гиперграфов могут выступать реальные технические задачи, возникающие на этапе проектирования сложных электронных систем. Подобные задачи также имеют место при проектировании и управлении вычислительными системами, при сегментации машинных программ, при распределении программ между машинами в вычислительных системах, на транспортных сетях, при автоматизации конструкторского синтеза дискретных устройств и т.д.

Программные системы, реализованные в ходе данной работы, не имеют четкой направленности на перечисленные задачи и могут быть использованы при решении целого ряда различных проблем, связанных с гиперграфами и многоуровневыми алгоритмами, как практического, так и академического характера.

Апробация результатов

Результаты диссертации докладывались и обсуждались на 6-ом международном конгрессе по математическому моделированию (Н.Новгород, 2004г.), Всероссийской научно-технической конференции «Информационные системы и технологии» ИСТ-2005 (Н.Новгород, 2005г.), конференции «Технологии Мюго-

soft в теории и практике программирования» (Н.Новгород, 2006), Всероссийской научно-технической конференции «Информационные системы и технологии» ИСТ-2007 (Н.Новгород, 2007г.), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Кроме того, результаты диссертационной работы прошли апробацию при выполнении хоздоговорных работ между ННГУ и НИИИС, в которых автор был исполнителем-разработчиком алгоритмов и автором программных реализаций функциональных блоков систем. Это хоздоговорные работы: «Оптимальная трассировка кабельных соединений в монтажном шкафе» (2005г.), «Исследование методов и разработка системы интеллектуальной поддержки этапов конструкторского проектирования РЭА» (2006г.), «Разработка и реализация программного средства трассировки БИС с одним слоем металлизации»(2007г.), «Разработка и реализация диалоговых программных средств решения задач размещения элементов БИС» (2008г.).

Структура и объем работы

Работа состоит из введения, пяти глав, заключения, списка литературы и приложений. Общий объем работы составляет 124 страницы. Список литературы составляет 145 наименований. Основные результаты излагаются в главах 2, 3 и 5.

Краткое содержание работы

Во введении обосновывается актуальность графовых и гиперграфовых проблем, указывается место многоуровневых и генетических алгоритмов в общем классе методов оптимального проектирования. Обсуждаются преимущества и недостатки, а также основные сферы применимости этих алгоритмов в сравнении с традиционными "классическими" методами оптимизации.

В главе 1 ставится задача k-декомпозиции гиперграфа и приводится обзор точных и эвристических методов и подходов к решению данной задачи, существующих в данный момент, с кратким анализом их характеристик.

Проблема k-разбиения гиперграфа H=(V,E), где V-множество вершин, Е -множество гиперребер, состоит в разбиении множества вершин V по к подмножествам V,,...Vb таким образом, чтобы удовлетворялся набор ограничений, называемых декомпозиционными ограничениями, а оптимизируемая функция (функция цели, критерий оптимальности, функционал), определенная над разбиением, принимала экстремальное значение. Разбиение предполагает, что множества V|,...Vk попарно не пересекаются и при объединении составляют исходное множество V:

Подмножества разбиения определяют подграфы разбиения. Значение к фиксировано и задается как параметр задачи.

Определим декомпозиционные ограничения так, чтобы вес каждого подграфа разбиения w(K,) = ^ w(v?), лежал в следующих пределах:

L, <и<Г,)<U„i = TJ, L| и Uj - минимальный и максимальный вершинные веса под- (2)

графов разбиения.

В ограничениях (2) константы L; и U| определяют пределы, в которых могут варьироваться веса подграфов разбиения.

Критерии оптимальности, как и декомпозиционные ограничения, определяются спецификой конкретной задачи. Один из наиболее часто используемых критериев - минимизация веса сечения. Вес сечения определяется суммой весов ребер, которые целиком не принадлежат ни одному подграфу разбиения: Wс = ^ -> min,

есе£(

Г _ _] (3)

Ес = <е е Е 1е е : v, е V„,Vj е Vb,a * Ь, а - \,к,Ь = \,к>

Задачу (1)-(3) будем называть задачей k-разбиения гиперграфа. Возможны различные расширения проблемы (1)-(3). Например, задача может иметь несколько функций цели (многокритериальный случай), тогда решение состоит в нахождении Парето-области решений.

Глава 2 посвящена обзору теоретических основ гипеграфовых структур. В данной главе вводится ряд понятий, необходимых описания манипуляций с гиперграфами. В этот ряд входят как базовые понятия, такие как вершина, ребро, гиперграф, так и более сложные, такие как части и куски гиперграфа, подграфы, суграфы и т.д. Также описывается ряд базовых операций над гиперграфом и элементами гиперграфа, такие как введение, удаление и стягивание вершин и гиперребер, расщепление вершин и ребер, удаление частей гиперграфа и различные бинарные операции с гипеграфами.

Отдельное место в главе занимает проблема визуализации гиперграфа. Визуализация сложных концептуальных структур, отражающая особенности их внутренней организации, занимает ключевое место во многих приложениях в науке и технике. Гиперграф - это абстрактная структура, которая используется для моделирования информации. Системы из объектов и групповых связей между ними естественно моделируются гиперграфами, а их грамотная визуализация обеспечивает дополнительной информацией исследователя в понимании принципов организации объекта исследования. Поэтому многие прикладные системы, например, в сфере проектирование радиоэлектронной аппаратуры, требуют понятного изображения объекта исследования. В главе рассматривается несколько методой визуализации гипеграфа, это: кенигово представление, диаграмма Венна и группа шинно-блочных методов. Все эти методы обладают

б

достоинствами и недостатками, описанными в виде сравнительной таблицы. Выбор того или иного метода зависит от преследуемых при визуализации целей.

Кроме набора базовых понятий и операций в главе описана так называемая концепция «фильтр-вид» и лежащие в се основе понятия атрибута, фильтра, вида и основания. Эта концепция расширяет классическое определения веса элемента гиперграфа, вводя понятие атрибута, и предлагает общий аппарат для построения многоуровневых алгоритмов над гипеграфами. Это связано с тем, что в реальных задачах в гиперграфовые модели приходится добавлять разнообразную дополнительную информацию, причем часто нечислового характера. В силу этого в действительности исследователям приходится работать с помеченными гиперграфами. Задавая на вершинах и гиперребрах гиперграфа Н=(У,Е) отображения ан\У^)Е—*М, где Л/- некоторое семейство непустых (необязательно различных) подмножеств множества//, и а>ц:(УиЕ)хА—*Мполучим помеченный (взвешенный) гиперграф (Н,а,ш). Элементы множества А называются метками или атрибутами. В дальнейшем четверкой (У,Е,а,а>) будем обозначать помеченный гиперграф Н=(У,Е,ац,и>н).

Если отображение ан ставит в соответствие казадому элементу гиперграфа действительное число (вектор из действительных чисел), то (Н,а,ы) будем называть взвешенным гиперграфом.

Рассмотрим понятие атрибута подробнее. В общем случае ан отображает вершину уеКв набор атрибутов ац^)сА, приписанных этой вершине, и гиперребро ееЕ в набор атрибутов ая(е)с/1, приписанных этому гиперребру.

Выше было введено отображение (0//:(УиЕ)хА—»Д которое каждой паре значений: элементу гиперграфа и его атрибуту ставит в соответствие значение атрибута. Здесь Э{— это множество всевозможных значений атрибутов. Допустим, каждый элемент схемы характеризуется собственными габаритами: ширина и высота. В гиперграфовой модели этой схемы каждой вершине ve V будет приписан набор а «(у), состоящий из двух атрибутов «ширина» и «высота», а отображение Сй//(у,а,), где а,еа//(у), укажет численное значение габарита.

Будем говорить, что элемент с гиперграфа Н имеет атрибут а, со значением Ру, если а,еа//(с) и Р,=со//(с,а,). Соответственно, будем говорить, что элемент с гиперграфа Н имеет атрибут а, без значения, если а,еац(с) и отображение Ш/у(с,а,) на указанном наборе значений не определено. Набор атрибутов а//(с) и отображение со ¡¡(с): ссдг(с)—будем называть атрибутивной информацией элемента сеН.

Можно привести массу алгоритмов, которые в процессе работы над графом не меняют его структуру, но вводят в графовую модель дополнительную информацию. Подобная информация укладывается в графовую модель в виде специальных меток, которые приписываются элементам графа. Примером подобных алгоритмов могут служить алгоритмы раскраски графа. В этом случае

информация принадлежности цветовому классу элемента графа носит глобальный характер и фактически в этой информации кодируется решение задачи. В других алгоритмах подобная дополнительная информация носит временный или вспомогательный характер. Так, например, в волновых алгоритмах схема распространения волны строится на приписывании специальных пометок для уже рассмотренных элементов графа.

Очевидно, что операции, позволяющие менять атрибутивную информацию гиперграфа, являются не менее важным компонентом в общей модели управления гиперграфом. Введем операции над атрибутами элементов гиперграфа.

Пусть имеется помеченный гиперграф H=(V,E,а,со). Добавление атрибута а0еА без значения к элементу се VvjE предполагает переход к новому помеченному гиперграфу ff=(V,E,а',ш), где а'//(с)=а//(с)и{ао}. Добавление атрибута а0еА со значением PosW к элементу сеКи£ предполагает переход к новому помеченному гиперграфу fT={V,E,а',со'), где а'//(с)=ая(с)и{а0}, co'w(c,a0)=Po.

Противоположной операцией добавлению атрибута является операция удаления атрибута. Удаление атрибута а0еА элемента сеУиЕ предполагает переход к новому помеченному гиперграфу tr=(V,E,а',со), где a7/(c)=a//(c)/{a0}.

Важно не только добавлять и удалять атрибуты, но и менять значение атрибута с одного на другое. Изменение значения атрибута а0еА на значение (30е Wдля элемента се УОЕ предполагает переход к новому помеченному гиперграфу ff=(V,E,a,a>'), где ®'н(с,а0)=Ро- Удобно ввести специальное значение атрибута - null. Будем считать, что если атрибут имеет значение null, то этот атрибут не имеет значения. Т.е. если o)//(c,a0)=null, то для элемента с гиперграфа Н атрибут задай без значения. В этом случае, операция удаления значения атрибута формально сводится к операции изменения значения атрибута.

Структура многоуровневых алгоритмов (описана в главе 3) предполагает наличие нескольких достаточно общих с точки зрения описания и реализации операций. В частности, любой многоуровневый алгоритм над гиперграфом подразумевает стадию редукции размерности задачи, в ходе которой выполняется ряд действий по удалению избыточной информации из гиперграфовой модели. Было решено унифицировать такого рода операции, что привело к появлению аппарата фильтров, использование которых, однако, не ограничено конструированием многоуровневых алгоритмов, т.к. фильтры представляют собой достаточно универсальный механизм выявления тех или иных структурных особенностей гиперграфа. Итак, под фильтром понимается оператор Ф, на вход которого подается гиперграф Н, а на выходе получается новый гиперграф ФН. Исходный гиперграф назовем гиперграфом-прообразом. Кроме исходного гиперграфа //фильтр на вход получает условие фильтрации, которое можно представить в виде отображения (р:Ах9?-~>{0,1}. Отображение ф каждой паре («атрибут», «значение») ставит в соответствие либо 0, либо 1. Значение 1 подразумевает, что элемент исходного гиперграфа, имеющий данный атрибут с данным

8

значением, будет профильтрован - т.е. подвержен работе оператора фильтрации. Таким образом, отображение —>{0,1} для гиперграфа //однозначно определяет множество элементов фЯ гиперграфа, для которых будет выполняться условие фильтрации:

ф//= {ceVuE| 3 а,еа/Хс), ф(а„ cow(c,a,))=l}.

Будем обозначать через фIIV - множество вершин гиперграфа Я, для которых выполняется условие фильтрации ф, фНЕ - множество гиперребер гиперграфа Я, для которых выполняется условие фильтрации ф. Таким образом, фЯ = фЯКифЯ£.

Элементы, для которых НЕ выполняется условие фильтрации, "переходят" в новый гиперграф фЯ, причем набор атрибутов элемента и их значений в гиперграфе фЯ будет таким же, как и в исходном гиперграфе Я:

ац(с)=афц{с) и «л(с,а;)=мф//(с,ы,) для Va,ea//(c), где се Я/фЯу.

Предлагается два типа фильтров: скрывающие фильтры и объединяющие фильтры. Для обозначения фильтров примем следующую форму записи'.

<t>H=filter{ миожество_элементов [ | разбисние_на_классы ] }Я. Здесь ФЯ - результат работы фильтра; вместо filter указывается либо hide -скрывающий фильтр, либо join - объединяющий фильтр; множест-во_элементов описывает множество элементов, удовлетворяющих условию фильтрации; разбиение_на_классы (может быть опущено) описывает признак, по которому будет происходить разбиение множества элементов на классы, каждый класс будет подвержен действию, указанному в filter.

В общем случае скрывающий фильтр на входе принимает гиперграф Я, а на выходе получает новый гиперграф ФЯ = Я/фЯ. Таким образом, результатом работы скрывающего фильтра есть исходный гиперграф без элементов, удовлетворяющих условию фильтрации.

Другая группа фильтров — объединяющие фильтры. Основная идея объединяющих фильтров заключается в применении операций стягивания элементов исходного гиперграфа Я, удовлетворяющих условию фильтрации ф.

В работе описаны подклассы данных классов фильтров, их формальное описание и принципы действия, работа фильтров показана на примерах.

Аппарат фильтров подразумевает создание из исходного гиперграфа другого, который обладает теми или иными структурными особенностями, необходимыми исследователю. Исходный гиперграф и гиперграф, полученный в результате работы фильтра - два несвязанных между собой гиперграфа. Однако, часто, особенно при использовании фильтров в составе многоуровневых алго-

1 Под операцией вычитания гиперграфов здесь понимается операция, состоящая из двух частей: слабого удаления вершин ФНУ=НУ\фУ и слабого удаления гиперребер ФНЕ=НЕ\фЕ, таким образом ФН=( НУ\ф, НЕ\срЕ)

9

ритмов, необходимо передавать информацию из одного гиперграфа в другой; под информацией здесь подразумевается атрибутивная информация. Будем говорить, что два гиперграфа, способные передавать друг другу атрибутивную информацию имеют атрибутивную связь. Пусть имеется помеченный гиперграф Н-{У,Е,а,ю), задано условие фильтрации ср для некоторого фильтра Ф, осуществляющего перенос атрибутивной информации от исходного графа Я к результирующему ФЯ. Представим работу фильтров на уровне отдельных элементов. Очевидно, что после работы фильтра Ф для любого элемента с гиперграфа ФЯ можно указать непустое множество элементов Ф"'(с) исходного гиперграфа Я, которые оказали влияние на формирование атрибутивной информации ан{с) и ш я(с).

Результат работы фильтра ФЯ=(ФК,Ф£,аф,(Оф) назовем видом гиперграфа Я, если любая операция по изменению атрибутивной информации для любого элемента из ФЯ приводит к изменению атрибутивной информации соответствующих элементов из Я по следующему правилу: добавление (изменение) атрибута а0еА со значением РоеЛ'для элемента сеФЯ приводит к добавлению (изменению) атрибута а0еА со значением р0е.9?для всех элементов из где ф-'(с) - множество элементов исходного гиперграфа Я, которые оказали влияние на формирование атрибутивной информации аф (с) и соф(с)

В тоже время, помеченный гиперграф Я=(К,Е,а,со) будем называть основанием вида ФЯ=(ФК,Ф£,аф,Юф), если любая операция по изменению атрибутивной информации для любого элемента из Я приводит к изменению атрибутивной информации соответствующих элементов из ФЯ по следующему правилу: добавление (изменение) атрибута а0еА со значением [¡ое 91 для элемента сеЯ приводит к добавлению (изменению) атрибута сс0еА со значением Рое^У для всех элементов Ф(с)сФЯ.

Пусть имеется пара помеченных гиперграфов Н\ и Я2. Будем говорить, что Яг атрибутивно зависим от Н\ и обозначать Я;—>//2 (либо Н2<-Н{), если либо Нг является видом Н\, либо Н\ является основанием Яг.

Будем говорить, что Н\ и Яг атрибутивно связаны и обозначать //, <->//2, если Я|—>Я2 и //,<-//2.

Очевидны следующие утверждения.

• Суперпозиция фильтров Ф есть фильтр, т.е. если Ф1 и Ф2 - фильтры, тогда и Ф|Ф2 - тоже фильтр.

• ЕслиЯ,->Яг и Я2->Я3, тогдаЯ]->Я3.

• Если Я[<->Я2 и Я2<-> Я3, тогда Я1ОЯ3.

• Отношение <-» является отношением эквивалентности.

Число суперпозиций фильтров Ф, примененных к гиперграфу Я назовем порядком вида гиперграфа Я, если между ними имеется отношение гиперграф-

вид. Таким образом, Н- это вид нулевого порядка гиперграфа Н; ФН- вид первого порядка гиперграфа Я, если Ф//; ФФН - вид второго порядка гиперграфа Н, если !!<-ФФН.

Глава 3 описывает основные принципы построения и функционирования многоуровневого алгоритма декомпозиции гиперграфа, обосновывает необходимость применения многоуровневых схем при решении задач большой размерности, а также описывает способ организации многоуровневых методов с применением концепции «фильтр-вид».

Применение эвристик, таких как многоуровневые алгоритмы связано с тем, что исследуемые задачи декомпозиции гиперграфа ЫР-трудны и на практике, как правило, имеют большие размерности. Алгоритмы, получающие точные решения таких задач, оказываются неприменимыми в силу большой вычислительной сложности. Известно множество попыток сведения подобных задач к менее сложным. Условно методы решения задач декомпозиции больших порядков можно разбить на две группы. В первую группу отнесем методы, которые осуществляют переход к более простым задачам, не используя понижение размерности задачи. Например, бисекционные алгоритмы предполагают рекурсивную бисекцию графа до тех пор, пока не будет получено необходимое количество подграфов разбиения. Вторую группу составляют методы, которые сокращают вычислительную сложность за счет уменьшения размерности исходной задачи.

Методы второй группы, осуществляющие непосредственное к-разбиение, в целом получают более качественное решение. Например, показано, что решение, полученное рекурсивной бисекцией, может быть вплоть до О(1о§ п), где п - размерность графа, хуже, чем решение алгоритма, осуществляющего непосредственное к-разбиение. Такое положение вещей объясняется тем, что рекурсивный метод не позволяет напрямую оптимизировать функционалы, значение которых зависит от того, каким способом ребра распределены по подграфам разбиения. Второе существенное преимущество - в ходе работы алгоритм второго типа способен более жестко контролировать декомпозиционные ограничения, в то время как бисекционные алгоритмы должны иметь специальные фазы коррекции решения для удовлетворения этим ограничениям, что существенно ограничивает область поиска решения.

В последнее время популярность приобрели так называемые многоуровневые алгоритмы. Ключевая идея многоуровневого алгоритма декомпозиции1 состоит следующем: вместо того, чтобы строить к-разбиение непосредственно для исходного гиперграфа, сначала строится ряд его приближений (загрублений). Каждое загрубление уменьшает (редуцирует) размерность исходной задачи. Процесс редукции продолжается до тех пор, пока порядок гиперграфа не снизится до

1 В дальнейшем будем употреблять термин «декомпозиция» как синоним термина «разбиение», за исключением специально оговоренных случаев.

11

сотен или даже десятков. На гиперграфе таких размерностей и отыскивается так называемое начальное разбиение. Полученное решение используется для построения решения для исходной задачи. Это достигается путем выполнения серии переносов решения задачи меньшей размерности на задачу большей размерности с последующим улучшением перенесенного решения. Таким образом, работу многоуровневого алгоритма можно разделить на три фазы: первая - фаза за-грубления, когда производится ряд последовательных редукций размерности задачи, вторая - фаза поиска начального разбиения и третья - фаза восстановления решения, когда производится серия последовательных переносов решения задачи меньшей размерности на менее редуцированную задачу с последующим улучшением спроецированного решения. Работа алгоритма для задачи 3-декомпозиции схематично показана на рис.1.

Рисунок 11. Многоуровневый алгоритм З-разбнення гиперграфа

Загрубление гиперграфа - это удаление избыточной информации, которая, с одной стороны, не является необходимой для поиска решения на данном этапе, а с другой стороны ухудшает характеристики решающего алгоритма.

Рассмотрим фазу загрубления на примере (рис. 1). Исходная задача 3-разбиения поставлена над гиперграфом Н0. В ходе фазы загрубления строится редуцированный гиперграф H¡, получаемый из Но удалением избыточной информации1, и над полученным гиперграфом ставится новая задача 3-декомпозиции. Удаление избыточной информации из гиперграфа и постановка новой задачи должно производиться таким образом, чтобы по решению новой задачи могло быть построено решение исходной задачи. Если это условие вы-

1 Критерий определения избыточности специфичен как для каждой конкретной задами, так и для конкретного многоуровневого алгоритма, поэтому здесь не уточняется.

12

полнено, то процесс удаления избыточной информации из гиперграфа назовем загрублением гиперграфа, а процесс построения загубленного гиперграфа и постановки над ним новой декомпозиционной задачи назовем редуцированием задачи; построение решения исходной задачи по решению вновь построенной будем называть переносом (проекцией) решения; исходную задачу будем называть задачей-прообразом, а вновь полученную - задачей-редуктантом. Таким образом, на первом этапе фазы загрубления мы получили из задачи-прообраза, определенной над гиперграфом Н0, задачу-редуктант, определенную над затрубленным гиперграфом //;, обладающую меньшей размерностью. В дальнейшем для простоты будем обозначать декомпозиционную задачу, определенную над гиперграфом Нт, «задача Ят».

На втором этапе повторим процесс редуцирования, используя задачу Я/ в качестве задачи-прообраза, и получим задачу Н2. Следующий этап позволит получить задачу Н3, обладающую достаточно малой размерностью, чтобы для нее можно было отыскать разбиение.

Описанное выше условие редуцирования задачи, при котором решение, полученное для задачи-редуктапта, может быть спроецировано на задачу-прообраз, позволяет утверждать, что решение задачи Нт может быть использовано для построения решения задачи Нт п < т. Действительно, решение Я„, можно спроецировать на Ят_/, затем, полученное решение Я„,_/ спроецировать на Нт.2, и так далее до Я„. Таким образом, задача Нт, по сути, является задачей-редуктантом Я,„ а Я„ в свою очередь - задачей-прообразом Нт. Число т-п назовем глубиной редукции. Задачу Нт будем называть задачей-редуктантом задачи Я„ глубины т-п. Очевидно, задача Я„ является задачей-редуктантом исходной задачи глубины ш. Так, к примеру, на рис.1 задача Н2 является задачей-редуктантом задачи Н0 глубины 2 и задачей-редуктантом глубины 1 для Н1. Возможность построения решения исходной задачи по решению любой задачи-редуктанта позволяет говорить о решении задачи-редуктанта как о решении исходной задачи. Т.е. можно говорить о процессе построения начального разбиения (для примера на рис.1 это решение задачи II3) как об отыскании некоего начального решения исходной задачи.

Для рассматриваемых задач декомпозиции гиперграфа процесс загрубления строится па выделении и объединении групп вершин, которые целесообразно всегда определять целиком в одну из компонент разбиения. Естественно, что в такой ситуации на группы должны быть наложены некоторые ограничения, например, вес группы не должен превышать вес компоненты разбиения, иначе алгоритм поиска начального разбиения не сможет найти решение.

Глава описывает ряд схем загрубления гипеграфа, которые обладают различными характеристиками и применимы для различных видов гиперграфов.

Поскольку размерность задачи-редуктанта самой большой глубины невелика, то ряд алгоритмов, способных получить начальное разбиение в многоуровневом алгоритме достаточно широк. В случае, когда самый затрубленный

13

гиперграф содержит десяток вершин возможно применение переборных методов. Однако, в силу ограничений схем загрубления, редукция гиперграфов больших размеров (десятки и сотни тысяч) до размерностей в несколько десятков часто невозможна. Поэтому можно использовать менее ресурсоемкие алгоритмы, например, т.н. region-growing алгоритмы или алгоритмы, строящие случайные разбиения с последующим их улучшением с помощью эвристик типа алгоритма Кернигана-Лина (Kernigan and Lin, KL), Фидуччиа-Мэтьюза (Fiduccia and Mattheyses, FM), спектральных методов, табу-поиска или методов simulated annealing, модифицированных для работы с гиперграфами или описанного ниже генетического улучшающего алгоритма.

Решение задачи Н3 может быть спроецировано на задачу Н0, в этом состоит суть фазы восстановления решения. Поскольку вычислительная сложность алгоритмов загрубления, как правило, несравнимо меньше вычислительной сложности декомпозиционных алгоритмов, а размерность задачи-редуктанта самого высокого порядка на несколько порядков ниже размерности исходной задачи, такой подход дает существенный выигрыш по вычислительной сложности по сравнению с «классическими» декомпозиционными алгоритмами.

Однако, приведенная схема решения, когда решение, полученное для за-дачи-редуктанта самого высокого порядка, проецируется на исходную задачу, обладает одним существенным недостатком. Потеря информации в процессе редуцирования задачи не может не сказаться на качестве решения, построенного на этапе построения начального разбиения. Поэтому имеет смысл попытаться улучшить это решение в ходе фазы восстановления. Действительно, при переходе от задачи-редуктанта на задачу-прообраз появляется информация, отброшенная при редукции, которая может быть использована для улучшения спроецированного решения. Таким образом, каждый этап фазы восстановления решения состоит из двух подэтапов - проецирования решения задачи-редуктанта на задачу-прообраз и улучшение спроецированного решения. Описанный в работе алгоритм использует жадную методику улучшения разбиения, основанную на т.н. процессе локализации гиперребер, когда «тяжелые» ребра, попавшие в сечение гиперграфа целиком переносятся в одну из компонент разбиения.

Кроме того, в главе 3 описан принцип построения улучшающего генетического алгоритма. Алгоритмы улучшения решения задачи декомпозиции гиперграфа, как правило, основаны на жадном принципе и работают достаточно быстро. Однако, они не содержат никаких средств преодоления локальных экстремумов, что сказывается на качестве находимых ими решений.

Для того чтобы значительно расширить исследуемое пространство области поиска задачи предлагается сконструировать гибридный алгоритм улучшения решения, основанный на предложенной жадной методике и эксплуатирующий эволюционно-генетический подход.

Классический генетический алгоритм (ГА), в том числе работающий с графовыми или гиперграфовыми моделями, подразумевает манипулирование

14

так называемыми кодировками (генотипами). Каждая кодировка представляет собой некоторое представление решения задачи в форме, удобной для применения различных операторов ГА. Каждая кодировка имеет оценку, называемую приспособленностью, которая характеризует качество решения, соответствующего данной кодировке. В результате процесса, моделирующего эволюцию набора кодировок, определяется «кодировка-победитель», обладающая наилучшей приспособленностью, которой соответствует решение задачи с наивысшим качеством.

Поскольку классический ГА - это решающий алгоритм, а цель - построить улучшающий, то, очевидно, необходимо изменить состав информации, закодированный в генотипе. Предлагается кодировать не само решение, а некий сценарий получения нового решения из существующего.

Описанный выше жадный алгоритм улучшения решения, основанный па локализации ребер, на каждом шаге принимает решение, руководствуясь наибольшим сокращением веса сечения, т.е. выбирает одно из нескольких возможных направлений движения по ОП, оставляя остальные направления неисследованными. Внедрение генетического алгоритма в качестве управляющей схемы, принимающей решение, в каком направлении двигаться по ОП на каждом шаге, позволяет существенно расширить исследуемую область ОП.

Для реализации предложенного подхода модифицируем жадный алгоритм таким образом, чтобы решение о том, какой шаг сделать в ОП принимал не он, а ГА в соответствии с маршрутом ОП, закодированном в генотипе. Фактически, модифицированный жадный алгоритм формирует набор направлений, в которых можно двигаться по ОП с целью улучшения решения, а ГА принимает решение в каком именно направлении сделать шаг. Такой синтез ГА и жадных техник позволяет построить достаточно быстрый улучшающий алгоритм, лишенный недостатка жадных алгоритмов скатываться в локальный экстремум.

На рис.2 схематично изображен процесс движения по ОП; точки обозначают решения, через которые проходит маршрут, стрелки - возможные направления движения на каждом шаге; на каждом шаге выбирается одно из направлений определяемое соответствующим геном.

Текупее __/-\ Оппшишровгнное

решение Ч ^ ^Г^^Р^нне

Область попска

\ М 1 I

Генотип

а: а; аз ал а5

Рис 2. Маршрут поиска закодирован в генотипе

В главе описана адаптация этой общей схемы построения улучшающего ГА к жадному алгоритму улучшения разбиения, основанному на переносах групп вершин. Для этого предложены символьная модели и оператор декодирования генотипа в решение задачи.

В главе 4 содержится описание программной реализации принципов и понятий, изложенных в предыдущих главах. Условно глава может быть поделена на четыре части: описание реализации среды работы с гипеграфами, описание реализации концепции «фильтр-вид», описание реализации многоуровневого алгоритма декомпозиции гиперграфа с элементами эволюционно-генетического поиска и вычислительный эксперимент.

Первая часть главы кроме непосредственного описания структур хранения и работы с гиперграфами содержит изложение приемов решения технических проблем, возникающих при реализации среды работы с гиперграфами, таких как когерентность (целостность) хранимых данных и производительность.

Вторая часть четвертой главы содержит описание механизмов обработки гиперграфов, составляющих реализацию концепции «фильтр-вид». Описываются сущности, обеспечивающие данную функциональность, их обязанности, контракты и взаимоотношения. Рассматриваются проблемы, возникающие при работе фильтров и видов, в частности проблема бесполезных вычислений в многоуровневых иерархиях видов. Основные и наиболее сложные для понимания аспекты функционирования рассмотрены на примерах.

Третья часть главы описывает абстракции и конкретные реализации сущностей, обеспечивающих конструирование и функционирование многоуровневого алгоритма декомпозиции. Указаны проблемы, возникающие при реализации и работе многоуровневого алгоритма, описаны способы решения этих проблем. Кроме того, описана абстрактная реализация улучшающего генетического алгоритма и конкретная адаптация этого ГА для нужд многоуровневого алгоритма декомпозиции гиперграфа.

Для реализации гиперграфов и алгоритмов работы с ними был выбран объектно-ориентированный подход. Такой выбор обусловлен двумя факторами: большой инженерной сложностью реализуемой системы и тем, что большинство современных средств программирования, обладающих достаточной для написания данной системы функциональностью, поддерживают объектно-ориентированный подход, и было бы неразумно не воспользоваться предлагаемыми возможностями. Большая инженерная сложность означает, что код, представляющий систему, во-первых, имеет значительный объем, т.к. реализует обширную функциональность, во-вторых, достаточно сложен по структуре. Описание такой системы с помощью, например, структурного подхода, сулило бы разрастание и так достаточно большого объема кода и, как следствие, увеличение вероятности появления различного рода ошибок. Кроме того, объекты предметной области достаточно легко идентифицируются и абстрагируются в классы, что значительно упрощает проектирование с помощью объектно-ориентированной парадигмы. Почти все современные среды разработки и языки программирования

16

поддерживают объектно-ориентированную парадигму. Более того, выбранный для реализации системы язык С# полностью объектно-ориентирован, и, хотя и допускает некоторые формы структурного программирования, все же значительно более удобен при использовании ООП.

Последняя часть главы содержит описание результатов вычислительного эксперимента решения задачи декомпозиции гиперграфа для набора тестовых задач и различных конфигураций многоуровневого алгоритма.

В главе 5 изложены основные принципы и виды процессов конструирования больших и сверхбольших интегральных схем (БИС и СБИС). Более подробно рассматривается одна из задач проектирования БИС на основе БМК. Классический вариант конструкции БМК представлен на рис. 3. Такая БИС содержит центральную часть с матрицей регулярно расположенных базовых ячеек (БЯ) и каналы трассировки связей между нескоммутированными элементами БМК. По периферии расположены ячейки ввода-вывода и контактные площадки, предназначенные для организации ввода-вывода сигналов. Каждая БЯ может представлять собой как функционально законченный узел, выполняющий конкретную операцию, например И-НЕ, так и набор нескоммутированных элементов - транзисторов и резисторов, из которых формируется тот или иной библиотечный элемент.

Рисунок 3. Типовая структура БМК

Будем рассматривать процесс проектирования БМК, который подразумевает то, что БЯ - это набор нескоммутированных элементов. Каждая БЯ пли группа БЯ путем коммутации внутренних элементов может быть превращена в один из библиотечных элементов, из которых состоит функциональная схема заказчика. Таким образом, проектирование БМК состоит из двух этапов - опре-

17

деления какие именно БЯ будет занимать тот или иной элемент функциональной схемы и трассировки соединений между этими элементами на кристалле. Эти два этапа формализуются в задачи размещения и трассировки соединений.

Суть задачи трассировки - в проведении всех трасс между элементами функциональной схемы на кристалле. Трассы при этом могут проходить только в специально отведенных зонах БМК, называемых каналами трассировки. Очевидно, что, поскольку место для трассировки ограничено, то с увеличением количества связей между элементами вероятность успешной прокладки всех трасс уменьшается. Кроме того, успех решения задачи трассировки напрямую зависит от того, каким именно образом элементы функциональной схемы (ФС) расположены на кристалле. Поэтому основная цель решения задачи размещения -расположить элементы ФС так, чтобы максимизировать вероятность успешного решения задачи трассировки.

Нетрудно заметить, что при размещении элементов ФС существуют ситуации, возникновение которых резко снижает вероятность успешной трассировки. К таким ситуациям можно отнести возникновение так называемых «горизонтальных связей». Рассмотрим фрагмент БМК с размещенными элементами ФС (рис 4). Пусть между элементами 5 и 15 существует связь. Это означает, что трассировщик должен будет проложить горизонтальную трассу через весь канал трассировки. Такое расположение трассы 5-15 приведет к тому, что возможности прокладки других трасс в этом канале станут намного меньше. В частности, в этом канале не смогут быть проложены любые трассы, соединяющие элемент выше горизонтальной трассы и ниже, например трассы 4-9 и 3-18.

1. 11

2 12

з • -- 13

4 — 14

V 15

6 16

7 У-

8 18

9 — 19

10 20

Рисунок 4. Пример нежелательного размещения

Очевидно, что для предотвращения подобных ситуаций необходимо размещать элементы ФС, имеющие связи в пределах одного столбца матричных БЯ, т.е. необходимо максимально сократить число связей между элементами, расположенными на разных столбцах матричных БЯ. Таким образом, одним из

18

этапов решения задачи размещения может являться решение задачи компоновки элементов ФС в ряды с минимизацией связей между рядами.

Как уже было сказано, гиперграф является удобным средством моделирования электронных схем, в том числе и интегральных. Это связано с тем, что поскольку гиперграф является обобщением классического графа, то значительная часть методов и приемов теории графов может быть перенесена на гиперграфы, очень часто с сохранением семантики той или иной операции. С другой стороны, гиперграфы - более общий аппарат и предоставляют несравненно большие возможности моделирования электронных схем в различных задачах проектирования. В частности, предложенная выше задача компоновки элементов подразумевает достаточно простую формализацию в терминах гиперграфовой модели.

Формализация электронной схемы может быть проведена следующим образом: элементам ФС ставятся в соответствие вершины гиперграфа, а цепям, соединяющим элементы ФС - гиперребра. Рассмотрим небольшую схему (рис. 5) и ее гиперграфовую модель (рис. 6). Пусть мы имеем элементы и Ьб и соответствующие им вершины гиперграфа у5 и у6, тогда в гиперграфе будет существовать гиперребро {у5, у6}. Цепи, естественно, могут соединять более двух элементов, как например цепь с2, соединяющая элементы Ьь Ь2, Ь3 и Ь4, в этом случае соответствующее гиперребро будет содержать вершины У|,у2,у3,У4.

Рисунок 5. Пример функциональной схемы

Теперь каждой вершине гиперграфа припишем вес равный количеству занимаемых соответствующим элементом ФС матричных базовых ячеек БМК. Так, для простых элементов типа И - это число 1, для триггеров - 2.

Предложенная модель позволяет формализовать задачу компоновки, описанную выше, в задачу декомпозиции гиперграфа. При этом:

• подграфы разбиения соответствуют вертикальным рядам матричных

БЯ.

• Для каждого подграфа разбиения определяется минимальный суммарный вес, равный нулю, и максимальный суммарный вес, равный количеству БЯ в ряду.

• Вес каждой вершины равен количеству БЯ, занимаемому соответствующим элементом ФС.

• Вес каждого гиперребра равен 1.

• Значение критерия задачи декомпозиции соответствует количеству межрядных связей в решении задачи компоновки.

Рисунок 6. Гиперграфовая модель схемы

Решение задачи декомпозиции гиперграфа в терминах исходной задачи компоновки следует интерпретировать следующим образом: попадание какой-либо вершины в подграф разбиения говорит о том, что соответствующий элемент ФС должен быть определен в вертикальный ряд БЯ БМК, который соответствует этому подграфу. Дальнейшее размещение элементов ФС, т.е. определение какие именно БЯ будет занимать тот или иной элемент, выполняется алгоритмом размещения, частью входной информации которого являются данные о том, какому ряду принадлежит тот или иной элемент. Таким образом, задача алгоритма размещения - определение местоположения элемента ФС в априорно определенном алгоритмом компоновки ряду БЯ, что является несравненно более простой задачей, чем полное размещение, т.е. размещение элемента ФС в пределах всего кристалла.

Заключительная часть данной главы содержит описание вычислительного эксперимента по компоновке реальной ИС, основанной на БМК. Данная ИС используется в технологическом процессе ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова». Схема содержит 55 элементов, организованных в 6 рядов по 76 БЯ, каждый из которых занимает от одной до двадцати двух БЯ и 86 цепей, соединяющих от двух до девяти элементов. Схема имеет решение задачи компоновки с количество горизонтальных связей равным 40, построенное вручную.

Для схемы была построена математическая модель в виде атрибутированного гиперграфа и решена задача компоновки с применением многоуровневого алгоритма декомпозиции с элементами эволюционно-генетического поиска. Решение, полученное многоуровневым алгоритмом, содержит 14 горизонтальных связей.

Основные результаты:

1. Описан и реализован в виде среды управления гиперграфами ряд понятий и операций над гиперграфами.

2. Представлены различные способы визуализации гиперграфов, выявлены преимущества и недостатки каждого из способов.

3. Предложена и реализована концепция «фильтр-вид», представляющая собой инструмент анализа структурных особенностей гиперграфа и средство упрощения конструирования алгоритмов над гиперграфами.

4. Поставлена задача к-разбиения гиперграфа с минимизацией веса сечения. Для решения задачи разработан и реализован многоуровневый алгоритм декомпозиции гиперграфа.

5. Предложено несколько схем загрубления гиперграфа и алгоритмов улучшения решения в ходе фазы восстановления.

6. Описаны и реализованы общая концепция улучшающего генетического алгоритма, принципы построения и функционирования.

7. Предложена и реализована адаптация улучшающего ГА для оптимизации к-разбиения гиперграфа.

8. Построен многоуровневый алгоритм декомпозиции гиперграфа с использованием улучшающего ГА.

9. Проанализированы некоторые проблемы, возникающие при работе с гиперграфами и использовании концепции «фильтр-вид». Предложены и реализованы способы преодоления таких проблем.

10.Проведен ряд вычислительных экспериментов на тестовых задачах с априорно известными решениями, а так же выполнена компоновка реальной ИС, основанной на БМК, принимающей участие в технологическом процессе ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова». Во всех сериях экспериментов многоуровневый алгоритм декомпозиции гиперграфов показал способность получать приемлемые решения за разумное время, что позволяет сделать вывод о пригодности данного алгоритма для решения реальных задач проектирования ИС.

11.Разработан способ формализации задачи компоновки ИС в задачу декомпозиции гиперграфа. Задача компоновки элементов функциональной схемы по к рядам БЯ БМК сводится к задаче к-разбиения гиперграфа.

Публикации

Публикации в изданиях, рекомендованных ВАК РФ

1) Батищев, Д.И. Оптимальная трехмерная трассировка кабелей по кабельным каналам монтажного шкафа. / Д.И. Батищев, С.Е. Власов, Н.В. Старостин, A.B. Филимонов. //Известия СПбГЭТУ "ЛЭТИ". Серия "Информатика управление и компьютерные технологии", Вып. 1, 2004 г., стр. 3442.

2) Батищев, Д.И. Компоновка радиоэлектронного оборудования по блокам. /Д.И. Батищев, С.Е. Власов, Н.В. Старостин, A.B. Филимонов. //Вестник Нижегородского университета им. Н.И. Лобачевского. Н. Новгород. Изд-во ННГУ им. Н.И. Лобачевского, 2007, стр. 183-189

3) Батищев, Д.И. Многоуровневый генетический алгоритм решения задачи декомпозиции гиперграфа. /Д.И. Батищев, Н.В. Старостин, A.B. Филимонов. //Известия СПбГЭТУ "ЛЭТИ". Серия "Информатика управление и компьютерные технологии", выпуск 2 2007, стр. 3-14.

4) Батищев, Д.И. Многоуровневый алгоритм решения задачи компоновки интегральных схем. /Д.И. Батищев, Н.В. Старостин, A.B. Филимонов. //Научно-технический журнал «Системы управления и информационные технологии», г.Воронеж: Изд-во «Научная книга», 2007, с.48-53

5) Батищев, Д.И. Многоуровневая декомпозиция гиперграфовых структур. /Д.И. Батищев, Н.В. Старостин, A.B. Филимонов. //Прилож. к журналу «Информационные технологии» №5(141) 2008, стр.1 - 32

Публикации в прочих изданиях

6) Батищев, Д.И. Эволюционно-генетический подход к автоматическому распараллеливанию программ. / Д.И. Батищев, Н.В. Старостин, A.B. Филимонов, A.B. Лобанов. //Сборник научных статей юбилейной научно-практической конференции «Математика и кибернетика 2003» факультета ВМК ННГУ и НИИ ПМК, Нижний Новгород: Изд-во ННГУ, 2003 г., стр. 43-48.

7) Filimonov, A.V. Hybrid solving algorithm for uniform graph k-decomposition problem. /A.V. Filimonov, N.V. Starostin. //VI International congress on mathematical modeling/ book of abstract/ September 20-26, 2004, Nizhny Novgorod, University of Nizhny Novgorod, page 353.

8) Старостин, Н.В. Многоуровневый подход к решению задач декомпозиции гиперграфов большой размерности. /Н.В. Старостин, A.B. Филимонов. //Тезисы докладов Всероссийской научно-технической конференции «Информационные системы и технологии» ИСТ-2005, Нижний Новгород, 2005 г., стр. 118-119.

9) Батищев, Д.И. Новый подход к представлению гиперграфовых структур. /Д.И Батищев, С.Е. Власов, Н.В. Старостин, A.B. Филимонов. //Вестник

ВГЛВТ. Межвузовская серия Моделирование и оптимизация сложных систем. Вып. 14, 2005 г., стр. 67-78

10)Филимопов, A.B. О решении задачи трехмерной трассировки кабелей по кабельным каналам монтажного шкафа. /A.B. Филимонов. //Труды НГТУ. Том 64. Радиоэлектронные и телекоммуникационные системы и устройства. Выпуск 11. С.136-140

11)Старостин, Н.В. Аспекты программной реализации гиперграфов. /Н.В. Старостин, A.B. Филимонов.//Сборник научных статей НГТУ 2005 "Информационные технологии", том 56, с. 80-89

12)Старостин, Н.В. Применение генетического алгоритма в многоуровневых схемах. /Н.В. Старостин, A.B. Филимонов. //Материалы конференции «Технологии Microsoft в теории и практике программирования», г.Н.Новгород: Изд-во ННГУ, 2006г, с. 282-284

13)Филимонов, A.B. Эволюционно-генетический подход к построению улучшающих алгоритмов. /A.B. Филимонов. //Информационные системы и технологии ИСТ-2007. Материалы международной научно-технической конференции, посвященной 90-летию Нижегородского государственного технического университета. Изд-во НГТУ, 2007, стр. 209-211

14)Старостин, Н.В. Место задачи компоновки в процессе проектирования БМК. /Н.В. Старостин, A.B. Филимонов. //Материалы конференции «Технологии Microsoft в теории и практике программирования», г.Н.Новгород: Изд-во ННГУ, 2007г, с. 271-274.

Подписано в печать 3.07.2008. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Гарнитура «Тайме». Усл. п. л. 1. Заказ № 514. Тираж 100 экз.

Отпечатано с готового оригинал-макета в типографии Нижегородского госуниверситета им. Н.И. Лобачевского. 603000, г. Н. Новгород, ул. Б. Покровская, 37

Оглавление.

Введение.

Актуальность темы исследований.

Цель работы.

Научная новизна.

Теоретическая и практическая ценность работы.

Апробация результатов.

Глава 1. Методы решения декомпозиционных задач на гиперграфах.

1.1. Постановка задачи разбиения.

1.2 Методы решения экстремальных декомпозиционных задач на гипер графах.

1.2.1 Конструктивные алгоритмы.

1.2.2 Улучшающие алгоритмы.

1.2.3 Использование элементов рандомизации.

Глава 2. Теоретические аспекты гиперграфовых структур.

2.1 Основные определения и понятия.

2.1.1 Гиперграф, вершина, гиперребро.

2.1.2 Визуализация гиперграфа.

2.1.4 Части, подграфы, суграфы и куски.

2.1.5 Связность, компоненты, независимые множества.

2.2. Базовые операции над гиперграфом.

2.2.1 Введение, удаление и стягивание гиперребра.

2.2.2 Введение и удаление вершины из гиперребра.

2.2.3 Введение и удаление вершины.

2.2.4 Удаление частей гиперграфа.

2.2.5 Стягивание множества вершин и отождествление множества гиперребер.

2.2.6 Расщепление вершин и гиперребер.

2.2.7 Бинарные операции над гиперграфами.

2.3. Операции фильтрации и фильтры.

2.3.1 Помеченные гиперграфы.

2.3.2 Операции с атрибутивной информацией.

2.3.3 Фильтр и процесс фильтрации.

2.3.4 Категории (типы) фильтров.

2.4. Виды гиперграфа.

3. Многоуровневый алгоритм декомпозиции гиперграфа.

3.1 Общая схема работы многоуровневого алгоритма декомпозиции.

3.2 Фаза загрубления.

3.2.1 Алгоритм реберного загрубления.

3.2.2 Схема гиперреберного загрубления.

3.2.3 Модифицированная схема гиперреберного загрубления.

3.2.4 Алгоритм построения затрубленного гиперграфа.

3.3 Фаза поиска начального разбиения.61 ч

3.4 Фаза восстановления решения.

3.5 Использование концепции «фильтр-вид» для построения многоуровневого алгоритма декомпозиции.

3.5.1 Фаза загрубления.

2.5.2 Фаза поиска начального разбиения.

3.5.3 Фаза восстановления решения.

3.6 Многоуровневый алгоритм с элементами эволюционно-генетического поиска.

4. Программная реализация.

4.1. Объектно-ориентированная реализация гиперграфовой системы.

4.1.1. Модель работы с гиперграфом.

4.1.2. Объектно-ориентированное представление гиперграфовой структуры.:.

4.1.3. Фильтры и виды гиперграфа.

4.1.4. Повышение производительности работы системы.

4.2 Реализация многоуровневого алгоритма декомпозиции.

4.2.1 Общая структура классов многоуровневого алгоритма декомпозиции.

4.2.2 Конфигурирование многоуровневого алгоритма.

4.2.3 Трудности реализации многоуровневого подхода.

4.2.4 Реализация улучшающего генетического алгоритма.

4.3 Вычислительный эксперимент.

5. Задача компоновки при проектировании полузаказных БИС на основе базовых матричных кристаллов.

5.1. Процессы проектирования БИС.

5.2 Задача компоновки при проектировании БМК.

5.3 Формализация задачи компоновки.

5.4 Вычислительный эксперимент.

Актуальность темы исследований

Проектирование современной радиоэлектронной аппаратуры (РЭА), программных систем и вычислительных комплексов предполагает решение большого количества различных математических задач. Естественно, способность решать такие задачи предполагает наличие соответствующих алгоритмов решения. Однако, зачастую размерности и сложность таких задач настолько велики, что делают невозможным их решение, даже с использованием мощнейшей вычислительной техники. В связи с этим возникла проблема практической разрешимости задач: найти реализуемый, эффективный или хотя бы достаточно простой в практически важных случаях алгоритм ее решения. Подходы, относящиеся к этой категории применимы исключительно к оптимизационным задачам (однако это обстоятельство не является сильным ограничением, поскольку огромное количество прикладных задач естественно формулируются как оптимизационные) и включают прием, который заключается в отказе от поиска оптимального решения и нахождении вместо этого "приемлемого" решения за обозримое время. Методы, применяемые для построения алгоритмов такого типа, сильно зависят от специфики задачи, и хотя на практике оказываются весьма неплохими, для получения удовлетворительных характеристик алгоритма обычно требуется довольно большая работа по его "доводке11. В результате удается только в очень редких случаях предсказать и оценить поведение таких алгоритмов.

Конечно, термин "приемлемые" не сгрог в математическом смысле. Под "приемлемыми" решениями нами понимаются решения, которые удовлетворяют исследователя. Ведь в большинстве реальных задач нет особой необходимости находить именно глобальный оптимум. Чаще всего целью поисков являются решения, удовлетворяющих определенным ограничениям. Например, электрические цепи принципиальной схемы некоторого электронного устройства требуется распределить в непересекающихся слоях, а число таких слоев не должно превышать заданной величины. В этом смысле достаточно найти именно "приемлемые", т.е. разумные решения.

Традиционно, решения задач проектирования РЭА [3, 10, 11, 12, 13, 15, 49, 51, 53, 56, 65, 67, 81, 95, 106, 115, 131, 136, 141] связывают с решением графовых задач. Так, например, при производстве современного электронного оборудования особое место занимает разработка печатных плат [2, 141, 83, 53, 136, 144, 72, 88, 10, 81, 11, 12, 13, 102]. Одной из задач, которая требует решения при их конструировании, является задача разбиения принципиальных схем устройств на составные части (подсхемы, функциональные блоки). Типовые элементы принципиальной схемы должны таким образом быть распределены по отдельным подсхемам, чтобы число внешних соединений было как можно меньше. Это необходимо е целью повышения надежности схемы, уменьшения влияния наводок, повышения технологичности и простоты конструктивного оформления.

При разработке топологии многослойных схем возникает задача распределения "конфликтующих" соединений по отдельным слоям (задача расслоения цепей) [2, 59, 15, 136, 10]. Расслоение до трассировки основано на анализе схемы соединений для выявления тех соединений или их групп, которые не могут быть расположены на одной плоскости из-за неизбежности "сложных" ситуаций трассировки. В частности, усложняется форма соединений, увеличивается их длина, растет время поиска трасс при реализации алгоритма трассировки на ЭВМ.

Кроме того задачи подобного рода возникают при проектировании и управлении вычислительных систем, при сегментации машинных программ, при распределении программ между машинами в вычислительных системах, на транспортных сетях, автоматизации конструкторского синтеза дискретных устройств, при размещении конструктивных элементов на монтажных платах и т.д. [6, 140,2, 138, 109, 18, 135, 143,72, 88, 9, 10, 73, 81,96, 11, 13, 137, 64, 102].

Использование графов при решении такого рода задач часто налагает существенные ограничения, как на математические модели, так и на решающие алгоритмы, что, в конечном итоге, отрицательно сказывается на качестве получаемых решений. Часто более предпочтительным с точки зрения точности моделирования является использование обобщения графов - гиперграфов, поскольку они не только более естественно описывают названные выше инженерные задачи, по и позволяют решать некоторые задачи линейной алгебры и дискретной математики, сведение которых к классическим графам либо невозможно, либо порождает очень сложные модели. Однако, несмотря на значительно более широкие возможности, предоставляемые гиперграфовыми моделями, сложность машинной реализации самих моделей и алгоритмов, работающих над ними, также выше. В этой ситуации особенно остро встает проблема построения алгоритмов, осуществляющий поиск приближенных решений.

Можно выделить два класса подходов решения задач высокой сложности -это упрощение алгоритмов: снижение их математической и инженерной сложности, применение различного вида эвристик, и упрощение решаемых задач. Часто для решения задачи создается метод, который сочетает в себе два этих подхода. Такой метод реализует целый класс алгоритмов, получающий широкое распространение в последнее время — т.н. многоуровневые алгоритмы. Ключевая идея многоуровневого алгоритма состоит следующем: размерность задачи редуцируется путем удаления наименее существенной информации, затем производится поиск решения редуцированной задачи, после этого производится ряд улучшений полученного решения на основе добавления в модель задачи ранее удаленной информации.

Многоуровневые алгоритмы предполагают широкие возможности по настройке алгоритма, поскольку позволяют достаточно легко интегрировать в структуру алгоритма различные эвристики, направленные на улучшение получаемого решения. Не смотря па очевидные достоинства многоуровневых методов, разработка и исследование этого класса алгоритмов применительно к графовым и гиперграфовым моделям у нас в стране - редкое явление. За рубежом такого рода методами занимаются G.Karypis, V.Kumar[66], B.Hendrickson, R.Leland[26], S. Barnard, II. Simon [124] и др.

Еще одним примером способа сокращения вычислительной сложности решающих алгоритмов может служить введение элементов рандомизации. Данное направление дало толчок к развитию методов эволюционных вычислений (подкласс методов случайного поиска), что позволило построить универсальные и достаточно мощные алгоритмы для широкого класса задач. У нас в стране разработкой такого типа алгоритмов занимались JI.A. Растригип[20-24], Ю.И. Неймарк[145, 146], Б.П. Коробков, В.М. Курейчик, A.M. Мелихов, JI.C. Бернштсйн, А.П. Рыжков, Г.И. Орлова, Я.Г. Дорфман, И.Л. Букагова, Д.Б. Юдин и другие. Методы эволюционных вычислений не гарантируют обнаружения оптимального решения. Однако практический интерес к ним не ослабевает, а наоборот усиливается. Объяснить это можно тем обстоятельством, что эти методы позволяют исследовать и находить приемлемые решения таких задач, решение которых при помощи традиционных методов оказывается затруднительным, а в некоторых случаях и просто невозможным.

Синтез многоуровневых и эволюционно-генетических алгоритмов позволяет получать гибкие, легко настраиваемые под каждую конкретную задачу методы, которые позволяют контролировать баланс между качеством решения и вычислительным ресурсом, потраченным на его получение.

Цель работы

Цель работы заключается в создании алгоритма поиска решения задачи к-декомпозиции гиперграфа большой размерности, позволяющий находить решения приемлевого качества за обозримое время. Основу такого алгоритма составляет многоуровневая схема с использованием эволюционио-генетических методов. Такой гибридный алгоритм сочетает в себе скорость и качество поиска решения, характерное для многоуровневых алгоритмов, с высокими способностями исследования области поиска, свойственными генетическим алгоритмам (ГА).

Научная новизна

Разработана концепция «фильтр-вид», предполагающая построение специального вида иерархий гиперграфов на основе атрибутивной информации, содержащейся в них, правила изменения и передачи этой атрибутивной информации, а также методы построения и управления такими иерархиями на основе специальных операторов — фильтров.

Разработана гибридная схема решения задачи k-декомпозиции графа на основе многоуровневого и генетического алгоритма. Предложена методика работы и принципы построения улучшающего ГА в структуре многоуровневого алгоритма. Использование ГА в качестве улучшающего алгоритма, позволяет значительно повысить качество получаемого разбиения вследствие значительно более детального исследования области поиска на каждой из стадий многоуровневого алгоритма.

Предложен метод реализации многоуровневого алгоритма декомпозиции гиперграфа на основе концепции «фильтр-вид», позволяющей автоматизировать частные для многоуровневой парадигмы процессы и сосредоточиться непосредственно на логике решающего алгоритма. Алгоритм позволяет решать задачи достаточно большой размерности за счет ее редуцирования и исследовать обширные области поиска и получать приемлемые результаты за счет применения ГА в сочетании с различными эвристиками, направленными на улучшение качества решения.

Разработана и реализована система машинного представления гиперграфовых структур, а также логика наиболее употребимых при работе с гиперграфами операций. Это позволяет значительно сэкономить время при разработке алгоритмов. Система оформлена в виде библиотеки классов, что делает возможным использовать ее при решении практических и академических задач сторонними пользователями. Исследованы и реализованы различные методики ускорения работы системы представления гиперграфов. Проведены вычислительные эксперименты, подтверждающие эффективность разработанных методов.

Реализована программная система, осуществляющая управление гиперграфами в соответствии с концепцией «фильтр-вид». Предложены и реализованы различные методы повышения быстродействия в сложных иерархиях гиперграфов. Методы системы также доступны для использования сторонними разработчиками.

Предложен метод сведения экстремальной задачи компоновки БИС на основе БМК к задаче k-декомпозиции гиперграфа. Выполнена компоновка конкретного радиоэлектронного устройства.

Теоретическая и практическая ценность работы

В качестве технических приложений класса задач декомпозиции гиперграфов могут выступать реальные технические задачи, возникающие на этапе проектирования сложных электронных систем: задача компоновки типовых модулей по отдельным блокам и задача расслоения цепей. Подобные задачи имеют место как при проектировании, гак и при управлении вычислительными системами, при сегментации машинных программ, при распределении программ между машинами в вычислительных системах, на транспортных сетях, автоматизации различного конструкторского синтеза дискретных устройств и т.д.

Программные системы, реализованные в ходе данной работы, не имеют четкой направленности на представленные в работе задачи и могут быть использованы при решении целого ряда различных проблем, связанных с гиперграфами и многоуровневыми алгоритмами, как практического, так и академического характера.

Апробация результатов

Результаты диссертации докладывались и обсуждались на 6-ом международном конгрессе по математическому моделированию (Н.Новгород, 2004г.), Всероссийской научно-технической конференции «Информационные системы и технологии» ИСТ-2005 (Н.Новгород, 2005г.), конференции «Технологии Microsoft в теории и практике программирования» (Н.Новгород, 2006), Всероссийской научно-технической конференции «Информационные системы и технологии» ИСТ-2007 (Н.Новгород, 2007г.), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Заключение

В диссертационной работе представлен метод решения задач компоновки ИС, основанных на БМК, с использованием многоуровневой парадигмы и эволюционно-генетического подхода.

Описан и реализован в виде среды управления гиперграфами ряд понятий и операций над гиперграфами.

Представлены различные способы визуализации гиперграфов, выявлены преимущества и недостатки каждого из способов.

Предложена и реализована концепция «фильтр-вид», представляющая собой инструмент анализа структурных особенностей гиперграфа и средство упрощения конструирования алгоритмов над гиперграфами.

Поставлена задача k-разбиения гиперграфа с минимизацией веса сечения. Для решения задачи разработан и реализован многоуровневый алгоритм декомпозиции гиперграфа. Предложено несколько схем загрубления гиперграфа и алгоритмов улучшения решения в ходе фазы восстановления.

Описаны и реализованы общая концепция улучшающего генетического алгоритма, принципы построения и функционирования. Предложена и реализована адаптация улучшающего ГА для улучшения k-разбиения гиперграфа. Построен многоуровневый алгоритм декомпозиции гиперграфа с использованием улучшающего ГА.

Предложен способ формализации задачи компоновки ИС в гиперграфовую модель, основанный на установлении соответствия между элементами функциональной схемы и вершинами гиперграфа, цепями и гиперребрами.

Проанализированы некоторые проблемы, возникающие при работе с гиперграфами и использовании концепции «фильтр-вид». Предложены и реализованы способы преодоления таких проблем.

Проведен ряд вычислительных экспериментов на тестовых задачах с априорно известными решениями, а так же выполнена компоновка реальной ИС, основанной на БМК, принимающей участие в технологическом процессе ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова». Во всех сериях экспериментов многоуровневый алгоритм декомпозиции гиперграфов показал способность получать приемлемые решения за разумное время, что позволяет сделать вывод о пригодности данного алгоритма для решения реальных задач проектирования ИС.

1. Зыков А.А. Гиперграфы. Успехи математических наук. 1974. 6(180). С. 89 - 154

2. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Саратов: СГУ, 1983.

3. Филимонов А.В. Об одном алгоритме трехмерной трассировки кабелей по кабельным каналам монтажного шкафа. Межвузовский сборник научных трудов "Прикладные задачи моделирования и оптимизации", Воронеж. 2005 г.

4. Filimonov A.V., Starostin N.V. Hybrid solving algorithm for uniform graph k-decomposition problem. VI International congress on mathematical modeling/ book of abstract/ September 20-26, 2004, Nizhny Novgorod, University of Nizhny Novgorod, page 353.

5. Geoffrion A.M. Lagrangian relaxation and its uses in integer programming. Math. Programming Study 2, 1974, pp. 82-114

6. Iwainsky, A., Canuto, E., Taraszow, O., and Villa, A. Network Decomposition for the Optimization of Connected Structures. Networks 16 (1986), pp. 205-235

7. Кныш A.A. Об эффективности итеративных алгоритмов в задачах разрезания. Автоматизация проектирования средств автоматизации и вычислительной техники. Саратов, 1976, с.21-32

8. Коган А.Я., Файнштейн И.А., Шеймап М.В. Исследование и оптимизация систем программного обеспечения. Автоматика и вычисл. техника, 1976, № 2, с.55-63

9. Максименков А.В., Щорс А.Л. Алгоритм сегментации машинных программ. Автоматика и телемеханика, 1976, № 5, с. 52-60

10. Меликов A.M., Бернштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М: Наука, 1974, 304 с

11. Остапенко А.Г. Анализ и синтез линейных радиоэлектронных цепей с помощью графов: Аналоговые и цифровые фильтры. М: Радио и связь, 1985, 280 с.

12. Петренко А.И. и др. Алгоритмы и методы решения задач технического проектирования электронной аппаратуры с помощью ЭВМ. Автоматизация проектирования в электронике: Республ.межведомственный науч. техн. сборник, вып. 18, 1978, с.3-9

13. Петренко А.И. Тетельбаум А.Я. К вопросу о разбиении большой интегральной схемы па подсхемы. Машинные методы проектир. электронных схем, 1975, 273 с.

14. Pothen A., Simon H.D. and Liou К.Р. Partitioning Sparse Matrices with Eigenvectors of Graphs. Si am J. Matrix Anal. Appl. vol.11, № 3, 1990(jul), pp. 430-452

15. Закраевский А.Д. и др. Приложения теории графов к задачам логического проектирования дискретных устройств. Исследования по прикладной теории графов. Новосибирск: Наука, 1986

16. Aspvall В., Gilbert J. R. Graph coloring using eigenvalue decomposition, SIAM J. Alg. Disc. Meth., № 5, 1984, pp. 526-538

17. Bette Bultena, Frank Ruskey. "Venn Diagrams with Few Vertices", 1998.

18. Коробков Б.П. Методы разрезания графов на минимально связанные подграфы и их использование в задачах адаптивной обработки информации. В кн.: Адаптация в вычислительных системах. Рига: Зинатне, 1978, вып.4, с. 107-129

19. Коробков Б.П., Подкорытов М.П. Рандомизированная оптимизация системы интерфейсных модулей. В кн.: Системы автоматизации научных исследований. Рига: Зинатне, 1980, вып.4, с.6-17

20. Коробков Б.П., Растригин JI.A. Рандомизированные методы разрезания графов. Часть 1. Изв. АН СССР. Техническая кибернетика, № 3, 1982, с. 163-172

21. Коробков Б.П., Растригин JI.A. Рандомизированные методы разрезания графов. Часть 2. Изв. АН СССР. Техническая кибернетика, № 4, 1982, с. 120-126

22. Коробков Б.П., Растригин JI.A. Глобальный рандомизированный алгоритм разрезания графов. В кн.: Структурная адаптация многомашинных систем обработки информации, Рига: Зинатне, 1978, с.56-62

23. Коробков Б.П., Растригин JI.A. Метод адаптивного разрезания графов и его использование в задаче сегментации. В кн.: Системы автоматизации научных исследований. Рига: Зинатне, 1980, вып.4, с.52-63

24. Коробков Б.П., Растригин JI.A. Рандомизированные алгоритмы агрегации графов. В сборнике "Адаптация в вычислительных системах". Рига: Зинатне, 1978, вып.4, е.6-20

25. В. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291-307, 1970.

26. Bruce Hendrickson, Robert Leland. "A Multilevel Algorithm for Partitioning Graphs", 1993

27. Hendrickson В., Leland R. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J.Sci.Comput., Vol.16, № 2, 1995, pp. 452-469

28. C. J. Alpert and A. B. Kahng. Multi-way partitioning via space-filling curves and dynamic programming. In Proc. of the Design Automation Conference, pages 652-657, 1994.

29. Charles J. Alpert and Andrew B. Kahng. Recent directions in netlist partitioning. Integration, the VLSI Journal, 19(1-2):1-81, 1995.

30. C. J. Alpert, J. H. Huang, and A. B. Kahng. Multilevel circuit partitioning. In Proc. of the 34th ACM/IEEE Design Automation Conference, 1997.

31. Ashcraft C., Liu J.W.H. Applications of Dulmage-Mendelsohn decomposition and network flow to graph bisection improvement. Technical Report CS-96-05, York University, Dept. of Computer Science, York University, North York, Ontario, Canada, August 1996

32. Farhat C. A simple and efficient automatic FEM domain decomposer. Computers and Structures, Vol. 28, № 5, 1988, pp. 579-602

33. Farhat C., Lesoinne M. Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics. Internat. J. Numer. Meth. Engrg., Vol. 36,№5, 1993, pp.745-764

34. С. М. Fiduccia and R. M. Mattheyscs. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175-181, 1982.

35. Ou C.W., Ranka S. Parallel remapping algorithms for adaptive problems. Technical Report CRP,C-TR94506, Center for Research on Parallel Computation, Rice University, 1994

36. Ozturan C., deCougny H.L., Shephard M.S., Flaherty J.E. Parallel adaptive mesh refinement and redistribution on distributed memory computers. Computer Methods in Applied Mechanics and Engineering, Vol. 119, 1994, pp. 123-137

37. C. W. Yeh, С. K. Cheng, and Т. T. Lin. A general purpose multiple-way partitioning algorithm. In Proc. of the Design Automation Conference, pages 421-426, 1991.

38. Батпщев Д.И. Генетические алгоритмы решения экстремальных задач. Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995, 64 с.

39. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984

40. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский гос.университет, 1994

41. Батищев Д.И., Старостин II.B. k-разбиение графов. Вестник ННГУ "Математическое моделирование и оптимальное управление", Н.Новгород, 2000 г., стр. 37-25.

42. Батищев Д.И., Старостин Н.В. Оптимальное k-разбиение графов. Н.Новгород. Тезисы докладов. XII международная конференция "Проблемы теоретической кибернетики", 1999 г., стр.22-23.

43. Батищев Д.И., Старостин Н.В. Применение генетических алгоритмов к решению задачи дихотомического разбиения графа. Воронеж. Межвузовский сборник н. трудов "Оптимизация и моделирование в автоматизированных системах", 1998 г., стр.3 10.

44. Батищев Д.И., Старостин Н.В. Способы повышения эффективности генетического поиска оптимального k-разбиения графа. Воронеж. Межвузовский сборник науч. трудов "Прикладные задачи моделирования и оптимизации", 2000 г., Часть 2, стр. 4-17.

45. Д.И. Батищев, Н.В. Старостин, А.В. Филимонов. Многоуровневый генетический алгоритм решения задачи декомпозиции гиперграфа. Известия СПбГЭТУ "ЛЭТИ". Серия "Информатика управление и компьютерные технологии"

46. Д.И. Батищев, Н.В. Старостин, А.В. Филимонов. "Многоуровневый алгоритм решения задачи компоновки интегральных схем". "Системы управления и информационные технологии", г.Воронеж, 2007г

47. Батищев Д.И., С.А. Исаев, Старостин Н.В., Неймарк Е.А., Ремср Е.К. Вопросы визуализации при решении экстремальных задач с помощью ГА. Тезисы докладов.

48. Всероссийская научно-практической конференции "Компьютерная геометрия и графика", Н.Новгород, НГТУ, 1998г., стр. 101-102.

49. Батищев Д.И., Власов С.Е., Старостин Н.В., Филимонов А.В. Оптимальная трехмерная трассировка кабелей по кабельным каналам монтажного шкафа. Известия СПбГЭТУ "ЛЭТИ". Серия "Информатика управление и компьютерные технологии", Вып. 1, 2004 г., стр. 34-42.

50. Батищев Д.И., Власов С.Е., Старостин Н.В., Филимонов А.В. Новый подход к представлению гиперграфовых структур. Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем. Вып. 14, 2005 г., стр. 67-78

51. Батищев Д.И., Власов С.Е., Старостин Н.В., Филимонов А.В. Компоновка радиоэлектронного оборудования по блокам. Вестник Нижегородского унверситета им. Н.И. Лобачевского. 1. Н. НовогородЖ Изд-во НПГУ им. Н.И. Лобачевского, 2007, стр. 183-188

52. Батищев Д.И., Кириллов С.В., Старостин Н.В. Дихотомическое разбиение мультиграфов. Воронеж. Тезисы докладов. Всероссийское совещанис-семинар "высокие технологии в региональной информатике", 1998 г.

53. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Воронеж: Издательство Воронежского государственного университета, 1997

54. Johnson D.E., Aragon C.R., McGoech L.A., Schevon С. Optimization by simulated annealing: an experimental evaluation; Part I, Graph Partitioning. Operations Research. Vol.37, № 6, 1998, pp. 865-892

55. Moore, D. A Round-Robin Parallel Partitioning Algorithm. Tech. Rep. 88-916, Cornell University, 1988

56. D. G. Schweikert and B.W. Kernighan. A proper model for the partitioning of electrical circuits. In Proc. ACM/IEEE Design Automation Conference, pages 57-62, 1972.

57. Spielman D.A., Teng S.H. Spectral partitioning works: Planar graphs and finite element meshes. Technical Report CSD-96-989, U.C. Berkley, February 1996. extended abstract in Proc. 37. IEEE Conf. Foundations of Сотр. Sci., 1996.

58. Barnes E.R., Vannelli A., Walker J.Q. A New Heuristic for Partitioning the Nodes of a Graph. SIAM Journal of Discrete Mathematics. Vol.1, № 3, 1988(aug), pp. 299-305

59. Гринберг Э.Я., Илзиня И.Г. О раскраске вершин неориентированных графов. Автоматика и вычислительная техника. Рига. 1964, вып.7, с. 143-153

60. Е. Gamma, R. Helm, R Johnson, J.Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Reading, Mass. : Addison-Wesley, 1995

61. Rolland E., Pirkul H., Glover F. Tabu search for graph partitioning. Ann. Oper. Res., Vol. 63, 1996, pp. 209-232

62. Darema F., Kirkpatrick S., Norton V.A. Parallel Algorithms for Chip Placement by Simulated Annealing. IBM Journal of Research and Development, vol.31, № 3, 1987(may), pp. 391-401

63. Glover F. Tabu search part I,II. ORSA J. Comput., Vol. 1-2, 1989(90), pp. 190-206, 4-32

64. Роберте Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экономическим задачам. М.: Наука, 1986

65. Бутыдьский Ю.Г., Брунченко А.В. Алгоритм разрезания двудольного графа для построения цифровых устройств на основе больших интегральных схем. Автоматика и вычислительная техника, 1976, № 4, с.72-76

66. George Karypis, Vipin Kumar. "Parallel Multilevel Graph Partitioning", 1995

67. George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of the Design and Automation Conference, 1997.

68. G. Karypis and V. Kumar. hMETIS 1.5: A hypergraph partitioning package. Technical report, Department of Computer Science, University of Minnesota, 1998

69. G. Karypis and V. Kumar. Multilevel algorithms for multi-constraint graph partitioning. In Proceedings of Supercomputing, 1998.

70. George Karypis and Vipin Kumar."Multilevel k-way Hypergraph Partitioning"

71. Schloegel K., Karypis G., Kumar V. Multilevel diffusion schemes for repartitioning of adaptive meshes. Technical Report 97-013, University of Minnesota, Department of Computer Science, 1997

72. Липатов Г.П. Теория графов и ее применение. М: Зииатне, 1986, 32 с.

73. Моисеенко Г.В. Оптимальное разбиение систем на подсистемы. Автоматика и телемеханика, 1979, №7, с.103-107

74. Орлова Г.И., Доффман Я.Г. Оптимальное деление графа на несколько подграфов. Известия АН СССР. Техническая кибернетика, 1972, № 1, с.118-121

75. Шилдт Г. Полный справочник по С#. М:. Изд. «Вильяме».

76. Шилдт Г. С#, учебный курс. М:. изд. «bhv».

77. Schaffer J.D. Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of an International Conference on GA and Their Applications, pp. 93-100.

78. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985

79. Horst D. Simon and Shang-IIua Teng. How good is recursive bisection? Technical Report RNR-93-012, NAS Systems Division, NASA, Moffet Field, CA, 1993.

80. Hall К. M. An r-dimensional quadratic placement algorithm, Management Science, Vol. 17, 1970, pp. 219-229

81. Морозов K.K., Мелихов A.H., Бернштейн Л.С. Методы разбиения РЭА на конструктивно законченные части. М.: Советское радио, 1974, 304 с.

82. Kirk Schloegel, George Karypis, and Vipin Kumar. "Graph Partitioning for High Performance Scientific Simulations", 2000.

83. Абрайтис Л.Б. Шимайтис А.П. Алгоритмы компоновки узлов и исследование их эффективности. Вычислительная техника, вып.З, Том 2, Каунас, 1971, с.66-76

84. Laszewski G. Intelligent structural operators for the k-way graph partitioning problem. In Proc. Fourth Int. Conf. Genetic Algorithms, 1991, pp. 45-52

85. Laszewski G. A collection of graph partitioning algorithms. Northeast Parallel Architectures Center at Syracuse University. Technical Report NY 13244-4100, 1993 (may)

86. Laszewski, G. A Genetic Algorithm for the Graph Partitioning Problem. Master's thesis, University of Bonn, Nov., 1990

87. Laszewski, G. Object Oriented Recursive Bisection on the CM-5. Tech. Rep. SCCS 476-477, Northeast Parallel Architectures Center at Syracuse University, April 1993

88. Липатов Г.П. Теория графов и ее применение. М: Зинагне, 1986, 32 с.

89. Марин Л.Ф., Бойченко Е.В., Сурначев Д.В., Шестопалова О.В. Государственная автоматизированная система "Выборы" по Москве (о решении задачи оптимальной нарезки избирательных округов). Ж.КомпыоЛог, № 4, М., 1997

90. Miller G.L., Teng S.H., Thurston W., Vavasis S.A. Automatic mesh partitioning. In Graph Theory and Sparse Matrix Computation. The IMA Volumes in Mathematics and its Applications, Springer Verlag, Vol. 56 of, 1993, pp. 57-84

91. L. A. Sanchis. Multiple-way network partitioning. IEEE Transactions on Computers, pages 62-81, 1989.

92. L. A. Sanchis. Multiple-way network partitioning with different cost functions. IEEE Transactions on Computers, pages 1500-1504, 1993.

93. Гарусин М.И., Каплипский А.И. О формировании адаптивных алгоритмов оптимизации псевдобулевых функций на основе метода локального улучшения. Автоматика и телемеханика, 1976, № 9, с.96-104

94. Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи, М.: Мир, 1982.

95. Морозов К.К., Мелихов А.Н., Бернштейн Л.С. Методы разбиения РЭА на конструктивно законченные части. М.: Советское радио, 1974.

96. Моисеенко Г.В. Оптимальное разбиение систем на подсистемы. Автоматика и телемеханика, 1979, №7, с. 103-107

97. М.Ф. Пономарев, Б.П. Коноплев. Микроэлектроника: Учеб. Пособие для ВУЗов. М.: Высшая школа, 1987 г.

98. Бурков В.II., Гроппен В.О. Решение задачи о минимальном разрезе в бисвязном орграфе алгоритмами типа ветвей и границ. Автоматика и телемех., 1974, № 9, с.104-110

99. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978

100. Старостин Н.В. Эволюционно-генетический подход для решения экстремальных задач на графах. Н.Новгород. ННГУ. Конференция "Вычислительная математика и кибернетика 2000", 2000 г. (ноябрь), стр. 64.

101. Селютин Н.И. Разбиение микромодульных схем. Изв. Северо-Кавказ. Научный центр высшей школы, Сер. Технических наук, 1975, № 5, с.13-18

102. Старостин Н.В., Филимонов А.В. Аспекты программной реализации гиперграфов. Сборник научных статей НГТУ 2005 "Информационные технологии", том 56, с. 80-89

103. Старостин П.В., Филимонов А.В. Применение генетического алгоритма в многоуровневых схемах. Материалы конференции "Технологии Microsoft в теории и практике программирования", г.Н.Новгород: Изд-во ННГУ, 2006г, с. 282-284

104. Н.В. Старостин, А.В. Филимонов. "Место задачи компоновки в процессе проектирования БМК". Материалы конференции "Технологии Microsoft в теории и практике программирования", г.Н.Новгород: Изд-во ННГУ, 2007г

105. Старостин Н.В., Дроздова Е.П. Выделение двудольного графа. Воронеж. Тезисы докладов на Всероссийскую конференцию "Интеллектуальные информационные системы", 1999 г., стр. 72.

106. Navaratnasothie Selvakkumaran and George Karypis. "Multi-Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization", 2005

107. Загоруйко Н.Г., Скоробогатов B.A., Хворостов П.В. Вопросы анализа и распознавания молекулярных структур на основе общих фрагментов. Алгоритмы анализа структурной информации: Вычислительные системы. Новосибирск: ИМ СО АН СССР, 1984, вып. 103, с.26-50

108. Ciarlet P., Lamour J., Lamour F. Recursive partitioning methods and greedy partitioning methods: a comparison on finite element graphs. Technical Report CAM 949, UCLA, 1994

109. P. Chan, M. Schlag, and J. Zien. Spectral k-way ratio-cut partitioning and clustering. In Proc. of the Design Automation Conference, pages 749-754, 1993.

110. Kadluczka P., Wala K. Tabu search and genetic algorithms for the generalized graph partitioning problem. Control and cybernetics, vol. 24, № 4, 1995, pp. 459-476

111. Липатов Г.П. Теория графов и ее применение. М: Зинатне, 1986, 32 с.

112. Sadayappan P., Ercal F., Ramanujam J. Cluster Partitioning Approaches to Mapping Parallel Programs Onto a Hypercube. Department of Computer and Information Science, Ohio State University. 1988

113. Suaris P., Kedem G. An algorithm for quadrisection and its application to standard cell placement, IEEE Transactions on Circuits and Systems, № 35, 1988, pp. 294-303

114. Рыжков А.П. Алгоритм разбиения графа на минимально связанные подграфы. Известия АН СССР. Техническая кибернетика, 1975, № 6, с. 122-128

115. Рейнгольд Э., Мивергельд Ю., Део М. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980

116. Boppana R. В. Eigenvalues and graph bisection: an average case analysis, in 28th Annual Symp. Found. Сотр. Sci, 1987, pp. 280-285

117. Diekmann R., Monien В., Preis R. Using helpful sets to improve graph bisections. Technical Report TR-RF-94-008, Dept. of Сотр. Science, University of Paderborn, 1994

118. Leland R., Hendrickson B. An empirical study of static load balancing algorithms. In Proc. Scalable High-Performance Comput. Conf., 1994, pp. 682-685

119. Diekmann R., Luling R., Monien В., Spraner C. Combining helpful sets and parallel simulated annealing for the graph-partitioning problem. Parallel Algorithms and Applications, vol. 8, 1996, pp. 61-84

120. Williams R.D. Performance of dynamic load balancing algorithms for unstructured mesh calculations. Concurrency: Practice and Experience, Vol. 3, № 5, 1991, pp. 457481

121. Stephen T. Barnard, Horst D. Simon. "A Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems", 1994

122. Bokhari S.H., Crockett T.W., Nicol D.M. Parametric binary dissection. Technical Report 93-39, Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, 1993

123. Dutt S. New faster Kernighan-Lin-type graph partitioning algorithms. In Proc. IEEE Intl. Conf. Computer-Aided Design, 1993, pp. 370-377

124. Kirkpatrick, S. Optimization by Simulated Annealing: Quantitative Studies. Journal of Statistical Physics 34 (1984), pp. 975-986

125. Lin S. Heuristic programming as an aid to network design, Networks 5, 1975, pp. 33-43

126. С. Мурога. Системное проектирование сверхбольших интегральных схем. Кн.2. М.: Мир, 1985г.

127. Бернштейн JI.C., Селянкин В.В. О минимальном разрезании графов со взвешенными ребрами. Электронная техника. Сер.9. АСУ, 1976, вып.4(20), с.96-106

128. Sverre Wichlund and Einar J. Aas. On Multilevel Circuit Partitioning. In Intl. Conference on Computer Aided Design, 1998.

129. Bui T.N., Heigham С., Jones С., Leighton Т. Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms. 26th |DAC|. ACM/IEEE. 1989, pp. 775-778

130. Hu Т.Е. Integer Programming and Network Flows. Addison-Wesley. Reading, 1969

131. Магрупов T.M. Графы, сети алгоритмы и из применения. Ташкент: Фан, 1990, 120 с.

132. Фещенко В.П., Матюшков Л.П. Итерационный алгоритм разрезания графа на к подграфов. Автоматизация проектирования сложных систем, Минск, 1976, вып.2, с. 74-77

133. Курейчик В.М., Калашников В.А., Лебедев Б.К. Автоматизация проектирования печатных плат. Изд.ростовского университета, 1984, 80 с.

134. Попков В.К. О решении некоторых задач на сверхбольших графах. Моделирование на вычислительных системах. СМ-3, Новосибирск: ВЦ СО АН СССР, 1982. с. 93-106

135. Попков В.К., Кауль С.Б., Нечепуренко М.И. и др. Методы оптимизации структур зоновых сетей связи Новосибирск: ВЦ СО АН СССР, 1983

136. Визинг В.Г. Сводимость ряда задач теории графов к задаче о минимальной связке. Вычислительная математика и вычислительная техника, 1971, вып.2, с.52-55

137. Donath W.E., Hoffman A.J. Lower Bounds for the Partitioning of Graphs.{IBM} Journal of Research and Development, vol.17, 1973, pp. 420—425

138. Kordes U.R. Formulation and solution of circuit card design problems through use of a graph methods. Advances in Electronic Circuit packaging. Vol.2, № 7, 1962

139. Faigle, U., and Schrade, R. Simulated Annealing Eine Fallstudie. Angewandte Informatik, № 6, 1988(June), pp. 259-263

140. Chung Y.C., Yeh Y.J., Liu J.S. A parallel dynamic load-balancing algorithm for solution-adaptive finite element meshes on 2D tori. Concurrency: Practice and Experience, Vol. 7, № 7, 1995, pp. 615-631

141. Ландау И.Я. Применение ЦВМ для проектирования ЦВМ. М.: Энергия, 1974

142. Неймарк Ю., Григоренко В., Рапоппорт А. Исследования одной модели коллективного поведения. Изв. ВУЗов. Радиофизика, 1970, № 8

143. Неймарк Ю., Григоренко В., Рапоппорт А. Об оптимизации независимыми детерминированными и стохастическими автоматами. В кн.: Прикладная математика и кибернетика. Горький: Изд-во ГГУ, 1967