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

• Дуккардт, Александр Николаевич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Дуккардт, Александр Николаевич

ВВЕДЕНИЕ.

1 АНАЛИЗ АЛГОРИТМОВ И МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ РАЗБИЕНИЯ СХЕМ.

1.1 Анализ и выбор математической модели.

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

J .3 Анализ существующих алгоритмов разбиения.

1.4 Выводы.

2 РАЗРАБОТКА БАЗОВЫХ МЕТОДОВ ГЕНЕТИЧЕСКОГО ПОИСКА

ДЛЯ ЗАДАЧИ РАЗБИЕНИЯ СХЕМ.

2.1 Отличие методов генетического поиска от других методов оптимизации

2.2 Структура генетического алгоритма.

2.3 Кодирование информации для задачи разбиения схем.

2.3.1 Структура хромосом и принципы декодирования на основе назначения гиперребер в узлы.

2.3.2 Структура хромосом и принципы декодирования на основе рекурсивного применения процедуры дихотомического разбиения.

2.4 Генетические операторы.

2.5 Выводы.

3 РАЗРАБОТКА КОМПЛЕКСНОГО ГИБРИДНОГО

ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗБИЕНИЯ СХЕМ.

3.1 Структурная схема комплексного гибридного генетического алгоритма разбиения схем.

3.2 Блок генерации начальной популяции.

3.3 Блок модифицированных Генетических Операторов.!.

3.4 Блок анализа преждевременной сходимости и критерия остановки алгоритма.

3.5 Блок локального улучшения решений.

3.6 Блок альтернативного декодирования решений.

3.7 Блок адаптации генетического поиска.

3.8 Теоретические оценки алгоритма.

3.9 Выводы.

4 РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ И

ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА РАЗБИЕНИЯ ЭЛЕМЕНТОВ СБИС.

4.1 Цель вычислительного эксперимента.

4.2 Планирование вычислительного эксперимента.

4.3 Результаты вычислительного эксперимента.

4.4 Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование комплексного гибридного генетического алгоритма разбиения схем»

Современный этап развития человеческой цивилизации, характеризующийся высокими темпами роста развития науки и техники, нелегко представить без использования изделий микроэлектронной промышленности в повседневной жизни. Использование различных достижений микроэлектроники при производстве интегральных схем (ИС), больших ИС (БИС), сверхбольших ИС (СБИС), суперкристаллов, обуславливает повышение основных характеристик электронных вычислительных средств (ЭВС) проектируемых на их основе, например, снижаются массогабаритные показатели, уменьшаются потребляемая и рассеиваемая мощности, повышаются быстродействие и надёжность[1 -3]. Современные ЭВС, такие как, персональные компьютеры, оборудование вычислительных и специальных пользовательских сетей, контроллеры и другие управляющие устройства и системы содержат в своём составе десятки, а иногда и сотни СБИС[3]. Однако к характеристикам ЭВС предъявляются неоднозначные требования в зависимости от класса и назначения аппаратуры, использующей СБИС и суперкристаллы. Какая-то из характеристик или их совокупность могут быть определяющими, тогда как требования к остальным снижаются. К примеру, в аппаратуре с автономным питанием потребляемая мощность микросхем должна быть как можно меньшей по сравнению с мощностью аналогичных изделий, используемых в стационарных радиоэлектронных средствах (РЭС). В бытовой же аппаратуре компоненты со сверхвысоким быстродействием (электронные цифровые часы, калькуляторы, игрушки) использовать ни к чему.

Развитие микроэлектроники происходило поэтапно: малые схемы, средние, большие, сверхбольшие. Первые ИС представляли собой объединение транзистора с набором сопротивлений и выполняли какую-либо логическую функцию. Степень интеграции постоянно возрастает с момента изобретения ИС. Применение на этапе проектирования различных САПР способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом [4-6]. Эта тенденция была сведена в закон Гордоном Муром[7]. Сегодня СБИС способны выполнять сложнейшие наборы функции, а геометрические размеры транзисторов сократились до 0.18 микрона и меньше! В настоящее время промышленностью выпускается широкая номенклатура СБИС, суперкристаллов, содержащих миллионы элементов на кристалле 25x25мм. Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, • предназначенной для активных элементов. В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя- металлизации, около 40% площади отводится под межсоединения. Кроме того, рост числа транзисторов на кристалле, увеличивает также и средние размеры кристаллов.

Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [8, 9, 10]. Сейчас, на всех стадиях проектирования топологии схем интенсивно используют средства автоматизации проектирования (САПР) и многие фазы могут быть полностью или частично автоматизированы. Важнейшим этапом в цикле проектирования схем, является этап конструкторского проектирования, на котором решаются задачи разбиения, планирования, размещения, трассировки, упаковки, верификации [9].

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

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

