[VLSI CAD] Почему двухуровневая минимизация логики является сложной задачей

TL;DR

• Чтобы «точно» решить задачу двухуровневой логической минимизации, необходимо следовать подходу Куайна–МакКласки (QM).
  • Поскольку покрытие является NP-полным, «оптимальное решение» представляет собой не значение, а проблему доказательства.
  • (минимальное покрытие столбцов).
    • Покрытие является NP-полным, поэтому «оптимальное решение» — это не значение, а проблема доказательства.
    • SAT вряд ли является серьезной проблемой. Причина в том, что SAT по своей сути является проблемой принятия решения.li>
    • SAT не представляет собой значительной проблемы. Это связано с тем, что SAT по сути является проблемой принятия решения.
• A: Переключатель 1
• B: Переключатель 2
• C: Переключатель 3
1. A=0, B=0, C=1 -> A'B'C
2. A=0, B=1, C=1 -> A'BC
3. A=1, B=0, C=1 -> AB'C
• Все C = 1
• A и B варьируются по-разному
• минимальный термин: комбинации входов (или точки перед расширением куба), где (f=1) в таблице истинности
• простая импликанта: «максимальный куб», который не может быть далее расширен (объединен)
• Цель: Покрыть все (f=1) минтермы с помощью простых импликантов, минимизируя выбранное количество простых (или затраты).
1. A выключена, B выключена, C включена
2. A выключена, B включена, C включена
3. A включена, B выключена, C включена
• A: Оба выключены
• C: Оба включены
• EA%B2%BD%EC%9A%B0-2">Случай 1 против случая 2
  • A: Оба выключены
  • C: Оба включены
  • Различается только B
• При этом единственном условии
  • (A=0, B=0, C=1)
  • (A=0, B=1, C=1)
    Оба случая могут быть объяснены одновременно
  • B: Оба выключены
  • C: Оба включены
  • Различается только A
• Это единственное условие
  • (A=0, B=0, C=1)
  • (A=1, B=0, C=1)
    Объясняет оба случая одновременно
  • A также отличается
  • B также отличается
• Остаются два условия:
  • Условие X: «A не имеет значения, B выключено, а C включено»
  • Условие Y: «A выключено, B не имеет значения, а C включено»
• Сравнивая эти два:
  • A отличается
  • B отличается
• Следовательно, условия для включения лампочки:
• То есть F = C(A' + B')
  • ✔️ Исчерпывающий перечень всех «случаев включения»
  • ✔️ Автоматически объединять случаи, когда различается только один переключатель
  • ✔️ Останавливаться, когда дальнейшие комбинации невозможны
  • ✔️ Остальные условия являются минимальной логикой
• Этот метод доведения правила до абсолютного предела называется Quine–McCluskey.

Метод Куайна-МакКласки (QM) страдает от «экспоненциального взрыва» вычислительной сложности.
Даже небольшое увеличение числа переменных перегружает компьютер.-%EB%AF%B8%EC%B3%A4%EB%8B%A4">Почему? Количество возможностей просто безумное

Если количество переменных обозначить как n,Возможные случаи ввода: 2ⁿМаксимальное количество минтермов: 2^n

Пример:6 переменных → 64 случая10 переменных → 1024 случая15 переменных → 32 768 случаев20 переменных → 1048 576QM обрабатывает «все возможные состояния включения»
Этот этап уже является финальной стадией2️⃣ QM выполняет «все парные сравнения»

Суть QM заключается в следующем:«Отличаются ли этот минтерм и тот минтерм ровно на один бит?»

То есть,Если есть M минтермов,Количество сравнений ≈ M²

Пример:1000 минтермов → 1 миллион сравнений10 000 минтермов → 100 миллионов сравнений30 000 минтермов → 900 миллионов сравнений3️⃣ Настоящий ад — это «выбор простых импликантов»

Самая худшая часть QM — это последняя.Увеличение количества простых импликантовИсследование «Может ли это охватить все минтермы?»Это проблема покрытия множестваNP-трудная, требующая проверки всех возможностей для нахождения ответаЧто такое SAT?

