Математические модели и методы синтеза СБИС — различия между версиями
Материал из Кафедра математической кибернетики
м (→Материалы к экзамену) |
м (→Материалы к экзамену) |
||
| (не показаны 4 промежуточных версий 1 участника) | |||
| Строка 7: | Строка 7: | ||
Курс является вводным и посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС. | Курс является вводным и посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС. | ||
| + | == Материалы к экзамену == | ||
| + | # Список вопросов к экзамену (вариант 2024 года) [[Media:MMMSBIS_2024.pdf|[1]]]. | ||
| + | |||
| + | == Материалы к экзаменам прошлых лет == | ||
| + | |||
| + | # Список вопросов к экзамену (вариант 2023 года) [[Media:MMMSBIS_2023.pdf|[1]]]. | ||
| + | # Список вопросов к экзамену (вариант 2019 года) [[Media:MMMSBIS_2019.pdf|[2]]]. | ||
| + | # Список вопросов к экзамену (вариант 2018 года) [[Media:MMMSBIS_2018.pdf|[3]]]. | ||
| + | # Список вопросов к экзамену (вариант 2017 года) [[Media:MMMSBIS_2017.pdf|[4]]]. | ||
| + | # Список вопросов к экзамену (вариант 2016 года) [[Media:MMMSBIS_2016.pdf|[5]]]. | ||
| + | # Список вопросов к экзамену (вариант 2015 года) [[Media:MMMSBIS_2015.pdf|[6]]]. | ||
| + | # Список вопросов к экзамену (вариант 2014 года) [[Media:MMMSBIS_2014.pdf|[7]]]. | ||
== Программа курса == | == Программа курса == | ||
| Строка 59: | Строка 71: | ||
[[Media:VLSI_318_graph_partitioning_2017.pdf|Презентация(2017)]] | [[Media:VLSI_318_graph_partitioning_2017.pdf|Презентация(2017)]] | ||
| + | |||
| + | [http://vlsicad.eecs.umich.edu/KLMH/downloads/book/chapter2/chap2r-130523.pdf Презентация(2019)] | ||
=== Размещение модулей интегральной схемы === | === Размещение модулей интегральной схемы === | ||
| Строка 65: | Строка 79: | ||
# Основные подходы к размещению: | # Основные подходы к размещению: | ||
## геометрические методы и подходы, основанные на декомпозиции (min-cut placement), | ## геометрические методы и подходы, основанные на декомпозиции (min-cut placement), | ||
| − | ## аналитические подходы ( | + | ## аналитические подходы (размещение как задача квадратичного программирования), |
## стохастические подходы (моделирование отжига). | ## стохастические подходы (моделирование отжига). | ||
# Современные алгоритмы размещения. | # Современные алгоритмы размещения. | ||
| Строка 74: | Строка 88: | ||
[[Media:VLSI_318_placement_2017.pdf|Презентация(2017)]] | [[Media:VLSI_318_placement_2017.pdf|Презентация(2017)]] | ||
| + | |||
| + | [http://vlsicad.eecs.umich.edu/KLMH/downloads/book/chapter4/chap4-141124.pdf Презентация(2019)] | ||
=== Трассировка соединений в интегральной схеме === | === Трассировка соединений в интегральной схеме === | ||
| − | # | + | # Основные задачи трассировки соединений: детальная и глобальная трассировка. |
| − | + | ||
| − | + | ||
# Задача трассировки соединений. Классификация алгоритмов трассировки. Представление областей трассировки. | # Задача трассировки соединений. Классификация алгоритмов трассировки. Представление областей трассировки. | ||
# Задача глобальной трассировки. MST и SMT деревья. Последовательный алгоритм построения дерева Штейнера. | # Задача глобальной трассировки. MST и SMT деревья. Последовательный алгоритм построения дерева Штейнера. | ||
| − | # | + | # Одновременная трассировка всех сетей. Сведение задачи глобальной трассировки к задаче целочисленного линейного программирования. |
[[Media:VLSI_418_routing.pdf|Презентация]] | [[Media:VLSI_418_routing.pdf|Презентация]] | ||
| Строка 89: | Строка 103: | ||
[[Media:VLSI_318_routing_2017.pdf|Презентация(2017)]] | [[Media:VLSI_318_routing_2017.pdf|Презентация(2017)]] | ||
| + | |||
| + | [http://vlsicad.eecs.umich.edu/KLMH/downloads/book/chapter5/chap5-130517.pdf Презентация(2019)] | ||
== Литература == | == Литература == | ||
| Строка 103: | Строка 119: | ||
# Handbook of Algorithms for Physical design Automation, Edited by Charles J. Alpert Dinesh P. Mehta Sachin S. Sapatnekar, 2009. | # Handbook of Algorithms for Physical design Automation, Edited by Charles J. Alpert Dinesh P. Mehta Sachin S. Sapatnekar, 2009. | ||
# Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu. VLSI Physical Design: From Graph Partitioning to Timing Closure, 2011 | # Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu. VLSI Physical Design: From Graph Partitioning to Timing Closure, 2011 | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
[[Категория:Лекционные_курсы_кафедры_МК]] | [[Категория:Лекционные_курсы_кафедры_МК]] | ||
Текущая версия на 14:26, 31 мая 2024
Обязательный семестровый курс для студентов 318 группы.
Лекции по данному курсу читает доцент Шуплецов М.С.. До 2017 года данный курс читался совместно с профессором Марченко А. М.
Лекции проходят один раз в неделю в 12:50 в аудитории 505. Материалы по семинарским занятиям курса можно найти здесь.
Курс является вводным и посвящен изложению ключевых вопросов, связанных с логическим и топологическим синтезом СБИС. В нем рассматриваются математические модели современных электронных схем, описываются основные подходы к решению задач логического и топологического синтеза СБИС.
Содержание
- 1 Материалы к экзамену
- 2 Материалы к экзаменам прошлых лет
- 3 Программа курса
- 3.1 Задача синтеза интегральных схем и основные сведения о КМОП технологии
- 3.2 Двухуровневый логический синтез
- 3.3 Многоуровневый логический синтез
- 3.4 Привязка к библиотечному базису
- 3.5 Разбиение интегральной схемы
- 3.6 Размещение модулей интегральной схемы
- 3.7 Трассировка соединений в интегральной схеме
- 4 Литература
Материалы к экзамену
- Список вопросов к экзамену (вариант 2024 года) [1].
Материалы к экзаменам прошлых лет
- Список вопросов к экзамену (вариант 2023 года) [1].
- Список вопросов к экзамену (вариант 2019 года) [2].
- Список вопросов к экзамену (вариант 2018 года) [3].
- Список вопросов к экзамену (вариант 2017 года) [4].
- Список вопросов к экзамену (вариант 2016 года) [5].
- Список вопросов к экзамену (вариант 2015 года) [6].
- Список вопросов к экзамену (вариант 2014 года) [7].
Программа курса
Задача синтеза интегральных схем и основные сведения о КМОП технологии
- Общие сведения о проектировании цифровых интегральных схем
- КМОП транзисторы.
- Маршруты проектирования интегральных схем.
- Проектирование программируемых логических матриц (ПЛМ), полузаказных и заказных схем.
- Метод стандартных ячеек.
Презентация о технологии производства микроэлектронных устройств от Марченко А.М.
Двухуровневый логический синтез
- Реализация функций алгебры логики в виде дизъюнктивных нормальных форм (ДНФ) и ее связь с ПЛМ.
- Простые импликанты и неизбыточные покрытия.
- Обобщенно-монотонное разложение булевых функций.
- Эвристические подходы к минимизации ДНФ.
Многоуровневый логический синтез
- Модель логических сетей и основные структурные операции над ними: упрощение вершин, декомпозиция и подстановка вершин.
- Операция деления и модель алгебраического деления.
- Совокупное ядро делителей и алгоритмы его нахождения.
- Основные способы нахождения общих делителей.
- Использование областей неопределенности (don’t care) для упрощения логических сетей.
Привязка к библиотечному базису
- Задача привязки логической схемы к технологической библиотеке (technology mapping).
- Основные алгоритмы привязки к технологической библиотеке.
Разбиение интегральной схемы
- Основные цели разбиения интегральной схемы, оценка качества разбиения и связь с теорией графов.
- Алгоритмы разбиения графов и гиперграфов: алгоритм Кернигана-Лина и его расширения, алгоритм Федуччи-Маттеуса (Fiduccia-Mattheyses).
- Задачи кластеризации и основные подходы к многоуровневому разбиению интегральной схемы.
Размещение модулей интегральной схемы
- Задача глобального размещения элементов интегральной схемы и основные метрики оценки качества размещения.
- Основные подходы к размещению:
- геометрические методы и подходы, основанные на декомпозиции (min-cut placement),
- аналитические подходы (размещение как задача квадратичного программирования),
- стохастические подходы (моделирование отжига).
- Современные алгоритмы размещения.
Трассировка соединений в интегральной схеме
- Основные задачи трассировки соединений: детальная и глобальная трассировка.
- Задача трассировки соединений. Классификация алгоритмов трассировки. Представление областей трассировки.
- Задача глобальной трассировки. MST и SMT деревья. Последовательный алгоритм построения дерева Штейнера.
- Одновременная трассировка всех сетей. Сведение задачи глобальной трассировки к задаче целочисленного линейного программирования.
Литература
- Г.Г.Казеннов, В.М.Щемелинин. Топологическое проектирование нерегулярных БИС. М., Высшая школа, 1990, 109с.
- Ложкин С.А. Лекции по основам кибернетики. — М.: Изд. Отдел ф-та ВМиК МГУ, 2004. — 256 с.
- Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС [1].
- Ж.М. Рабаи, А. Чандракасан, Б. Николич Цифровые интегральные схемы. Методология проектирования. – Вильямс, 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.
- T. Lengauer. Combinatorial algorithms for integrated circuit layout. Wiley, 1990, 694 p.
- Naveed Sherwani. Algorithms for VLSI physical design automation. Kluwer academic publishers, 1995, 538p.
- Introduction to Algorithms, T. Cormen, C. Lesierson, R. Rivest, The MIT Press, Second Printing, 1996.
- Handbook of Algorithms for Physical design Automation, Edited by Charles J. Alpert Dinesh P. Mehta Sachin S. Sapatnekar, 2009.
- Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu. VLSI Physical Design: From Graph Partitioning to Timing Closure, 2011