Задачей размещения является определение конкретного места ' для каждого блока на кристалле. ' '

Трассировка заключается в конструктивной реализации связей между элементами.

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

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

В своей многочисленной массе разработанные алгоритмы, программы и пакеты в САПР предназначены для оптимального решения задач разбиения, размещения разногабаритных объектов (формирования базового плана кристалла) и межблочной трассировки межсоединений по критерию минимизации занимаемой площади и длины связей [13, 14, 15, 16]. В связи с большой сложностью и размерностью задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач. Поскольку даже в условиях современного развития информационных технологий, многие алгоритмы не справляются с решением или требуют много процессорного времени для поиска решений. С точки зрения повышения эффективности САПР, представляет интерес разработка новых алгоритмов и методов проектирования, для -так называемых NP-полных задач, в которых нахождение оптимального решения возможно только полным перебором и которые являлись бы достаточно эффективными как с точки зрения точности и оптимальности получаемых решений, так и с позиции времени работы. К таким можно отнести методы эволюционного моделирования, которые были разработаны, как новое направление, в начале 1970 гг., но только сейчас приобрели приоритет в отношении других методов. Сравнительно недавно, их начали широко применять для решения задач в самых различных областях [17, 18, 19, 20], в том числе для решения задач проектирования СБИС, поскольку эти методы способны обрабатывать множество решений при учёте множества критериев [21-29]. Данными свойствами обладают генетические алгоритмы (ГА) - поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Основная цель ГА - абстрактно и формально объяснить адаптацию процессов в естественных системах и спроектировать искусственные программные системы, которые содержат основные механизмы естественных систем. Основная тема поиска ГА - поиск баланса между эффективностью и качеством для "выживания" в различных условиях. Главные отличия ГА от других оптимизационных и поисковых процедур следующие: осуществляют поиск из множества точек, а не из единственной точки; используют целевую функцию, а не её различные приращения; для оценки получаемой информации используют не детерминированные, а вероятностные правила; дают не одно решение, а целый спектр решений, из которых возможно выбрать наилучшее, с точки зрения поставленной задачи. Пожалуй, одним из главных свойств ГА является, то что, они достаточно легко преодолевают локальные оптимумы в силу своей "природы". Гибкость структуры ГА, возможность её настройки и перенастройки дают возможность создания структур, обеспечивающих получение наилучшего результата за приемлемое время. Это, в свою очередь, предоставляет исследователям широчайшие возможности, для поиска альтернативных решений в этом направлении.

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

ЦЕЛЬЮ диссертационной работы является исследование и разработка комплексного гибридного генетического алгоритма разбиения схем с учетом числа межузловых связей и общей временной задержки, позволяющего повысить качество разбиения схем.

Для достижения поставленной цели в работе были решены следующие основные задачи: t

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

2. Построена архитектура генетического поиска для решения задачи разбиения схем.

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

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

5. Построены модифицированные генетические операторы.

Для решения поставленных задач использовались следующие МЕТОДЫ ИССЛЕДОВАНИЙ: элементы теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска, параллельного и объектно-ориентированного программирования. НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

1. Построена архитектура генетического поиска для решения задачи разбиения схем.

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

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

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

НАУЧНЫЕ РЕЗУЛЬТАТЫ работы представляют:

1. новая архитектура комплексного гибридного генетического алгоритма для решения задачи разбиения схем;

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

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

4. новые технологии и средства повышения эффективности выхода из "локальных ям" и снижения общего времени поиска квазиоптимальных решений;

5. новые и усовершенствованные операторы генетического поиска обеспечивающие снижение времени поиска.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

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

3. Комплексный Гибридный Генетический алгоритм и программа для разбиения схем.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».

Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин: «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

Работа выполнена в рамках приоритетного национального проекта «Образование».

АПРОБАЦИЯ основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Всероссийских и Международных научно-технических конференциях: «Интеллектуальные САПР», (г. Таганрог, 2003 - 2005 гг.); VII Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», (г. Таганрог, 2004г.); II Всероссийская научная конференции молодых ученых, аспирантов и студентов

