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

таганрогский государственный радиотехнический университет

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

КУРЕЙЧИК Владимир Викторович

уж 621.393

исследование к разработка генетических алгоритмов для конструкторского синтеза элементов сбис

Специальность: 03.13.12. - системы автоматизации

проектирования

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

Таганрог - 1995

Работа выполнена на кафедре МЭТ БИС Таганрогского Государственного радиотехнического университета

НАУЧНЫЙ РУКОВОДИТЕЛЬ - доктор технических наук, профессор

ЧЕРНЫШЕВ ¡0. 0.

(ШЦИДЛЫКЕ ОППОНЕНТЫ - доктор технических каук, профессор

РШДШ А. Л. ,

кандидат технически к каук, е.н.с. ЯРКЫХ В. Б.

ВБДУШЕ №'КД11РИЛТКЕ - Российский КШ ш&дюдиошпк окопек, г.Ыэета^.

Зажгла состоит-о? •■¿У ■ ¿L0.pTО- Ю3:5'г. Г. 14 ч.чООй г.;1. зазс-дашш дмзсерчйшюиного совета Д 053.13.02 по ^-х© хмлсоргащ;/;

1агаьрогсг;о« Госуддрстеоинои радкотскиичзскас уш&растоти т 8/!рл«у: г. Тагяярог, пор. НзгргсоасквЯ, ауд. Д.-<0С5.

С д'.сссртациэй мокко ознакомиться в библиотеке университета. Автореферат ¡«заслан " 2.0 " О 2 1993 года.

У"ч о н у. й с о к р от п р 1, диссертационного соиета кандидат технических наук, доцент

А. Н. Цель'

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

АКТУАЛЬНОСТЬ ТЕМЫ. Постоянный прогресс науки и техники требует совершенствования одного из основных помощников человека - ЭВМ. Основные задачи, стоящие перед ЭВМ - это обработка знаний, обучение и самообучение, самоорганизация, адаптация к окружающей среде, накапливание информации, естественное общение с человеком в процессе решения различных задач. Создание-' интеллектуальных ЭВМ и рабочих станций с "дружественным" по отношению к пользователю математическим и программным •обеспечениями С МО и ПО), переход от алгоритмов обработки данных к альтернативной технологии автоформализации профессиональных знаний, моделирование эволюции позволяют увеличить эффективность деятельности инженеров, конструкторов, технологов, менеджеров. Все это должно' быть связано с новой концепцией компьютерного, интеллектуального, интегрированного моделирования, проектирования и производства.

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

ЦЕЛЬ ДИССЕРТАЦИИ состоит в анализе, разработке, исследовании и применении методов эволюционного моделирования и генетических алгоритмов для решения задач конструкторского проектирования.

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

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

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

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

поиска, ориентированные на комбинаторно-логические задачи.

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

4. Предложены алгоритмы. компоновки, размещения, трассировки, сжатия и верификации, г—«¿ляющие получать множество локальных оптимумов. Этап экспериментаиол«х исследований показал преимущество генетических алгоритмов С ГА) по сравнение с последовательными и итерационными методами.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ И РЕКОМЕНДАЦИИ ПО ПРИМЕНЕНИЮ. Результаты диссертационной работы состоят в следующем:

- разработанные методы с применением ГА могут быть использованы для разработки технологических конструкций ЭВМ различного назначения;

- автоматизированное проектирование, основанное на использовании эволюционного моделирования и ГА, позволяет изменять степень автоматизации процесса проектирования с ууетом квалификации пользователя;

- методология ГА позволяет распараллеливать процесс решения;

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

РЕАЛИЗАЦИЯ РАБОТЫ. Разработанные алгоритмы использованы при выполнении межвузовской научно-технической программы "Разработка учебно-мет<?дических комплексов по изучению перспективных информационных технологий", а также при выполнении подпрограмма "Информатизация проектирования", программы Госкомвуза России "Информатизация образования". В рамках договора о творческое содружестве между Ассоциацией САПР и Центром САПР Мичиганского университета (США) разработаны алгоритмы упаковки и сжатия топологии СБИС. Результаты этих работ внедрены на предприятиях г.Москвы, г.Таганрога. Материалы диссертации используются в учебном процессе I МГТУ и МИРЭА Сг.Москва). Акты о внедрении и использовании результате! работы приведены в приложении к диссертации.

