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

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

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

Автоматизация проектирования — это многоаспектная, многоуровневая проблема, охватывающая исследование, разработку, производство и эксплуатацию технических, математических, программных и информационных средств [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.50 004 188), «Разработка методов и моделей генетического поиска в интеллектуальных САПР» выполненной в рамках государственной научно-технической программы «Университеты России» (1995;1996 г. г.), хоздоговорной работе «Учебно-методический комплекс. Применение экспертных систем в инженерной практике» выполненной в рамках научно-технической программы «Компьютеризация образования» (1995 г.), «Исследование генетических методов оптимизации» (№ГР 02.9.70 001 838).

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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