Разработка и исследование комбинированного алгоритма генетического поиска и имитации отжига для задачи размещения элементов СБИС тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Ведерникова, Ольга Геннадьевна

• Ведерникова, Ольга Геннадьевна
• кандидат технических наук
• 1999

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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

СБИС

1.1. Конструктивные особенности матричных СБИС

1.2. Иерархический подход к проектированию СБИС

1.3. Этапы проектирования СБИС

1.4. Анализ математических моделей схем для задачи размещения

1.5. Классификация критериев задачи размещения

1.6. Анализ методов решения задачи размещения

1.6.1. Классификация традиционных методов размещения

1.6.2. Метод имитации отжига

1.6.3. Метод имитации эволюции

1.6.4. Анализ достоинств и недостатков методов размещения

1.7. Выводы и рекомендации

2. ТЕОРЕТИЧЕСКИЕ ИССЛЕДОВАНИЯ ФАКТОРОВ;.ВЛИЯЮЩИХ

НА КАЧЕСТВО И СХОДИМОСТЬ АЛГОРИТМСШ ГЕНЕТИЧЕСКОГО ПОИСКА И ИМИТАЦИИ ОТЖИГА

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

2.2. Символьная модель задачи оптимизации

2.2.1 Функция степени приспособленности

2.3. Цель эволюции популяции в процессе естественного отбора

2.4. Оценка генетического разнообразия популяции

2.5. Способы создания стартовой популяции

2.6. Классификация способов образования новых особей

2.7. Системы скрещивания особей

2.7.1. Панмиксия (случайное скрещивание)

2.7.2. Инбридинг и аутбридинг

2.7.3. Ассортативное скрещивание

2.8. Классификация стратегий отбора

2.9. Оценка эффективности генетических операторов

2.10. Анализ макроэволюции

2.11. Исследование метода имитации отжига

2.11.1 Марковская модель алгоритма моделирования отжига

2.11.2. Универсальное расписание отжига

2.11.3. Начальная температура

2.11.4. Правило изменения температуры

2.11.5. Ограничивающее окно

2.11.6. Инкрементный способ вычисления значений целевой функции

2.12. Выводы и рекомендации

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

ПОИСКА И ИМИТАЦИИ ОТЖИГА

3.1. Математическая модель и целевая функция

3.2. Формирование кластеров

3.3. Создание начальной популяции, основанное на методе последовательного размещения по связности

3.4. Модифицированные операторы направленной мутации

3.4.1. Операторы мутации, основанные на методе релаксации

3.4.2. Операторы мутации, основанные на методе Кернигана-Лина, уменьшающие степень загруженности каналов

3.4.3. Динамические нормы случайной и направленной мутаций

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

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

для оператора кроссинговера

3.6. Динамический оператор отбора, основанный на методе имитации отжига

3.7. Механизм управления процессом генетического поиска

3.8. Стратегия макроэволюции

3.9. Улучшение решения после разрушения кластеров методом имитации отжига

3.10. Выводы и рекомендации

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

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

4.2. Теоретическая оценка временной сложности алгоритма

4.3. Определение пространственной и временной сложности алгоритма

4.4. Определение управляющих параметров разработанного генетического алгоритма

4.4.1. Генетические параметры

4.4.2. Параметры кластеризации

4.4.3. Параметры имитации отжига

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

4.6. Выводы и рекомендации

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

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

ВВЕДЕНИЕ

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

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

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

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

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

К третьему классу относятся алгоритмы случайно-направленного поиска, основанные на принципах моделирования.

Недостатки методов первого класса очевидны. Недостатки эвристических алгоритмов решения задачи размещения сводятся, в общем, к низкому качеству решения, либо затрачивают на его поиск избыточное количество времени [4-6]. Алгоритмы случайно-направленного поиска обладают способностью находить более высококачественные решения и за приемлемое время.

Одним из методов случайно-направленного поиска является метод генетического поиска. В 1975 году американский исследователь Дж. Холланд описал методологию изучения адаптивных систем и их применения для искусственных систем, а также разработал подходы к решению комбинаторно-оптимизационных задач. Сейчас генетические алгоритмы (ГА) хорошо известная и эффективная технология оптимизации, применяемая для различных задач техники, моделирующая естественный процесс эволюции в качестве средства достижения оптимума и основанная на имитации процессов натуральной селекции и генетических преобразований [26].

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