Информационные технологии, системный анализ и управление», (г.

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

ПУБЛИКАЦИИ. По теме диссертации опубликовано 6 печатных работ. СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, и списка использованных источников. Работа содержит 139 стр., включая 38 рис., 17 табл., список использованных источников из 103 наименований, 12 стр. приложений и актов об использовании. СОДЕРЖАНИЕ РАБОТЫ.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Дуккардт, Александр Николаевич

4.4 Выводы

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

2. Сформулированы цели выполнения экспериментальных исследований; составлен план проведения и выполнены серии экспериментов; произведена статистическая обработка экспе]риментальных данных, что позволило уточнить теоретические оценки ВСА и ПСА алгоритма разбиения, подтвердившие, в целом, ранее полученные теоретические оценки. Полученные экспериментальные данные и их статистическая обработка позволили определить характер зависимости времени и памяти от количества вершин гиперграфа (примерно квадратичная). Проведенные исследования позволили получить ответы на вопросы прикладного характера, а также адекватно оценить разработанный алгоритм.

3. Проведены серии тестов и экспериментов и выполнена обработка экспериментальных данных.'

4. Подтверждена гипотеза использования стратегии «Эволюция - Эволюция» для задачи разбиения схем с учетом временных задержек и числа межмодульных связей. При использовании данной стратегии поиска требуется в среднем на 50% больше процессорного времени, но в то же время, при этом алгоритм находит в среднем на 15,5% лучшее решение, чем при использовании поиска на основе стратегии «Эволюция».

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

ЗАКЛЮЧЕНИЕ

• В результате выполненных теоретических и практических исследований по теме диссертационной работы реализованы следующие научные и практические положения:

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

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

3. Для повышения качества решений, были разработаны методы кодирования использующие знание о решаемой задачи, что позволило повысить качество получаемых решений на начальном этапе работы алгоритма. Созданы модифицированные процедуры, для генетических операторов, зависящие от динамических параметров, позволяющие повысить устойчивость генетического поиска и качество получаемых решений. Теоретически определена оценка пространственной сложности алгоритма, вычислительной сложности применяемых генетических операторов и алгоритма в целом. Оценка ПСА составляет 0(n ), а ВСА модифицированных процедур для генетических операторов и разработанного алгоритма составляет не выше 0(п2), что в целом ниже либо равно ВСА многих из существующих равнозначных методов.

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

5. Выполнены тестирование и обработка экспериментальных данных, что позволило уточнить теоретические оценки временной сложности разработанных алгоритмов размещения. Проведённые комплексные исследования показали улучшение работы алгоритма по сравнению с ПГА от 3% до 7% в зависимости от вида задачи. В задачах с числом-элементов более 100, разработанный алгоритм по качеству получаемых решений, выглядел значительно лучше. По - сравнению с существующими алгоритмами, разработанный алгоритм, имеющий практическую реализацию, в некоторых случаях достигал улучшения, позволяющие сократить сроки проектирования до 15%.

6. Разработано программное обеспечение, приведено его описание для изучения характеристик алгоритма (экспериментального тестирования), разбиения схем. При создании программ использовался пакет Visual Studio 2005 для 32-разрядных ОС семейства Windows® 9х, а отладка, тестирование и эксперименты поводились на IBM® совместимом компьютере с процессором AMD Athlon-64® 3000+ и оперативной памятью 512 MB DIMM РС-3200.

Для адекватного сравнения программного обеспечения использовались стандартные оценки производительности различных систем, представленные фирмой Intel [75].

Проведённые комплексные исследования показали улучшение работы алгоритма по сравнению с ПГА от 3% до 7% в зависимости от вида задачи. В задачах с числом элементов более 100, разработанный алгоритм по качеству получаемых решений, выглядел значительно лучше. По сравнению с существующими алгоритмами, разработанный алгоритм, имеющий практическую реализацию, в некоторых случаях достигал улучшения, позволяющие сократить сроки проектирования до 15%.

Список литературы диссертационного исследования кандидат технических наук Дуккардт, Александр Николаевич, 2007 год

1. Конструирование аппаратуры на БИС и СБИС. Под ред. Высоцкого Б.Ф. и Стерепского В.П. М.: Радио и связь, 1989.

2. Петренко А.И., Лошаков В.Н., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизированное проектирование СБИС на базовых кристаллах. М.: Радио и связь, 1988. 160 е., ил.

3. Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем. Москва, Высшая школа, 1989.

