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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м (→‎Литература)
м
Строка 1: Строка 1:
−
Обязательный годовой курс для студентов 418 группы. В 2011-2012 учебном году лекции по данному курсу читают м.н.с. [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]] (первая часть) и профессор Марченко А. М. (вторая часть), а практические занятия проводит [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]]. В предыдущие годы лекции по этому курсу читались [[Ложкин Сергей Андреевич|Ложкиным С. А.]] (первая часть), а практические занятия проводились доцентом [[Романов Дмитрий Сергеевич|Романовым Д. С.]].
+
Обязательный семестровый курс для студентов 418 группы. Лекции по данному курсу читают м.н.с. [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]] (первая часть) и профессор Марченко А. М. (вторая часть).
  
−
Курс посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задачи логического синтеза СБИС, а также задачи размещения модулей СБИС и трассировки межсоединений. В рамках практических занятий осуществляется знакомство с базовыми пакетами программ логического и топологического синтеза СБИС, формируются навыки работы с этими пакетами.
+
Курс посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС.
  
  
−
== Вопросы по курсу (I часть) ==
+
== Программа курса ==
  
−
=== Задача синтеза СБИС и связанные с ней модели дискретных управляющих систем ===
+
=== Задача синтеза интегральных схем и основные сведения о КМОП технологии ===
  
−
# Полевые транзисторы, принцип их работы и устройство. Основные сведения о КМОП-технологии и проектировании СБИС.
+
# КМОП транзисторы.
−
## n- и p-канальные транзисторы, их проводимость;
+
# Маршруты проектирования интегральных схем.
−
## представление об интегральной КМОП-технологии;
+
# Проектирование программируемых логических матриц (ПЛМ), полузаказных и заказных схем.
−
## задача проектирования СБИС и маршрут ее решения.
+
# Метод стандартных ячеек.
−
# Простейшие логические схемы на КМОП-транзисторах. Функционирование и классификация комбинационных КМОП-схем, оценка их числа.
+
−
## логические схемы НЕ, 2-НЕ-ИЛИ и др.;
+
−
## структура и функционирование КМОП-схемы общего вида, правильные комбинационные КМОП-схемы;
+
−
## оценка числа правильных комбинационных КМОП-схем;
+
−
## комбинационные КМОП-схемы с проблемами переключения, схемы с нагрузочными транзисторами и др.
+
−
# Представление об RC-схемах и их задержке. Быстродействие КМОП-схем.
+
−
## распространение сигнала в КМОП-схемах на примере открытого транзистора;
+
−
## RC-схемы из дискретных элементов и их задержка, представление об RC-схемах с непрерывным распределением емкости и сопротивления;
+
−
## основные факторы, влияющие на быстродействие КМОП-схем.
+
−
# Синтез комбинационных КМОП-схем на основе структурного моделирования контактных схем (КС) и итеративных контактных схем (ИКС).
+
−
## моделирование КС;
+
−
## моделирование ИКС;
+
−
## поведение функции Шеннона для сложности правильных комбинационных КМОП-схем.
+
−
# Синтез комбинационных КМОП-схем на основе структурного моделирования схем из функциональных элементов (СФЭ).
+
−
## моделирование СФЭ в различных базисах и вложение в библиотеку;
+
−
## СФЭ на негативных элементах и инверсная сложность ФАЛ;
+
−
## примеры и сравнительный анализ разных типов структурного моделирования.
+
−
# КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами.
+
−
## логическая и транзисторная схемы RS-триггера, его функционирование;
+
−
## логическая и транзисторная схемы асинхронной ячейки памяти, ее функционирование;
+
−
## схема D-триггера и его связь с единичной задержкой;
+
−
## общая структура автоматных схем, задача их оптимизации.
+
−
# Клеточные схемы как «грубая» топологическая модель СБИС. Порядок функции Шеннона для площади клеточных схем.
+
−
## клеточные схемы из функциональных и коммутационных элементов в стандартном базисе;
+
−
## клеточная реализация дешифратора, построенного по совершенной ДНФ;
+
−
## порядок функции Шеннона для площади клеточных схем.
+
−
# Асимптотика площади дешифратора и ее антагонизм с числом функциональных элементов.
+
−
## нижняя оценка и асимптотика площади клеточного дешифратора;
+
−
## нижняя оценка площади дешифратора, построенного асимптотически наилучшим по числу функциональных элементов методом.
+
−
# Основные понятия, связанные с вложением графов. Вложения полных двоичных деревьев в плоские прямоугольные решетки (ППР) минимальной высоты.
+
−
## вложения графов и связанные с ними понятия;
+
−
## вложения графов в различные типы ППР, высота и площадь полного двоичного дерева;
+
−
# Асимптотика площади полных двоичных деревьев.
+
−
##асимптотика площади полного двоичного дерева при различных перегрузках и различных способах расположения листьев на границе решетки;
+
−
##Н-деревья и порядок площади полного двоичного дерева при произвольном расположении листьев.
+
  
−
=== Основные подходы и методы логического синтеза СБИС ===
+
=== Представление логических схем ===
  