Другой метод случайно-направленного поиска - метод имитации отжига. В 1953 году Метрополис сделал попытку применить идею процесса отжига, заимствованную из физики, к проблемам численных методов на основе имитационного моделирования. В 1983 году Кирпатрик использовал эту концепцию для решения комбинаторно-оптимизационных задач. С тех пор этот метод широко используется при решении технических задач, проводятся исследования и разработки его модификаций. Алгоритм имитации отжига обладает высокой способностью выходить из локальных ям и сходиться к глобальному минимуму, но при этом имеет один недостаток: большая временная сложность. Алгоритм генетического поиска обладает иными качествами: быстрой сходимостью, простотой реализации и иногда может сходиться к локальному минимуму. Скомбинировав должным образом эти алгоритмы можно устранить присущие им недостатки, сохранив при этом их достоинства и преимущества [91-95].

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

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

ЦЕЛЬЮ диссертационной работы является разработка и исследование комбинированного алгоритма генетического поиска и имитации отжига для решения задачи размещения ячеек СБИС.

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

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

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

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

4) построены и исследованы: а) комбинированный алгоритм решения задачи размещения элементов СБИС без предварительного формирования кластеров; б) комбинированный алгоритм решения задачи размещения элементов СБИС с предварительным формированием кластеров и заключительным этапом имитации отжига после разрушения кластеров;

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании элементов теории множеств, теории графов, теории алгоритмов, теории комбинаторной оптимизации, элементов теории статистических вычислений.

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

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

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

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

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

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

- комбинированный алгоритм и программа генетического поиска и имитации отжига для решения задачи размещения ячеек СБИС без предварительного формирования кластеров;

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе, проводимой кафедрой «ПМ и ВТ» Ростовской государственной академии сельскохозяйственного машиностроения (РГАСХМ) по темам: «Разработка мультипликативных и генетических алгоритмов решения оптимизационных задач САПР» 1993-1994гг, «Разработка генетических алгоритмов для решения оптимизационных задач технического обслуживания в условиях эксплуатации» (19951996гг.) В Ростовском-на-Дону филиале Ниижелдоравтоматизация использованы при выполнении НИОКР в 1998 г. комбинированный алгоритм решения задачи размещения элементов СБИС без предварительного формирования кластеров и программы размещения элементов СБИС на плоскости, основанные на разработанном алгоритме, и внедрены в 1999 г. в качестве программного обеспечения решения задач САПР. Комбинированный алгоритм генетического поиска с предварительным формированием кластеров внедрен в Майкопском государственном технологическом институте (МГТИ) в 1999 г. и используется в научно-исследовательском секторе (НИС) МГТИ для выработки управляющих решений в условиях высокой размерности и многовариантности решений. Кроме того, мате-

риалы диссертации использованы в учебном процессе на кафедре «ПМ и ВТ» РГАСХМа в цикле лабораторных работ и практических занятий по курсу «Математическое моделирование» в 1992-1995г.

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на НТК РГАСХМа (г. Ростов-на-Дону,1994-1998гг.), Всероссийских научно-технических конференциях студентов и аспирантов «Новые информационные технологии. Информационное, программное и аппаратное обеспечение» (г. Таганрог, 1995, 1998гг.), Всероссийских научно-технических конференциях с участием зарубежных представителей "Интеллектуальные САПР" (г. Геленджик, 1995-1998гг.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 6-ти печатных работах.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 142 стр., а также 46 рис., список литературы из 111 наименований, 12 стр. приложений и актов об использовании.

Во ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, поставлена цель работы, дано общее описание выполненной работы.

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

Во ВТОРОЙ ГЛАВЕ Приведен анализ способов создания стартовой популяции и способ оценки генетического разнообразия популяции. Сделаны выводы о перспективности создания стартовых популяций, на основе детерминированных методов. Приведены классификация и анализ способов образования новых особей и систем скрещивания особей. Приведена классификация стратегий отбора и сделаны выводы о перспективности комбинирования детерминированных и вероятностных стратегий отбора. Разработан способ оценки эффективности генетических операторов. Проанализирован метод имитации отжига. Обоснован оптимальный режим отжига и оптимальный выбор начальной температуры. Сделан

вывод о перспективности комбинирования метода генетического поиска и метода имитации отжига.

В ТРЕТЬЕЙ ГЛАВЕ приведена постановка задачи размещения ячеек СБИС. Выбран комплексный критерий размещения. Разработан алгоритм формирования кластеров. Разработан алгоритм создания начальной популяции, основанный на методе последовательного размещения по связности. Разработаны модифицированные операторы направленной мутации на основе метода релаксации и на основе метода Кернигана-Лина для уменьшения степени загруженности каналов. Разработаны динамические режимы случайной и направленной мутации на основе имитации отжига. Разработаны динамические стратегии скрещивания и отбора особей для новой популяции на основе метода имитации отжига.

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

В ЧЕТВЕРТОЙ ГЛАВЕ описано проведение серии экспериментов для разработанных в третьей главе алгоритмов размещения. По результатам экспериментов уточнены оценки пространственной и временной сложности алгоритмов. Определены оптимальные сочетания управляющих параметров разработанного алгоритма размещения элементов БИС.

В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.

1. АНАЛИЗ ИИССЛЕДОВАНИЕМАТЕМЕТИЧЕСКИХМОДЕЛЕЙИ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ПРИ ПРОЕКТИРОВАНИИ СБИС. 1.1. КОНСТРУКТИВНЫЕ ОСОБЕННОСТИ МАТРИЧНЫХСБИС.

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

Полузаказные СБИС обладают большим разнообразием конструктивно-технологических решений. Полузаказные (матричные) СБИС (МаБИС) в соответствии с внутренней структурой делятся на четыре типа: 1) нескоммутированные логические матрицы (НЛМ), логические матрицы (JIM); 2) матрицы стандартных ячеек (МСЯ); 3) программируемые логические матрицы (ПЛМ); 4) аналоговые матрицы (AM). Существуют матричные СБИС и других типов. Например, широко известны цифроаналоговые (ЦАП) и аналого-цифровые (АЦП) преобразователи в интегральном исполнении [8,9].