Автор защищает следующие новые научные положения:

1. Обобщенная Методология решения основных зада* конструкторского проектирования с помощью ГА.

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

3. Алгоритмы компоновки, размещения, трассировки и други: основных задач конструкторского проектирования с применением ГА

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

АПРОБАЦИЯ основных научных и практических результатов работы преходилась на Всероссийских научно-технических конференциях с участием зарубежных представителей "Интеллектуальные САПР" Сг. Гелендзшк, 1990г., 1992г.,. 1993г., 1994г.), Семинаре НТО радиотехники, электроники и- связи им. А. С. Попова "Проблемы магнитной записи" (г. Москва, 1993г.), Зональной конференции Пензенского ВНТОРЭС ем.А.С. Попова "Автоматизация проектирования РЭА и ЭВА" Сг. Пенза, 1990г.), Всесоюзном семинаре "Создание ИСАПР СБИС" Сг.Москва, 1990г.)

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

СТРУКТУРА И ОБЪЕЛ РАБОТЫ. Диссертация состоит из введения, четырех глав, заключения, галогенных на 136 страницах, 55 рисунков, 12 таблиц, списка литературы из 115 наименований к приложения.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

- С -

новую популяцию. Каждая индивидуальность , икэзт • целевое-(функциональное) значение, которое' определяется коделирувде15 функцией (КФ). Основная задача ГА оптимизировать МФ.

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

Натуральная селекция - это процесс, посредством которого хромосомы, содержащие более высокое функциональное значение С с сильными признаками), имеют'большую вероятность для репродукции, чек слабые хромосомы. Проанализированы методы селекции. Селекция на основе рулетки - это простой и наиболее используемы» в ГА метол;. Селекция на основе заданной шкалы. Здесь популяция,предварительно сортируется от лучшей индивидуальности к худшей на основе заданного критерия. Элитная селекция. В этом случае выбираются лучике Сэлитные) индивидуальности на основе КФ. Турнирная селекция. При этом некоторое-число индивидуальностей (согласно размеру "турнира") выбирается случайно из популяции-, к лучшие индивидуальности в этой группа селектируется для дальнейшего генетического процесса. Различная методы селекции и ик кодификации позволяют в некоторых случаях рашато проблему предварительной сходимости алгоритмов.

Исследованы операторы кроссинговера (ОК). Основная функция 01". создавать последовательности потомков ■ на основе различного скрещивания родителей. Существует огромное число ОК, так как его структура, в основном, и определяет эффективность алгоритма: одноточечный (простой) ОК (00К); двухточечный.ОК (ДОК); многоточечный ОК (МОК) или Н-точэчный ОГ..

Рассмотрены основные операторы мутации (ОЫ). Обычно ОМ является одноточечны.« оператором, который случайно выбирает позицию хромосоме ;: случайна,; образом обменивает ее на рядом расположенно; ген. Если вероятность ОК лежит мэвду 0,5 - 0,99, то вероятность 0. обычно составляет 0,05 и ниже процентов. В задачах САПР, с нашей точки зрения, интерес представляет использование ОМ, основанных нг знаниях о решаемой задачи.

Популярным и используемым в кивых системах является оператор инверсии (0И). В Ой случайным образом определяется одна или несколько точек инверсии, внутри которых элементы инвертируются. Кроме простогс 01!, описан специальный 0И С СОИ). В СОИ точки инверсии определяются с заданной вероятностью для каздой новой создаваемой индивидуальности.

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

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

