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

Обязательный семестровый курс для студентов 318 группы.

Лекции по данному курсу читает доцент Шуплецов М.С.. До 2017 года данный курс читался совместно с профессором Марченко А. М.

Лекции проходят один раз в неделю в 12:50 в аудитории 505. Материалы по семинарским занятиям курса можно найти здесь.

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

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

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

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

Презентация

Презентация о технологии производства микроэлектронных устройств от Марченко А.М.

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

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

Презентация

Презентация - ESPRESSO

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

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

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

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

Презентация

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

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

Презентация

Презентация(2016)

Презентация(2017)

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

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

Презентация

Презентация(2016)

Презентация(2017)

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

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

Презентация

Презентация(2016)

Презентация(2017)

Литература

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. Список вопросов к экзамену (вариант 2018 года) [1].
2. Список вопросов к экзамену (вариант 2017 года) [2].
3. Список вопросов к экзамену (вариант 2016 года) [3].
4. Список вопросов к экзамену (вариант 2015 года) [4].
5. Список вопросов к экзамену (вариант 2014 года) [5].