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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Литература)
м (→‎Материалы к экзамену)
(не показаны 24 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
Обязательный годовой курс для студентов 418 группы. В 2011-2012 учебном году лекции по данному курсу читают м.н.с. [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]] (первая часть) и профессор Марченко А. М. (вторая часть), а практические занятия проводит [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]]. В предыдущие годы лекции по этому курсу читались [[Ложкин Сергей Андреевич|Ложкиным С. А.]] (первая часть), а практические занятия проводились доцентом [[Романов Дмитрий Сергеевич|Романовым Д. С.]].
+
Обязательный семестровый курс для студентов 318 группы.
  
−
Курс посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задачи логического синтеза СБИС, а также задачи размещения модулей СБИС и трассировки межсоединений. В рамках практических занятий осуществляется знакомство с базовыми пакетами программ логического и топологического синтеза СБИС, формируются навыки работы с этими пакетами.
+
Лекции по данному курсу читает доцент [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]]. До 2017 года данный курс читался совместно с профессором Марченко А. М.
  
 +
Лекции проходят один раз в неделю в 12:50 в аудитории 505. Материалы по семинарским занятиям курса можно найти [[Математические модели и методы синтеза СБИС(семинар)|здесь]].
  
−
== Вопросы по курсу (I часть) ==
+
Курс является вводным и посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС.
  
−
=== Задача синтеза СБИС и связанные с ней модели дискретных управляющих систем ===
 
  
−
# Полевые транзисторы, принцип их работы и устройство. Основные сведения о КМОП-технологии и проектировании СБИС.
+
== Программа курса ==
−
## n- и p-канальные транзисторы, их проводимость;
+
−
## представление об интегральной КМОП-технологии;
+
−
## задача проектирования СБИС и маршрут ее решения.
+
−
# Простейшие логические схемы на КМОП-транзисторах. Функционирование и классификация комбинационных КМОП-схем, оценка их числа.
+
−
## логические схемы НЕ, 2-НЕ-ИЛИ и др.;
+
−
## структура и функционирование КМОП-схемы общего вида, правильные комбинационные КМОП-схемы;
+
−
## оценка числа правильных комбинационных КМОП-схем;
+
−
## комбинационные КМОП-схемы с проблемами переключения, схемы с нагрузочными транзисторами и др.
+
−
# Представление об RC-схемах и их задержке. Быстродействие КМОП-схем.
+
−
## распространение сигнала в КМОП-схемах на примере открытого транзистора;
+
−
## RC-схемы из дискретных элементов и их задержка, представление об RC-схемах с непрерывным распределением емкости и сопротивления;
+
−
## основные факторы, влияющие на быстродействие КМОП-схем.
+
−
# Синтез комбинационных КМОП-схем на основе структурного моделирования контактных схем (КС) и итеративных контактных схем (ИКС).
+
−
## моделирование КС;
+
−
## моделирование ИКС;
+
−
## поведение функции Шеннона для сложности правильных комбинационных КМОП-схем.
+
−
# Синтез комбинационных КМОП-схем на основе структурного моделирования схем из функциональных элементов (СФЭ).
+
−
## моделирование СФЭ в различных базисах и вложение в библиотеку;
+
−
## СФЭ на негативных элементах и инверсная сложность ФАЛ;
+
−
## примеры и сравнительный анализ разных типов структурного моделирования.
+
−
# КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами.
+
−
## логическая и транзисторная схемы RS-триггера, его функционирование;
+
−
## логическая и транзисторная схемы асинхронной ячейки памяти, ее функционирование;
+
−
## схема D-триггера и его связь с единичной задержкой;
+
−
## общая структура автоматных схем, задача их оптимизации.
+
−
# Клеточные схемы как «грубая» топологическая модель СБИС. Порядок функции Шеннона для площади клеточных схем.
+
−
## клеточные схемы из функциональных и коммутационных элементов в стандартном базисе;
+
−
## клеточная реализация дешифратора, построенного по совершенной ДНФ;
+
−
## порядок функции Шеннона для площади клеточных схем.
+
−
# Асимптотика площади дешифратора и ее антагонизм с числом функциональных элементов.
+
−
## нижняя оценка и асимптотика площади клеточного дешифратора;
+
−
## нижняя оценка площади дешифратора, построенного асимптотически наилучшим по числу функциональных элементов методом.
+
−
# Основные понятия, связанные с вложением графов. Вложения полных двоичных деревьев в плоские прямоугольные решетки (ППР) минимальной высоты.
+
−
## вложения графов и связанные с ними понятия;
+
−
## вложения графов в различные типы ППР, высота и площадь полного двоичного дерева;
+
−
# Асимптотика площади полных двоичных деревьев.
+
−
##асимптотика площади полного двоичного дерева при различных перегрузках и различных способах расположения листьев на границе решетки;
+
−
##Н-деревья и порядок площади полного двоичного дерева при произвольном расположении листьев.
+
  
