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

• Полупанов, Алексей Александрович
• кандидат технических наук
• 2003

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

ВВЕДЕНИЕ.

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

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

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

1.3. Учёт тепловых характеристик.

1.4. Классификация методов и алгоритмов решения поставленной задачи

1.5. Выводы.

2. ПРИМЕНЕНИЕ МЕТОДОВ ГЕНЕТИЧЕСКОГО ПОИСКА ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАЗБИЕНИЯ СХЕМ ПРИ ПРОЕКТИРОВАНИИ СБИС.45 '

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

2.2. Элементы генетических алгоритмов.

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

2.4, Выбор методики кодирования информации. 2.5. Селекция.

2.6. Основные генетические операторы.

2.6.1. Оператор кроссинговера.

2.6.2. Оператор мутации.

2.6.3. Оператор инверсии.

2.7. Выводы.

3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗБИЕНИЯ С ЭЛЕМЕНТАМИ АДАПТАЦИИ (ГАСЭА).

3.1. Структурная схема ГАСЭА для разбиения схем при проектировании

СБЙС.

3.2. Элементы адаптации в ГАСЭА.

3.3. Генератор хромосом содержащих группы вершин (ГХСЯ).

3.4. Модифицированные процедуры, применяемые для ГО.

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

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

3.7. Блок адаптации алгоритма.

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

3.9. Выводы.

4. РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА РАЗБИЫ 1И>

СХЕМ ПРИ ПРОЕКТИРОВАНИИ СБИС.

4.1. Разработка основных пунктов меню программного обеспечения.

4.2. Формат входного файла гиперграфа.

4.3 * Формат выходного файла (решения). 4.4. Цель экспериментального исследования.

4.5. Этапы экспериментальных исследований.

4.6. Результаты экспериментальных исследований.

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

4.6.2. Результаты исследований для проблемно-ориентированного генератора стартовой популяции (ГХСЯ). 4.6.3. Результаты исследований для разработанного алгоритма (ГАСЭА)

4.7. Сравнение полученных экспериментальных данных ГАСЭА с результатами аналогов.

4.8. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

Большой ,вклад в развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС внесли такие учёные, как: Бершадский A.M., Деньдобренко Б.П., Казеннов Г.Г., Курейчик В.М., Морозов К.К., Норенков И.П., Селютин В.А., Шервани Н. и др. В многочисленной своей массе разработанные алгоритмы, программы и пакеты в САПР предназначены для оптимальной компоновки, размещении разногабаритных объектов (формирования базового плана кристалла) и межблочной трассировки межсоединений по критерию минимизации занимаемой площади и длины связей [13 - 16]. В связи с большой сложностью и размерностью задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется . необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач. Поскольку даже в условиях современного развития информационных технологий, многие алгоритмы не справляются с решением или требуют много процессорного времени для поиска решений. С точки зрения повышения эффективности САПР, представляет интерес разработка новых алгоритмов и методов проектирования, для так называемых NP-полных задач, в которых нахождение оптимального решения возможно только полным перебором и которые являлись бы достаточно эффективными как с точки зрения точности и оптимальности получаемых решений, так и с позиции времени работы. К таким можно отнести методы эволюционного моделирования, которые были разработаны, как новое направление, в начале 1970 гг., но только сейчас приобрели приоритет в отношении других методов. Сравнительно недавно, их начали широко применять для решения задач в самых различных областях [17-23], в том числе для решения задач проектирования СБИС, поскольку эти методы способны обрабатывать множество решений при учёте множества критериев [24-36]. Данными свойствами обладают генетические алгоритмы (ГА) -поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска.