SAT (булева удовлетворимость) — это именно этот вопрос.«Существует ли хотя бы одно входное назначение, которое делает это логическое выражение ИСТИННЫМ?»

Если оно существует, SAT; если нет, UNSAT.
Ключевым моментом является то, что это проблема Да/Нет (существование).Почему SAT хорошо работает на практике, а оптимизация остается сложной задачей?

Здесь многие люди запутываются, но вывод прост.(1) SAT — это проблема принятия решения, поэтому «нахождение одного решения заканчивает ее»Решатель SAT завершает работу, как только находит одно решение.Если UNSAT, накапливаются доказательства «невозможности» (на практике — конфликтное обучение), усиливая обрезку.Таким образом, даже без проверки всех возможностей часто происходит ранний выход.(2) Оптимизация никогда не заканчивается, потому что требует «доказательства оптимальности»

Это то, что действительно требует оптимизация.«Докажите, что лучшего года не существует».»

Другими словами,нахождение решения, лучшего, чем исходное, — это только началоМожно утверждать, что решение является глобально оптимальным, только доказав, что лучшего решения не существует тогда мы можем назвать его «глобально оптимальным».

Это сложно, потому что в конечном итоге требуется обширное исключение комбинаторного пространства.

Даже для трех примеров с лампочками, которые мы рассмотрели ранее, потребовалось несколько вычислений. Однако, если посмотреть на полупроводники для смартфонов, разработанные с 2020 года, то они содержат более 10 миллиардов транзисторов.-Оптимизация-и-проблемы-проектирования-и-производственных-процессов-E2%80%9C%EB%B0%98%EB%B3%B5%E2%80%9D%EC%9D%B4%EB%9D%BC-%EB%AC%B4%EA%B2%81%EB%8B%A4">(3) Существует стандартный прием для решения оптимизационных задач с помощью SAT, но он является громоздким, поскольку включает в себя «итерацию»

Типичный метод преобразования оптимизации в SAT:Применить ограничение, такое как «стоимость ≤ k», и решить задачу SATВ случае успеха уменьшить k и снова решить SATВ случае неудачи увеличить k или остановиться (= бинарный поиск/итеративное ужение)

То есть, SAT решается не один раз, а несколько раз. Более того, по мере уменьшения k ограничения часто становятся более жесткими и сложными.(4) EDA обычно более грязный, чем одноцелевой

Практический EDA обычно включает в себя:Время / Площадь / Мощность / Перегрузка / Маршрутизация … такие как многоцелевыеограничения также включают несколько условий, таких как настройки углов/режимовфункции затрат не являются непрерывными, а демонстрируют неровный ландшафт с резкими изменениями

Следовательно, термин «оптимальный» становится более проблематичным.
В большинстве случаев более честным выражением будет «наилучший из найденных / улучшенный по сравнению с базовым».Разница между «перечислением и оптимизацией»SAT (проблема существования): «Существует ли хотя бы одно удовлетворительное решение?» → Можно завершить поиск после нахождения одного решения. → Для завершения необходимо доказать, что «лучшего решения не существует»

Другими словами,Оптимизация требует доказательства отсутствия (лучшего решения), а не поиска значения.QM страдает от чрезмерно больших таблиц покрытия.Число минтермов составляет примерно ~ (2^n) (строки)Число простых чисел составляет примерно ~ (3^n/n) (столбцов)А минимальное покрытие является NP-полным

Здесь происходит следующее:Существует множество возможностейВ момент выбора «минимальной комбинации» из множества простых чисел начинается комбинаторный взрыв

Поэтому QM, вместо того чтобы предоставлять «точным минимумом», но становится непрактичным для промышленного использования по мере увеличения масштаба.Таким образом, в промышленных условиях эвристика: «Достаточно хороший и стабильный», а не «оптимальный»Фиксированный с самого начала: существенный приоритетСокращение самой таблицы случаев: доминирование / равенствоОсновные случаи, остающиеся до конца: циклическое ядро

