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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м (→‎Материалы к экзамену)
 
(не показаны 28 промежуточные версии 3 участников)
Строка 1: Строка 1:
−
Обязательный годовой курс для студентов 418 группы. В 2011-2012 учебном году лекции по данному курсу читают м.н.с. [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]] (первая часть) и профессор Марченко А. М. (вторая часть), а практические занятия проводит [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]]. В предыдущие годы лекции по этому курсу читались [[Ложкин Сергей Андреевич|Ложкиным С. А.]] (первая часть), а практические занятия проводились доцентом [[Романов Дмитрий Сергеевич|Романовым Д. С.]].
+
Обязательный семестровый курс для студентов 318 группы.
  
−
Курс посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задачи логического синтеза СБИС, а также задачи размещения модулей СБИС и трассировки межсоединений. В рамках практических занятий осуществляется знакомство с базовыми пакетами программ логического и топологического синтеза СБИС, формируются навыки работы с этими пакетами.
+
Лекции по данному курсу читает доцент [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]]. До 2017 года данный курс читался совместно с профессором Марченко А. М.
  
 +
Лекции проходят один раз в неделю в 12:50 в аудитории 505. Материалы по семинарским занятиям курса можно найти [[Математические модели и методы синтеза СБИС(семинар)|здесь]].
  
−
== Вопросы по курсу (I часть) ==
+
Курс является вводным и посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС.
  
−
=== Задача синтеза СБИС и связанные с ней модели дискретных управляющих систем ===
+
== Материалы к экзамену ==
 +
# Список вопросов к экзамену (вариант 2024 года) [[Media:MMMSBIS_2024.pdf|[1]]].
  
−
# Полевые транзисторы, принцип их работы и устройство. Основные сведения о КМОП-технологии и проектировании СБИС.
+
== Материалы к экзаменам прошлых лет ==
−
## n- и p-канальные транзисторы, их проводимость;
+
−
## представление об интегральной КМОП-технологии;
+
−
## задача проектирования СБИС и маршрут ее решения.
+
−
# Простейшие логические схемы на КМОП-транзисторах. Функционирование и классификация комбинационных КМОП-схем, оценка их числа.
+
−
## логические схемы НЕ, 2-НЕ-ИЛИ и др.;
+
−
## структура и функционирование КМОП-схемы общего вида, правильные комбинационные КМОП-схемы;
+
−
## оценка числа правильных комбинационных КМОП-схем;
+
−
## комбинационные КМОП-схемы с проблемами переключения, схемы с нагрузочными транзисторами и др.
+
−
# Представление об RC-схемах и их задержке. Быстродействие КМОП-схем.
+
−
## распространение сигнала в КМОП-схемах на примере открытого транзистора;
+
−
## RC-схемы из дискретных элементов и их задержка, представление об RC-схемах с непрерывным распределением емкости и сопротивления;
+
−
## основные факторы, влияющие на быстродействие КМОП-схем.
+
−
# Синтез комбинационных КМОП-схем на основе структурного моделирования контактных схем (КС) и итеративных контактных схем (ИКС).
+
−
## моделирование КС;
+
−
## моделирование ИКС;
+
−
## поведение функции Шеннона для сложности правильных комбинационных КМОП-схем.
+
−
# Синтез комбинационных КМОП-схем на основе структурного моделирования схем из функциональных элементов (СФЭ).
+
−
## моделирование СФЭ в различных базисах и вложение в библиотеку;
+
−
## СФЭ на негативных элементах и инверсная сложность ФАЛ;
+
−
## примеры и сравнительный анализ разных типов структурного моделирования.
+
−
# КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами.
+
−
## логическая и транзисторная схемы RS-триггера, его функционирование;
+
−
## логическая и транзисторная схемы асинхронной ячейки памяти, ее функционирование;
+
−
## схема D-триггера и его связь с единичной задержкой;
+
−
## общая структура автоматных схем, задача их оптимизации.
+
−
# Клеточные схемы как «грубая» топологическая модель СБИС. Порядок функции Шеннона для площади клеточных схем.
+
−
## клеточные схемы из функциональных и коммутационных элементов в стандартном базисе;
+
−
## клеточная реализация дешифратора, построенного по совершенной ДНФ;
+
−
## порядок функции Шеннона для площади клеточных схем.
+
−
# Асимптотика площади дешифратора и ее антагонизм с числом функциональных элементов.
+
−
## нижняя оценка и асимптотика площади клеточного дешифратора;
+
−
## нижняя оценка площади дешифратора, построенного асимптотически наилучшим по числу функциональных элементов методом.
+
−
# Основные понятия, связанные с вложением графов. Вложения полных двоичных деревьев в плоские прямоугольные решетки (ППР) минимальной высоты.
+
−
## вложения графов и связанные с ними понятия;
+
−
## вложения графов в различные типы ППР, высота и площадь полного двоичного дерева;
+
−
# Асимптотика площади полных двоичных деревьев.
+
−
##асимптотика площади полного двоичного дерева при различных перегрузках и различных способах расположения листьев на границе решетки;
+
−
##Н-деревья и порядок площади полного двоичного дерева при произвольном расположении листьев.
+
  
