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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м (→‎Материалы к экзамену)
м (→‎Материалы к экзамену)
 
(не показаны 6 промежуточные версии 1 участника)
Строка 15: Строка 15:
  
 
== Материалы к экзамену ==
 
== Материалы к экзамену ==
−
* [[Media:Logic_synthesis_2020_exam_rules.pdf|Правила проведения экзамена]].
+
* [[Media:Logic_synthesis_2023_exam_rules.pdf|Правила проведения экзамена]].
−
* [[Media:Logic_synthesis_2020_exam_questions.pdf|Список вопросов к экзамену(2020-2021 учебный год)]].
+
* [[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_2019_exam_questions.pdf|Список вопросов к экзамену(2019-2020 учебный год)]].
 
* [[Media:Logic_synthesis_2018_exam_questions.pdf|Список вопросов к экзамену(2018-2019 учебный год)]].
 
* [[Media:Logic_synthesis_2018_exam_questions.pdf|Список вопросов к экзамену(2018-2019 учебный год)]].
Строка 53: Строка 54:
  
 
Связь между логическим и транзисторным уровнем, понятие о технологической библиотеке.
 
Связь между логическим и транзисторным уровнем, понятие о технологической библиотеке.
 +
 +
Задача поиска оптимальных и близких к ним схем, реализующих функции от малого числа переменных.
  
 
[[Media:Logic_synthesis_CMOS.pdf|Презентация]].
 
[[Media:Logic_synthesis_CMOS.pdf|Презентация]].
−
 
−
==== КМОП-схемы с памятью, реализация автоматных функций КМОП-схемами ====
 
−
 
−
Представление об RC-схемах и их задержке, временной анализ транзисторных схем.  Логическая и транзисторная схемы асинхронной ячейки памяти(защелки), ее функционирование.  Схема D-триггера и его связь с единичной задержкой.
 
−
 
−
[[Media:Logic_synthesis_CMOS_memory.pdf|Презентация]].
 
  
 
=== Логическая оптимизация комбинационных логических схем ===
 
=== Логическая оптимизация комбинационных логических схем ===
Строка 67: Строка 64:
  
 
Комбинационные логические сети (КЛС). Задача оптимизации КЛС (различные постановки задач, функционалы качества при оптимизации КЛС). Основные типы преобразований КЛС: исключение, разложение, экстракция, упрощение и подстановка.
 
Комбинационные логические сети (КЛС). Задача оптимизации КЛС (различные постановки задач, функционалы качества при оптимизации КЛС). Основные типы преобразований КЛС: исключение, разложение, экстракция, упрощение и подстановка.
 +
Алгебраическая модель. Разложение на основе деления. Булевская модель и разложение на основе булевского деления.
  
 
[[Media:Logic_synthesis_CLS.pdf|Презентация]].
 
[[Media:Logic_synthesis_CLS.pdf|Презентация]].
  
−
Моделирование задержки на логическом уровне и задача оценки задержки КЛС. Ложные критические пути и алгоритмы их обнаружения. Алгоритмы оптимизации задержки.
+
Не всюду определенные функции. Использование областей неопределенности для локальной оптимизации схем.
  
−
[[Media:Logic_synthesis_depth.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|Презентация]].
  
−
Общее описание автоматных моделей. Основные задачи. Структурная и поведенческая модель.
+
=== Временная оптимизация схем на логическом уровне ===
  
−
[[Media:Logic_synthesis_sequential.pdf|Презентация]].
+
==== Элементы с памятью, особенности временных характеристик схем ====
  
−
Оптимизация последовательных схем на основе автоматных моделей. Задачи минимизации и кодирования состояний автомата.
+
Представление об RC-схемах и их задержке, временной анализ схем. Логическая и транзисторная схемы асинхронной ячейки памяти(защелки), ее функционирование.  Схема D-триггера и его связь с единичной задержкой. Статический временной анализ. Трепетание сигнала (glitches). Понятие о ложном критическом пути.
  
−
Минимизация числа состояний детерминированного конечного автомата(ДКА). Теорема Мура и рекурсивное определение множества эквивалентных состояний. Алгоритм Хопкрофта. Не всюду определенные ДКА. Задача минимизации числа состояний не всюду определенного ДКА.
+
[[Media:Logic_synthesis_CMOS_memory.pdf|Презентация]].
  
−
Синхронные логические схемы (СЛС). Связь СЛС со схемами из функциональных элементов и элементов задержки. Алгоритмы временной оптимизации СЛС (Retiming).
+
==== Задачи временной оптимизации (retiming) ====
 +
Общее описание автоматных моделей. Основные задачи. Синхронные логические схемы (СЛС). Связь СЛС со схемами из функциональных элементов и элементов задержки. Алгоритмы временной оптимизации СЛС (Retiming).
  
−
[http://www.ecs.umass.edu/ece/labs/vlsicad/ece667/lectures/ece667-LSyn-retiming.ppt Презентация (ECE 667, University of Massachusetts) ]
+
[[Media:Logic_synthesis_retiming.pdf|Презентация]].
  
 
=== Привязка логической схемы к библиотеке ===
 
=== Привязка логической схемы к библиотеке ===
Строка 98: Строка 97:
 
[[Media:Logic_synthesis_structural_matching.pdf|Презентация]].
 
[[Media:Logic_synthesis_structural_matching.pdf|Презентация]].
  
−
Поиск логических соответствий (Boolean matching). Постановка задачи. Алгоритмы поиска логических соответствий.
+
Решение задачи привязки логической схемы к библиотеке при помощи методов динамического программирования.
−
 
+
−
Задача привязки к библиотеке для ПЛИС. Особенности постановки задачи и этапы ее решения.  Алгоритмы привязки к библиотеке для ПЛИС.
+
−
 
+
−
== Тестирование и верификация логических схем ==
+
−
Задачи верификации и тестирования логических схем и основные подходы к ее решению. Методы автоматической генерации тестов для схем. Задача выполнимости булевых формул. Основные принципы и подходы к построению эффективных программ для решения указанной задачи.
+
  
−
[http://www.ecs.umass.edu/ece/labs/vlsicad/ece667/lectures/ece667-Verif-intro.ppt Презентация (ECE 667, University of Massachusetts) ]
+
[[Media:Logic_synthesis_mapping.pdf|Презентация]].
  
−
Задача верификации логических комбинационных схем (combinational equivalence checking). Основные методы решения указанной задачи.
+
=== Тестирование и верификация логических схем ===
 +
Задачи верификации и тестирования логических схем и основные подходы к ее решению. Методы автоматической генерации тестов для схем. Задача выполнимости булевых формул. Основные принципы и подходы к построению эффективных программ для решения указанной задачи. Задача верификации логических комбинационных схем (combinational equivalence checking). Основные методы решения указанной задачи.
  
−
[http://www.ecs.umass.edu/ece/labs/vlsicad/ece667/lectures/ece667-Verif-EquivCheck.ppt Презентация (ECE 667, University of Massachusetts)]
+
[[Media:Logic_synthesis_verification_intro.pdf|Презентация]]
  
 
== Литература ==
 
== Литература ==

Текущая версия на 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»