Введение к работе
. Аннотация.
Одним из ключевых этапов топологического проектирования СБИС является трассировка цепей. Применительно к нанометровым СБИС проблема существенно усложняется за счет того, что в процессе трассировки необходимо выполнять оптимизацию одновременно по нескольким критериям.
Данная работа посвящена проблеме планировки цепей. С ее помощью формируются эскизы трасс, что в значительной мере предопределяет функциональные характеристики схемы. Построение деревьев Штейнера является наиболее распространенным подходом в данной области. В диссертационной работе предлагается новый метод, суть которого состоит в построении не одного, а множества (семейства) деревьев Штейнера для каждой цепи.
В рамках диссертации разработаны: алгоритм построения семейства остовных деревьев, алгоритм приведения остовных деревьев к деревьям Штейнера с ортогональными ребрами, алгоритм фильтрации семейства деревьев и алгоритм оптимизации планировки цепей для всей схемы, выбирающий определенное дерево Штейнера для каждой цепи. Математически формализованы: оценка близости топологии двух деревьев Штейнера, целевая функция, отражающая равномерность распределения загруженности коммутационных областей. На основе разработанных алгоритмов создано программное обеспечение для планировки цепей при автоматизированном проектировании топологии СБИС.
В работе проведено исследование программной реализации разработанного метода планировки цепей, сравнение с традиционно применяемыми методами. Сделан вывод о перспективности предложенного подхода.
Актуальность темы.
Уменьшение топологических норм до 45нм и меньше приводит к существенному увеличению стоимости производства. Как следствие, задача минимизации площади кристалла становится еще более актуальной, загруженность коммутационных областей при этом значительно повышается. Быстродействие нанометровых СБИС зависит в основном от физических параметров межсоединений (длина, ширина и толщина металлизации), поэтому минимизация суммарной длины цепей - один из важнейших критериев проектирования. Увеличение
количества выделяемого тепла приводит к проблеме его отвода и равномерного распределения по площади кристалла.
В связи с усилением влияния паразитных эффектов суб-100нм технологии (cross-talk, IR-drop) на работоспособность нанометровых СБИС возникает необходимость учитывать их непосредственно на этапах размещения и трассировки. Коррекция паразитных эффектов оптической близости (ОРС - Optical proximity Correction) частично производится с помощью добавления принципиально новых конструкторско-технологических ограничений. Также вводятся дополнительные требования к максимальной и минимальной плотности металлизации, что должно обеспечить качество химико-механической полировки.
Появление описанных эффектов приводит к усложнению задачи топологического проектирования в целом, и планировки цепей в частности. Необходимость одновременной оптимизации по нескольким критериям непосредственно при синтезе топологии выводит на первый план поиск новых методов планировки цепей. На этом этапе основной моделью топологии цепи является дерево Штейнера. Большинство существующих алгоритмов проводит только пост-оптимизацию и не учитывает влияние всех деревьев целиком, а разбивает их на составляющие. Данная работа посвящена решению проблемы построения дерева Штейнера с возможностью одновременного учета критериев при построении топологии цепей на этапе планировки цепей.
Цели и задачи работы.
Целью данной диссертационной работы является разработка математического, алгоритмического и программного обеспечения для планировки цепей СБИС с равномерным заполнением области трассировки. Для достижения данной цели в диссертационной работе решены следующие задачи:
Проведен анализ существующих методов построения и оптимизации деревьев Штейнера, рассмотрены их преимущества и недостатки;
Предложен метод планировки цепей с использованием семейств деревьев Штейнера, устраняющий выявленные недостатки;
Разработан алгоритм генерации семейства деревьев Штейнера;
Разработан алгоритм фильтрации семейства деревьев Штейнера и критерий близости структуры двух деревьев;
Разработан алгоритм оптимизации, выбирающий определенное дерево Штейнера для каждой цепи исходя из состава семейств;
Разработанные алгоритмы реализованы в виде комплекса программного обеспечения;
Проведена практическая апробация результатов работы.
Научная новизна работы
Разработан, реализован и исследован метод планировки цепей СБИС, основанный на использовании семейств деревьев Штейнера, что позволяет при оптимизации учитывать деревья целиком, а не разбивать их на составляющие;
Разработан алгоритм генерации семейства деревьев Штейнера на основе семейства остовных деревьев, который позволяет получить деревья Штейнера с заданной длиной и различной топологией;
Предложен и обоснован критерий сравнения структуры двух деревьев Штейнера, основанный на анализе влияния дерева на локальную коммутационную плотность, что позволяет определять и исключать одно из деревьев с близкой топологией;
4. Введена целевая функция для оптимизации планировки цепей, основанная на оценке равномерности заполнения коммутационного пространства, что позволяет учитывать решение целиком и распределять цепи в минимально загруженные коммутационные области.
Методы исследования.
При разработке алгоритма генерации семейств деревьев Штейнера был использован математический аппарат дискретной математики. При разработке алгоритмов фильтрации и оптимизации был использован математический аппарат теории множеств, теории алгоритмов и математической статистики. При разработке программного обеспечения были использованы унифицированный язык моделирования (UML), профилирование и отладка. Экспериментальные результаты были получены при помощи разработанного программного обеспечения.
Достоверность полученных результатов подтверждается
используемым в работе математическим аппаратом,
экспериментальным тестированием и эксплуатацией разработанного программного обеспечения.
Личный вклад автора.
Все результаты, приведенные в диссертации, получены либо лично соискателем, либо при его непосредственном участии. Можно выделить следующие наиболее значимые результаты:
Решена задача использования семейства деревьев Штейнера для планировки цепей СБИС с равномерным заполнением области трассировки;
Разработан алгоритм генерации семейства деревьев Штейнера;
Разработан алгоритм фильтрации семейства деревьев Штейнера на основе критерия близости структуры двух деревьев Штейнера;
Разработан алгоритм оптимизации, определяющий топологию цепей исходя из состава семейств деревьев Штейнера и равномерности заполнения области трассировки;
Создано программное обеспечение для реализации разработанных алгоритмов.
Диссертационная работа выполнена в рамках очной аспирантуры МИЭТ (ТУ).
Практическая значимость работы.
На основе разработанных алгоритмов был создан комплекс прикладного программного обеспечения для планировки цепей при проектировании топологии СБИС. Использование разработанных алгоритмов и программного обеспечения позволяет улучшать трассируемость схем путем повышения равномерности заполнения области трассировки без существенного увеличения суммарной длины цепей.
Реализация результатов работы.
Результаты работы в виде программных модулей для программы планировки цепей при топологическом проектировании ИС внедрены в учебный процесс МИЭТ, а также в процесс проектирования базовых матричных кристаллов на ОАО «Ангстрем».
Представляются к защите.
Метод планировки цепей СБИС с равномерным заполнением области трассировки, основанный на использовании семейств деревьев Штейнера.
Алгоритм генерации семейства деревьев Штейнера на основе остовных деревьев.
Алгоритм фильтрации семейства деревьев Штейнера, основанный на критерии близости структуры двух деревьев Штейнера.
Целевая функция для учета трассируемости схемы, описывающая равномерность заполнения области трассировки.
Апробация результатов работы.
Результаты диссертационной работы докладывались и обсуждались на следующих конференциях:
XIII Всероссийская межвузовская научно-техническая
конференция студентов и аспирантов, Москва, Зеленоград, 19-21 апреля
2006 г.
XIV Всероссийская межвузовская научно-техническая
конференция студентов и аспирантов, Москва, Зеленоград, 18-20 апреля
2007 г.
XV Всероссийская межвузовская научно-техническая конференция
студентов и аспирантов, Москва, Зеленоград, 23-25 апреля 2008 г.
Moscow-Bavarian Joint Advanced Student School (MB JASS), Москва, Зеленоград, 2-11 марта 2009 г.
XVI Всероссийская межвузовская научно-техническая
конференция студентов и аспирантов, Москва, Зеленоград, 22-24 апреля
2009 г.
XVII Всероссийская межвузовская научно-техническая
конференция студентов и аспирантов, Москва, Зеленоград, 28-30 апреля
2010 г.
Международная научно-техническая конференция
«Проектирование систем на кристалле: тенденции развития и проблемы», Москва, Зеленоград, 19-21 октября 2010 г.
Moscow-Bavarian Joint Advanced Student School (MB JASS), Москва, Зеленоград, 20-27 марта 2011 г.
Публикации.
Основные результаты диссертационной работы опубликованы в двух научных статьях и семи докладах в трудах научно-технических конференций.
Структура и объём работы.
Диссертационная работа состоит из введения, четырёх глав, заключения, приложения, содержащего акты внедрения результатов работы, и списка использованных литературных источников, содержащего 94 наименования.
