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

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

РГ6 од

2 з

Гаврилов Сергей Витальевич

Методы и алгоритмы оптимизации комбинационных схем для САПР цифровых КМОП БИС

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

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

Москва - 1997

Работа выполнена в Научно-исследовательском институте систем автоматизированного проектирования радиоэлектронной аппаратуры и сверхбольших интегральных схем Российской Академии наук (НИИСАПРАН).

Научный руководитель:

доктор технических наук Русаков С.Г.

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

доктор технических наук, профессор Щемелинин В.М. кандидат технических наук Святский А.Б.

Ведущее предприятие: АООТ "НИИМЭ и завод Микрон"

Защита состоится "_"_ 1997 года в _ на заседании

специализированного совета К200:42.01 в НИИСАПРАН по адресу: 103681, г.Москва, Зеленоград, ул. Советская д.З

С диссертацией можно ознакомиться в библиотеке НИИСАПРАН.

Автореферат разослан "_"_1997 г.

Ученый секретарь специализированного совета кандидат технических наук

В.А. Шепелев

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

Актуальность темы.

Диссертационная работа посвящена исследованию проблем автоматизации проектирования нерегулярных цифровых КМОП схем.

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

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

Вместе с тем, в связи с повышением степени интеграции БИС и сокращением сроков проектирования возникли принципиально новые требования к проектированию БИС. Современные технологические возможности, а именно, появление субмикронных технологии н увеличение количества технологических слоев, привели ' к появлению новых функциональных требований. Потребности современных технологий таковы, чю приемлемое проектное решение может быть найдено только при комплексном учете разнородной проектной информации, традиционно относящейся к разным областям проектирования а разным этапам оптимизации. Существующие коммерческие САПР не содержат эффективных средстЕ для решения ряда пробам, связанных с оптимизацией проектоз з соотигтсшш с новыми технологическими и функциональными требованиями. Ноше амуаишме проблемы проектирования требуют решения оптяишиношши задач с уточненной оцеккск текущей проектной информации. В частной», !р',Г>уетс^ учет •задержек, погреблппюК иодаюгти, топонопкссхпь перямггроз »нугрм ютсяго onrwimsuffii прппцппяелших cxe?f и тониюгки. Bromciuis ?itis тр«к»!>анпй дглмг трбхплямдо! р^рг.Сотку иют-, -imopmîio». Ис«о»ь-«<ч*п1;>.т tn«cn«r; FTiopimw nvt pp«iew"f ког-пч м,тл чтфуягта » чзеки.спг. ><■>■','-

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

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

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

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

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

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

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

2) разработка алгоритмов быстрого расчета задержек и потребляемой мощности ИС для использования внутри оптимизационных циклов;

3) разработка алгоритмов оптимизации мощности и площади ИС на этапе реструктуризации схемы;

4) разработка алгоритмов минимизации площади ИС на этапах размещения элементов и трассировки межсоединений с учетом особенностей результатов синтеза схем.

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

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

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

3) Предложен новый алгоритм для совместного решения задач размещения и глобальной трассировки. В отличие от известных подходов, задача глобальной трассировки, т.е. проблема построения оптимального дерева Штейнера, решается не как самостоятельная проблема, а как составная чясть этапа размещения элементов, что обеспечивает на этапе размещения точный расчет площади кристалла, необходимой для трассировки.

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

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

Реализация.

Разработанные алгоритмы доведены до программной реализации. Проведен цикл экспериментальных исследований. На основе полученных результатов разработан комплекс программ "СТОКС" для синтеза п оптимизации нерегулярных цифровых КМОП-схеы, внедренный на следующих предприятиях: АО "НИИМЭ и з-д Микром", АО "Ангстрем", АО "Институт Точной Технологии и Проектирования", НПО Измерительной Техники, в Наушэ-Пронзводстаняой Ассоциации "Техпрпбор-РКТ". Эффективное«, разработанных алгоритмов и методов описания проектной информации подтверждена опытом эксплуатация более чем на 20 предприятиях электронной промышленности.

Практическая значимость.

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

Апробация работы.

Основные результаты работы были доложены на отраслевом координационном научно-техническом семинаре "Проблемы создания САПР СБИС кремниевый компилятор" (Рига 1987), на отраслевом координационном научно-техническом семинаре "Проблемы создания библиотек САПР СБИС" (Минск 1988), на научных семинарах в НИИСАПРАН РАН, на международном семинаре 4-th International Automation Workshop (IDAW), June, 1994, Moscow, на международной конференции European Design & Test Conference, Paris, France, 1997.