Разработана нозая базисная структура простого ГА. Она состоит из блоков: создание начальной популяции; моделирование популяции Гопределение МО; селектирование индивидуальностей для репродукции; применение ОК для создания потомков; применение ОМ, ОИ, ОТ, ОС; рекомбинация родителей и потомков для создания новой популяции; отдание новой генерации. Отметим, что такая структура ГА не единственная. В работе описана архитектура различных модификаций ГА для эффективного решения задач проектирования СБИС.

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

Необходимым условием эффективной работы интеллектуальной САПР СИСАПР), является ее автоматическая или автоматизированная адаптивная настройка на объект проектирования и все виды обеспечений САПР. Разработанный блок эволюционной адаптации СБЭА} основан на стандартных моделях наследственности и эволюции из области популяционной генетики, являющихся воплощением тех механизмов адаптации, которые имеют место в различных видах живой природы. Дана классификация суцествуящих форм отбора. Механизм адаптации элементов в процессе эволюции состоит из трех основных этапов: генерация новых элементов на основе различных генетических операторов; построение МФ для оценки новых элементов на предмет включения в строющуюся популяцию; селекция популяции для выживания сильнейших.

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

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

поиска. В работе для какдой задач! конструкторского проектирования строится своя М-5. При построении МФ используются знания проектировщика о конкретной задаче и элементы экспертных систем ОС). На -основе МФ производится ранжирование и сортировка популяции решений Р. Затем в результате резличных методов селекции вуР подбираются пары для применения различных генетических операторов СГО). В такой схема возкокео концентрировать поиск ка наиболее перспективных решениях. Периодически в каждой итерации косно проводить различные изменения в перспективных, . неперспективных и, вообще, в лвбых решениях. Временная сло^сность таких глгоришов, в основном, совпадает со сложность» быстрых итерационных алгоритмов и лэаит в пределах ОСК п)

-гОСК.п2), где К4; К^ - коэффициенты, п - число входов алгоритмов.

ВО ВТОРОЙ ШЕЕ разработаны алгоритмы кокпокош» к разкещешт элементов СБИС на основа генетических кетодоь.

Ко:«1,!утациокная схема 1 СБИС представлена в взде гкпергра^оЕс,'; кодели Н = СХ, Е, Ю, где X представляет мкохество верщ;:к гкпоргрг^а, Е - шюейство гкперребер, а V - общий суыариьй вес воракк. Ксвдо» ьераине х б X соответствует зяекект СБ132 к вес ^ е у. Вас вержжи соответствует интегральной оценке, в которуо входят шгощадь, оанимаекая элементом СБИС, ч а тагхз различало кокструкторско-технояогичзсккз ограничения ка проекткроЕакпо. Прп«ш:, значения м £ V ке превышают некоторой пороговой величии. Бесова?; функция для разбиения гшергра$а Н запиветск:

1=1 ¿=1

здесь К.^ - число связей мэвду частями II и Н при разбкещ.;,. п:пзргра£а Н ка две части; 1 - количество частей в разбиении; К -сухарное количество связей при разбиении гкперграйа ка части.

Стандартная задача разбиения заключается в минимизации К СК=>иип). Минимизация К при разбиении козегутациошок схец ка част;: позволяет косвенно учитывать практически все критерии г; конструкторско-технологическко ограничения СБИС.

Построена схека разбиения гипергра^а на части на основе генетического подхода. Она состоит из 6 блоков. Здесь в блоке 1 строится текущая С начальная) популяция решений. Такое подмножества рсшзнкй иокет быть получено ■ случайны:,:, направленные: ил;: случайно-направленным катодами. В. блоке 2 для каждого эиекэнта текущей популяции вычисляется К п определяется К 0 - сроднее значок;;:

- У -

