[VLSI CAD] Выраженный в EDA

Что такое Espresso? Классический и эталонный подход, который сводит к минимуму количество терминов AND/OR, сохраняя при этом функциональность логического выражения.

Espresso — это алгоритм и инструмент минимизации булевой логики.

1. Проблема, которую решает Espresso

Следующие два логических выражения выполняют точно одну и ту же функцию.

f = a b c + a b ~c

f = a b 

Второе выражение:

• короче
• быстрее
• дешевле.

Espresso имеет только одну цель.

«Сохранить логическую функциональность, минимизировать выражение».

Вывод в одной строке

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

Если QM — это перфекционистский алгоритм,
то Espresso — реалистичный алгоритм.

QM придерживается следующей позиции:

«Я сравню каждый отдельный случай, когда загорается лампочка,
и найду абсолютно кратчайшее объяснение."

Следовательно:

• Даже небольшое увеличение числа случаев приводит к
• взрывному росту числа случаев
• сбою компьютера

Подход Espresso совершенно иной

Espresso думает так:

«Начните описание лампочки
немного грубо,
затем постепенно уточняйте его.
Оно не должно быть идеальным».

Другими словами,

• Он не ищет оптимального решения с самого начала
• Вместо этого он быстро сходится к решению

Основная идея Espresso (3-ступенчатый цикл)

Espresso всегда повторяет эти три вещи.

1️⃣ РАСШИРЕНИЕ (группируйте как можно шире)

1️⃣ РАСШИРЕНИЕ (группируйте как можно шире)

Сформулируйте условия для включения лампочки
сначала как можно более свободно.

Пример:

• «A=0, B=0, C=1»
• «A=0, B=1, C=1»

👉
«Но разве это не означает, что
лампа будет гореть почти все время, если C=1?»

→ Смело расширяйте условия

2️⃣ REDUCE (Удалите ненужные части)

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

Следовательно:

• «А, это нужно удалить»
• «Это условие нужно ужесточить»

👉 Убирайте только ненужные части

3️⃣ ИЗБЫТОЧНОСТЬ (удалите повторяющиеся условия)

Если есть несколько похожих описаний:

«Это описание не нужно
поскольку оно уже охвачено другим описанием?»

👉 Удалите дубликаты

Этот процесс РАСШИРЕНИЕ → СОКРАЩЕНИЕ → ОЧИСТКА
повторяется всего несколько раз до завершения.

Почему это быстро?

• ❌ Он не проверяет все возможные случаи
• ❌ Он не проверяет все комбинации
• ⭕ Он останавливается на «этого достаточно»

👉 Вычислительная сложность не взрывается

Итак, каков результат?

• Результат QM: Настоящая оптимизация
• Результат Espresso: 95% уровень оптимизации по сравнению с результатами QM

Практические причины использования Espresso на практике

• Способность обрабатывать от тысяч до десятков тысяч переменных
  • Способность обрабатывать от тысяч до десятков тысяч переменных
  • Подходит для PLA, логики управления и декодеров
  • Служит в качестве стратегии по умолчанию в инструментах EDA
• QM:
  «Я сравню каждый ответ на экзаменационные вопросы
  по одному
  , чтобы создать окончательный сводный документ»
• Espresso:
  «Сначала создайте одно резюме,
  затем удалите все ненужные предложения»
• QM:
  • Точный
  • Медленный
  • Обучающий
• Espresso:
  • Приблизительный
  • Быстрый
  • Промышленный стандарт
• «Почему многоуровневая оптимизация — это совершенно другой мир»
• «Почему инструменты синтеза намеренно нарушают правило двух уровней»
  и многое другое.
• SOP (сумма произведений)
• Формат PLA
• Выражения на основе таблицы истинности
• Уменьшение количества вентилей
• Уменьшение задержки
• Уменьшение энергопотребления
• PLA / ROM / LUT
• Улучшение качества после синтеза
• Каждый вентиль был дорогостоящим
• Поскольку PLA были основным методом реализации
• Не гарантирует точное оптимальное решение
• Вместо этого быстро находит очень хорошее приближение
• Расширить до максимально возможного импликанта
• Удалить ненужные литералы
• Удалить избыточные области
• Сократить ненужные оси покрытия
• Удалить избыточные литералы
• Удалить избыточные оси покрытия
• Удалить избыточные литералы
• Удалить избыточные оси покрытия
• Удалить избыточные литералы
• Удалить избыточные оси покрытия
• 2️⃣ Сократите
  • Удалите перекрывающиеся области
  • Сократите ненужное покрытие
  • Удалите ненужные термины
• Повторите это.
• То есть:
• Espresso:
  • Изменить логику
    MiniSat:
  • Найти значения, сохранив логику
• Это совершенно другая проблема.
• Рассмотрим традиционный поток:
• Сегодня:
  • Прямое использование самого Эспрессо сократилось, но
  • идеи и принципы остаются очень актуальными
• В частности:
  • Синтез на основе LUT
  • Логика управления
  • Микрокод / декодер
  • Академические инструменты CAD
• Он по-прежнему упоминается в этих контекстах.
• Espresso может быть старым, но его значение значительно.EC%9C%A0-1">Причина 1
• Бесчисленные статьи и инструменты оцениваются по следующему критерию:
  • «Насколько они лучше по сравнению с Espresso»
  • Точная оптимизация является NP-трудной задачей
  • Вместо этого хорошо разработанные эвристические методы предоставляют практические решения
• Этот подход:
  • Синтез
  • Размещение и трассировка
  • Оптимизация времени
  • Оптимизация мощности
• применима ко всем из них в равной степени.

Учебник эвристических алгоритмов CAD

Причина 2

Эталон для минимизации логики

7. Почему Espresso по-прежнему важен сегодня

Спецификация
   ↓ Таблица истинности / булева функция ↓ Эспрессо (минимизация логики) ↓ PLA / Логическая сеть ↓ Технологическое отображение 

6. Положение Espresso в потоке EDA-%EC%9C%84%EC%B9%98">6. Положение Espresso в потоке EDA

Именно здесь многие люди запутываются.

5. Отличия от SAT / MiniSat (важно)

Расширять → Сокращать → Уточнять

3️⃣ Избыточность

Espresso используется на практике, потому что-Практическое применение">Почему Espresso используется на практике

«Более быстрая подготовка к производству» важнее, чем
главное — это быстрое выведение на ленту»

Аналогия со школой (очень интуитивная)

👉 Если есть миллион экзаменационных работ,
QM умрет на полпути,
Espresso дойдет до конца

Основное резюме

В EDA важно не
«самая маленькая формула», а
«чип, который мы можем изготовить сейчас».

Вот почему Espresso победил.Далее мы можем рассмотреть:

2. Какие входные данные он получает?

Espresso обычно обрабатывает логику этой формы.Например, такая функция:

f(a,b,c) = Σ m(1,3,5,7)

Или в стиле PLA:

a b c | f ------ 0 0 1 | 1 0 1 1 | 1 1 0 1 | 1 1 1 1 | 1 

Он принимает это и выражает в виде меньшего количества слагаемых.

3. Почему «минимизация» важна?

Это не просто вопрос визуальной привлекательности.

Почему важна минимизация логики

Особенно в прошлом:Минимизация логики была вопросом выживания.

4. Как Espresso достигает минимизации? (Концепция)

Эспрессо:Основная идея состоит из трех шагов.

1️⃣ Расширить

2️⃣ Сократить

3️⃣ Удалить

4️⃣ Удалить

5️⃣ Удалить