Введение к работе
Актуальность темы.
Диссертационная работа посвящена исследованию проблем автоматизации проектирования нерегулярных цифровых КМОП схем.
Ключевыми характеристиками качества проектирования таких схем являются площадь, быстродействие, потребляемая мощность. Важную роль и автоматизированном проектировании играют автоматические средства оптимизации этих характеристик. К числу актуальных проблем относятся, и частности, проблемы минимизации площади или мощности при заданных ограничениях на быстродействие. Задачи, связанные с минимизацией этих характеристик, представляют собой проблемы очень высокой сложности. В реальном проектировании процесс оптимизации разбивается на последовательность отдельных этапоз. Характерная последовательность этапов, связанных с решением оптимизационных проблем для рассматриваемого класса схем, включает этапы логической оптимизации системы булевых функций, этапы оптимизации принципиальных схем и этапы топологической оптимизации. К этапам оптимизации принципиальных схем относятся разложение системы булевых функций в заданном базисе элементов, структурная оптимизация принципиальных схем, параметрическая оптимизация размеров транзисторов. Этапами топологической оптимизации являются размещение элементов на плоскости кристалла, глобальная трассировка, детальная трассировка.
Среди коммерческих САПР наибольшее распространение получили средства топологической оптимизации в составе систем автоматического синтеза топологии. В ряде САПР, среди которых наиболее известна система компании "Synopsys", реализована также логическая оптимизация с разложением системы булевых функций в заданном базисе элементов.
Вместе с тем, в связи с повышением степени интеграции БИС и сокращением сроков проектирования возникли принципиально новые требования к проектированию БИС. Современные технологические возможности, а именно, появление субмнкронных технологий и увеличение количества технологических слоев, привели ' к появлению новых функциональных требований. Потребности современных технологий таковы, ч\о приемлемое проектное решение может быть найдено только при комплексном учете разнородной проектной информации, традиционно относящейся к разным областям проектирования и разным этапам оптимизации. Существующие коммерческие САПР не содержат эффективных средах для решения ряда пробам, связанных с оптимизацией проешоз з соответстыш с новыми техі!с;:огаческтіми и функциональными требованиями. Новые змуапмсые проблемы проектирования требуют решения оптамт.'шишшы;: задач с. уточненной оцекксі'ї текущей проектной информации, В частноси!, ір'.буетс'і учет задертке:;, поіребппгігоП нотяногти, топочопічески*. параигіров i»nyf;:.i 1111^: оптишпаш:;! припннпмаяьния схел п то!-ои»п:и. Вглмчснп; '.'ш:; требі^лнпн делает і>гг4шш!Мі."гі глчргботку ііозіг; ічгпршмо:». Исііощ.'іч.'-.яіі'.т rnatcunr; п'їіорит^п:» ічі річиенг"? иог-пч з.їд".ч чтфуягшч!, в чг>сі;ї<>сіп. іч-'. -
разного характера моделей для различных аспектов описания схемы: логического, схемотехнического, топологического.
Диссертация посвящена разработке комплекса вычислительных алгоритмов для решения оптимизационных задач на стадиях проектирования принципиальных схем и топологии с уточненной оценкой текущей проектной информации. Рассматривается класс комбинационных КМОП схем для реализации нерегулярных логических функций. Актуальность проблемы именно для данного класса схем обусловлена двумя факторами. Во-первых, проблема минимизации задержек имеет непосредственное отношение к комбинационным фрагментам БИС. Во-вторых, комбинационные схемы, в отличие от трактов обработки данных и элементов памяти, являются, как правило, нерегулярными структурами, что составляет наибольшую проблему при оптимизации в связи с высокой размерностью задачи.
Детальный учет проектной информации становится реальным при помощи обобщенной модели схемы. Разработка обобщенных моделей ИС для разных этапов оптимизации и обобщенных методов описания алгоритмов является в настоящее время задачей, не решенной на практическом уровне. Необходимы модели, обеспечивающие возможность разрабатывать новые алгоритмы структурной оптимизации схемы (реструктуризации), объединяющие по своим возможностям классические этапы логической оптимизации, разложения в заданном библиотечном базисе, параметрической оптимизации размеров транзисторов. С результатами параметрической оптимизации схем неразрывно связаны новые проблемы топологической оптимизации. К таким проблемам относятся: размещение разновысотных элементов в связи с изменением диффузионных областей в результате параметрической оптимизации, и проблема трассировки в каналах непрямоугольной формы с использованием области над элементами.
Основные исследования диссертационной работы связаны с разработкой модели КМОП-схем, разработкой алгоритмов для расчета значений характеристик схемы, разработкой алгоритмов для реструктуризации схемы и решением новых проблем топологической оптимизации.
Цель работы. Целью диссертационной работы является исследование и разработка комплекса вычислительных алгоритмов для оптимизации заказных нерегулярных цифровых КМОП-схем.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
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 страниц.