кЗъективной функции на ■ данной популяции. Блок 3 осуществляет юргировку популяции на основе К. Сначала расставляются элсг.сенгп с ;анценьшин значением К и т. д. по возрастали». Блок 4 выполняет :елекцик> популяции для получения родительских пар. Блок 5 юуцествляет реалкзацкп генетических оператороз. 8 6 бпоко юуществляется построение повой популяции реаенпй. Далее- для каждой шдивидуалькостн из ново!! популяции вычисляется К, и вызивапт те цементы кз старой я новой популяции, у которых К > К„. Разработай:! юследозательний и 'итерационный алгоритм компоновки на осносо ■биотического поиска с использованием ' козых модифицировании:: ■енетическнх операторов. Сложность последовательного алгоритма

:о!лтонозкк яежт в пределах ОСп) - ОСп3). Причем, крайний случай с

Кп3) тсеат место прп популяции болыга ста и от пятьсот' и вксо операций алгоритма.

Определена трудоемкость итерационного ГА ко!шоновки. Пусть II -ш;:зр популяции, I-T - количество, полученных потоков, 1чг0 -солич?стео генераций ■ ГА. Тогда обдая трудоемкость алгориткч ориентир чочнэ определяется

Т* [СП t + ILt_ + СИ * IL) t ] IL,

1 р р пп p п с-0 g

t - трудоо'зсость построения одной индивидуальности в популяш;:;; ;п - трудоэидаегь генерации одного потомка; t - совокупи-.- , грудоекхость селекции и отбора. Трудоемкость построения одно"-'; ¡ндивидуалыюсти ког.эт колебаться от ОСп) до ОСп!), а трудоемкость генерации одного -потока зависит от сложности прнг/еняеюто генетического оператора и ориентировочно ко.сеяяется от ОСп) до ОСп icgn). Трудоемкость селекции и отбора меняется от ОСп) до

Хп2). Сложность итерационного алгоритма. ориентировочно составляет

ХХл8) для одной генерации. Здесь X. - коэффициент,. определяем количеством ГО.

Разработан генетический ,.алгоритм группирования "элекэнтог., эснованшгД на простых преобразованиям матричной иодолк.' BGA данного алгоритма для одной генерации меняется от ОСоп) до ОСan logn).

Разработаны алгоритм! размещения элементов с использование;: методов ?.:оделирования эволмши. Основная цель алгоритмов размецоки-::тшкпзировать оба,ую плоцадь чипа, где разкедартся ¡элемента, п ¡шшпеюпровать обэуз суиггарнуп длину веек цепей. Часто такгэ отагптс.? задача Сил;: ограничение): ьвнгашзировать общее число внутрасяегсяс: пересечений соодкиктелышх проводников.

Стратегия генетического поиска заключается' .в испсльзованш дополнительных генетических операторов, имеющих аналоги в биологии. Начальная "популяция-конструируется тремя способами , Аг, Аз- 1 случае Ai популяция решений (заданных размещений) формируется случайным образом. В случае Аг популяция решений получается путе! неоднократного применения последовательного алгоритма. Форкированш популяции Аз производится совместно случайным и направленным образом. После формирования популяции к каждому ее элементу применяете: оператор мутации. Причем, ОМ может выполняться независимо для каждой элемента популяции. Вводится три варианта ОМ (случайная направленная, комбинированная). Затем выполняется оператор инверси; (0И). Предлагается две версии 0И: случайная (0И ) и направленна: (0И ). Потом выполняются три версии оператора сегрегации. Зате1 переход к выполнению оператора транслокации (ОТ). Также вводится дв< версии ОТ: случайная (ОТ ) и направленная (ОТ,). Последнш выполняется набор операторов кроссинговера СОХ - 0Ки). Предварительно вычисляется верхняя оценка абсолютно' минимальное размещения для заданной конфигурации плоскости. После каждого ГО и: результаты сравниваются с оценкой. При получении искомых результате] алгоритм заканчивает свою работу. После OK вычисляется МФ, и на е< основе сортируются варианты решений. После этого формируется нова: популяция, • и процесс продолжается аналогично. Возможен выход и: каждого оператора в отдельности при получении локального оптимума

ВСА линейного размещения меняется от 0(ап) до 0(ßn2), где а, ß ■ коэффициенты, зависящие от используемых процедур поиска.

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