4. Dominic A. Antonelli, Danny Z. Chen, Timothy J. Dysart, Xiaobo S. Hundrew, B. Kahng Peter, M. Kogge Richard, C., Murphy Michael, T. Niemier, "Quantum-Dot Cellular Automata (QCA) Circuit Partitioning: Problem Modeling and Solutions", DAC, 2004 .

5. Гладков Л.А., Курейчик В.В., Курейчик В.М. .Дискретная математика. Часть 2. Теория алгоритмов и алгебра логики: Учебное пособие. Под ред. В.М. Курейчика. Таганрог: Изд-во ТРТУ, 2006. -152 с.

6. Норенков И.П. Основы автоматизированного проектирования. М.: Изд-во МГТУ имени Н.Э.Баумана, 2006.-360с.

7. Schaller Robert R. MOORE IS LAW: past, present, and future. IEEE SPECTRUM JUNE, 1997, pp. 53-59.

8. Деньдобренко Б.П., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 1980. 384 с.

9. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. Москва, Радио и связь, 1990. 352 е.: ил.

10. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Norweil, Kluwer Academic Publishers, 1995, 538 p.

11. Горинштейи Л.Л. О разрезании графа. Известия АН СССР, Техническая кибернетика, 1969, №1.

12. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа. Известия Академии наук. Теория и системы управления, №4, 1999.

13. Youssef G. Saab, Vasant В. Rao. "Fast Effective Heuristics for the Graph Bisectioning Problem", IEEE, vol.9 N1, January 1990, Transaction on computer-aided design.

14. Y.C. Wei, C.K. Cheng. "A two-level two-way Partitioning Algorithm", Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

15. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. "A general purpose multiple way Partitioning Algorithm", 28th ACM/IEEE Design Automation Conference, paper 25/1, pp.421-425., 1991.

16. C.J. Aipert, A.B. Kahng. "Geometric Embeddings for Faster and Better Multi-Way Netlist Partitioning", in 30th ACM/IEEE Design automation conference, 1993, pp. 743-748.

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

18. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company Inc., Massachusetts, 1989.412 р.

19. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1992

20. Kureichik V.M. et all. Some new features in Genetic Solution of the Traveling Salesman Problem. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control, Plymouth, UK, 1996. pp. 294-296.

21. Курейчик B.M. Генетические алгоритмы и их применение в САПР. Интеллектуальные САПР, меж. сб., Таганрог, 1995. стр. 7-11.

22. Лебедев Б.К. Канальная трассировка на основе генетических процедур. Известия ТРТУ, №3, Таганрог, 1997. 53-60 с.

23. Лебедев Б.К. Планирование СБИС методом генетического поиска. Известия ТРТУ. Интеллектуальные САПР. Таганрог, Изд-во ТРТУ, 1999, №3.119-126 с

24. Schnecke V., Vornberger O. A Genetic Algorithms for VLSI Design Automation. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control, Plymouth, UK, March 1996. pp. 53-58.

25. Батищев Д.И., Власов C.E., Булгаков И.В. Плотное размещение разногабаритных объектов на плоскости с помощью генетических алгоритмов. XXIII International School and Conference on Computer Aided Design. Yalta-Gurzuff, 2001. 354 c.

26. Rahmani, A.T. and Ono N. A Genetic Algorithm for Channel Routing Problem, in Proc. 5th Intl. Conf. on GAs, 1993. pp. 494-498.

27. Lieng J., Thulasiraman K. A Genetic Algorithm for Channel Routing in VLSI Circuits. Evolutionary Computation, 1(4), MIT, 1994. pp. 293-311.

28. Cohoon J.P. and Paris W.D. Genetic placement. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.6, № 6, 1987. pp. 956-964.

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

30. Мелихов А.Н., Берштейн JI.C. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: издательство Ростовского университета, 1981. 112 с.

31. Харари Ф. Теория графов. М.: Мир, 1973. 300 е., ил.

32. Уилсон Р. Введение в теорию графов. М.: Мир, 1977. 208 с.

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

34. Оре О. Теория графов. М.: Наука, 1980. 356 с.

35. Гатчин Ю.А., Коробейников А.Г. Методы представления математических моделей в САПР при концептуальном и инфологическом моделировании. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 35-41.

36. Марченко А. «Современные проблемы автоматизации проектирования топологии СБИС», МЭС 2006

37. J. Cong, С. Wu, 'Global Clustering-Based Performance-Driven Circuit Partitioning', Proc. ISPD, 2002.

38. W.E. Donath et al, 'Timing Driven Placement Using Complete Path Delays', Proc. ACM/IEEE DAC, 1990.

