Математические модели и методы синтеза СБИС — различия между версиями
Материал из Кафедра математической кибернетики
м (→Материалы к экзамену) |
м (→Трассировка соединений в интегральной схеме) |
||
Строка 80: | Строка 80: | ||
[[Media:VLSI_418_routing.pdf|Презентация]] | [[Media:VLSI_418_routing.pdf|Презентация]] | ||
+ | [[Media:VLSI_418_routing_2016.pdf|Презентация(2016)]] | ||
== Литература == | == Литература == |
Версия 23:29, 22 июня 2016
Обязательный семестровый курс для студентов 318 группы. Лекции по данному курсу читают м.н.с. Шуплецов М.С. (первая часть) и профессор Марченко А. М. (вторая часть).
Лекции проходят один раз в неделю в 14:35 в аудитории 604. Материалы по семинарским занятиям курса можно найти здесь.
Курс является вводным и посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС.
Содержание
- 1 Программа курса
- 1.1 Задача синтеза интегральных схем и основные сведения о КМОП технологии
- 1.2 Представление логических схем
- 1.3 Двухуровневый логический синтез
- 1.4 Многоуровневый логический синтез
- 1.5 Привязка к библиотечному базису
- 1.6 Разбиение интегральной схемы
- 1.7 Размещение модулей интегральной схемы
- 1.8 Трассировка соединений в интегральной схеме
- 2 Литература
- 3 Материалы к экзамену
Программа курса
Задача синтеза интегральных схем и основные сведения о КМОП технологии
- КМОП транзисторы.
- Маршруты проектирования интегральных схем.
- Проектирование программируемых логических матриц (ПЛМ), полузаказных и заказных схем.
- Метод стандартных ячеек.
Представление логических схем
- Двоичные решающие диаграммы (BDD) и представление булевых функций в виде BDD.
- Различные типы BDD. Связь BDD с контактными схемами и схемами из функциональных элементов.
- Основные операции над BDD. Выбор оптимального порядка переменных разложения и его значение для упорядоченных BDD.
- Представление логических схем с использованием BDD.
- Особенности построения эффективных систем для манипуляции с BDD.
Двухуровневый логический синтез
- Реализация функций алгебры логики в виде дизъюнктивных нормальных форм (ДНФ) и ее связь с ПЛМ.
- Простые импликанты и неизбыточные покрытия.
- Обобщенно-монотонное разложение булевых функций.
- Эвристические подходы к минимизации ДНФ.
Многоуровневый логический синтез
- Модель логических сетей и основные структурные операции над ними: упрощение вершин, декомпозиция и подстановка вершин.
- Операция деления и модель алгебраического деления.
- Совокупное ядро делителей и алгоритмы его нахождения.
- Основные способы нахождения общих делителей.
- Использование областей неопределенности (don’t care) для упрощения логических сетей.
Привязка к библиотечному базису
- Задача привязки логической схемы к технологической библиотеке (technology mapping).
- Основные алгоритмы привязки к технологической библиотеке.
Разбиение интегральной схемы
- Основные цели разбиения интегральной схемы, оценка качества разбиения и связь с теорией графов.
- Алгоритмы разбиения графов и гиперграфов: алгоритм Кернигана-Лина и его расширения, алгоритм Федуччи-Маттеуса (Fiduccia-Mattheyses).
- Задачи кластеризации и основные подходы к многоуровневому разбиению интегральной схемы.
Размещение модулей интегральной схемы
- Задача глобального размещения элементов интегральной схемы и основные метрики оценки качества размещения.
- Основные подходы к размещению:
- геометрические методы и подходы, основанные на декомпозиции (min-cut placement),
- аналитические подходы (силовой метод, размещение как задача квадратичного программирования),
- стохастические подходы (моделирование отжига).
- Современные алгоритмы размещения.
Трассировка соединений в интегральной схеме
- Алгоритмы на графах. Основные определения. Методы и структуры представления графов. Обходы графов. Стягивающие деревья.
- Эйлеровы пути. Нахождение Эйлеровых путей в электрической схеме.
- Кратчайшие пути. Вычисление расстояний. Алгоритм Форда-Беллмана. Алгоритм Дейкстры. Алгоритм Флойда.
- Задача трассировки соединений. Классификация алгоритмов трассировки. Представление областей трассировки.
- Задача глобальной трассировки. MST и SMT деревья. Последовательный алгоритм построения дерева Штейнера.
- Волновая трассировка. Ограничения и модификации алгоритма.
Литература
- Г.Г.Казеннов, В.М.Щемелинин. Топологическое проектирование нерегулярных БИС. М., Высшая школа, 1990, 109с.
- Ложкин С.А. Лекции по основам кибернетики. — М.: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.
- Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС [1].
- Ж.М. Рабаи, А. Чандракасан, Б. Николич Цифровые интегральные схемы. Методология проектирования. – Вильямс, 2007.
- Brayton R.K., Logic Synthesis. — Univ. of California, Berkeley, 2000.
- Hatchel G.D., Somenzi F. Logic Synthesis and Verification Algorithms. – Kluwer Academic Publishers, 2002.
- Giovanni De Micheli Synthesis and Optimization of Digital Circuits. – McGraw-Hill Science/Engeneering/Math, 1994.
- T. Lengauer. Combinatorial algorithms for integrated circuit layout. Wiley, 1990, 694 p.
- Naveed Sherwani. Algorithms for VLSI physical design automation. Kluwer academic publishers, 1995, 538p.
- Introduction to Algorithms, T. Cormen, C. Lesierson, R. Rivest, The MIT Press, Second Printing, 1996.
- Handbook of Algorithms for Physical design Automation, Edited by Charles J. Alpert Dinesh P. Mehta Sachin S. Sapatnekar, 2009.
- Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu. VLSI Physical Design: From Graph Partitioning to Timing Closure, 2011