−
=== Основные подходы и методы логического синтеза СБИС ===
+
# Список вопросов к экзамену (вариант 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]]].
  
−
# Двухуровневый логический синтез и ДНФ. Основные подходы к двухуровневой оптимизации.
+
== Программа курса ==
−
## реализация функций в виде ДНФ и ее связь с ПЛМ;
+
−
## простые импликанты и неизбыточные покрытия;
+
−
## кофакторы и разложение Шеннона;
+
−
## использование областей неопределенности (don’t care);
+
−
# Многоуровневый логический синтез и связанные с ним представления функций.
+
−
## скобочные формы, построенные на основе ДНФ;
+
−
## определение двоичных решающих диаграмм (BDD) и представления функций в виде BDD;
+
−
## связь BDD с контактными схемами и операции над BDD, различные типы BDD;
+
−
## выбор оптимального порядка переменных разложения и его значение для упорядоченных BDD.
+
−
# Основные подходы к многоуровневой оптимизации.
+
−
## декомпозиция и другие структурные операции над булевскими сетями;
+
−
## упрощение вершин и его основные приемы;
+
−
## использование булевских и алгебраических делителей;
+
−
## привязка к библиотечному базису (mapping).
+
−
# Анализ задержек и временная оптимизация схем.
+
−
## временной анализ транзисторных схем;
+
−
## модели задержек функциональных элементов и задержки СФЭ;
+
−
## статические критические пути и борьба с ними, выявление «ложных» критических путей.
+
  
−
=== Логический синтез СБИС в системе SIS ===
+
=== Задача синтеза интегральных схем и основные сведения о КМОП технологии ===
  
−
# Знакомство с системой логического синтеза СБИС SIS. Форматы представления данных.
+
# Общие сведения о проектировании цифровых интегральных схем
−
## понятие о логическом синтезе. Общие сведения о системе SIS. Основные возможности системы;
+
# КМОП транзисторы.
−
## форматы представления данных в SIS: .pla, .blif, .eqn (подробный разбор формата .blif);
+
# Маршруты проектирования интегральных схем.
−
## формат файлов библиотеки .genlib;
+
# Проектирование программируемых логических матриц (ПЛМ), полузаказных и заказных схем.
−
## привязка к библиотеке (мэппинг) и пример её  простой реализации;
+
# Метод стандартных ячеек.
−
## основные команды и операции системы SIS.
+
 
−
# Алгоритмы логической оптимизации в SIS.
+
[[Media:VLSI_318_intro_2018.pdf|Презентация]]
−
## описание двухуровневой и многоуровневой модели представления функций;
+
 
−
## основные команды логической оптимизации в системе SIS (simplify,  resub, gkx, gcx и др.) и описание их работы;
+
[[Media:VLSI_418_technology_2017.pdf|Презентация о технологии производства микроэлектронных устройств от Марченко А.М.]]
−
## оптимизационные скрипты в SIS (на примере скрипта script.algebraic).
+
 
−
# Эвристический алгоритм двухуровневой оптимизации ESPRESSO.
+
=== Двухуровневый логический синтез ===
−
## общее описание идеи и структуры алгоритма;
+
 
−
## построение тупикового покрытия по заданному покрытию (процедура IRREDUNDANT);
+
# Реализация функций алгебры логики в виде дизъюнктивных нормальных форм (ДНФ) и ее связь с ПЛМ.
−
## сужение граней заданного покрытия (процедура REDUCE);
+
# Простые импликанты и неизбыточные покрытия.
−
## максимальное расширение граней заданного покрытия (процедура EXPAND).
+
# Обобщенно-монотонное разложение булевых функций.
−
#Моделирование асинхронных систем.
+
# Эвристические подходы к минимизации ДНФ.
−
##сети Петри (описание модели и особенности функционирования);
+
 
−
##моделирование различных асинхронных систем при помощи сетей Петри;
+
[[Media:VLSI_318_two_level_2018.pdf|Презентация]]
−
##основные характеристики сетей Петри: ограниченность, живучесть, обратимость (на примере конкретных схем).
+
 
 +