−
=== Основные подходы и методы логического синтеза СБИС ===
+
=== Задача синтеза интегральных схем и основные сведения о КМОП технологии ===
  
−
# Двухуровневый логический синтез и ДНФ. Основные подходы к двухуровневой оптимизации.
+
# Общие сведения о проектировании цифровых интегральных схем
−
## реализация функций в виде ДНФ и ее связь с ПЛМ;
+
# КМОП транзисторы.
−
## простые импликанты и неизбыточные покрытия;
+
# Маршруты проектирования интегральных схем.
−
## кофакторы и разложение Шеннона;
+
# Проектирование программируемых логических матриц (ПЛМ), полузаказных и заказных схем.
−
## использование областей неопределенности (don’t care);
+
# Метод стандартных ячеек.
−
# Многоуровневый логический синтез и связанные с ним представления функций.
+
−
## скобочные формы, построенные на основе ДНФ;
+
−
## определение двоичных решающих диаграмм (BDD) и представления функций в виде BDD;
+
−
## связь BDD с контактными схемами и операции над BDD, различные типы BDD;
+
−
## выбор оптимального порядка переменных разложения и его значение для упорядоченных BDD.
+
−
# Основные подходы к многоуровневой оптимизации.
+
−
## декомпозиция и другие структурные операции над булевскими сетями;
+
−
## упрощение вершин и его основные приемы;
+
−
## использование булевских и алгебраических делителей;
+
−
## привязка к библиотечному базису (mapping).
+
−
# Анализ задержек и временная оптимизация схем.
+
−
## временной анализ транзисторных схем;
+
−
## модели задержек функциональных элементов и задержки СФЭ;
+
−
## статические критические пути и борьба с ними, выявление «ложных» критических путей.
+
  
−
=== Логический синтез СБИС в системе SIS ===
+
[[Media:VLSI_318_intro_2018.pdf|Презентация]]
  
−
# Знакомство с системой логического синтеза СБИС SIS. Форматы представления данных.
+
[[Media:VLSI_418_technology_2017.pdf|Презентация о технологии производства микроэлектронных устройств от Марченко А.М.]]
−
## понятие о логическом синтезе. Общие сведения о системе SIS. Основные возможности системы;
+
 
−
## форматы представления данных в SIS: .pla, .blif, .eqn (подробный разбор формата .blif);
+
=== Двухуровневый логический синтез ===
−
## формат файлов библиотеки .genlib;
+
 
−
## привязка к библиотеке (мэппинг) и пример её  простой реализации;
+
# Реализация функций алгебры логики в виде дизъюнктивных нормальных форм (ДНФ) и ее связь с ПЛМ.
−
## основные команды и операции системы SIS.
+
# Простые импликанты и неизбыточные покрытия.
−
# Алгоритмы логической оптимизации в SIS.
+
# Обобщенно-монотонное разложение булевых функций.
−
## описание двухуровневой и многоуровневой модели представления функций;
+
# Эвристические подходы к минимизации ДНФ.
−
## основные команды логической оптимизации в системе SIS (simplify,  resub, gkx, gcx и др.) и описание их работы;
+
 
