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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск

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