Математические модели и методы логического синтеза сверхбольших интегральных схем
Курс по магистерской программе Дискретные управляющие системы и их приложения.
Чтение курса обеспечивается кафедрой математической кибернетики, лектор — доцент Шуплецов Михаил Сергеевич.
Объем: 32 ч.
Начало курса: 10.09.2015
Время:
Аудитория:
Содержание
- 1 Аннотация
- 2 Материалы к экзамену
- 3 Программа Курса
- 4 Тестирование и верификация логических схем
- 5 Литература
Аннотация
Курс посвящен изложению ключевых вопросов, связанных с логическим синтезом сверхбольших интегральных схем (СБИС). В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задачи логического синтеза СБИС, а также задачи привязки логической схемы к технологической библиотеке.
Материалы к экзамену
Списки вопросов в экзамену прошлых лет
- Список вопросов к экзамену(2018-2019 учебный год).
- Список вопросов к экзамену(2017-2018 учебный год).
- Список вопросов к экзамену.
Программа Курса
Задача проектирования цифровых СБИС и связанные с ней модели дискретных управляющих систем
Общие сведения о проектировании цифровых СБИС, средства автоматизации проектирования. Основные стратегии проектирования цифровых СБИС.
Методология проектирования на основе стандартных элементов (ячеек). Программируемые матрицы логических элементов (ПЛИС). Системы на кристалле.
Уровни абстракции при проектировании цифровых СБИС. Математические модели, используемые для описания различных уровней абстракции цифровой СБИС. Комбинационные и последовательные схемы.
Упрощенный маршрут проектирования современных цифровых СБИС.
Меры качества разработки цифровых СБИС. Параметры, оптимизируемые при проектировании СБИС. Источники шума в СБИС, влияние шума на цифровые СБИС.
Модель логических схем на КМОП-транзисторах
Полевые транзисторы, принцип их работы и устройство
N- и P-канальные транзисторы, их проводимость. Логические схемы НЕ, 2-НЕ-ИЛИ и др. Передаточная характеристика по напряжению, запас устойчивости по шуму и поглощение шума на примере КМОП инвертора.
Модель комбинационных логических схем на КМОП-транзисторах
Структура и функционирование КМОП-схемы общего вида, правильные комбинационные КМОП- схемы.
Синтез комбинационных КМОП-схем на основе структурного моделирования контактных схем (КС), итеративно-контактных схем (ИКС) и схем из функциональных элементов (СФЭ). Примеры и сравнительный анализ разных типов структурного моделирования (СФЭ, КС и ИКС).
Связь между логическим и транзисторным уровнем, понятие о технологической библиотеке.
КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами
Представление об RC-схемах и их задержке, временной анализ транзисторных схем. Логическая и транзисторная схемы асинхронной ячейки памяти(защелки), ее функционирование. Схема D-триггера и его связь с единичной задержкой.
Логическая оптимизация комбинационных логических схем
Различные способы представления функций алгебры логики (ФАЛ) (таблицы истинности, формулы, двоичные решающие диаграммы, схемы из функциональных элементов). Сравнение указанных представлений и их ограничения.
Комбинационные логические сети (КЛС). Задача оптимизации КЛС (различные постановки задач, функционалы качества при оптимизации КЛС). Основные типы преобразований КЛС: исключение, разложение, экстракция, упрощение и подстановка.
Моделирование задержки на логическом уровне и задача оценки задержки КЛС. Ложные критические пути и алгоритмы их обнаружения. Алгоритмы оптимизации задержки.
Конъюнктивно-инверсные графы (And-Inverter Graphs (AIG)). Связь AIG со СФЭ в базисе Поста. Структурное хэширование AIG. Основные типы преобразования AIG. Алгоритмы минимизации AIG.
Логическая оптимизация последовательных схем
Общее описание автоматных моделей. Основные задачи. Структурная и поведенческая модель.
Оптимизация последовательных схем на основе автоматных моделей. Задачи минимизации и кодирования состояний автомата.
Минимизация числа состояний детерминированного конечного автомата(ДКА). Теорема Мура и рекурсивное определение множества эквивалентных состояний. Алгоритм Хопкрофта. Не всюду определенные ДКА. Задача минимизации числа состояний не всюду определенного ДКА.
Синхронные логические схемы (СЛС). Связь СЛС со схемами из функциональных элементов и элементов задержки. Алгоритмы временной оптимизации СЛС (Retiming).
Презентация (ECE 667, University of Massachusetts)
Привязка логической схемы к библиотеке
Общая постановка задачи. Общая схема решения (этапы решения). Приведение схемы(decomposition), разбиение схемы(partitioning), поиск соответствий(matching), поиск оптимального покрытия(covering).
Поиск структурных соответствий (structural matching). Постановка задачи. Рекурсивный алгоритм поиска структурных соответствий. Задача поиска подстроки в строки. Алгоритм Ахо-Корасик. Кодирование деревьев при помощи строк. Поиск структурных соответствий при помощи алгоритма Ахо-Корасик.
Поиск логических соответствий (Boolean matching). Постановка задачи. Алгоритмы поиска логических соответствий.
Задача привязки к библиотеке для ПЛИС. Особенности постановки задачи и этапы ее решения. Алгоритмы привязки к библиотеке для ПЛИС.
Тестирование и верификация логических схем
Задачи верификации и тестирования логических схем и основные подходы к ее решению. Методы автоматической генерации тестов для схем. Задача выполнимости булевых формул. Основные принципы и подходы к построению эффективных программ для решения указанной задачи.
Презентация (ECE 667, University of Massachusetts)
Задача верификации логических комбинационных схем (combinational equivalence checking). Основные методы решения указанной задачи.
Презентация (ECE 667, University of Massachusetts)
Литература
- Ложкин С.А. Лекции по основам кибернетики. — М.: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.
- Ж.М. Рабаи, А. Чандракасан, Б. Николич Цифровые интегральные схемы. Методология проектирования. – Вильямс, 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.
