Математические модели и методы синтеза СБИС — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м (→‎Программа курса)
м (→‎Материалы к экзамену)
 
(не показаны 23 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
Обязательный семестровый курс для студентов 418 группы. Лекции по данному курсу читают м.н.с. [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]] (первая часть) и профессор Марченко А. М. (вторая часть).
+
Обязательный семестровый курс для студентов 318 группы.
  
−
Курс посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС.
+
Лекции по данному курсу читает доцент [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]]. До 2017 года данный курс читался совместно с профессором Марченко А. М.
  
 +
Лекции проходят один раз в неделю в 12:50 в аудитории 505. Материалы по семинарским занятиям курса можно найти [[Математические модели и методы синтеза СБИС(семинар)|здесь]].
 +
 +
Курс является вводным и посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС.
 +
 +
== Материалы к экзамену ==
 +
# Список вопросов к экзамену (вариант 2024 года) [[Media:MMMSBIS_2024.pdf|[1]]].
 +
 +
== Материалы к экзаменам прошлых лет ==
 +
 +
# Список вопросов к экзамену (вариант 2023 года) [[Media:MMMSBIS_2023.pdf|[1]]].
 +
# Список вопросов к экзамену (вариант 2019 года) [[Media:MMMSBIS_2019.pdf|[2]]].
 +
# Список вопросов к экзамену (вариант 2018 года) [[Media:MMMSBIS_2018.pdf|[3]]].
 +
# Список вопросов к экзамену (вариант 2017 года) [[Media:MMMSBIS_2017.pdf|[4]]].
 +
# Список вопросов к экзамену (вариант 2016 года) [[Media:MMMSBIS_2016.pdf|[5]]].
 +
# Список вопросов к экзамену (вариант 2015 года) [[Media:MMMSBIS_2015.pdf|[6]]].
 +
# Список вопросов к экзамену (вариант 2014 года) [[Media:MMMSBIS_2014.pdf|[7]]].
  
 
== Программа курса ==
 
== Программа курса ==
Строка 8: Строка 24:
 
=== Задача синтеза интегральных схем и основные сведения о КМОП технологии ===
 
=== Задача синтеза интегральных схем и основные сведения о КМОП технологии ===
  
 +
# Общие сведения о проектировании цифровых интегральных схем
 
# КМОП транзисторы.
 
# КМОП транзисторы.
 
# Маршруты проектирования интегральных схем.
 
# Маршруты проектирования интегральных схем.
Строка 13: Строка 30:
 
# Метод стандартных ячеек.
 
# Метод стандартных ячеек.
  
−
[[Media:VLSI_418_technology.pdf|Презентация]]
+
[[Media:VLSI_318_intro_2018.pdf|Презентация]]
  
−
=== Представление логических схем ===
+
[[Media:VLSI_418_technology_2017.pdf|Презентация о технологии производства микроэлектронных устройств от Марченко А.М.]]
−
 
+
−
# Двоичные решающие диаграммы (BDD) и представление булевых функций в виде BDD.
+
−
# Различные типы BDD. Связь BDD с контактными схемами и схемами из функциональных элементов.
+
−
# Основные операции над BDD. Выбор оптимального порядка переменных разложения и его значение для упорядоченных BDD.
+
−
# Представление логических схем с использованием BDD.
+
  
 
=== Двухуровневый логический синтез ===
 
=== Двухуровневый логический синтез ===
Строка 28: Строка 40:
 
# Обобщенно-монотонное разложение булевых функций.
 
# Обобщенно-монотонное разложение булевых функций.
 
# Эвристические подходы к минимизации ДНФ.
 
# Эвристические подходы к минимизации ДНФ.
 +
 +
[[Media:VLSI_318_two_level_2018.pdf|Презентация]]
 +
 +
