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



ОД

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

Щеглов Сергей Николаевич

Разработка и исследование генетических методов расслоения топологии СБИС

Специальность: 05.13.12 - системы автоматизации проектирования

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

Таганрог 1998 г.

Работа выполнена на кафедре САПР Таганрогского государственного радиотехнического университета.

Научный руководитель - заслуженый деятель науки РФ,

академик АЕН РФ и МАИ, доктор технических наук, профессор Курейчик В.М.

Официальные оппоненты:

- д.т.н., профессор Калашников В.А. (ТРТУ, г. Таганрог)

- к.т.н., доцент Итенберг И.И. (НКБ ВС, г. Таганрог).

Ведущее предприятие - НИИ связи (г.Таганрог)

Защита состоится <<12 " фир&иЗ 1999 г. в часов на заседании диссертационного 'совета Д063.13.02 по защите диссертации при Таганрогском государственном радиотехническом университете по адресу: 347928, г. Таганрог, пер. Некрасовский 44, ауд. Д - 406.

С диссертацией можно ознакомится в. библиотеке университета. Автореферат разослан

"18 " С^сао^Я 1998 г.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент {/ Л А. .Н. Целых.

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

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

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

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

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

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

задачи:

1. Разработка структурной схемы процесса генетического поиска для задач расслоения топологии СБИС.

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

3. Разработка процедур оценки качества .

4. Разработка методов кодирования и декодирования хромосом.

5. Исследование генетических алгоритмов распределения топологии трассировки.

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

Научная новизна диссертационной работы заключается в разработке:

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

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

Генетический алгоритм и комплекс программ распределения соединений топологии СБИС.

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы: использование в госбюджетных работах "Разработка теории и методов построения интегрированных САПР БИС с элементами искусственного интеллекта" (№ ГР 01.9.50004188) /'Разработка методов и моделей генетического поиска в интеллектуальных САПР" выполненной в рамках государственной научно-технической программы "Университеты России" (1995-1996 г.г.), хоздоговорной работе "Учебно-методический комплекс. Применение экспертных систем в инженерной практике" выполненной в рамках научно-технической программы

"Компьютеризация образования" (1995 г.), "Исследование генетических методов оптимизации" (№ ГР 02.9.70001838).

Результаты работы используются в МГТИ (г. Майкоп). Кроме того материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций и в цикле лабораторных работ по курсу "Методы генетического поиска".

Апробация основных теоретических и практических результатов работы проводилась на научных семинарах "Генетические алгоритмы" (осень 1994 - весна 1995 г. г. ТРТУ), Всероссийской научно-технической конференции студентов и аспирантов "Новые информационные технологии. Информационное, программное и аппаратное обеспечение" (г. Таганрог 1995 - 97 г.), Всероссийской научно-технической конференции с участием зарубежных представителей "Интеллектуальные САПР" (г. Геленджик 1994-98 г.).

Публикации. Результаты диссертации отражены в 9 печатных работах.

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 133 страниц , включая 33 рисунка, 10 таблиц, список литературы из 102 наименований, 8 стр. приложений и актов об использовании.

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

Во введении обоснована актуальность диссертационной работы,

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

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

ограничений по другим критериям либо применяют аддитивную или мультипликативную форму оценочной функции, например следующего вида:

Б- аддитивный критерий; Д -весовой коэффициент; /. -частный критерий; р - число частных критериев.

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

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

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

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

V Л

где:

р

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

попытками дополнить их новыми цепями.

К достоинствам представленной структуры можно отнести следующее:

• отсутствие сложных элементов;

• согласованность генов, которая обеспечивает сокращение сроков проектирования;

• пространственная сложность хромосомы является линейной, что свидетельствует о небольшом количестве требуемой памяти ОЗУ для хранения популяции.

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

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

Пусть в операцию кроссинговера вступают две хромосомы "Родитель 1 "и "Родитель2". Выбор родителей производится на основе значений их целевых функций - чем лучше значение оценочной функции родителя, тем больше шансов быть выбранным для операции кроссинговера.Работа оператора кроссинговера основана на принципе обмена информацией между "родителями". У каждого родителя определяется слой, содержащий максимальное количество цепей. Затем происходит обмен данными между родителями, - выбранные слои переносятся от одного родителя к другому и наоборот. Цепи, перенесенные при переписывании слоев исключаются из остальных слоев новой хромосомы.

Операция мутации применяется к одной хромосоме и

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

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

Цель использования этих операторов - предотвращение единообразия во множестве решений. Сознательное ухудшение некоторых решений привносит новую информацию и является механизмом выхода из "локальных ям".

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

F(A) = —-—+--- ,

kS(A) fi-R{A)

где S - число слоев, в которых необходимо разместить заданные соединения;

R - количество соединений расположенных в одном слое (пара-плоскости);

к,р- весовые коэффициенты, устанавливаемые эмпирическим путем.

Задачей генетического поиска является максимизация значения целевой функции.

Теоретическая временная и пространственная сложность генетического алгоритма распределения трассируемых соединений по слоям составляет 0(N^), где N - число цепей.

В четвертой главе приведено описание экспериментальных исследований генетического алгоритма распределения трассируемых соединений по слоям. Экспериментальные исследования преследовали две цели: исследование механизмов генетического поиска для решаемых задач и исследование эффективности предложенного алгоритма. Для их проведения был разработан пакет программ на языке Borland С++ под Windows 95, которые позволяют эффективно использовать преимущества генетического поиска. Эксперименты проводились на ЭВМ типа IBM PC с процессором Pentium.

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

После проведения регрессионного анализа были получены следующие зависимости для генетического алгоритма распределения топологии СБИС:

- зависимость времени решения задачи от числа цепей в

задаче

у(х) = 3.632103-Ю"3 -X2 + 2.743389-101-х + 2.157987-Ю"1;

- зависимость занимаемой оперативной памяти от числа цепей в задаче

у(х) = 6.824533- 10-3-х2 + 8.486845-101-х + 1.656174. Для алгоритма расслоения топологии СБИС зависимость времени решения задачи и зависимость занимаемой оперативной памяти от числа цепей в задаче составили О(N2). Во втором разделе исследовались механизмы генетического поиска. Задачей исследования являлось выявление наилучших сочетаний управляющих параметров генетического поиска (тип селекции, тип кроссинговера, вероятность переноса гена из одной хромосомы в другую, вероятность мутации и размер популяции) для генетического алгоритма распределения трассируемых соединений по слоям. В третьем разделе сравнивались качества решений, полученных представленными алгоритмами, с качеством решений, получаемых существующими алгоритмами. Сравнение проводилось на стандартных примерах Ех1, ЕхЗа, ЕхЗЬ, ЕхЗс, Ех4Ь, Ех5 и "трудном" канале Дойча.

Проведенные исследования показали, что применение генетического алгоритма распределения трассируемых соединений по слоям позволяет сократить сроки проектирования на 8-14% и улучшить качество получаемых решений на 5-10%.

ЗАКЛЮЧЕНИЕ

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

2. Рассмотрены структуры процесса генетического поиска, методы селекции и отбора, выявлены их особенности и даны

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

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

4. Для разработанного алгоритма создан пакет программ на языке Borland С++ под Windows 95, который позволяет эффективно использовать преимущества генетического поиска.

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

алгоритмами, которое показало преимущество представленных алгоритмов над существующими. 6. Проведенные исследования показали, что применение генетического алгоритма распределения трассируемых соединений по слоям позволяет сократить сроки проектирования на 8-14% и улучшить качество получаемых решений на 5-10%.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ.

1. Щеглов С.Н. Канальный трассировщик на основе метода имитации эволюции. // Тезисы докладов 3-й Всероссийской научной студенческой конференции, Таганрог, 1996, с. 72.

2. Щеглов С.Н. Применение генетических алгоритмов для

решения задачи назначения слоев в базовых матричных кристаллах. Известия ТРТУ №3 "Материалы Всероссийской научно-технической конференции с участием зарубежных представителей "Интеллектуальные САПР - 95", Таганрог, ТРТУ, 1996 г., с.28-31.

3. Щеглов С.Н. Исследование генетического алгоритма для решения задачи назначения слоев в базовых матричных кристаллах. Известия ТРТУ № 3, Таганрог, 1997, с.232-234.

4. Щеглов С.Н. Эволюционный подход к адаптации в интеллектуальной САПР СБИС. //Тезисы докладов Всероссийской научной конференции студентов и аспирантов "Радиоэлектроника.

Микроэлектроника. Системы связи и управления", Таганрог, 1997, с.297.

5. Щеглов С.Н., Мухлаев A.B., Кулинский В.А. Разработка методов исследования характеристик генетического алгоритма распределения цепей по слоям в МСМ. Известия ТРТУ № 2, Таганрог, 1998, с.296-298.

6. Мухлаев A.B., Щеглов С.Н., Сеченов М.Д. Ликвидация

вертикальных конфликтов межсоединений в канале перед трассировкой Известия ТРТУ № 2, Таганрог, 1998, с. 166.

8. Щеглов С.Н., Кулинский В.А. Программная реализация алгоритма решения задачи назначения слоев в мультикристальных модулях. //Тезисы докладов 4-й Всероссийской научной конференции студентов и аспирантов, Таганрог, 1998. с. 91.

9. Щеглов С.Н. и др. Исследование генетических методов оптимизации. // Депонир. во ВНТИ № ГР 02.9.70001.838, Таганрог, 1996.

Личный вклад автора в работах, написанных в соавторстве:

[5] - разработка методики создания популяции, разработка целевой функции; >

[6] - разработка методики кодирования и декодирования хромосом;

[8] - разработка программы-оболочки алгоритма решения задачи;

[9] - разработка и модификация генетических операторов.

Соискатель:

С.Н. Щеглов

\

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

J

РОССИЙСКОЙ ФЕДЕРАЦИИ

ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

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

Л

" 1 ЩЕГЛОВ Сергей Николаевич

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

ТОПОЛОГИИ СБИС

Специальность: 05.13.12 - системы автоматизации проектирования

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: заслуженный деятель науки РФ, академик АЕН РФ и

МАИ, д.т.н., профессор Курейчик В.М.

Таганрог - 1998г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...............................................................................................4

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

1.1. Выбор модели исследования......................................................14

1.2. Классификация подходов к решению задачи расслоения соединений....................................................................................................22

1.3. Методы дотрассировочного расслоения.................................26

1.3.1. Распределение соединений по слоям методом пробного назначения..................................................................................................26

1.3.2. Методы учета степени "взаимодействия" связывающих деревьев.......................................................................................................34

1.4. Расслоение совмещенной топологии схемы. .........................38

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

2. ИССЛЕДОВАНИЕ МЕТОДОВ ГЕНЕТИЧЕСКОГО ПОИСКА

ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ ПО СЛОЯМ.........................................................................43

2.1. Анализ эволюционных процессов............................................43

2.1.1. Роль популяции в цепи естественного отбора.......................46

2.1.2. Стратегии формирования популяции в задачах САПР.........48

2.1.3. Наследственные факторы и их оценка в оптимизационных задачах.........................................................................................................50

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

2.3. Структура основных операторов генетического поиска......56

2.3.1 Селекция...................................................................................56

2.3.2 Кроссинговер...........................................................................59

2.3.3. Мутация...................................................................................67

2.3.4. Отбор.......................................................................................71

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

3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ТРАССИРУЕМЫХ СОЕДИНЕНИЙ ПО СЛОЯМ В СБИС......74

3.1. Формулировка задачи, основные понятия и определения. ... 74

3.2. Разработка структурной схемы процесса генетического

поиска для задач расслоения топологии СБИС......................................77

3.3 генетический алгоритм распределения трассируемых соединений по слоям...................................................................................84

3.3.1 Представление хромосомы......................................................85

3.3.2 Разработка процедуры определения пересечений.................90

3.3.3 Целевая функция......................................................................92

3.3.4. Генетические операторы и генетический алгоритм............263

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

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

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

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

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

4.3. Определение управляющих параметров генетического алгоритма решения задачи распределения трассируемых соединений по слоям.......................................................................................................331

4.4. Сравнение результатов, получаемых представленным генетическим алгоритмом распределения трассируемых соединений по слоям.......................................................................................................356

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

ЗАКЛЮЧЕНИЕ....................................................................................358

ЛИТЕРАТУРА......................................................................................358

ВВЕДЕНИЕ

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

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

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

Одним из важнейших достижений человечества стало создание интегральных схем. Возникшие в 60-х годах нашего века, интегральные схемы развились, за короткое время, от объединения нескольких транзисторов до интеграции миллионов транзисторов в одной схеме. Первые интегральные схемы (ИС) представляли собой объединение одиночного транзистора с набором сопротивлений, предназначенное для выполнения какой-либо логической функции. Сейчас ИС способны выполнять сложнейшие функции, они проникли во все слои человеческого общества, современное общество не смогло бы возникнуть без использования ИС. В настоящее время, геометрические размеры элементов могут иметь размеры до 0.18 микрона (один микрон = 1.0 х 10~6 метра), для сравнения человеческий

волос в диаметре около 75 микронов. В ближайшие пять лет ожидается уменьшение размеров на 0.1 микрона. Современная технология позволяет разместить 10-15 миллионов транзисторов на схеме размером 25 мм. х 25мм. Такая быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [1-26]. Сейчас, на всех стадиях проектирования топологии сверхбольших ИС (СБИС), интенсивно используют средства автоматизации проектирования и многие фазы могут быть полностью или частично автоматизированы.

Цикл проектирования СБИС включает следующие основные фазы:

• спецификация системы;

• функциональное проектирование;

• логическое проектирование;

• схемное проектирование;

• конструкторское проектирование;

• изготовление;

• сборка, тестирование и контроль.

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

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

Фаза логического проектирования заключается в определении размера слов, распределении регистров и управляющих потоков, арифметических и логических операций. Для логического описания систем используют язык УНБЬ. Логическое описание включает минимизированные булевы функции и описание временных задержек. При логическом проектировании делается моделирование и тестирование системы для проверки корректности построенной системы.

Целью схемного проектирования является преобразование результатов логического проектирования в схемы. На этом этапе выполняется схемное моделирование для проверки корректности и задержек каждого компонента. Результатом схемного проектирования является подробное схемное представление системы.

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

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

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

Этап конструкторского проектирования подразделяется на разбиение, планирование, размещение, трассировку, упаковку и верификацию.

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

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

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

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

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

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

использующем 4 слоя металлизации, около 40% площади отводится под межсоединения. Эти тенденции ведут к возрастанию значения трассировки при конструкторском проектировании, требуют разработки методов получения более качественных решений на этом этапе.

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

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

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

Большой вклад в решение задач внесли работы таких учёных как Селютин В. И., Курейчик В. М., Корячко В. П., Норенков И. П., Анисимов В. И., Батищев Д. И., Вермишев Ю. X., Лошаков В. Н., Широ Г. Э., Бершадский А. М., а также зарубежные учёные такие как: N. Sherwani, С. Sechen, М. А.

Breuer, S. В. Akers, H. H. Chen, D. N. Deutsch, R. Joobbani. [1 - 8, 64 - 71, 73 -76]

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

Существует несколько подходов к решению NP - полных задач.

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

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

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

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

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

Сравнительно недавно их начали широко применять для решения задач в самых различных областях, в том числе для решения задач проектирования СБИС [38,60-61], [41].

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

• осуществляют поиск из множества точек, а не из единственной точки;

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

• используют не детерминированные, а вероятностные правила;

• дают не одно решение, а целый спектр решений.

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

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

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

1. Разработка структурной схемы процесса генетического поиска для задач расслоения топологии СБИС.

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

3. Разработка процедур оценки качества (фитнесса).

4. Разработка методов кодирования и декодирования хромосом.

5. Исследование генетических алгоритмов распределения топологии трассировки.

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

и

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

a) разработке архитектуры генетического поиска, ориентированной на решение задач распределения трассируемых соединений по слоям;

b) определении методики решения задачи расслоения топологии;

c) разработке модифицированных генетических операторов, ориентированных на решение задач трассировки.

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

Генетический алгоритм и комплекс программ распределения соединений топологии СБИС.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Основные теоретические и практические результаты диссертационной работы: использование в госбюджетных работах «Разработка теории и методов построения интегрированных САПР БИС с элементами искусственного интеллекта» (№ ГР 01.9.50004188), «Разработка методов и моделей генетического поиска в интеллектуальных САПР» выполненной в рамках государственной научно-технической программы «Университеты �