Самыми распространенными типами полузаказных СБИС являются схемы на основе матричных кристаллов. Базовый матричный кристалл (БМК) представляет собой монокристаллическую полупроводниковую пластину (рис. 1.1.) на которой размещена матрица нескоммутированных базовых ячеек (БЯ)-(1), в которых находится определенное количество транзисторов и резисторов. Базовая ячейка представляет собой логический модуль с внутренней структурой. Пример внутренней структуры или топологии базовой ячейки приведен на рисунке 1.2. В периферийной части БМК располагаются интерфейсные элементы ввода-вывода (буферные ячейки -(2)). Для прокладки соединений выделяются специальные коммутационные области - вертикальные и горизонтальные каналы трассировки -(3).

ггопппп.....ЁГ ,

□□□□□□□

Рис. 1.1. Структура базового матричного 1фисталла: 1 - базовые ячейки; 2 - буферные ячейки; 3 - коммутационные каналы;

Рис. 1.2. Пример внутренней топологии базовой ячейки.

1.2.ИЕРАРХИЧЕСКИЙ ПОДХОД К ПРОЕКТИРОВАНИЮ СБИС

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

Иерархическая структура проектирования БИС, заданная делением всей конструкции на блоки разного ранга, обеспечивает удобство проектирования, изготовления, эксплуатации и является необходимым условием для автоматизации проектирования БИС и применения алгоритмических методов проектирования^].

В проектно-конструкторских задачах применяют двух уровневое (фрагмент В на рис. 1.3.) или трехуровневое (фрагмент А на рис. 1.3.) рассмотрение устройства. При двухуровневом представлении элемент (1+1)-го уровня рассматривается как некоторое устройство с соответствующим делением на составные элементы (компоненты) ьго уровня. При трехуровневом представлении элемент (1+2)-го уровня рассматривается как некоторое устройство (кристалл, чип) состоящий из макроэлементов (1+1)-го уровня (слои, линейки, блоки), которые в свою очередь состоят из базовых элементов (элементов ьго уровня). Примеры таких иерархических структур приведены на рис. 1.4 и 1.5.

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

\+2 уровень

¡+1 уровень;

I ;

уровень

I

У

слои

Б компоненты

/ \

\

А:

Л } \

блок блок блок

¡-1

уровень

...□...□..п.]

Л Л Л Л Л Л Л Л Л Л А

Рис. 1.3. Иерархическое деление устройства на блоки разных уровней.

а) двухуровневое представление;

в) трехуровневое представление;

Рис. 1.4. Примеры иерархических структур СБИС, а) двухуровневое представление; в) трехуровневое представление;

кристалл

в\ с

Рис.1.5. Пример топологии БИС иерархической структуры и иерархическое

дерево, описывающее ее структуру.

1.3. ЭТАПЫ ПРОЕКТИРОВАНИЯ СБИС.

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

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