[https://people.eecs.berkeley.edu/~brayton/courses/219b/ppslides/2-espresso.ppt Презентация - ESPRESSO]
 +
 
 +
=== Многоуровневый логический синтез ===
 +
 
 +
# Модель логических сетей и основные структурные операции над ними: упрощение вершин, декомпозиция и подстановка вершин.
 +
# Операция деления и модель алгебраического деления.
 +
# Совокупное ядро делителей и алгоритмы его нахождения.
 +
# Основные способы нахождения общих делителей.
 +
# Использование областей неопределенности (don’t care) для упрощения логических сетей.
 +
 
 +
=== Привязка к библиотечному базису ===
 +
 
 +
# Задача привязки логической схемы к технологической библиотеке (technology mapping).
 +
# Основные алгоритмы привязки к технологической библиотеке.
 +
 
 +
[[Media:VLSI_418_tech_mapping.pdf|Презентация]]
 +
 
 +
=== Разбиение интегральной схемы ===
 +
 
 +
# Основные цели разбиения интегральной схемы, оценка качества разбиения и связь с теорией графов.
 +
# Алгоритмы разбиения графов и гиперграфов: алгоритм Кернигана-Лина и его расширения, алгоритм Федуччи-Маттеуса (Fiduccia-Mattheyses).
 +
# Задачи кластеризации и основные подходы к многоуровневому разбиению интегральной схемы.
 +
 
 +
[[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),
 +
## аналитические подходы (размещение как задача квадратичного программирования),
 +
## стохастические подходы (моделирование отжига).
 +
# Современные алгоритмы размещения.
 +
 
 +
[[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 деревья. Последовательный алгоритм построения дерева Штейнера.
 +
# Одновременная трассировка всех сетей. Сведение задачи глобальной трассировки к задаче целочисленного линейного программирования.
 +
 
 +
[[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)]
  
 
== Литература ==
 
== Литература ==
−
# Ложкин С.А. Лекции по основам кибернетики <sup>[[Media:Lozh-lectures1.pdf|[1]]][[Media:Lozh-lectures2-2007.pdf|[2]]][[Media:Lozh-lectures3-2007.pdf|[3]]]</sup>. — М.: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.
+
# Г.Г.Казеннов, В.М.Щемелинин. Топологическое проектирование нерегулярных БИС. М., Высшая школа, 1990, 109с.
 +
# Ложкин С.А. Лекции по основам кибернетики. — М.: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.
 +
# Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС <sup>[[Media:Lozhkin-Marchenko-VSLI-models.pdf|[1]]]</sup>.
 +
# Ж.М. Рабаи, А. Чандракасан, Б. Николич Цифровые интегральные схемы. Методология проектирования. – Вильямс, 2007.
 
# Brayton R.K., Logic Synthesis. — Univ. of California, Berkeley, 2000.
 
# Brayton R.K., Logic Synthesis. — Univ. of California, Berkeley, 2000.
−
# Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС <sup>[[Media:VMK-2009part1.pdf|[1]]]</sup>.
+
# 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.
−
# Меры качества разработки цифровой интегральной схемы [[Media:SBIS_slides_2012_metrics.pdf|[1]]]
+
# Naveed Sherwani. Algorithms for VLSI physical design automation. Kluwer academic publishers, 1995, 538p.
−
# КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами [[Media:SBIS_slides_2012_CMOS_memory.pdf|[2]]]
+
# 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
  
−
== Домашние задания (2011 год) ==
 
−
# Домашнее задание №2 <sup>[[Media:MMMSBIS_HW2.pdf|[1]]]</sup>.
 
−
# Домашнее задание №3 <sup>[[Media:MMMSBIS_HW3.pdf|[2]]]</sup>.
 
−
[[Категория:Лекционные курсы кафедры МК]]
 
  
−
== Материалы к зачету по курсу ==
+
[[Категория:Лекционные_курсы_кафедры_МК]]
−
# Список вопросов к зачету (вариант 2012 года) [[Media:MMMSBIS_2012.pdf|[1]]].
+
−
# Список вопросов к зачету (вариант 2011 года) [[Media:MMMSBIS_2011.pdf|[1]]].
+
−
# Таблица успеваемости (2011-2012 учебный год) [https://docs.google.com/spreadsheet/pub?hl=en_US&hl=en_US&key=0An6Aw8HJE2VpdFExbjBFQzBRN1VTMzFmYXZ5RF8yTGc&output=html [2]]
+

Текущая версия на 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»