величиной. Для одной генерации ВСА лежит в пределах 0(апЕ)

ОСа^п3), где с^ , а£ - коэффициенты, определяемые количеством ГО и и: спецификой.

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

j.ene!i, которые долгий соединять модули. Общая ИФ для задачи тланирования определена

МФ = ^ х. • у + Д- с. . • d. ..

Здесь с. . - количество связей, соединяющих inj модули, d -расстояние г.сеглу модулям! i,- j. .

Структура ГА для решения данной задачи описана следующим, эбразом. Сначала создается одна или несколько популяций решений. Рассмотрен случай наличия нескольких популяций. Произведена юртировка хромосом в каздой из популяций. Затем применены описанию :хэ!ш селекции для ЕЫбора. родительских пар. Причем, в кавдой паре родители долгим быть из разных популяций. Описаны четыре кодифицированных ОК. Кахдой хромосоме соответствует определенный план кристалла. Основная задача ГО найти строительные блоки с лучокки характеристикам для копирования их в потошш. Для задач планирования sírfeKTMDiibjyji оказались операторы сегрегации, мутации и инверсии.

Трудоогкость алгоритма ориентировочно определена Т % Т., + [Ш t + CK + lU(tnr. + Ln„ + t„„ tn,J + ¡i, tj IL,

'■! L r> n ;> П О!1. ОС OH Oh PCO

гхе T„ - трудоемкость реализация модели, например, з вяде польско'; записи; t, - трудоемкость селекции; t-.., t„, t„„ t„, - тоудоеккостд

С * ' Oh. ОС Orí Oil

соотготстзу":;:::: гзнотичсскп:: спзратороз.

Увеличить вероятность получения оптимального решения кояю за счет управления процессом генетического поиска путем кзиеиеип.'. (определенного увеличения до попадания з локальный оптимук) размера популяцк.1, количества генераций, вероятности применения генетических операторов, искусственной ютрацзп хромосом, и направленной солекцнк.

В ТРЕТЬЕЙ ГЛАВЕ исследована возможность решения задач трассировки, сгатия топологии и верификации элементов СБИС. Основным-: алгоритма)''; первого этапа трассировки являются. алгоритмы построена;»" кратчайших связывающих дзрезьоз Прима и Штейиерг.

Предложен просто:! эсркстачесготЯ алгоритм построения дерот Штейнера СДШ), ВСА которого ОСоп). Шея алгоритма заключается в следующем. Выбираются первые три точки кз п точек, на которых долгко быть построено ДИ. И строится оптимальный фрагмент ДШ для трех точек. Затем выбираются следующие по порядку три точки, одна из которых принадлежит построс-якому фрагменту. На этих точках строится второ?; оптимальный фрагмент ЛШ. Далее процесс повторяется аналогично, пот не будет построено ДИ. Отметим, что каэдый фрагмент ДШ оптимальны;:, но полное ДЗ в общем случае кокет оказаться неоптикзльны?.-;.

Предложена у1 ценная эвристическая процедура построения ДШ, основанная на "столбах" Штейнера. -Из любой точки, которые требуете: соединить ДШ, проводится вертикальный столб Штейнера, а затем и: остальных, точек проводятся перпендикулярные отрезки на этот столб. Вертикальный столб mosho проводить в любом месте плоскост; (желательно в прямоугольнике, ограничивающем заданные точки) Аналогичным образом строится горизонтальный столб Штейнера.

Представляется возможным иопо.'ъэевать схемы генетического поиск; для построения прямоугольных ДШ. Сначала, используя предложении эвристические алгоритмы, строится популяция Р, каждый элемент которо представляет собой закодированное ДШ. Далее производится сортировк популяции и селекция родительских пар. Затем возможно применени любых ГО на основе мета, микро или ыахро ГА.