Публикации.

По теме диссертации автором опубликовано 11 работ

Структура и объем работы.

Диссертация состоит из введения, четырех глав и заключения. Основной текст занимает 139 страниц.

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

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

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

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

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

В начале первой главы даны основные понятия и определения, используемые в диссертации. В частности, граф булевых функций (В-грзф) определяется как бинарный ориентированный упорядоченный ациклический граф G — (У, Е), где каждая вершина из множества У описывает логическую функцию, а каждая дуга в множестве Е, исходящая из вершины, описывает ссылки на аргументы соответствующей функции. Рассматриваются функции четырех типов, а именно, конъюнкция (f(a,b) = а&Ь), дизъюнкция (f(a,b) - a+b), отрицание (f(a) = ~а) и тождественное равенство (f(a) = а). Соответственно, любая бинарная вершина а имеет тип Туре(а) = [&! или Туре(а) - f+J и любая унарная вершина имеет тип Туре(а) или Туре(а) ~ [-/.

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

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

_Рисунок 1. Структурная интерпретация графов булевых функций._

Под структурной интерпретацией понимается установление взаимнооднозначного соответствия между некоторым подмножеством множества В-графов и множеством электрических схем заданного класса. Для решения этой задачи предложена классификация вершин и классификация типов графов булевых функций. в-класс вводится для обозначения внешних узлов вентилей и определяется как множество вершин типа [&], [+] или [~], на которые ссылаются только унарные вершины. 1-класс вводится для описания внутренних узлов и транзисторов и определяется как множество вершин типа /А/, [+] или /~/, на каждую из которых ссылается одна бинарная вершина, и никакие друг ие вершины не ссылаются. Канонический В-граф определяется как В-граф, п котором тип левосторонней дочерней вершины отличается от типа родительской вершины. Функционально-структурный граф (ВЭ-граф) определяется как канонический В-граф, удовлетворяющий двум условиям:

(1) первичные входы и выходы имеют тип /=/;

(2) любая вершина, не являющаяся первичным входом или выходом, принадлежит к одному из классов в или I.

В работе показано, что между множеством ВЭ-графов, и множеством комбинационных стандартных КМОП-схем существует взаимно-однозначное соответствие. Примеры Вй-графа и соответствующих схем изображены на рисунке 1.

Для описания топологической информации ВЭ-граф может быть расширен введением дополнительных унарных вершин типа /==/. Топологическое расширение ВЭ-графа или ВЭЬ-граф определяется как В-граф, из которого исходный ВЭ-граф получается в результате операции удаления всех вершин типа [-], не являющихся первичными входами или выходами. Операция удаления заключается в замене ссылок на вершину типа [=} ссылкой на ее потомка.

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

Используя типы вершин для обозначения операций на множестве V, отношение Е предложено описывать в форме операций;

с := а [&} Ь; с .=а /+/ о; с :=> /~/а; с ;= ¡-¡а.

Для обозначения вершнн-аргументоа предложено ввести обратные операции:

если с ;= о /Л/ Ь, то а :- с ]:} Ь (левое деление) и й :=> с /;/ а (правое деление);

если с а /+/ Ь, то а := с ]-] Ь (левое вычитание) и Ь с [-[ а (правое вычитание);

если с :--[~}Ь, то Ь := }~[с

если с := /~]Ь, то Ь }~{с

Для описания алгоритмов расчета характеристик БИС по схеме снизу вверх от первичных входов к первичным выходам предложен метод синтезированных атрибутов. Синтезированный атрибут определяется как функционал, аргументами которого являются отношения [&], [+], ¡~],

Аналогично для описания алгоритмов по схеме сверху вниз от первичных выходов к первичным входам предложен метод унаследованных атрибутов. Унаследованный атрибут определяется как функционал, аргументами которого являются обратные отношения]•], /-/, /.•/, [:[, /~/,/=/.

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

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

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

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

FCOSJ (G)^kA~ + {]~kA)~+knex^- + kD max ^Ш* + knW NnW, А) ро °0 А')

