Исследование и разработка метода планировки цепей СБИС с равномерным заполнением области трассировки

• Автор: Заглядин, Глеб Георгиевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 116 с. : ил.

Содержание
Введение

Глава 1. Обзор алгоритмов и методов планировки цепей

1.1. Этапы решения задачи трассировки.

1.2. Модели представления коммутационного пространства

1.3. Методы планировки цепей

1.3.1. Алгоритмы лабиринтной трассировки

1.3.2. Алгоритмы трассировки многотерминальных цепей

1.3.3. Методы оптимизации множества цепей.

1.4. Алгоритмы планировки цепей с конкурса БРР .

1.5. Выводы.

Глава 2. Алгоритм построения множества деревьев Штейнера
2.1. Необходимость разработки нового алгоритма для построения деревьев Штейнера.
2.2. Постановка задачи построения семейства деревьев Штейнера.
2.3. Алгоритм построения семейства деревьев Штейнера
2.3.1. Алгоритм построения семейства остовных деревьев
2.3.2. Алгоритм преобразования остовных деревьев к деревьям Штейнера с ортогональными ребрами.
2. 4. Фильтрация семейства деревьев.
2.4.1. Оценка близости двух деревьев
2.4.2. Фильтрация семейства деревьев Штейнера.
2.5. Выводы.
Глава 3. Метод планировки цепей с использованием семейств деревьев Штейнера
3.1. Постановка задачи
3.1. Выбор деревьев для равномерного заполнения области трассировки
3.2. Алгоритм оптимизации с использованием семейства деревьев Штейнера.
3.2.1. Целевая функция для оценки распределения загруженности области трассировки
3.2.2. Алгоритм выбора деревьев из семейства
3.3. Демонстрация работы алгоритма выбора деревьев Штейнера.
3.5. Выводы.
Глава 4. Программная реализация метода планировки цепей и результаты тестирования
4.1. Программная реализация метода планировки цепей
4.1.1. Программная реализация алгоритма генерации семейства деревьев Штейнера
4.1.2. Программная реализация алгоритма выбора деревьев Штейнера
4.2. Исследование реализации алгоритмов
4.2.1. Результаты тестирования быстродействия
4.2.2. Результаты тестирования эффективности предложенных алгоритмов.
4.4. Выводы.
Заключение
Список литературы


Результаты работы в виде программных модулей для программы планировки цепей при топологическом проектировании ИС внедрены в учебный процесс МИЭТ, а также в процесс проектирования базовых матричных кристаллов на ОАО «Ангстрем». Практическая значимость работы. На основе разработанных алгоритмов был создан комплекс прикладного программного обеспечения для планировки цепей при проектировании топологии СБИС. Использование разработанных алгоритмов и программного обеспечения позволяет улучшать трассируемость схем путем повышения равномерности заполнения области трассировки без существенного увеличения суммарной длины цепей. Апробация результатов работы. XIII Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, - апреля г. XIV Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, - апреля г. XV Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, - апреля г. Moscow-Bavarian Joint Advanced Student School (MB JASS), Москва, Зеленоград, 2- марта г. XVI Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, - апреля г. XVII Всероссийская межвузовская научно-техническая конференция студентов и аспирантов, Москва, Зеленоград, - апреля г. Международная научно-техническая конференция «Проектирование систем на кристалле: тенденции развития и проблемы», Москва, Зеленоград, - октября г. Moscow-Bavarian Joint Advanced Student School (MB JASS), Москва, Зеленоград, - марта г. Публикации. Основные результаты диссертационной работы опубликованы в двух научных статьях [,] и семи докладах [,,-,] в трудах научно-технических конференций (еще одна статья находится в печати). Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Во введении раскрывается проблематика диссертационной работы и обосновывается ее актуальность. Дополнительно показана научная новизна и значимость полученных результатов. Приводится список положений, выносимых на защиту, раскрывается структура диссертационной работы. В первой главе приводятся: постановка задачи планировки цепей, актуальные подходы и алгоритмы для ее решения. Проведен анализ эффективности решений, представленных на конкурсе планировки цепей ISPD- (International Symposium of Physical Design), выявлены их основные достоинства и недостатки. Вторая глава диссертационной работы посвящена описанию разработанного автором алгоритма формирования семейства деревьев Штейнера на основе остовных деревьев. Для генерации семейства остовных деревьев ищется множество ребер для подстановки в минимальное остовное дерево. Ребра построенных деревьев приводятся в ортогональный вид, формируя искомое семейство деревьев Штейнера. Далее происходит его фильтрация - деревья с близкой топологией исключаются из состава семейства. Она осуществляется с помощью попарного сравнения деревьев Штейнера с использованием введенной оценки близости двух деревьев. В третьей главе изложен алгоритм выбора деревьев Штейнера с учетом состава семейств, рассмотрена целевая функция, отражающая равномерность распределения загруженности коммутационных областей. Четвёртая глава посвящена рассмотрению аспектов программной реализации разработанных в диссертации алгоритмов. В ней приводится архитектура классов , необходимых для реализации разработанного метода. Проанализировано быстродействие каждого из его этапов, приведены результаты тестирования эффективности метода. В заключении отмечается, что поставленная в данной работе задача выполнена в полной мере: исследованы существующие подходы к решению задачи планировки цепей, разработан метод, обеспечивающий равномерное заполнение области трассировки при использовании семейства деревьев Штейнера, и составляющие его этапы, разработано программное обеспечение и произведено его исследование. В приложении содержатся акты внедрения результатов работы. Работа содержит 6 страниц и 2 акта о внедрении.