"Эксперименты, проведенные в данной работе, показывают, чт наилучший размер популяции % п/2, число генераций для получени квазиоптимальных результатов колеблется от 10 до 100 для соединена 5, 10, 20 и 30 точек. Трудоемкость получения одного потомка меняете

в. пределах 0(п) - 0(п2) и ВСА для разработанных эвристически

алгоритмов ДШ % 0(апг), где а - коэффициент.

При проектировании БИС и СБИС наибольшее применение наш; алгоритмы канальной трассировки. Задан горизонтальный кана; ограниченный верхним и нижним рядами контактов цепей, котор! необходимо соединить. Горизонтальные фрагменты цепей буд] проводиться в первом.слое, а вертикальные фрагменты цепей - во вторе слое. Канал обычно разбивается на- горизонтальные магистрали. Тог; необходимо соединить контакты одноименных цепей канала с минимизащк количества занятых магистралей. При этом допкхы выполнять< горизонтальные (Г) и вертикальные (V) ограничения Г = <(е., е Э | г. п г = 0 Ь V = -{Ca. ,Ь.) | а. * bj * 0; 1 < i, j < Здесь е-. , е^ - цепи, и горизонтальные фрагменты-указанных цепей (г. г ) не .должны пересекаться.Согласно вертикальному ограничен некоторые фрагменты цепей inj должны быть расположены так образом, чтобы верхний вертикальный фрагмент а. не пересекался нижним вертикальным фрагментом Ъ. . .

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

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

Иф = к + иоу) '.

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

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

трассировку за время ОСп2). ,

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

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

/

Данные процедуры выполняются итерационно, и число генераций' зависи' от наличия вычислительных ресурсов. ВСА лежит в пределах OCn log п!

- ОСп3).

Заключительный этап конструкторского синтеза СБИС - верификация, Одной из задач верификации является установление изоморфизма межд; структурной или электрической схемой СБИС и ее топологическо] реализации. Данные задачи решаются путем установления изоморфизм: между графовой моделью электрической 'схемы и графовой моделью ei топологии. Наибольшую трудоемкость представляет установлена изоморфизма однородных графов, имеющих автоморфные подграфы. Дл. решения таких задач используются методы разбиения исследуемых графо: на различные уровни. Предлагается, после получения разбиения, подмножествах наибольшей мощности выполнять ГО мутаций и инверсии Это позволяет параллельно анализировать все подмножество автоморфны вершин и уменьшает время нахождения результата.-

В ЧЕТВЕРТОЙ ГЛАВЕ описаны результаты экспериментальны исследований .генетических алгоритмов при конструкторском синтез элементов СБИС. Все алгоритмы реализованы на языке "С" в вид комплекса программных средств. Эксперименты производились н персональных компьютерах IBM PC - 386, 486. Стандартное модифицированное программное обеспечение ГА расположено в следующи семи файлах: основная программа модифицированного ГА; инициализаци (входные данные); моделирующая функция; селекция; генетически операторы; выходные данные и статистика; интерфейс и управление.

Эксперименты показали, что при компоновке элементов СШ. использование ГА позволяет получать набор локально-оптимальнь решений. При этом с большой вероятностью среди этих решений може быть найдено оптимальное. Из приведенных статистических даннь следует, что в общем случае время решения линейно зависит, с количества генераций и ВСА последовательного алгоритма % ОС a n logr

и для итерационных алгоритмов ВСА % 0(а п2).'

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

сложности (ВСА % 0(n logn) - 0(а п3)). Кроме использован! стаьдартных ОК, ОМ проводились эксперименты с модифицированными О! ОМ, а также с ОИ, ОТ, ОС. При этом время решения ■ возрастало не

линейной, а в квадратичной зависимости, а насыщение, т.е. попадание г. локальный оиттисум происходило при МФ % 0,9000 - 0,9499. Эксперимент показали, что не всегда увеличение размера популяции улучшает Очевидно, что существует какой-то оптимальный размер популяции, отыскать который чрезвычайно трудно, при котором получается оптимальное значение Mî>.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