Значительный вклад в развитие стратегий эволюционного поиска внесли такие учёные, как: Батищев Д.И., Букатова И.Л, Гольдберг Д.Е., Курейчик В.М., Норенков И.П., Растригин Л.А., Холланд Д.Х. и др. Основная цель ГА -абстрактно и формально объяснить адаптацию процессов в естественных системах и спроектировать искусственные программные системы, которые содержат основные механизмы естественных систем. Основная тема поиска ГА - поиск баланса между эффективностью и качеством для "выживания" в различных условиях. Главные отличия ГА от других оптимизационных и поисковых процедур следующие: осуществляют поиск из множества точек, а не из единственной точки; используют целевую функцию, а не её различные приращения; для оценки получаемой информации используют не детерминированные, а вероятностные правила; дают не одно решение, а целый спектр решений, из которых возможно выбрать наилучшее, с точки зрения поставленной задачи. Пожалуй, одним из главных свойств ГА является, то что, они достаточно легко преодолевают локальные оптимумы в силу своей "природы". Гибкость структуры ГА, возможность её настройки и перенастройки дают возможность создания структур, обеспечивающих получение наилучшего результата за приемлемое время. Это, в свою очередь, предоставляет исследователям широчайшие возможности, для поиска альтернативных решений в этом направлении.

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

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

Для достижения поставленной цели были выполнены следующие этапы:

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

2. Разработан новый проблемно-ориентированный генератор стартовой популяции (ГХСЯ), использующий знания о решаемой задаче и позволяющий генерировать хромосомы, содержащие группы генов (опорное подмножество или ядро), что позволило повысить качество получаемых решений и сократить время работы алгоритма.

3. Выполнен анализ основных генетических операторов с точки зрения их пригодности и эффективности для решения поставленной задачи.

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

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

6. Разработана структурная схема генетического алгоритма разбиения гиперграфов на подгиперграфы с элементами адаптации (ГАСЭА) для задачи разбиения схем при проектировании СБИС.

7. Выполнены экспериментальные исследования разработанного проблемно-ориентированного генератора стартовой популяции решений (ГХСЯ), блока модифицированных процедур генетических операторов, разработанного алгоритма (ГАСЭА), а также сравнение его с известными алгоритмами разбиения.

Для решения поставленных задач использовались следующие МЕТОДЫ « ИССЛЕДОВАНИИ: элементы теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

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

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

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

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

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

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

3. Генетический алгоритм с элементами адаптации и программа для разбиения схем при проектировании СБИС, разработанная под наиболее популярное семейство 32-разрядных операционных систем Windows® 9х/МЕ/2000/ХР фирмы Microsoft Corporation, созданная в среде объектно-ориентированного программирования Borland С++ Builder " 5.0.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе « Разработка интеллектуальных систем проектирования на основе эволюционной адаптации » (№ ГР 1.8.96), г/б « Разработка теории и принципов построения интеллектуальных систем автоматизированного - проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений» (№ ГР 1.04.01), х/д между ТРТУ и Российским научно-исследовательским институтом информационных технологий и систем автоматизированного проектирования (Рос НИИ ИТ и АП) «Разработка эволюционных алгоритмов на графах с динамическими параметрами» (№ 12301).

Результаты работы используются в НИИ ТКБ ТРТУ по договору №71-0/98-16002-7 «Участие в разработке технических предложений по созданию РИС и алгоритмов её функционирования». Кроме того, материалы . диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсу "Методы оптимизации", "Методы генетического поиска", а также в - цикле лабораторных работ по курсу "Автоматизация конструкторского проектирования СБИС".

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на научных семинарах (с 2000 по 2003 гг., ТРТУ), V, VI Всероссийских научно-технических конференциях студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (г. Таганрог, 2000 г., 2002 г.), XVII Международной научно-технической конференции "Интеллектуальные САПР" (г. Геленджик, 2002 г.), Пятой Всероссийской научной конференции молодых учёных и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2002 г.)."

ПУБЛИКАЦИИ. По теме диссертации опубликовано 8 печатных работ.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырёх глав, заключения, и списка использованных источников. Работа содержит 173 стр., включая 69 рис., 18 табл., список использованных источников из 107 наименований, 23 стр. приложений и актов об использовании.

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

