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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Новая страница: «Курс по магистерской программе Дискретные управляющие системы и их приложения. Чтение …»)
 
м (→‎Материалы к экзамену)
 
(не показаны 14 промежуточные версии 1 участника)
Строка 1: Строка 1:
 
Курс по магистерской программе Дискретные управляющие системы и их приложения.
 
Курс по магистерской программе Дискретные управляющие системы и их приложения.
  
−
Чтение курса обеспечивается кафедрой математической кибернетики, лектор — ассистент [[Шуплецов Михаил Сергеевич]].
+
Чтение курса обеспечивается кафедрой математической кибернетики, лектор — доцент [[Шуплецов Михаил Сергеевич]].
  
 
'''Объем:''' 32 ч.
 
'''Объем:''' 32 ч.
  
−
'''Начало курса:''' 10.09.2015
+
'''Начало курса:'''
  
 
'''Время:'''
 
'''Время:'''
Строка 12: Строка 12:
  
 
== Аннотация ==
 
== Аннотация ==
−
Курс посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом сверхбольших интегральных схем (СБИС). В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задачи логического синтеза СБИС, а также задачи размещения модулей СБИС и трассировки межсоединений. В рамках практических занятий осуществляется знакомство с базовыми пакетами программ логического и топологического синтеза СБИС, формируются навыки работы с этими пакетами.
+
Курс посвящен изложению ключевых вопросов, связанных с логическим синтезом сверхбольших интегральных схем (СБИС). В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задачи логического синтеза СБИС, а также задачи привязки логической схемы к технологической библиотеке.
 +
 
 +
== Материалы к экзамену ==
 +
* [[Media:Logic_synthesis_2023_exam_rules.pdf|Правила проведения экзамена]].
 +
* [[Media:Logic_synthesis_2023_exam_questions.pdf|Список вопросов к экзамену]].
 +
 
 +
=== Списки вопросов в экзамену прошлых лет ===
 +
* [[Media:Logic_synthesis_2020_exam_questions.pdf|Список вопросов к экзамену(2020-2021 учебный год)]].
 +
* [[Media:Logic_synthesis_2019_exam_questions.pdf|Список вопросов к экзамену(2019-2020 учебный год)]].
 +
* [[Media:Logic_synthesis_2018_exam_questions.pdf|Список вопросов к экзамену(2018-2019 учебный год)]].
 +
* [[Media:Logic_synthesis_2017_exam_questions.pdf|Список вопросов к экзамену(2017-2018 учебный год)]].
 +
* [[Media:Logic_synthesis_2015_exam_questions.pdf|Список вопросов к экзамену]].
  
 
== Программа Курса ==
 
== Программа Курса ==
Строка 27: Строка 38:
  
 
Меры качества разработки цифровых СБИС. Параметры, оптимизируемые при проектировании СБИС. Источники шума в СБИС, влияние шума на цифровые СБИС.
 
Меры качества разработки цифровых СБИС. Параметры, оптимизируемые при проектировании СБИС. Источники шума в СБИС, влияние шума на цифровые СБИС.
 +
 +
[[Media:Logic_synthesis_intro.pdf|Презентация]].
  
 
=== Модель логических схем на КМОП-транзисторах ===
 
=== Модель логических схем на КМОП-транзисторах ===
Строка 42: Строка 55:
 
Связь между логическим и транзисторным уровнем, понятие о технологической библиотеке.
 
Связь между логическим и транзисторным уровнем, понятие о технологической библиотеке.
  
−
==== КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами ====
+
Задача поиска оптимальных и близких к ним схем, реализующих функции от малого числа переменных.
  
−
Представление об RC-схемах и их задержке, временной анализ транзисторных схем. Логическая и транзисторная схемы асинхронной ячейки памяти(защелки), ее функционирование.  Схема D-триггера и его связь с единичной задержкой.
+
[[Media:Logic_synthesis_CMOS.pdf|Презентация]].
  
 
=== Логическая оптимизация комбинационных логических схем ===
 
=== Логическая оптимизация комбинационных логических схем ===
Строка 51: Строка 64:
  
 
Комбинационные логические сети (КЛС). Задача оптимизации КЛС (различные постановки задач, функционалы качества при оптимизации КЛС). Основные типы преобразований КЛС: исключение, разложение, экстракция, упрощение и подстановка.
 
Комбинационные логические сети (КЛС). Задача оптимизации КЛС (различные постановки задач, функционалы качества при оптимизации КЛС). Основные типы преобразований КЛС: исключение, разложение, экстракция, упрощение и подстановка.
 +
Алгебраическая модель. Разложение на основе деления. Булевская модель и разложение на основе булевского деления.
  
−
Моделирование задержки на логическом уровне и задача оценки задержки КЛС. Ложные критические пути и алгоритмы их обнаружения. Алгоритмы оптимизации задержки.
+
[[Media:Logic_synthesis_CLS.pdf|Презентация]].
 +
 
 +
