Введение к работе
Актуальность темы
Современная БИС содержит порядка 10-15 миллионов вентилей на кристалле размером 25x25 мм с минимальным топологическим размером ~0.18д. Конструирование такой сложной системы является чрезвычайно трудоемкой и многоплановой задачей, которую невозможно решить без автоматизации проектирования. Одним из самых трудоемких этапов проектирования СБИС является трассировка; для большой схемы требуется обработать ~107-108 соединений. Учет конфигурации соединения может.еще на порядок увеличить размерность задачи. Даже мощности современных вычислительных комплексов для этого недостаточно. Необходимо применять иерархический подход, при котором весь кристалл разбивается на блоки, каждый из которых проектируется отдельно путем его рззбиения на субблоки. Для цифровых БИС важно, чтобы сигнальные цепи и цепи синхронизации попадали в отведенные для них временные рамки, поэтому для уменьшения задержки надо минимизировать длину цепей и количество переходов из слоя в слой. Для аналоговых БИС важно избегать, например, паразитных емкостей, для чего необходимо минимизировать количество теневых сегментов проводников. Оптимальный синтез топологии цифровых и аналоговых БИС во многом зависит от эффективного проектирования прямоугольной топологической ячейки с выводами на ее границе (свичбокса).
На существующем этапе развития, вычислительных средств, предназначенных для решения задач трассировки, главная роль при принятии особо важных решений до сих пор отводится человеку. В результате время проектирования все еще остается большим Необходимо менять ситуацию в сторону полной автоматизации процесса проектирования. Поэтому проблема автоматизации синтеза топологии остается актуальной в наши дни.
Цель и задачи работы
Целью диссертационной работы является разработка методов и алгоритмов автоматизированного синтеза топологии БИС на основе более эффективных моделей трассировки топологической ячейки.
В ходе выполнения работы ставились и решались следующие задачи:
Анализ структуры современной схемы проектирования БИС и основных ее алгоритмов.
Анализ существующих методов трассировки свичбокса.
Разработка нового подхода к трассировке свичбокса.
Разработка программного обеспечения, иллюстрирующего эффективность предлагаемого подхода.
Тестирование программного комплекса на стандартных и усложненных примерах.
Методы исследования
"В ходе выполнения работы использовались методы общей алгебры, теория множеств, теория графов, алгоритмы на графах, исследование операций, методы объектно-ориентированного программирования.
Научная новизна результатов работы
Предложен подход к решению задачи свичбокса, удовлетворяющий современным требованиям. Он опирается на многоуровневую, многовариантную и многокритериальную трассировку.
Предложена новая многоуровневая модель решения задачи свичбокса. Выделены алгебраический, топологический и геометрический уровни.
На алгебраическом уровне введено понятие Х- простейшей трассировки.' Обоснован синтез топологии в классе Х- простейших трассировок. Показаны возможности ухода от NP-полноты задачи трассировки при таком подходе.
Введены параметры модели трассировки для каждого уровня абстракции. Показана их связь с соответствующими параметрами границы свичбокса.
Сформулированы критерии оптимизации эскиза на основе предложенных характеристик. Проведена классификация критериев по уровням модели.
Проведена оценка сложности операторного метода трассировки свичбокса. Показано, что сложность операторного метода синтеза оптимальной Х-трассировки равна 0(n2 logn), где п - число активных выводов на границе свичбокса.
Практическая значимость и результаты внедрения работы Разработаны алгоритмы синтеза трассировки свичбокса на ochodo предложенной математической модели, которые обеспечивают
скорость получения одного решения, превышающую лучшие зарубежные аналоги;
настройку решения на любой критерий, задаваемый пользователем.
Разработан программный комплекс, реализующий алгоритмы синтеза трассировки, который ориентирован на распространенные и относительно дешевые технические средства, такие как IBM PC совместимые компьютеры.
Система синтеза трассировки включает входной язык, позволяющий пользователю легко вводить и менять критерии проектирования, а также параметры ее настройки.
Предложен новый конструкторский элемент, позволяющий значительно эффективнее использовать коммутационное пространство по сравнению с известными технологиями.
Результаты диссертационной работы внедрены в учебный процесс МИЭТ (Зеленоград) и использовались при проектировании топологии БИС на основе базовых кристаллов в ООО «Ангстрем - Р7Л%, о ^м свидетельствуют прилагаемые акты внедрения
На защиту выносятся:
Многоуровневая модель топологии ячейки общего вида, позволяющая на каждом ее уровне представить множество вариантов, выражающих определенные свойства топологии.
Настройка модели на многокритериальную оптимизацию топологии, определяемую проектировщиком.
Настройка модели ячейки на различные способы расслоения.
Эффективные алгоритмы построения оптимальной топологии ячейки.
Эффективный выбор средств реализации алгоритмов оптимизации топологии ячейки в среде WINDOWS 95/98/NT для персональных ЭВМ.
Структура и объем диссертационной работы
Диссертационная работа содержит введение, пять глав, заключение, список литературы (191 наименование) и приложение. Полный объем работы - 176 страниц, в том числе 7 таблиц и 42 рисунка.