При проектировании СБИС в настоящее время выполняются следующие шаги [11-13] : системная спецификация; функциональное проектирование; логическое проектирование; схемное проектирование; конструкторское проектирование; изготовление твердотельной структуры; сборка, тестирование и контроль. Структура циклов при проектировании СБИС отражена на рисунке 1,6.

При детальном рассмотрении этапа конструкторского проектирования, происходит его разделение на следующие основные подзадачи: планирование, размещение элементов на БМК, трассировка соединений элементов, компакция, верификация топологии [14,16]. Иногда в качестве предварительного этапа перед размещением решаются вопросы компоновки (распределения элементов по макроячейкам). Конструкторское проектирование чаще всего реализуется в итерационных процедурах, т. е. отдельные шаги могут повторяться или может происходить возврат к ним в цикле столько раз, сколько это необходимо. На рисунке 1.7.

Рис. 1.6. Этапы проектирования БИС.

Рис. 1.7. Этапы конструкторского проектирования

представлена структура этапа конструкторского проектирования с отражением его итерационного характера.

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

1.4. АНАЛИЗ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СХЕМ ДЛЯ

ЗАДАЧИ РАЗМЕЩЕНИЯ.

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

Эта задача имеет сложный комбинаторный характер и нахождение точного ее решения в большинстве случаев затруднено, поэтому для ее решения используют формальные математические модели и алгоритмы [15,16].

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

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

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

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

1) Степень применимости для решения конкретной задачи конструирования

2) Точность описания основных параметров устройств

3) Сложность работы с моделью (сложность алгоритмов обработки)

4) Сложность определения параметров модели (сложность перехода от схемы к модели)

5) Сложность описания модели

6) Степень разработанности математического аппарата для данной модели

7) Информационную сложность модели (возможность перехода от описания одной модели к более простой)

Широкое распространение получили ниже описанные математические модели, схем электронных устройств, представленные в порядке повышения сложности.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Ведерникова, Ольга Геннадьевна

4.6. ВЫВОДЫ И РЕКОМЕНДАЦИИ

1. С помощью аппроксимации полиномами Чебышева экспериментальных данных были определены пространственные и временные сложности разработанных алгоритмов, которая показывает что для комбинированного алгоритма без кластеризации пространственная и временная сложности порядка 0(п 2), для алгоритма в сочетании с предварительным формированием кластеров и заключительным этапом имитации отжига временная сложность порядка 0(п 3), пространственная - 0(п), что подтвердило теоретические оценки.

