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

Обязательный годовой курс для студентов 418 группы. В 2011-2012 учебном году лекции по данному курсу читают м.н.с. Шуплецов М.С. (первая часть) и профессор Марченко А. М. (вторая часть), а практические занятия проводит Шуплецов М.С.. В предыдущие годы лекции по этому курсу читались Ложкиным С. А. (первая часть), а практические занятия проводились доцентом Романовым Д. С..

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

Вопросы по курсу (I часть)

Задача синтеза СБИС и связанные с ней модели дискретных управляющих систем

1. Полевые транзисторы, принцип их работы и устройство. Основные сведения о КМОП-технологии и проектировании СБИС.
   1. n- и p-канальные транзисторы, их проводимость;
   2. представление об интегральной КМОП-технологии;
   3. задача проектирования СБИС и маршрут ее решения.
2. Простейшие логические схемы на КМОП-транзисторах. Функционирование и классификация комбинационных КМОП-схем, оценка их числа.
   1. логические схемы НЕ, 2-НЕ-ИЛИ и др.;
   2. структура и функционирование КМОП-схемы общего вида, правильные комбинационные КМОП-схемы;
   3. оценка числа правильных комбинационных КМОП-схем;
   4. комбинационные КМОП-схемы с проблемами переключения, схемы с нагрузочными транзисторами и др.
3. Представление об RC-схемах и их задержке. Быстродействие КМОП-схем.
   1. распространение сигнала в КМОП-схемах на примере открытого транзистора;
   2. RC-схемы из дискретных элементов и их задержка, представление об RC-схемах с непрерывным распределением емкости и сопротивления;
   3. основные факторы, влияющие на быстродействие КМОП-схем.
4. Синтез комбинационных КМОП-схем на основе структурного моделирования контактных схем (КС) и итеративных контактных схем (ИКС).
   1. моделирование КС;
   2. моделирование ИКС;
   3. поведение функции Шеннона для сложности правильных комбинационных КМОП-схем.
5. Синтез комбинационных КМОП-схем на основе структурного моделирования схем из функциональных элементов (СФЭ).
   1. моделирование СФЭ в различных базисах и вложение в библиотеку;
   2. СФЭ на негативных элементах и инверсная сложность ФАЛ;
   3. примеры и сравнительный анализ разных типов структурного моделирования.
6. КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами.
   1. логическая и транзисторная схемы RS-триггера, его функционирование;
   2. логическая и транзисторная схемы асинхронной ячейки памяти, ее функционирование;
   3. схема D-триггера и его связь с единичной задержкой;
   4. общая структура автоматных схем, задача их оптимизации.
7. Клеточные схемы как «грубая» топологическая модель СБИС. Порядок функции Шеннона для площади клеточных схем.
   1. клеточные схемы из функциональных и коммутационных элементов в стандартном базисе;
   2. клеточная реализация дешифратора, построенного по совершенной ДНФ;
   3. порядок функции Шеннона для площади клеточных схем.
8. Асимптотика площади дешифратора и ее антагонизм с числом функциональных элементов.
   1. нижняя оценка и асимптотика площади клеточного дешифратора;
   2. нижняя оценка площади дешифратора, построенного асимптотически наилучшим по числу функциональных элементов методом.
9. Основные понятия, связанные с вложением графов. Вложения полных двоичных деревьев в плоские прямоугольные решетки (ППР) минимальной высоты.
   1. вложения графов и связанные с ними понятия;
   2. вложения графов в различные типы ППР, высота и площадь полного двоичного дерева;
10. Асимптотика площади полных двоичных деревьев.
    1. асимптотика площади полного двоичного дерева при различных перегрузках и различных способах расположения листьев на границе решетки;
    2. Н-деревья и порядок площади полного двоичного дерева при произвольном расположении листьев.

Основные подходы и методы логического синтеза СБИС

1. Двухуровневый логический синтез и ДНФ. Основные подходы к двухуровневой оптимизации.
   1. реализация функций в виде ДНФ и ее связь с ПЛМ;
   2. простые импликанты и неизбыточные покрытия;
   3. кофакторы и разложение Шеннона;
   4. использование областей неопределенности (don’t care);
2. Многоуровневый логический синтез и связанные с ним представления функций.
   1. скобочные формы, построенные на основе ДНФ;
   2. определение двоичных решающих диаграмм (BDD) и представления функций в виде BDD;
   3. связь BDD с контактными схемами и операции над BDD, различные типы BDD;
   4. выбор оптимального порядка переменных разложения и его значение для упорядоченных BDD.
3. Основные подходы к многоуровневой оптимизации.
   1. декомпозиция и другие структурные операции над булевскими сетями;
   2. упрощение вершин и его основные приемы;
   3. использование булевских и алгебраических делителей;
   4. привязка к библиотечному базису (mapping).
4. Анализ задержек и временная оптимизация схем.
   1. временной анализ транзисторных схем;
   2. модели задержек функциональных элементов и задержки СФЭ;
   3. статические критические пути и борьба с ними, выявление «ложных» критических путей.

Логический синтез СБИС в системе SIS

1. Знакомство с системой логического синтеза СБИС SIS. Форматы представления данных.
   1. понятие о логическом синтезе. Общие сведения о системе SIS. Основные возможности системы;
   2. форматы представления данных в SIS: .pla, .blif, .eqn (подробный разбор формата .blif);
   3. формат файлов библиотеки .genlib;
   4. привязка к библиотеке (мэппинг) и пример её простой реализации;
   5. основные команды и операции системы SIS.
2. Алгоритмы логической оптимизации в SIS.
   1. описание двухуровневой и многоуровневой модели представления функций;
   2. основные команды логической оптимизации в системе SIS (simplify, resub, gkx, gcx и др.) и описание их работы;
   3. оптимизационные скрипты в SIS (на примере скрипта script.algebraic).
3. Эвристический алгоритм двухуровневой оптимизации ESPRESSO.
   1. общее описание идеи и структуры алгоритма;
   2. построение тупикового покрытия по заданному покрытию (процедура IRREDUNDANT);
   3. сужение граней заданного покрытия (процедура REDUCE);
   4. максимальное расширение граней заданного покрытия (процедура EXPAND).
4. Моделирование асинхронных систем.
   1. сети Петри (описание модели и особенности функционирования);
   2. моделирование различных асинхронных систем при помощи сетей Петри;
   3. основные характеристики сетей Петри: ограниченность, живучесть, обратимость (на примере конкретных схем).

Литература

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. Меры качества разработки цифровой интегральной схемы [1]
2. КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами [2]

Домашние задания (2011 год)

1. Домашнее задание №2 ^[1].
2. Домашнее задание №3 ^[2].

Материалы к зачету по курсу

1. Список вопросов к зачету (вариант 2012 года) [1].
2. Список вопросов к зачету (вариант 2011 года) [1].
3. Таблица успеваемости (2011-2012 учебный год) [2]