1. })рзало"ги ао?;Ш подход к редояш» осповкн:: пал:1*? ;oiicî'pyi;iopc);oro прсс;ст!;рсг,а;;ия СЕКС, состоядай в ксполлоою:;;*1; г;тодог; генетического пом ска к позвояяоаий- получать теклпьпо-'ся-лаплшк реггзяй* са пркз!зшяз врег-.-т.

2. гг>:п:Ц'<п:! « кошзгкггя реализация гаяеттскегс юрска п САПР. Пполл'су;-n::i ¡юг:;:: грт»:тсг;г/р« гоиотичэсг:?;:' алгоргл. оч, ¡дат ¡î 07",:<: 'о от г.зг-с&чK:6;:p:iï7, ?лгор,:г. •

о у^-то" елэ/^гсгй пг>с->кткги задяч, орг.'чгпогг iTf,p,!t;,ч п.'^.'С.тгг! ро- "iv;.;.

3. Р:.:урчботан н гссладсззи сритгальш'* алгоритм ш отопок. ; с. ip;ikoircir,:c'.j познх г^^гг.чоссгх cac-paropc1,, попволлплрг; пог;т.ть токалт.пэ-оптиг'аяькпг ргьгже в ВСА аналогичной пссязд>ззтея&н£: с mpsusornr.rî аягортт'-!:.

4. разргботак алгоратк г::гэ:':-;ого разкеггшиг эяег.гктов на ocnoi-:-гэдфщяровтггс гепэтячзскях операторов кроссингог-?р.1, -нутэщ;..:, звере::;:, трэнсяокацп:: ¡1 сегрэггдпи, позвояявдий за счет пригешгг-; генотичгекого поиска :: зф:>:сгивного управления ии попугать набор зптигалыис: рокэниН.

5. Показана воз>.:ог.кссть рзпевая задач трассировки соединений, 5гатия топологии, Ееря^шсацк!! и пестроогош деревьев Ктейнер.ч о :спольоовз.нког£ ксв:,гх архитектур генетического поиска л дадй-*яцпроз?ягоя генетических операторов. Это дает возкогаость, в 5ТЛИЧИЭ от известил: алгоритмов, распараллеливать процесс фоектированпя,1 получать опткталыше и квазпоптшхальнн-з решения с? $рзая, сопоставимое с атерздЕояккмл алгоритмами.

0. Разработал адшиквянй пакет прикладник програл:.

реализованный на языке "С" для IBM совместимых персональны: компьютеров Проведенные экспериментальные исследования показал! перспективность применения генетических алгоритмов при решении зада' конструкторского проектирования.

публикации по теме диссертационной работы

1. Курейчик В.В. Применение генетических методов для компоновк! схем БИС. Междуведомственный тематический научный сборни! "Интеллектуальные САПР", Таганрог, вып. 4, 1994,4 - С. 85 - 88.

2. Чернышев С. 0. , Курейчик В. В. Проблемы построения экспертны подсистем в САПР. Тезисы докладов к• зональной конфереици: "Автоматизация проектирования РЭА к ЭВА", ВНТО РЭС им. А.С.Попова Пенза, 1990. - С. 33 - 34.

3. ' Ивачцов-В. В., Курейчик В. В. Подсистема автоматизированного проектирования технологических маршрутов. Тезисы докладов Всесоюзному НТС "Создание интеллектуальных САПР СБИС и электронны средств",- М. , Радио и связь, 1990. - С. 79 - 80.

4. Курейчик В.М. , Курейчик В. В. Архитектура САПР. Тезис докладов НТС "Проблемы магнитной записи", НТО РЭС им. А.С.Попова, М. 1993. - С. 54.

5. Курейчик В. В. Применение генетических алгоритмов дл компоновки схем РЭА. Тезисы докладов к Всероссийской НТК с участие зарубежных представителей "Интеллектуальные САПР", Таганрог, 1992. С. 40 - 41.' ■

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

on ТР7У. Зак iZQ Тир. 100 199fr.

I