где А - суммарная площадь, Р - мощность, Dex - суммарное превышение норм по задержкам для первичных иыходов, Dn)s% - максимальное превышение нормы по задержке среди первичных выходов, ^„LG " количество небиблиотечных вентилей, Pq - начальные значения площади и мощности, Dg - задержка минимального инвертора, кд,к pft, кртзх, kn^Q коэффициенты, определяющие приоритетность составных частей.

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

Проблема расчета задержек связана с вычислением атрибутов трех типов: синтезированных атрибутов для опенки накопленной задержки распространения сигнала (ariival time) при переключении узла из 0 в 1 и из 1 в 0: TllrrQ\, Tarrw, унаследованных атрибутов для описания требуемой задержки: 7'mjoi.7"т/10> 11 собственней задержки при переключении выхода вентиля по отношению к

u

времени переключения его входов: Oq¡, D¡q. Перечисленные атрибуты связаны, в частности, следующими рекурсивно-определяемыми функционалами: Т^гО 1 (я[+№) = Тапо) (Й[ & ]Ь) = шах(Гягго i (а), Тс!гг0, (6)); ^rrOJ ([~]«) = ТаггЮ («) + А» (Н«)--штоКН^) = т«гга\(я) + Qoi(Ha);

TreqOl (с]-]а) - Tree¡!)l(c[-[b) = Treq0l (с]:]а) = J^oi №t¿) = TreqQ} (с);

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

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

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

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

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

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

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

