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

• Филимонов, Андрей Викторович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Филимонов, Андрей Викторович

Оглавление.

Введение.

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

Цель работы.

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

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

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

Глава 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-разбиения гиперграфа. Построен многоуровневый алгоритм декомпозиции гиперграфа с использованием улучшающего ГА.

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

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

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

Список литературы диссертационного исследования кандидат технических наук Филимонов, Андрей Викторович, 2008 год

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