«Цикл», остающийся после всех сокращений, является циклическим ядром.
Отсюда подход обычно заключается в следующем:разветвление и ограничениеРешение с помощью эвристики, которая дает «хорошее ограничение».Вывод: задача EDA заключается не в «вычислении», а в «доказательстве оптимальности»"

Двухуровневая логическая минимизация — отличный учебный пример.
Потому что с помощью одного экземпляра NP-полного покрытия можно легко вывести реальность EDA в целом (размещение / маршрутизация / планирование / …).EDA — это инженерия.
Цель — «быстрое, стабильное и метрическое улучшение».

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

В этом заключается суть метода Куайна–МакКласки

C должен быть включен,
и либо A должен быть выключен,
либо B должен быть выключен

3️⃣ Окончательное оставшееся объяснение

Поскольку два переключателя отличаются,
их нельзя комбинировать дальше

2️⃣ Переоценить возможность дальнейшего объединения

Если оба переключателя отличаются
Правила QM запрещают их объединение

Случай 2 против случая 3

A не имеет значения
«B должен быть выключен, а C должен быть включен»

Случай 1 против случая 3

B не имеет значения
«A должен быть выключен, и только C должен быть включен»

Когда в статьях встречаются такие термины, как «глобальный оптимум» или «оптимальное решение», необходимо проверить следующий контрольный список.

Контрольный список:

• Есть ли фактические доказательства гарантии оптимальности?
• Каков размер задачи (n)?
• Сравнение проводится с эвристическим базовым уровнем или с «оптимальным»?
• Какова цель? (Только время? Только площадь? Только мощность?)
• Есть ли повторение/распределение семян? (Проверить надежность)
• Следовательно, это воспроизводимо?

Узким местом в QM является этап минимального покрытия столбцов.

EDA использует эвристику + обрезку + метод ветвей и границ для быстрого генерации «достаточно хороших решений».

Что такое двухуровневая логическая минимизация??

Сценарий

Предположим, что есть три переключателя.Лампочка F включается при следующих трех условиях:То есть F = A'B'C + A'BC + AB'C👉 Три AND + одно OR
👉 Необходимо ли это?

Процесс упрощения — это процесс оптимизации.

Внимательно рассмотрите три выражения:То есть F = C(A'B' + A'B + AB')

Дальнейшее сокращение внутренней части,

A'B' + A'B = A'(B' + B) = A'То есть F = C(A' + AB')

Подводя итог.

A' + AB' = A' + B'

Конечный результат (минимизация двухуровневой логики)

F = (A' + B')CКоличество элементов AND и OR уменьшилось, а выражение стало проще. На аппаратном уровне это означает уменьшение количества ячеек и межсоединений.EB%A1%9C-%EB%A7%90%ED%95%98%EB%A9%B4">В двух словах

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

Это двухуровневая логическая минимизация.Говоря более академическим языком,

выразите заданную булеву функцию (f) с использованием минимального числа произведений (SOP).

Ключевыми компонентами здесь являются:

Алгоритм QM (Quine–McCluskey) (точное решение)

На рисунке выше цифра 4 является основным элементом.Решите задачу минимального преобразования столбцов для B (задача преобразования unate).Сначала рассмотрим QM.EB%AC%B8%EC%A0%9C-%EB%8B%A4%EC%8B%9C-%EC%8B%9C%EC%9E%91">Проблема с лампочкой ПерезапускБыло ровно три случая, когда лампочка F загоралась.Пока что давайте просто подумаем об этом так:

«Существует точный список состояний выключателя, который включает лампочку».

Квина–МакКласки?

Это метод, с помощью которого компьютеры автоматически комбинируют условия, используя только правила.Правило простое:

Если лампочка загорается в двух разных случаях
и только один переключатель отличается,
то этот переключатель не имеет значения.

Случай 1 против случая 2