[https://people.eecs.berkeley.edu/~brayton/courses/219b/ppslides/2-espresso.ppt Презентация - ESPRESSO]
  
 
=== Многоуровневый логический синтез ===
 
=== Многоуровневый логический синтез ===
Строка 38: Строка 54:
  
 
=== Привязка к библиотечному базису ===
 
=== Привязка к библиотечному базису ===
 +
 
# Задача привязки логической схемы к технологической библиотеке (technology mapping).
 
# Задача привязки логической схемы к технологической библиотеке (technology mapping).
 
# Основные алгоритмы привязки к технологической библиотеке.
 
# Основные алгоритмы привязки к технологической библиотеке.
 +
 +
[[Media:VLSI_418_tech_mapping.pdf|Презентация]]
  
 
=== Разбиение интегральной схемы ===
 
=== Разбиение интегральной схемы ===
 +
 
# Основные цели разбиения интегральной схемы, оценка качества разбиения и связь с теорией графов.
 
# Основные цели разбиения интегральной схемы, оценка качества разбиения и связь с теорией графов.
 
# Алгоритмы разбиения графов и гиперграфов: алгоритм Кернигана-Лина и его расширения, алгоритм Федуччи-Маттеуса (Fiduccia-Mattheyses).
 
# Алгоритмы разбиения графов и гиперграфов: алгоритм Кернигана-Лина и его расширения, алгоритм Федуччи-Маттеуса (Fiduccia-Mattheyses).
Строка 47: Строка 67:
  
 
[[Media:VLSI_418_graph_partitioning.pdf|Презентация]]
 
[[Media:VLSI_418_graph_partitioning.pdf|Презентация]]
 +
 +
[[Media:VLSI_418_graph_partitioning_2016.pdf|Презентация(2016)]]
 +
 +
[[Media:VLSI_318_graph_partitioning_2017.pdf|Презентация(2017)]]
 +
 +
[http://vlsicad.eecs.umich.edu/KLMH/downloads/book/chapter2/chap2r-130523.pdf Презентация(2019)]
  
 
=== Размещение модулей интегральной схемы ===
 
=== Размещение модулей интегральной схемы ===
 +
 
# Задача глобального размещения элементов интегральной схемы и основные метрики оценки качества размещения.
 
# Задача глобального размещения элементов интегральной схемы и основные метрики оценки качества размещения.
 
# Основные подходы к размещению:
 
# Основные подходы к размещению:
 
## геометрические методы и подходы, основанные на декомпозиции (min-cut placement),
 
## геометрические методы и подходы, основанные на декомпозиции (min-cut placement),
−
## аналитические подходы (силовой метод, размещение как задача квадратичного программирования),
+
## аналитические подходы (размещение как задача квадратичного программирования),
 
## стохастические подходы (моделирование отжига).
 
## стохастические подходы (моделирование отжига).
 
# Современные алгоритмы размещения.
 
# Современные алгоритмы размещения.
  
 
[[Media:VLSI_418_placement.pdf|Презентация]]
 
[[Media:VLSI_418_placement.pdf|Презентация]]
 +
 +
[[Media:VLSI_418_placement_2016.pdf|Презентация(2016)]]
 +
 +
[[Media:VLSI_318_placement_2017.pdf|Презентация(2017)]]
 +
 +
[http://vlsicad.eecs.umich.edu/KLMH/downloads/book/chapter4/chap4-141124.pdf Презентация(2019)]
  
 
=== Трассировка соединений в интегральной схеме ===
 
=== Трассировка соединений в интегральной схеме ===
−
# Алгоритмы на графах. Основные определения. Методы и структуры представления графов. Обходы графов. Стягивающие деревья.
+
 
−
# Эйлеровы пути. Нахождение Эйлеровых путей в электрической схеме.
+
# Основные задачи трассировки соединений: детальная и глобальная трассировка.
−
# Кратчайшие пути. Вычисление расстояний. Алгоритм Форда-Беллмана. Алгоритм Дейкстры. Алгоритм Флойда.
+
 
# Задача трассировки соединений. Классификация алгоритмов трассировки. Представление областей трассировки.
 
# Задача трассировки соединений. Классификация алгоритмов трассировки. Представление областей трассировки.
 
# Задача глобальной трассировки. MST и SMT деревья. Последовательный алгоритм построения дерева Штейнера.
 
# Задача глобальной трассировки. MST и SMT деревья. Последовательный алгоритм построения дерева Штейнера.
−
# Волновая трассировка. Ограничения и модификации алгоритма.
+
# Одновременная трассировка всех сетей. Сведение задачи глобальной трассировки к задаче целочисленного линейного программирования.
  
 
[[Media:VLSI_418_routing.pdf|Презентация]]
 
[[Media:VLSI_418_routing.pdf|Презентация]]
 +
 +
[[Media:VLSI_418_routing_2016.pdf|Презентация(2016)]]
 +
 +
[[Media:VLSI_318_routing_2017.pdf|Презентация(2017)]]
 +
 +
[http://vlsicad.eecs.umich.edu/KLMH/downloads/book/chapter5/chap5-130517.pdf Презентация(2019)]
  
 
== Литература ==
 
== Литература ==
Строка 80: Строка 118:
 
# Introduction to Algorithms, T. Cormen, C. Lesierson, R. Rivest, The MIT Press, Second Printing, 1996.
 
# 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.
 
# 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
+
# Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu. VLSI Physical Design: From Graph Partitioning to Timing Closure, 2011
  
−
== Материалы к экзамену ==
+
 
−
# Список вопросов к экзамену (вариант 2014 года) [[Media:MMMSBIS_2014.pdf|[1]]].
+
[[Категория:Лекционные_курсы_кафедры_МК]]

Текущая версия на 14:26, 31 мая 2024

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

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

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

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

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

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

Материалы к экзаменам прошлых лет

  1. Список вопросов к экзамену (вариант 2023 года) [1].
  2. Список вопросов к экзамену (вариант 2019 года) [2].
  3. Список вопросов к экзамену (вариант 2018 года) [3].
  4. Список вопросов к экзамену (вариант 2017 года) [4].
  5. Список вопросов к экзамену (вариант 2016 года) [5].
  6. Список вопросов к экзамену (вариант 2015 года) [6].
  7. Список вопросов к экзамену (вариант 2014 года) [7].

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

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

  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)

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

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

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

Презентация

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

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

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

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

  1. Основные задачи трассировки соединений: детальная и глобальная трассировка.
  2. Задача трассировки соединений. Классификация алгоритмов трассировки. Представление областей трассировки.
  3. Задача глобальной трассировки. MST и SMT деревья. Последовательный алгоритм построения дерева Штейнера.
  4. Одновременная трассировка всех сетей. Сведение задачи глобальной трассировки к задаче целочисленного линейного программирования.

Презентация

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

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

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

Литература

  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
Источник — «https://mk.cs.msu.ru/index.php?title=Математические_модели_и_методы_синтеза_СБИС&oldid=11199»