2. Определены оптимальные сочетания управляющих параметров разработанного алгоритма размещения элементов: максимальная вероятность направленной мутации РМщшр=0.8 и случайной мутации Рмсл=0.7; двухточечный и трехточечный кроссинговеры ; предельное Хеммингово расстояние (1=2; максимальная вероятность инбридинга Рт=0.8; соотношение долей случайных и направленных особей в начальной популяции 0.5 и 0.5 или 0.3 и 0.7; вероятность принятия новой конфигурации ао=0.8; параметр дистанции, определяющий величину, на которую уменьшается температура 5=0.6. Проведенные эксперименты подтвердили теоретические предположения о том, что применение модифицированных ГО (мутации, начальной популяции) и управление процессом генетического поиска позволяет повысить качество решений на 5% по сравнению с классическим генетическим алгоритмом.

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

4. Проведено сравнение разработанного алгоритма с существующими на основе экспериментальных данных задачи Штейнберга, которое показало, что качество получаемых решений на 5-15 % выше аналогичных, в частности, на 6% выше алгоритма Холла, на 7% выше алгоритма парных перестановок Хиллера, на 15% выше алгоритма Штейнберга, на 6% выше алгоритма имитации отжига, на 5% выше классического генетического алгоритма.

ЗАКЛЮЧЕНИЕ

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

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

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

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

5. Разработан комбинированный алгоритм, использующий макроэволюцию, алгоритмы формирования кластеров, создания начальной популяции, модифицированные ГО и этап имитации отжига после разрушения кластеров. На основе разработанного алгоритма создан пакет программ для ЭВМ типа ЮМ PC/AT Pentium-166 на языке программирования Paskal, позволяющий за время, сопоставимое со временем поиска стандартным ГА получать решения, качество которых на 5-10% выше.

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

7. Проведено сравнение разработанного алгоритма с существующими на основе экспериментальных данных задачи Штейнберга, которое показало, что качество получаемых решений на 5-15 % выше аналогичных, в частности, на 6% выше алгоритма Холла, на 7% выше алгоритма парных перестановок Хиллера, на 15% выше алгоритма Штейнберга, на 6% выше алгоритма имитации отжига, на 5% выше классического генетического алгоритма.

Список литературы диссертационного исследования кандидат технических наук Ведерникова, Ольга Геннадьевна, 1999 год

ЛИТЕРАТУРА

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

2.Разработка САПР. Под ред. A.B. Петрова. М., Высшая школа, 1990.

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

4.Казенов Г.Г., Сердобинцев Е.В. Проектирования топологии матричных БИС. М„ Высш. шк., 1990, с.112.

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

6.Селютин В.А. Автоматизированное проектирование топологии БИС. М-, Радио и связь, 1983. 112 с .

7.Абрайтис Л.А. Автоматизация проектирования топологии цифровых интегральных микросхем. М., Радио и связь, 1985. 200 с.

8.Автоматизированное проектирование СБИС на базовых кристаллах / А.И. Петренко, В.М. Лошаков, А. Тетельбаум и др. М., Радио и связь, 1988.

9.Селютин В.А. Машинное конструирование электронных устройств. М., Советское радио, 1977.

Ю.Петухов Г.А., Смолич Г.Г., Юлин Б.И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. М., Радио и связь, 1987, с. 157.

11.Быстродействующие матричные БИС и СБИС. Теория и проектирование. Под общей редакцией Б. Н. Файзулаева и И.П. Шагурина. М., Радио и связь, 1989.

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

13.Сквозное автоматизированное проектирование микроэлектронной ап-паратуры/З.Ю.Готра,В.В.Григорьев,Л.М.Смеркло,ВМ.Эйдельнант.М., Радио и связь, 1989. с.280.

14.Автоматизация проектирования БИС. Петренко А.И., Сыпчук П.П., А. Я.Тетельбаум и др. Киев: Виша школа, 1983. с.312.

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

16.Петренко А.И., Тетельбаум А.Я. Формальное конструирование электронно-вычислительной аппаратуры,- М.: Сов. радио, 1979.

17.Paris W. GENIF: A new placement Algorithms. Thesis (ms) University of Virginia, USA, 1989. - 56 p.

18.Shahookar K., Mazmnder P. VLSI Cell Placement Techniques. ACM Computing Surveys, vol.23, No 2, June 1991.

19. Shahookar K., Mazumder P. A genetic approach to standard cell placement using metagenetic parameter optimization. IEEE Transactions on Computer-Aided Design, 9(5): 500-511, May, 1990.

20.Cohoon J.P., Paris W.D. Genetic Placement, IEEE Trans, on CAD, Vol.6, No.6, November, 1987. . pp.956-964.

21.Kling R.M., Banerjee P. Empirical and Theoretical Studies of the Simulated Evolution Method applied to standart Cell Placement. IEEE Trans, on CAD, Vol.10, No. 10, October, 1991.

22 .Kling R. Placement by Simulated Evolution. Master of science thesis, Urbana, Illinois, USA, 1986.

23.Kling R.M., Baneijee P. ESP: Placement by Simulated Evolution. IEEE Trans, on CAD, Vol.8, No.3, March 1989.

24.Shahookar R. Mazumder P. Genetic Approoch to Standart Cell Placement Using Meta-Genetic Parameter Optimization. IEEE Trans. On CAD, vol 9, 1990, p.500-511.

25. Razaz M. A Fuzzy C-Means Clustering Placement Algorithm. Proc. International Symposium on C&S, Chicago, USA, 1993. P. 138 - 147.

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

27.Handbook of Genetic Algorithms, Edited by Lawrence Davis, Van Nostrand Reinhold, New York, 1991.

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

29.Foundation of Genetic Algorithms, edited by Rawlins Gregory. Morgan Kaufman. San Mateo, California, 1991.

30. Kirkpatrick S., Gellat C.D., Vecchi M.P. Optimization by simulated annealing. Science 220,4598 (May), 1983.

31. Sechen C., Lee K.-W. An improved simulated annealing algorithm for row-based placement. Proc. of the EEEE International conference on Computer-Aided Design, 1987.

32. Laarhoven P. J. van, Aarts E.H.L. Simulated Annealing: Theory and Applications. D.Riedel, Dordrecht, Holland, 1987.

33.P.Banneijee and M.Jones.A Parallel simulated annealing algorithm for standart cell placement on a hypercube computer.Proceedings of the IEEE International Conference on Computer Design, p. 34, 1986.

34.Grover. Standard cell placement using simulated sintering. Proceeding of the 24th Design Automation Conference^.56-59,1987

35. J. Lam and J. Delosme. Performance of a New Annealing Schedule Proceeding of the 25th Design Automation Conference.p. 306-311.1988.

36. F.Romeo. A.S.Vincentelli and C.Sechen. Research on simulated annealing of the 24th Conference on Description and Control, p.761-767. 1985.

37. П.Г.Романовский.Автореферат кандидатской диссертации. "Оптимизация метода моделируемого отжига при проектировании топологических схем на параллельной вычислительной системе с динамическим распределением задач".-Таганрог.:ТРТИ-1991.19с.

38. Ведерникова О.Г.,Чернышев Ю.О. Исследование алгоритма имитации отжига для решения задач размещения при проектировании БИС. Известия ТРТУ. Интеллектуальные САПР. Таганрог. 1995. с.68-71

39.Ведерникова О.Г. Исследование температурного режима алгоритма имитации отжига. Тезисы докладов Всероссийской научной конференции студентов и аспирантов,Таганрог,1995, с.89-90

40.Инге-Вечтомов С.Г. Введение в молекулярную генетику. - М., 1982.

41.Дубинин Н.П. Новое в современной генетике. М.: Наука, 1986, 322 с.

42.Приходченко Н.Н., Шкурат Т.П. Основы генетики человека. Ростов-на-Дону, Феникс, 1997, 360 с.

43.Букатова Й.Л. Эволюционное моделирование и его приложения. Наука, М., 1979.

44.Букатова И.Л. и др. Эвоинформатика. Теория и практика эволюционного моделирования. М: Наука, 1991.

45.Батищев Д.И., Скидкина Л.Н., Трапезникова Н.В. Глобальная оптимизация с помощью эволюционно-генетических алгоритмов./В Сб. научных трудов "Оптимизация и моделирование в автоматизированных системах",Воронеж, Воронежский гос.техн.ун-т,1994.

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

47.Батищев Д.И., Власов С.Е. Применение генетических алгоритмов для трассировки нерегулярных структур с однослойной коммутацией./В Сб.научных трудов "Оптимизация и моделирование в автоматизированных системах", Воронеж, Воронежский гос.техн.ун-т,1995,с.З-15.

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

49. Айала Ф. Введение в популяционную и эволюционную генетику / Пер. с англ.- М.: Мир, 1984.

50.В.М.Курейчик.Генетические алгоритмы. Монография. Таганрог. Из-во ТРТУ, 1998 с.242.

51 .Back Т., Fogel D.B., and Michalewuz Z. Handbook of Evolutionary Computation. Oxford University Press, New York, and Institute of Public Publishing, Bristol, 1997.

52. Rabinovich Y., Widgerson A. An Analysis of Simple Genetic Algorithm. Proc. of the Fourth International Conference on Genetic Algorithms. San Mateo. Morgan Kaufinan, 1991,

53. Whitely D., Starkweather D. GENITORII: a Distribute Genetic Algorithm. Jornal Expt. Theor. Artificial Intelligence, 2,1990, pp.189-214.

54. Annaiappa P. V. A critical analysis of genetic algorithms for global optimization. Ph.D. thesis. New Mexico State University, Las Cruses, 1991.

55.Родзин С.И. Проектирование самотестируемых СБИС с применением метода генетического поиска. Известия. ТРТУ ,№3,Таганрог.1997.стр. 84-86.

56.Lin S.C., Goodman Е.Р., Punch W.F. A Genetic Algorithm Approach to Dynamic Job Shop Scheduling Problems. Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufinann Publisher, San Mateo,California, 1997. pp. 481-488.

57.Ikonen I., Biles W.E., Kumar A., Wissel J.C. and Ragade R.K. A Genetic Algorithm for Packing Three-Dimensional Non-Convex Objects Having Cavities and Holes. Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1997. pp. 591-598.

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

59.Kureichik V., Miagkikh V., Topchy A. Combined Genetic and Local Search Algorithms for Quadratic Assignment Problem. Proc. First International conference on Evolutionary computation and its Applications, June 1996, Moscow, Russia.

60.Kureichik V., Miagkikh V., Some new features in genetic solution of the TSP (travelling salesman problem). Proc. Of the second International conference adaptive computing in engineering design and control - 96. UK, Plymouth, March, 1996. pp. 294296.

61.Kureichik V.Davidenko V.Miagkikh V.Genetic algorithms for restrictive channel routing. Proc. of the 7th International conference on Genetic Algorith-ms, USA,MSU, East Lansing, 1997.

62.A.Bertoni,P.Compadelli,V.Carpeneri,and G.Grossi. Analysis of Genetic Model. Proc. of the 7th International conference on Genetic Algorithms,USA, MSU, East Lansing, 1997.pp. 121-127

63.William Hart.A Generalised Stationery Point Convergence Theory for Evolu-tionery Algorithms.Proc. of the 7th International conference on Genetic Algorithms, USA,MSU,East Lansing,1997 .pp. 127-135

64.Martin Hulin. An Optimal Stop Criterion for Genetic Algorithms. Proc. of the 7th International conference on Genetic Algorithms,US A,MSU,East Lansing, 1997. pp.135-144

65.Isao Ono and Shigenoby Kobayashi.A Real Coded Genetic Algorithm for Function Optimizaiton Using Unimodal Normal Distributed Crossover. Proc. of the 7th International conference on Genetic Algorithms,USA,MSU, East Lansing, 1997.pp.246-254

66.Hisao Ishibuchi,Todahiko Murata and Shigemitsu Tomioka. Effectiveness of Genetic Local Search Algorithms. Proc. of the 7th International conference on Genetic Algorithms,USA,MSU, East Lansing, 1997.pp.505-513

67.Mark Land,John,!Sidorovich and Richard K.Belew. Using Genetic Algo-rithms with Local Search for Thin Film Metrology. Proc. of the 7th International conference on Genetic Algorithms,USA,MSU, East Lansing,1997 .pp.537-545

68.В.М.Курейчик.В.В.Курейчик.Генетические алгоритмы в комбинаторно логических задачах искусственного интеллекта. Сб.науч.трудов 6-ой национальной конференции с международным участием КИИ'98.Пущино. 1998. с.720-726

69.В.Н. Дцвиденко.Методика генетического поиска для задачи канальной трассировки. Тезисы докладов-0 4-ой Всероссийской научной конференции сту-

t

дентов и аспирантов,Таганрог, 1998,с.68-69

70.М.Н.Рябец.Последовательный генетический алгоритм компоновки. Тезисы докладов 4-ой Всероссийской научной конференции студентов и аспирантов,Таганрог ,1998,с. 80-81

71.С.В.Фролов.Трассировка СВИТЧ-бокса методом генетического поиска. Тезисы докладов 4-ой Всероссийской научной конференции студентов и аспирантов, Таганрог, 1998,с. 83-84

72.С.Н.Щеглов.Управление характеристиками генетических алгоритмов с использованием принципов адаптации. Тезисы докладов 4-ой Всероссийской научной конференции студентов и аспирантов, Таганрог, 1998,с.84-85

73.В.Б.Лебедев.Генетические процедуры трассировки в коммутационном блоке. Тезисы докладов 4-ой Всероссийской научной конференции студентов и аспирантов, Таганрог, 1998,с.87-88

74. Буракова А.В. Ведерникова О.Г.Чернышев Ю.О. Нетрадиционные алгоритмы решения задач оптимизации при проектировании БИС. Сб. науч.трудов РИАТМа.выпуск 1.1994.,с.66-78

75. Ведерникова О.Г.Метод эволюционной адаптации для решения задачи размещения. Сборник трудов научно-технической конференции РГАСХМа.1996.

76. Spears W.M. Crossover or mutation? Proc. of the Foundation of Genetic Algorithm Workshop. Morgan Kaufmann, 1992.

77. De Jong K., Spears W. M. A Formal Analysis of the Role of Multi-Point Crossover in Genetic Algorithms. Annals Of Mathematics and Artificial Intelligence Journal, v. 5, No 1,1992, pp. 1-26.

78. Spears W.M. Adapting Crossover in a Genetic Algorithm. Naval Research Laboratory, AI Center Report AIC-92-025. Washington, 1992.

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

80.01iver I., Smith D., and Holland J.R.. A study of permutation crossover operators on the travelling salesman problem. Proc. of the Second International Conf. on Genetic Algorithms, Pp: 224-230.

81.Ведерникова О.Г. Разработка адаптированного оператора мутации для задачи квадратичного назначения в генетических алгоритмах. Тезисы докладов 4-ой Всероссийской научной конференции студентов и аспирантов, Таганрог, 1998, с.61-63

82. Collins R., Jefferson D. Selection in Massively Parallel Genetic Algorithm. Proc. of the 4-th Interna-tional Conf. on Genetic Algorithms. San Mateo. Morgan Kaufinan, 1991.

83. 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 Raufinann, San Mateo, CA, 1991.

84.Elketroussi M., Fan D. GADELO: A Multi-Population Genetic Algorithm Based on Dynamic Exploration of Local Optima. Proc. of the Fith International Conference on Genetic Algorithms. San Mateo. Morgan Kaufinan, 1993.

85. Baker J. Adaptive Selection Methods for Genetic Algorithms. In: Grefenstette J. (Ed.) Proc. of the First International Conference on Genetic Algorithms and Their Applications. Hillsdale, N.J. Lawrence Erlbaum Ass., 1985.

86. Whitley D. The Genetic Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best. In: Schaffer D.(Ed.) Proc. of the Third International Conference on Genetic Algorithms. San Mateo. Morgan Kaufmann, 1989.

87. Mahfoud S. An Analysis of Boltzman Tornament Selection. IlliGAL Report No 91007, University of Illinois, Urbana Champaign, 1991.

88.Potts C.I., Giddens T.D., Yadav S.B. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial selection. IEEE Trans. On Systems, Man and Gybernetics, vol. 24, № 1,1994, p 73-86.

89.A,Petrowski.A New Selection Operator Dedicated to Speciation. Proc. of the 7th International conference on Genetic Algorithms,USA,MSU, East Lansing, 1997 .pp. 144-152

90. Koakutsu S., Sugai Y. Hirata H. Blok placement by improved simulated annealing based on genetic algorithms. In 5th Conference on Modeling and Optimization, vol. 180 of Lecture Notes in Control and Information Sciences, 648-656. SpringerVerlag, Berlin, 1992.

91. Koakutsu S., Sugai Y., Hirata H. Floorplanning by simulated annealing based on genetic algorithms. Transactions of the Insitute of Electrical Engineers of Japan, 112-c(7):411-416,1992.

92.Davis L., Genetic Algorithms and Simulated Annealing. San Mateo. Morgan Kaufinan Publisher, 1987.

93. Davis Т., Principe J. A simulated Annealing Like Convergence Theory for the Simple Genetic Algorithm. Proc. of the Fourth International Conference on Genetic Algorithms. San Mateo. Morgan Kaufman, 1991

94.Goldberg D. A Note on Boltzman Tournament Selection for Genetic Algorithms and Population-Oriented Simulated Annealing. Complex Systems, 4, 1990, pp.445-460.

95.Genetic Algorithms and Simulated Annealing. Editor L.Davis, Pitman, London, 1987,216 p.

96.Ведерникова О.Г. Метод решения задачи размещения, основанный на комбинировании методов эволюционной адаптации и имитации отжига. Известия ТРТУ. Интеллектуальные САПР Таганрог.1997.с.219-220

97. Ведерникова О.Г. Генетический метод с процессом селекции, основанным на принципе имитации отжига. Известия ТРТУ. Интеллектуальные САПР Таганрог. 1998.с.205-206

98.Мину М. Математическое программирование. М., Наука, 1990.

99.Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.

101.3айченкоЮ.П.Исследование операций.Киев:Вищашкола,1975.320 с.

102.Бентли Д. Жемчужины творчества программистов / пер. с англ. М., Радио и связь, 1990. 244 с.

103. Липский В. Комбинаторика для программистов / Пер. с польского Евстигнеева В. А., Логиновой О.А.М., Мир, 1988. 213 с.:ил.

104. Львовский Е.Н. Статистические методы построения эмпирических формул: Учеб.пособие для втузов. М., Высшая школа, 1988. 239 е.: ил.

105. Митропольский А.К. Техника статистических вычислений. М., Наука., 1971. 576 е.: ил.

106.Адлер Ю.П. Введение в планирование эксперимента. М., Металлургия, 1969. 157 с.:ил.

107. Steinberg L. The backboard wiring problem: a placement algorithm. «SIAM Review», 1961,v.3,No.l,p.37-50.

108. Hall K.M. An r-dimensional quadratic placement algorithm.-«Management Science»,1970,v.l7,No.3,p.218-229.

109. Hiller F.S. Quantitative tools for plant layout analysis.-«The Journal of Industrial Engeneering», 16 3, v. 14 ,No 1 ,p.33-40,

110. Gilmore P.C. Optimal and suboptimal algorithms for the quadratic assignment problem.-«J. SIAM»,1962, v. 10, No. 2, p. 305-313.

Ill .A.B. Лях. Автореферат кандидатской диссертации. «Разработка и исследование методов иерархического размещения компонентов матричных БИС на основе алгоритмов эволюционной адаптации».-Таганрог.:ТРТИ-1992.19с.