Математические модели и методы синтеза СБИС

Обязательный семестровый курс для студентов 418 группы. Лекции по данному курсу читают м.н.с. Шуплецов М.С. (первая часть) и профессор Марченко А. М. (вторая часть).

Курс посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС.

Программа курса

Задача синтеза интегральных схем и основные сведения о КМОП технологии

1. КМОП транзисторы.
2. Маршруты проектирования интегральных схем.
3. Проектирование программируемых логических матриц (ПЛМ), полузаказных и заказных схем.
4. Метод стандартных ячеек.

Представление логических схем

1. Двоичные решающие диаграммы (BDD) и представление булевых функций в виде BDD.
2. Различные типы BDD. Связь BDD с контактными схемами и схемами из функциональных элементов.
3. Основные операции над BDD. Выбор оптимального порядка переменных разложения и его значение для упорядоченных BDD.
4. Представление логических схем с использованием BDD.

Двухуровневый логический синтез

1. Реализация функций алгебры логики в виде дизъюнктивных нормальных форм (ДНФ) и ее связь с ПЛМ.
2. Простые импликанты и неизбыточные покрытия.
3. Обобщенно-монотонное разложение булевых функций.
4. Эвристические подходы к минимизации ДНФ.

Многоуровневый логический синтез

1. Модель логических сетей и основные структурные операции над ними: упрощение вершин, декомпозиция и подстановка вершин.
2. Операция деления и модель алгебраического деления.
3. Совокупное ядро делителей и алгоритмы его нахождения.
4. Основные способы нахождения общих делителей.
5. Использование областей неопределенности (don’t care) для упрощения логических сетей.

Привязка к библиотечному базису

1. Задача привязки логической схемы к технологической библиотеке (technology mapping).
2. Основные алгоритмы привязки к технологической библиотеке.

Разбиение интегральной схемы

1. Основные цели разбиения интегральной схемы, оценка качества разбиения и связь с теорией графов.
2. Алгоритмы разбиения графов и гиперграфов: алгоритм Кернигана-Лина и его расширения, алгоритм Федуччи-Маттеуса (Fiduccia-Mattheyses).
3. Задачи кластеризации и основные подходы к многоуровневому разбиению интегральной схемы.

Размещение модулей интегральной схемы

1. Задача глобального размещения элементов интегральной схемы и основные метрики оценки качества размещения.
2. Основные подходы к размещению:
   1. геометрические методы и подходы, основанные на декомпозиции (min-cut placement),
   2. аналитические подходы (силовой метод, размещение как задача квадратичного программирования),
   3. стохастические подходы (моделирование отжига).
3. Современные алгоритмы размещения.

Трассировка соединений в интегральной схеме

1. Алгоритмы на графах. Основные определения. Методы и структуры представления графов. Обходы графов. Стягивающие деревья.
2. Эйлеровы пути. Нахождение Эйлеровых путей в электрической схеме.
3. Кратчайшие пути. Вычисление расстояний. Алгоритм Форда-Беллмана. Алгоритм Дейкстры. Алгоритм Флойда.
4. Задача трассировки соединений. Классификация алгоритмов трассировки. Представление областей трассировки.
5. Задача глобальной трассировки. MST и SMT деревья. Последовательный алгоритм построения дерева Штейнера.
6. Волновая трассировка. Ограничения и модификации алгоритма.

Литература

1. Г.Г.Казеннов, В.М.Щемелинин. Топологическое проектирование нерегулярных БИС. М., Высшая школа, 1990, 109с.
2. Ложкин С.А. Лекции по основам кибернетики. — М.: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.
3. Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС ^[1].
4. Ж.М. Рабаи, А. Чандракасан, Б. Николич Цифровые интегральные схемы. Методология проектирования. – Вильямс, 2007.
5. Brayton R.K., Logic Synthesis. — Univ. of California, Berkeley, 2000.
6. Hatchel G.D., Somenzi F. Logic Synthesis and Verification Algorithms. – Kluwer Academic Publishers, 2002.
7. Giovanni De Micheli Synthesis and Optimization of Digital Circuits. – McGraw-Hill Science/Engeneering/Math, 1994.
8. T. Lengauer. Combinatorial algorithms for integrated circuit layout. Wiley, 1990, 694 p.
9. Naveed Sherwani. Algorithms for VLSI physical design automation. Kluwer academic publishers, 1995, 538p.
10. Introduction to Algorithms, T. Cormen, C. Lesierson, R. Rivest, The MIT Press, Second Printing, 1996.
11. Handbook of Algorithms for Physical design Automation, Edited by Charles J. Alpert Dinesh P. Mehta Sachin S. Sapatnekar, 2009.
12. Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Huю VLSI Physical Design: From Graph Partitioning to Timing Closure, 2011

Материалы к экзамену

1. Список вопросов к экзамену (вариант 2014 года) [1].