4.8. Выводы

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

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

3. Выполнено сравнение разработанного алгоритма разбиения схем с ПГА, а также с существующими аналогами. Экспериментально подтверждено, что применение разработанного алгоритма позволяет на 2 - 5% повысить качество решения задачи разбиения схем при проектировании СБИС.

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

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

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

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

4. Проведены серии тестов и экспериментов и выполнена обработка ' экспериментальных данных, что позволило уточнить теоретические оценки

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

5. Разработано программное обеспечение, приведено его описание для изучения характеристик алгоритма (экспериментального тестирования) разбиения схем при проектировании СБИС и утилита для конвертирования форматов данных входных файлов гиперграфов с целью совместимости с известными аналогами. При создании программ использовался пакет Borland С++ Builder™ 5.0 для 32-разрядных ОС семейства Windows® 9х, а

S) отладка, тестирование и эксперименты поводились на IBM совместимом компьютере с процессором Intel® Pentium® II \ 400 MHz и оперативной памятью 320 MB DIMM РС-133.

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

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

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

Более наглядно экспериментальные результаты приведены в приложении №2.

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

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

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

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

4. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учеб. пособие для вузов. М.: Радио и связь, 1983. 280 е.: ил.

5. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР: Учебник для вузов. М.: Энергоатомиздат, 1987. 400 е.: ил.

6. Системы автоматизированного проектирования: В 9-ти кн. Кн. 6.

7. Автоматизация конструкторского и технологического проектирования: Учеб. пособие для втузов/Под ред. Норенкова И.П. М.: Высшая школа, 1986. 160 е.: ил.

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

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

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

11. Под редакцией Норенкова И.П. Системы автоматизированногопроектирования в радиоэлектронике. Справочник. Москва, Радио и связь,1986.

12. Под редакцией Морозова К.К. Методы разбиения схем РЭА на конструктивно законченные части. Москва, Советское радио, 1978.

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

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

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

16. 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.

17. 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.

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

19. Davis L.D. Handbook of Genetic Algorithms. Van Nostrand Reinold, New York, 1991.

20. Goldberg D.E., Kalyanmoy D. A comparative analysis of selection schemes used in genetic algorithms. In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. Mogan Kaufmann, San Mateo, С A, 1991.

21. Syswerda G. Uniform Crossover in Genetic Algorithms. Proc. of the 3-rd Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1989. p. 2-9.

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

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

24. 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.

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

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

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

28. Чернышев Ю.О., Курейчик В.В. Генетические алгоритмы размещения / XXII International School And Conference On Computer Aided Design, CAD-95, Gurzuff; 1995. c. 329-330.

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

30. Goodman, E. Tetelbaum, A. and Kureichik, V. (1994). A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems. Case Center Technical Report #940702, Michigan State University

31. Chan, H.M. and Mazumder, P. A genetic algorithm for macro cell placement. Technical report, Department of Electrical Engineering and Computer Science, University of Michigan, 1989

32. Kureichik, V.M. Genetic Algorithms In CAD. Proc. Russia Conf. AI in CAD, Gelendzhik, September 1993.

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

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

35. Schnecke V., Vornberger O. A Genetic Algorithms for VLSI Design Automation. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and

36. Control, Plymouth, UK, March 1996. pp. 53-58. .

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

38. Мелихов A.H., Берштейн JI.C. Конечные чёткие и расплывчатые множества. Таганрог, ТРТИ. 1980.

39. Мелихов А.Н., Берштейн JI.C., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. 304 с.

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

41. 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.

42. Курейчик B.M. Генетические алгоритмы. Монография. Таганрог, ТРТУ,1998.• 42. Курейчик В.М. Оптимизация в САПР: Учебное пособие. Таганрог, ТРТУ, 1998.

43. Букатова ИЛ. Эволюционное моделирование: идеи, основы теории,