Так же, как и атрибутные соотношения, операторы преобразования подграфов предложено определять в рекурсивной форме с использованием операций /£/, /+/, /-</, /=/. Например, преобразование де Моргана [(¿м (а,п) для вершины а глубины п предложено определить в операторной форме:

"¿м ([->.») =» аМ1 (а, л), п> О аМ (а[+]Ь, п ам (4&]А, п), п > О ам (а[&]М + 1)=> а[Ы (с[+}М), п > О Остальные преобразования моту! быть определены аналогичным образом. Если результатом преобразования является В-граф, не удовлетворяющий условиям определения В8-графа, то преобразование результата в ВЯ-граф достигается применением ассоциативного закона и добавлением эквивалентных вентилей.

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

■ исключение буферов и эквивалентных вентилей; - синение вентилей с минимизацией;

- цикл декомпозиций с переупорядочиванием подфрагментов, контролем ограничений на задержки и внутренним циклом исследования макроподмножества Вв-графов на основе преобразований де Моргана.

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

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

Простой пример результата реструктуризации показан на рисунке 2.

Рисунох 2. Исходная схема (с!7) и результат реструктуризации

Результаты работы алгоритма на схеме большего размера приведены на рисунке 3. Исходное решение получено с использованием системы "Зупорзув". Результатом реструктуризации является множество решений для разных значений ограничений на быстродействие Показано, что результатом дополнительной реструктуризации на основе предложенных алгоритмов является улучшение площади при заданных ограничениях на задержки на 30% или улучшение быстродействия при той же площади на 15%.

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

и

учетом особенностей результатов синтеза схем. Решению этих проблем посвящена третья глава.

0.7

0.5 -

0.2

Суммарная площадь транзисторов, 10 6 »Г

15%

улучшения задержек

30%

улучшения площади

Исходное решение (ЭупорБуз)

Результат параметрической оптимизации

Результат реструктуризации

2.5 Максимальная задержка, {0Г сек.

Рисунок 3. Результаты реструктуризации для промышленной схемы ск(1.

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

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

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

В качестве глобального оптимизационного метода используется метод отжига. Для применения метода отжига к решению обобщенной задачи размещения и глобальной трассировки исследовано пространство состояний такой задачи и предложен набор операторов перехода в новое состояние. Предлагаемый список операторов включает: (I) изменение порядка соседних элементов в ряду; (2) изменение ориентации (зеркальное отражение); (3) перенос цепи в соседний канал; (4) изменение порядка логически-эквивалентных выводов. Дзе последние операции связаны с решением задачи построения дерева Штейнера в классическом понимании глобальной трассировки. К этой же задаче относится сдвиг вершин ВЭ-графа типа "[=] для описания проходов внутри элементов.

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

О/у, г = О,..., И^-= l,...,(NR +■ 1), где Wj - ширина ряда) в единицах сетки

трассировки, /У^ - число рядов элементов.

Для более точной оценки плотности заполнения каналов предложена модифицированная модель канала, объединяющая непрямоугольную свободную область и две "полузапрещённые зоны": верхнюю и нижнюю. Центральная свободная область доступна для разводки в к слоях с преимущественным горизонтальным направлением, "полузапрещенные зоны" доступны для разводки в I слоях с преимущественным горизонтальным направлением. Понятие "полузапрещенной зоны" означает, в частности, что I < к. Вводятся обозначения:

НЦ'р,Н$0"°т - число горизонтальных треков в верхней и нижней

полузапрещенных областях для столбца г в канале }. Для описания сложной

формы центральной области вводятся обозначения: , . число

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

Чтобы обеспечить трассировку в соответствии с расчетной формулой, нужно решить ряд нестандартных проблем детальной трассировки в канале. Отсюда вытекает задача детальной трассировки в каналах непрямоугольной формы с использованием, надъячеечной области. Решение опирается на использование метода Sangiovanni-Vincentelli (проекты Yack2, Chameleon). Для решения проблем трассировки в каналах сложной формы с нестандартными технологическими ограничениями предложены спецификации весовых функций

/

\

D: = шах ' 0 <i<Wj

\

/

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

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

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

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

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

- модуль расчета задержек;

- модуль расчета мощности методом ключевого моделирования;

- модуль расчета целевой функции;

- модуль сравнения подграфов;

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

- модуль локальной оптимизации в окне;

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

Для этапа топологического проектирования разработано программное

обеспечение, включающее следующие модули:

- модули генерации топологических моделей;

- модуль размещения и глобальной трассировки;

- модуль канальной трассировки;

- модуль расчета емкостей, сопротивлений и задержек межсоединений,

Система перечисленных модулей является базовым программным

обеспечением САПР цифровых КМОГ1 БИС, обеспечивающим комплексное решение задач оптимизации комбинационных КМОП-схем с уточненными оценками текущей проектной информации.

Перечисленные про1раммные средства внедрены на следующих предприятиях: АО "НИИМЭ и з-д Микрон", АО "Ангстрем", АО "Институт Точной Технологии и Проектирования", НПО Измерительной Техники, в Научно-Производспвенной Ассоциации "Техприбор-РКТ". Разработанное программное обеспечение использовано при проектировании свыше ста типов интегральных схем, в том числе, для системы регулирования РЭД-90Й авиадвигателя, перспективной топливоизмерительной системы, блоков микропроцессоров ВМЗБ/ВМ4, элементов АЛУ, умножителя УМБ и др.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ:

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

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

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

3) Разработан алгоритм расчета задержки схемы ira основе метода рекурсивно-опеределяемых функционалов. Отличительной особенностью разработанного алгоритма является использование общей графовой модели. Это обеспечивает высокую скорость работы алгоритма внутри оптимизационных циклов. В отличие от других известных подходов предлагаемый алгоритм позволяет рассчитать верхнюю оценку элморовской задержки для наихудшего дерева нагрузки. Результаты работы программы на основе данного алгоритма по сравнению с результатами точного электрического анализа в системе "Spice": среднее расхождение в расчете задержек: около 10%, максимальное расхождение: в пределах 40%, скорость в 1000-1500 раз выше.

4) Разработан алгоритм расчета потребляемой мощности с использованием метода рекурсивно-опеределяемых функционалов. В отличие от других известных подходов предлагаемый алгоритм позволяет учитывать мощность, рассеиваемую при переключении внутренних узлов схемы. Результаты работы программы на основе данного алгоритма по сравнению с результатами оценки мощности в системе "Epic": среднее расхождение в расчете мощности: около 3%, максимальное расхождение: в пределах 10%, скорость в 15-20 раз выше.

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

"Synopsys": уменьшение площади заказных схем на 20-50% при тех же ограничениях на задержки, уменьшение площади полузаказных схем для заданного библиотечного базиса на 10-20%, скорость в 15-20 раз выше при эквивалентном наборе ограничений, в 2 раза выше по сравнению со временем работы системы "Synopsys" без ограничений.

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

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

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

