Математические модели и методы логического синтеза сверхбольших интегральных схем

Курс по магистерской программе Дискретные управляющие системы и их приложения.

Чтение курса обеспечивается кафедрой математической кибернетики, лектор — доцент Шуплецов Михаил Сергеевич.

Объем: 32 ч.

Начало курса:

Время:

Аудитория:

Аннотация

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

Материалы к экзамену

• Правила проведения экзамена.
• Список вопросов к экзамену.

Списки вопросов в экзамену прошлых лет

• Список вопросов к экзамену(2020-2021 учебный год).
• Список вопросов к экзамену(2019-2020 учебный год).
• Список вопросов к экзамену(2018-2019 учебный год).
• Список вопросов к экзамену(2017-2018 учебный год).
• Список вопросов к экзамену.

Программа Курса

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

Общие сведения о проектировании цифровых СБИС, средства автоматизации проектирования. Основные стратегии проектирования цифровых СБИС.

Методология проектирования на основе стандартных элементов (ячеек). Программируемые матрицы логических элементов (ПЛИС). Системы на кристалле.

Уровни абстракции при проектировании цифровых СБИС. Математические модели, используемые для описания различных уровней абстракции цифровой СБИС. Комбинационные и последовательные схемы.

Упрощенный маршрут проектирования современных цифровых СБИС.

Меры качества разработки цифровых СБИС. Параметры, оптимизируемые при проектировании СБИС. Источники шума в СБИС, влияние шума на цифровые СБИС.

Презентация.

Модель логических схем на КМОП-транзисторах

Полевые транзисторы, принцип их работы и устройство

N- и P-канальные транзисторы, их проводимость. Логические схемы НЕ, 2-НЕ-ИЛИ и др. Передаточная характеристика по напряжению, запас устойчивости по шуму и поглощение шума на примере КМОП инвертора.

Модель комбинационных логических схем на КМОП-транзисторах

Структура и функционирование КМОП-схемы общего вида, правильные комбинационные КМОП- схемы.

Синтез комбинационных КМОП-схем на основе структурного моделирования контактных схем (КС), итеративно-контактных схем (ИКС) и схем из функциональных элементов (СФЭ). Примеры и сравнительный анализ разных типов структурного моделирования (СФЭ, КС и ИКС).

Связь между логическим и транзисторным уровнем, понятие о технологической библиотеке.

Задача поиска оптимальных и близких к ним схем, реализующих функции от малого числа переменных.

Презентация.

Логическая оптимизация комбинационных логических схем

Различные способы представления функций алгебры логики (ФАЛ) (таблицы истинности, формулы, двоичные решающие диаграммы, схемы из функциональных элементов). Сравнение указанных представлений и их ограничения.

Комбинационные логические сети (КЛС). Задача оптимизации КЛС (различные постановки задач, функционалы качества при оптимизации КЛС). Основные типы преобразований КЛС: исключение, разложение, экстракция, упрощение и подстановка. Алгебраическая модель. Разложение на основе деления. Булевская модель и разложение на основе булевского деления.

Презентация.

Не всюду определенные функции. Использование областей неопределенности для локальной оптимизации схем.

Презентация.

Конъюнктивно-инверсные графы (And-Inverter Graphs (AIG)). Связь AIG со СФЭ в базисе Поста. Структурное хэширование AIG. Основные типы преобразования AIG. Алгоритмы минимизации AIG.

Презентация.

Временная оптимизация схем на логическом уровне

Элементы с памятью, особенности временных характеристик схем

Представление об RC-схемах и их задержке, временной анализ схем. Логическая и транзисторная схемы асинхронной ячейки памяти(защелки), ее функционирование. Схема D-триггера и его связь с единичной задержкой. Статический временной анализ. Трепетание сигнала (glitches). Понятие о ложном критическом пути.

Презентация.

Задачи временной оптимизации (retiming)

Общее описание автоматных моделей. Основные задачи. Синхронные логические схемы (СЛС). Связь СЛС со схемами из функциональных элементов и элементов задержки. Алгоритмы временной оптимизации СЛС (Retiming).

Презентация.

Привязка логической схемы к библиотеке

Общая постановка задачи. Общая схема решения (этапы решения). Приведение схемы(decomposition), разбиение схемы(partitioning), поиск соответствий(matching), поиск оптимального покрытия(covering).

Поиск структурных соответствий (structural matching). Постановка задачи. Рекурсивный алгоритм поиска структурных соответствий. Задача поиска подстроки в строки. Алгоритм Ахо-Корасик. Кодирование деревьев при помощи строк. Поиск структурных соответствий при помощи алгоритма Ахо-Корасик.

Презентация.

Решение задачи привязки логической схемы к библиотеке при помощи методов динамического программирования.

Презентация.

Тестирование и верификация логических схем

Задачи верификации и тестирования логических схем и основные подходы к ее решению. Методы автоматической генерации тестов для схем. Задача выполнимости булевых формул. Основные принципы и подходы к построению эффективных программ для решения указанной задачи. Задача верификации логических комбинационных схем (combinational equivalence checking). Основные методы решения указанной задачи.

Презентация

Литература

1. Ложкин С.А. Лекции по основам кибернетики. — М.: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.
2. Ж.М. Рабаи, А. Чандракасан, Б. Николич Цифровые интегральные схемы. Методология проектирования. – Вильямс, 2007.
3. Brayton R.K., Logic Synthesis. — Univ. of California, Berkeley, 2000.
4. Hatchel G.D., Somenzi F. Logic Synthesis and Verification Algorithms. – Kluwer Academic Publishers, 2002.
5. Giovanni De Micheli Synthesis and Optimization of Digital Circuits. – McGraw-Hill Science/Engeneering/Math, 1994.