−
## оптимизационные скрипты в SIS (на примере скрипта script.algebraic).
+
[[Media:VLSI_318_two_level_2018.pdf|Презентация]]
−
# Эвристический алгоритм двухуровневой оптимизации ESPRESSO.
+
 
−
## общее описание идеи и структуры алгоритма;
+
[https://people.eecs.berkeley.edu/~brayton/courses/219b/ppslides/2-espresso.ppt Презентация - ESPRESSO]
−
## построение тупикового покрытия по заданному покрытию (процедура IRREDUNDANT);
+
 
−
## сужение граней заданного покрытия (процедура REDUCE);
+
=== Многоуровневый логический синтез ===
−
## максимальное расширение граней заданного покрытия (процедура EXPAND).
+
 
−
#Моделирование асинхронных систем.
+
# Модель логических сетей и основные структурные операции над ними: упрощение вершин, декомпозиция и подстановка вершин.
−
##сети Петри (описание модели и особенности функционирования);
+
# Операция деления и модель алгебраического деления.
−
##моделирование различных асинхронных систем при помощи сетей Петри;
+
# Совокупное ядро делителей и алгоритмы его нахождения.
−
##основные характеристики сетей Петри: ограниченность, живучесть, обратимость (на примере конкретных схем).
+
# Основные способы нахождения общих делителей.
 +
# Использование областей неопределенности (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с.
−
# Brayton R.K., Logic Synthesis. — Univ. of California, Berkeley, 2000.
+
# Ложкин С.А. Лекции по основам кибернетики. — М.: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.
 
# Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС <sup>[[Media:Lozhkin-Marchenko-VSLI-models.pdf|[1]]]</sup>.
 
# Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС <sup>[[Media:Lozhkin-Marchenko-VSLI-models.pdf|[1]]]</sup>.
 +
# Ж.М. Рабаи, А. Чандракасан, Б. Николич Цифровые интегральные схемы. Методология проектирования. – Вильямс, 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
  
−
== Слайды к лекциям ==
+
== Материалы к экзамену ==
−
# Меры качества разработки цифровой интегральной схемы [[Media:SBIS_slides_2012_metrics.pdf|[1]]]
+
# Список вопросов к экзамену (вариант 2019 года) [[Media:MMMSBIS_2019.pdf|[1]]].
−
# КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами [[Media:SBIS_slides_2012_CMOS_memory.pdf|[2]]]
+
# Список вопросов к экзамену (вариант 2018 года) [[Media:MMMSBIS_2018.pdf|[2]]].
 +
# Список вопросов к экзамену (вариант 2017 года) [[Media:MMMSBIS_2017.pdf|[3]]].
 +
# Список вопросов к экзамену (вариант 2016 года) [[Media:MMMSBIS_2016.pdf|[4]]].
 +
# Список вопросов к экзамену (вариант 2015 года) [[Media:MMMSBIS_2015.pdf|[5]]].
 +
# Список вопросов к экзамену (вариант 2014 года) [[Media:MMMSBIS_2014.pdf|[6]]].
  
−
== Домашние задания (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]]
+

Версия 23:30, 30 мая 2019

Обязательный семестровый курс для студентов 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)

Презентация(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

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

  1. Список вопросов к экзамену (вариант 2019 года) [1].
  2. Список вопросов к экзамену (вариант 2018 года) [2].
  3. Список вопросов к экзамену (вариант 2017 года) [3].
  4. Список вопросов к экзамену (вариант 2016 года) [4].
  5. Список вопросов к экзамену (вариант 2015 года) [5].
  6. Список вопросов к экзамену (вариант 2014 года) [6].
Источник — «https://mk.cs.msu.ru/index.php?title=Математические_модели_и_методы_синтеза_СБИС&oldid=6077»