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

Обязательный годовой курс для студентов 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. Ложкин С.А. Лекции по основам кибернетики ^[1][2][3]. — М.: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.
2. Brayton R.K., Logic Synthesis. — Univ. of California, Berkeley, 2000.
3. Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС ^[1].

Слайды к лекциям

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

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

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

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

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