9) Предложен модифицированный алгоритм локальной трассировки межсоединений. Предложенный алгоритм локальной трассировки является модификацией метода, разработанного в проектах Yack, Chameleon (Berkley University). Новыми разработками являются использование модифицированной модели канала, разработка спецификаций весовых функций для двух фаз канальной трассировки. Результат топологической оптимизации с помощью разработанных алгоритмов по сравнению с результатами аналогичных доступных коммерческих систем - уменьшение площади кристалла на 10-20 % для библиотек стандартных элементов и на 15-30% для заказного проектирования,

10) Разработано программное обеспечение: подсистема оптимизации мощности и площади на этапе проектирования принципиальных схем, система автоматического проектирования топологан заказных схем на основе стандартных элеменюз СТОКС, система автоматического проектирования топологии матричных схем СКАТ для БМК серий 1515ХМ1, 1537ХМ1, ЗОООС, 1806ХШ/ВП1 (АО"Ангстрем"), MS, М7, М9 (НПО "ЭЛЛЗ").

11) Рир&ботанйыг программные средства внедрены на следующих предприятиях: АО "Ш1И\ГЗ и з„ Микрон", АО "Ангстрем", АО "Институт Точной Технологии н Проектирования", НПО Измерительно;') Техник», в Научн1»-Прс<!пгодсгве1ШоП Ассоциации "Теяпри5зр-ГКТ". Перечисленное протраымз.ю сблснвченис использовано при проектировании спым: ста типов шг.чярзлшш схем, е юм чнсяг дня системы риулеротш РЭД-?0М B9¡mr.,!l8l®B.Í, Pípw'nCKtKSlíOil rOIWliCOBBífpbraíUIOn «rctc.-.u, блоки» 4HiíVupo!Urr;.:i,íi! Hf OF>TJMt. эчшгитог АЛУ,> •.адр.-ккге;::: VMH и an

Публикации. Основные результаты диссертации опубликованы в следующих работах:

1. Гаврилов C.B., Егоров Ю.Б., Кононов А.Н., Урахчин А.Ф. Подсистема кремниевой компиляции традиционной САПР СБИС. "Электронная промышленность", 1988, вып. 9(177), стр. 6-8.

2. Гаврилов C.B., Кононов А.Н. Мифологическая модель данных подсистемы кремниевой компиляции традиционной САПР СБИС. -"Электронная промышленность", 1988, вып. 9(177), стр. 8-10.

3. Гаврилов C.B., Надежин Д.Ю., Урахчин А.Ф. Входные языки функционально-структурного описания для подсистемы кремниевой компиляции САПР СБИС. - "Электронная промышленность", 1988, вып. 9(177), стр. 10-12.

4. Гаврилов C.B., Дьяков Ю.Н. Алгоритмы трассировки в кремниевом компиляторе. - "Электронная техника", серия 3 "Микроэлектроника", 1989, вып. 2(131), стр. 52-53.

5. Гаврилов C.B., Назаров С.М., Кононов А.Н. Процедурные возможности языка генераторов модулей. - "Электронная техника", серия 3 "Микроэлектроника", 1989, вып. 2(131), стр. 61-62.

6. S.V.Gavrilov, S.V.Skvortsov, I.G.Topuzov. TOPARS2 - The Software Package for Custom VLSI Layout Design. - In Proc. CCC'91, Sopron, Hungary, 1991.

7. Авдеев Ю.В., Гаврилов C.B., Гуров С.И., Егоров Ю.Б., Скворцов C.B., Топузов И.Г. САПР заказных БИС на открытых вычислительных системах. -"Электронная техника",, серия 3 "Микроэлектроника", 1992.

8. S.V.Gavrilov, E.G.Gorlatch. Detail Layout Optimization for Standard Cells of Arbitrary Height. - In Proc. 4-th International Design Automation Workshop (IDAW), June, 1994, Moscow, p.49-51.

9. Теоретические основы разработки методов моделирования и оптимизации цифровых КМОП схем: заключительный отчет по НИР (ном. гос. per. 01950 003645) - M.: НИИСАПРАН, 1995, 109 стр.

10. Методы и алгоритмы оптимального проектирования низкомощных цифровых и аналоговых КМОП ИС: заключительный отчет по НИР (ном. гос. per. 01960 005795) - M.: НИИСАПРАН, 1996, 75 стр.

11. S.Gavrilov, A.Glebov, S.Rusakov, D.Blaauw, L.Jones, G.Vijayan. Fast Power Loss Calculation for Digital Static CMOS Circuits. Proc. of ED&TC, Paris, 1997, p.411-415