39. J. Minami, T. Koide, S. Wakabayashi, 'An Iterative Improvement Circuit Partitioning Algorithm under Path Delay Constraints', IEICE Trans. Fundamentals, Dec. 2000.

40. S.-L Ou, M. Pedram, 'Timing-driven Partitioning Using Iterative Quadratic Programming', at http://atrak.usc.edu/~massoud/, see "Coming Attractions!", 2001.

41. P. Zarkesh-Ha, J.A. Davis, J.D. Meindl, 'Prediction of Net-Length Distribution for Global Interconnects in a Heterogeneous System-on-a-Chip', IEEE Trans. VLSI Systems, Dec. 2000.

42. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. Москва, Радио и связь, 1990. 352 е.: ил.

43. Деньдобренко Б.П., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 2002. 384 с.

44. Thang Nguyen Bui, Byung-Ro Moon. "GRCA: A Hybrid Genetic Algorithm for Circuit Ratio-Cut Partitioning". IEEE Transactions on computer-aided design of integrated circuits and systems, vol.17, No.3, March 1998, pp. 193-204.

45. Shihliang Ou and Massoud Pedram, "Timing-Driven Bipartitioning with Replication Using Iterative Quadratic Programming", ASPDAC, 2001.

46. Dominic A. Antonelli, Danny Z. Chen, Timothy J. Dysart, Xiaobo S. Hundrew, B. Kahng Peter, M. Kogge Richard, C., Murphy Michael, T. Niemier, "Quantum-Dot Cellular Automata (QCA) Circuit Partitioning: Problem Modeling and Solutions", DAC, 2004

47. Курейчик В.М. Оптимизация в САПР: Учебное пособие. Таганрог, ТРТУ, 1998.

48. Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС, Таганрог: Изд-во ТРТУ, 2003. 108 с.

49. S. Kirkpatrick, C.D. Gelatt, and М.Р. Vecchi. Optimization by simulated annealing. Science, 220(4598):671 680, 1983

50. Емельянов B.B, Курейчик В.М., Курейчик B.B. Теория и практика эволюционного моделирования. М.: Физматлит,2003.

51. Курейчик В.М. Генетические алгоритмы и их применение: Монография. Таганрог: Изд-во ТРТУ, 2002.

52. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. / под ред. В.М. Курейчика. Учебное пособие. Ростов на - Дону: Ростиздат, 2006.

53. Букатова И.Л. Эволюционное моделирование: идеи, основы теории, приложения. Москва, Знание, выпуск 10, 1981

54. Cristinel Ababei, Kia Bazargan, "Statistical Timing Driven Partitioning for VLSI Circuits", 2002

55. C.M. Fiduccia, R.M. Mattheyses, 'A Linear-Time Heuristic for Improving Network Partitions', Proc. ACM/IEEE DAC, 1982.

56. Yongseok Cheon, Seokjin Lee, Martin D. F. Wong, "Stable Multiway Circuit Partitioning for ECO", 2003

57. C. J. Alpert and S.-Z. Yao, "Spectral Partitioning: The More Eigenvectors, The Better," Proc. ACM/IEEE Design Automation Conf., 1995, pp. 195200.

58. P. K. Chan, M. D. F. Schlag and J. Zien, "Spectral K-Way Ratio Cut Partitioning and Clustering," IEEE Trans, on CAD 13(9), 1997, pp. 10881096.

59. L. Hagen and A. B. Kahng, "Fast Spectral Methods for Ratio Cut Partitioning and Clustering," Proc. IEEE Intl. Conf. on Computer-Aided Design, 2001, pp. 10-13.

60. Jan-Yang Chang, Yu-Chen Liu, and Ting-Chi Wang "Faster and Better Spectral Algorithms for Multi-Way Partitioning", ASPDAC 1999

61. Y.C. Wei, C.K. Cheng. "A two-level two-way Partitioning Algorithm", Tech. report CH2924-9, University of California, San Diego, IEEE, 1990

62. C.J. Alpert, A.B. Kahng. "Geometric Embeddings for Faster and Better Multi-Way Netlist Partitioning", in 30th ACM/IEEE Design automation conference, 1993, pp. 743-748.

63. G. Karypis. Multilevel hypergraph partitioning. In J. Cong and J. Shinnerl, editors, Multilevel Optimization Methods for VLSI, chapter 6. Kluwer Academic Publishers, Boston, MA, 2002.

64. С. Alpert and A. Kahng. A hybrid multilevel/genetic approach for circuit partitioning. In Proceedings of the Fifth ACM/SIGDA Physical Design Workshop, pages 100-105, 2002.

65. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Application in vlsi domain. IEEE Transactions on VLSI Systems, 20(1), 1999. A short ersion appears in the proceedings ofDAC1997.

66. Youssef Saab. A new effected and efficient multi-level partitioning algorithm: DATE, 2000.

67. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Application in VLSI domain. Design Automation Conference, pages 526-529,1997

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

69. Cristinel Ababei, Navaratnasothie Selvakkumaran, Kia Bazargan, George Karypis, "Multi-objective Circuit Partitioning for Cutsize and Path-Based Delay Minimization", ICCAD 2002

70. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика. РАН, №10, Москва, 2001,-с.174-187.

71. Kureichik V.V., Kureichik V.M., Genetic Algorithms. HG Verlag, Konstans, 2004

72. Курейчик B.M., Лебедев Б.К., Гладков Л.А. и др. Разработка интеллектуальных систем проектирования на основе эволюционной адаптации // Отчёт по НИР (промежуточный). Депонир. в ВНТИ № ГР 01.9.60004346, М: 1998,43 стр.

73. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: изд-во ТРТУ, 2000. 192 с.

74. Дуккардт А.Н., Лебедев Б.К. «Подход к решению задачи разбиения на основе квантовых алгоритмов», XI МНПК студентов и молодых ученых «Современные техника и технологии СТТ'2005» г. Томск

75. Дуккардт А.Н., «Методы Генетического поиска для мультихромосомных представлений», VII Всеросийскавя научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника, и системы управления», Таганрог, 2004, с. 108

76. Лебедев Б.К., Дуккардт А.Н., «Разбиение на основе комбинированных генетических процедур», Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №8(63). С. 46-51

77. Дуккардт А.Н., «Решение задачи разбиения на основе процедуры «Выбивания»», Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №6. С. 6366

78. Дуккардт А.Н., «Разбиение на основе процедуры «Выбивания»», VIII всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» Таганрог: Изд-во ТРТУ, 2006. С. 89-90

79. Дуккардт А.Н., Лебедев Б.К. «Гибридный генетический алгоритм с элементами антимонопольного развития», Известия ТРТУ.

80. Тематический выпуск "Интеллектуальные САПР".

81. Таганрог: Изд-во ТРТУ, 2007. №1. С. 86-91

82. Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.

83. Редько В.Г. Эволюционная кибернетика. М.: Наука, 2001.

84. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.l, Washington, USA, CRC Press, 1995.

85. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.2, Washington, USA, CRC Press, 1995.

86. Practical Handbook of Genetic Algorithms. Editor I. Chambers. T.3, Washington, USA, CRC Press, 1999.

87. Касьянов B.H., Евстигнеев B.A. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

88. Holland, John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.

89. Wolfe G., Wong J.L. and Potkonjak M.Watermarking Graph Partitioning Solutions. IEEE Transactions on CAD of Integrated Circuits and systems, V. 21, № 10, October 2002, pp. 1196 1204.

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

91. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учеб. пособие / Под общ. ред. Останина А.Н. -Минск: Вышэйшая школа., 1989. 218 е.: ил.

92. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий. М.: Наука, 1971. 283 е.: ил.

93. Митропольский А.К. Техника статистических исследований. М., "Наука", 1971.576 е.: ил

94. Navaratnasothie, Selvakkumaran, Kia Bazargan, George Karypis. Multi-objective Circuit Partitioning for Cutsize and Path-Based Delay Minimization. ICCAD 2002.

95. Yongseok Cheon Seokjin Lee Martin D. F. Wong. Stable Multiway Circuit Partitioning for ECO. ICCAD 2003.

96. Alpert C.J. et all. Hypergraph Partitioning with Fixed Vertices. //V.19, №2, February 2002, pp. 267 271.

97. Мищенко M. H. Операторы мутации в эволюционных алгоритмах размещения. Перспективные информационные технологии интеллектуальные системы, №4 (16), 2003. с.130-135.

98. Глушань В.М. Графовые модели представления вычислительных алгоритмов. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2. М.: Физматлит, 2003, с. 133 - 138.

99. Мак W.K. Mic Cut Partitioning With Functional Replication for Technology - Mapped Circuits Using Minimum Area Over hed. //V.21, №4, april 2002, - pp. 491 - 496

100. Курейчик B.B. Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. Таганрог: Изд-во ТРТУ, 2001.

101. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.М.: МЦНМО, 2000.

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