−
# Двухуровневый логический синтез и ДНФ. Основные подходы к двухуровневой оптимизации.
+
# Двоичные решающие диаграммы (BDD) и представление булевых функций в виде BDD.
−
## реализация функций в виде ДНФ и ее связь с ПЛМ;
+
# Различные типы BDD. Связь BDD с контактными схемами и схемами из функциональных элементов.
−
## простые импликанты и неизбыточные покрытия;
+
# Основные операции над BDD. Выбор оптимального порядка переменных разложения и его значение для упорядоченных BDD.
−
## кофакторы и разложение Шеннона;
+
# Представление логических схем с использованием BDD.
−
## использование областей неопределенности (don’t care);
+
−
# Многоуровневый логический синтез и связанные с ним представления функций.
+
−
## скобочные формы, построенные на основе ДНФ;
+
−
## определение двоичных решающих диаграмм (BDD) и представления функций в виде BDD;
+
−
## связь BDD с контактными схемами и операции над BDD, различные типы BDD;
+
−
## выбор оптимального порядка переменных разложения и его значение для упорядоченных BDD.
+
−
# Основные подходы к многоуровневой оптимизации.
+
−
## декомпозиция и другие структурные операции над булевскими сетями;
+
−
## упрощение вершин и его основные приемы;
+
−
## использование булевских и алгебраических делителей;
+
−
## привязка к библиотечному базису (mapping).
+
−
# Анализ задержек и временная оптимизация схем.
+
−
## временной анализ транзисторных схем;
+
−
## модели задержек функциональных элементов и задержки СФЭ;
+
−
## статические критические пути и борьба с ними, выявление «ложных» критических путей.
+
  
−
=== Логический синтез СБИС в системе SIS ===
+
=== Двухуровневый логический синтез ===
  
−
# Знакомство с системой логического синтеза СБИС SIS. Форматы представления данных.
+
# Реализация функций алгебры логики в виде дизъюнктивных нормальных форм (ДНФ) и ее связь с ПЛМ.
−
## понятие о логическом синтезе. Общие сведения о системе SIS. Основные возможности системы;
+
# Простые импликанты и неизбыточные покрытия.
−
## форматы представления данных в SIS: .pla, .blif, .eqn (подробный разбор формата .blif);
+
# Обобщенно-монотонное разложение булевых функций.
−
## формат файлов библиотеки .genlib;
+
# Эвристические подходы к минимизации ДНФ.
−
## привязка к библиотеке (мэппинг) и пример её  простой реализации;
+
 
−
## основные команды и операции системы SIS.
+
=== Многоуровневый логический синтез ===
−
# Алгоритмы логической оптимизации в SIS.
+
 
−
## описание двухуровневой и многоуровневой модели представления функций;
+
# Модель логических сетей и основные структурные операции над ними: упрощение вершин, декомпозиция и подстановка вершин.
−
## основные команды логической оптимизации в системе SIS (simplify,  resub, gkx, gcx и др.) и описание их работы;
+
# Операция деления и модель алгебраического деления.
−
## оптимизационные скрипты в SIS (на примере скрипта script.algebraic).
+
# Совокупное ядро делителей и алгоритмы его нахождения.
−
# Эвристический алгоритм двухуровневой оптимизации ESPRESSO.
+
# Основные способы нахождения общих делителей.
−
## общее описание идеи и структуры алгоритма;
+
# Использование областей неопределенности (don’t care) для упрощения логических сетей.
−
## построение тупикового покрытия по заданному покрытию (процедура IRREDUNDANT);
+
 
−
## сужение граней заданного покрытия (процедура REDUCE);
+
=== Привязка к библиотечному базису ===
−
## максимальное расширение граней заданного покрытия (процедура EXPAND).
+
# Задача привязки логической схемы к технологической библиотеке (technology mapping).
−
#Моделирование асинхронных систем.
+
# Основные алгоритмы привязки к технологической библиотеке.
−
##сети Петри (описание модели и особенности функционирования);
+
 
−
##моделирование различных асинхронных систем при помощи сетей Петри;
+
=== Разбиение интегральной схемы ===
−
##основные характеристики сетей Петри: ограниченность, живучесть, обратимость (на примере конкретных схем).
+
# Основные цели разбиения интегральной схемы, оценка качества разбиения и связь с теорией графов.
 +
# Алгоритмы разбиения графов и гиперграфов: алгоритм Кернигана-Лина и его расширения, алгоритм Федуччи-Маттеуса (Fiduccia-Mattheyses).
 +
# Задачи кластеризации и основные подходы к многоуровневому разбиению интегральной схемы.
 +
 
 +
=== Размещение модулей интегральной схемы ===
 +
# Задача глобального размещения элементов интегральной схемы и основные метрики оценки качества размещения.
 +
# Основные подходы к размещению:
 +
## геометрические методы и подходы, основанные на декомпозиции (min-cut placement),
 +
## аналитические подходы (силовой метод, размещение как задача квадратичного программирования),
 +
## стохастические подходы (моделирование отжига).
 +
# Современные алгоритмы размещения.
 +
 
 +
=== Трассировка соединений в интегральной схеме ===
 +
# Алгоритмы на графах. Основные определения. Методы и структуры представления графов. Обходы графов. Стягивающие деревья.
 +
# Эйлеровы пути. Нахождение Эйлеровых путей в электрической схеме.
 +
# Кратчайшие пути. Вычисление расстояний. Алгоритм Форда-Беллмана. Алгоритм Дейкстры. Алгоритм Флойда.
 +
# Задача трассировки соединений. Классификация алгоритмов трассировки. Представление областей трассировки.
 +
# Задача глобальной трассировки. MST и SMT деревья. Последовательный алгоритм построения дерева Штейнера.
 +
# Волновая трассировка. Ограничения и модификации алгоритма.
  
 
== Литература ==
 
== Литература ==
Строка 106: Строка 74:
 
# 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
  
−
== Слайды к лекциям ==
+
== Материалы к экзамену ==
−
# Меры качества разработки цифровой интегральной схемы [[Media:SBIS_slides_2012_metrics.pdf|[1]]]
+
# Список вопросов к экзамену (вариант 2014 года) [[Media:MMMSBIS_2014.pdf|[1]]].
−
# КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами [[Media:SBIS_slides_2012_CMOS_memory.pdf|[2]]]
+
−
 
+
−
== Домашние задания (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]]
+

Версия 13:32, 5 января 2015

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