Не всюду определенные функции. Использование областей неопределенности для локальной оптимизации схем.
 +
 
 +
[[Media:Logic_synthesis_CLS_bool.pdf|Презентация]].
  
 
Конъюнктивно-инверсные графы (And-Inverter Graphs (AIG)). Связь AIG со СФЭ в базисе Поста.  Структурное хэширование AIG. Основные типы преобразования AIG. Алгоритмы минимизации AIG.
 
Конъюнктивно-инверсные графы (And-Inverter Graphs (AIG)). Связь AIG со СФЭ в базисе Поста.  Структурное хэширование AIG. Основные типы преобразования AIG. Алгоритмы минимизации AIG.
  
−
=== Логическая оптимизация последовательных схем ===
+
[[Media:Logic_synthesis_AIG.pdf|Презентация]].
  
−
Общее описание автоматных моделей. Основные задачи. Структурная и поведенческая модель.
+
=== Временная оптимизация схем на логическом уровне ===
  
−
Оптимизация последовательных схем на основе автоматных моделей. Задачи минимизации и кодирования состояний автомата.
+
==== Элементы с памятью, особенности временных характеристик схем ====
  
−
Минимизация числа состояний детерминированного конечного автомата(ДКА). Теорема Мура и рекурсивное определение множества эквивалентных состояний. Алгоритм Хопкрофта. Не всюду определенные ДКА. Задача минимизации числа состояний не всюду определенного ДКА.
+
Представление об RC-схемах и их задержке, временной анализ схем. Логическая и транзисторная схемы асинхронной ячейки памяти(защелки), ее функционирование. Схема D-триггера и его связь с единичной задержкой. Статический временной анализ. Трепетание сигнала (glitches). Понятие о ложном критическом пути.
  
−
Синхронные логические схемы (СЛС). Связь СЛС со схемами из функциональных элементов и элементов задержки. Алгоритмы временной оптимизации СЛС (Retiming).
+
[[Media:Logic_synthesis_CMOS_memory.pdf|Презентация]].
 +
 
 +
==== Задачи временной оптимизации (retiming) ====
 +
Общее описание автоматных моделей. Основные задачи. Синхронные логические схемы (СЛС). Связь СЛС со схемами из функциональных элементов и элементов задержки. Алгоритмы временной оптимизации СЛС (Retiming).
 +
 
 +
[[Media:Logic_synthesis_retiming.pdf|Презентация]].
  
 
=== Привязка логической схемы к библиотеке ===
 
=== Привязка логической схемы к библиотеке ===
Строка 72: Строка 95:
 
Поиск структурных соответствий (structural matching). Постановка задачи. Рекурсивный алгоритм поиска структурных соответствий. Задача поиска подстроки в строки. Алгоритм Ахо-Корасик.  Кодирование деревьев при помощи строк. Поиск структурных соответствий при помощи алгоритма Ахо-Корасик.
 
Поиск структурных соответствий (structural matching). Постановка задачи. Рекурсивный алгоритм поиска структурных соответствий. Задача поиска подстроки в строки. Алгоритм Ахо-Корасик.  Кодирование деревьев при помощи строк. Поиск структурных соответствий при помощи алгоритма Ахо-Корасик.
  
−
Поиск логических соответствий (Boolean matching). Постановка задачи. Алгоритмы поиска логических соответствий.
+
[[Media:Logic_synthesis_structural_matching.pdf|Презентация]].
 +
 
 +
Решение задачи привязки логической схемы к библиотеке при помощи методов динамического программирования.
 +
 
 +
[[Media:Logic_synthesis_mapping.pdf|Презентация]].
 +
 
 +
=== Тестирование и верификация логических схем ===
 +
Задачи верификации и тестирования логических схем и основные подходы к ее решению. Методы автоматической генерации тестов для схем. Задача выполнимости булевых формул. Основные принципы и подходы к построению эффективных программ для решения указанной задачи. Задача верификации логических комбинационных схем (combinational equivalence checking). Основные методы решения указанной задачи.
  
−
Задача привязки к библиотеке для ПЛИС. Особенности постановки задачи и этапы ее решения.  Алгоритмы привязки к библиотеке для ПЛИС.
+
[[Media:Logic_synthesis_verification_intro.pdf|Презентация]]
  
 
== Литература ==
 
== Литература ==
 +
# Ложкин С.А. Лекции по основам кибернетики. — М.: Изд. Отдел ф-та ВМиК МГУ, 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.
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Магистерская программа Дискретные управляющие системы и их приложения]]
 
[[Категория:Магистерская программа Дискретные управляющие системы и их приложения]]

Текущая версия на 17:00, 4 декабря 2023

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

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

Объем: 32 ч.

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

Время:

Аудитория:

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

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.
Источник — «https://mk.cs.msu.ru/index.php?title=Математические_модели_и_методы_логического_синтеза_сверхбольших_интегральных_схем&oldid=10789»