Алгоритмы для оптимизации конъюнктивных выражений нормальной формы для конкретных наборов команд?
Я использую минимизатор логики Эспрессо для создания минимизированной формы набора булевых уравнений. Однако вместо того, чтобы генерировать логику для программируемой логики массива (для которой обычно используется Espresso), я собираюсь реализовать ее на стандартном микропроцессоре. Проблема в том, что Espresso выдает выходные данные в нормальной форме, что идеально для PAL, но не оптимально для x86 или PPC.
Например, Espresso полностью игнорирует XOR - в приведенном ниже выводе Espresso подвыражение (!B0&!B1&B2&!B3) | (!B0&!B1&!B2&B3) эквивалентно (!B0&!B1&(B2^B3)), Эта замена действительно увеличивает глубину шлюза / критический путь выражения, но, учитывая, что я смотрю на выражения с достаточным количеством терминов, чтобы полностью насытить ресурсы выполнения любого ЦП, кажется разумным обменять некоторую глубину шлюза на уменьшение общее количество инструкций. Я также хотел бы расширить его, чтобы понять, как использовать инструкции, такие как ANDC или NOR, которые доступны на некоторых процессорах, которые мне интересны.
Пример выражений CNF, на которые я смотрю:
O0 = (B0&!B1&!B2&B3) | (!B0&B1&B2&B3) | (!B0&!B1&B2&B3) | (B1&!B3) | (!B0 &!B2&!B3);
O1 = (B0&B1&!B2&B3) | (B0&!B1&B2&!B3) | (B0&B1&B2&!B3) | (!B0&!B1&B2&!B3) | (!B0&!B1&!B2&B3) | (!B0&!B1&B2&B3) | (!B0&!B2&!B3);
O2 = (B0&!B1&!B2&B3) | (B0&!B1&B2&!B3) | (B0&B1&B2&B3) | (!B0&B1&!B3) | (!B0&!B2&B3) | (!B0&!B1&B2&B3);
O3 = (!B0&B1&!B2&!B3) | (B0&B1&B2&B3) | (!B0&B1&B2&B3) | (B0&B1&B2&!B3) | (B0&!B1&!B2) | (!B0&!B1&B2&!B3) | (!B0&!B1&!B2&B3);
Итак, чтобы сделать это актуальным вопросом; в порядке предпочтения:
Знаете ли вы вариант или расширение Espresso, которое будет производить выражения, которые я хочу?
Знаете ли вы какой-либо инструмент минимизации булевой логики, который понимает (или может научить) различные типы шлюзов, а не только создает CNF для PAL?
Вам известен алгоритм преобразования из выражений CNF, подобных приведенным выше, в выражения с использованием дополнительных типов элементов?
Если вы не знаете алгоритм для этого, знаете ли вы или можете придумать какие-нибудь полезные эвристики для этого?
(И на всякий случай, если вы собираетесь это предложить - тестирование показывает, что GCC и ICC (или, я бы поспорил, любой другой существующий компилятор C) не достаточно умны, чтобы выполнить для меня специфическую для процессора минимизацию из выражений CNF - это было бы действительно здорово, но проверка вывода -O3 -S для обоих показывает, что они не могут даже поймать случаи, когда XOR может использоваться).
2 ответа
Наиболее известным алгоритмом минимизации булевых формул является алгоритм Куайна-МакКласки, который дает наименьшую формулу DNF, но требует больших вычислительных ресурсов (обязательно, поскольку проблема не в PTIME, см . Сложность минимизации булевых формул, 2007 г.). Есть грамотная реализация Java; основная концепция имеет решающее значение для Пролога, поэтому, если у вас есть опыт работы с Прологом, идея должна прийти достаточно легко.
Постскриптум Есть статья с платформой IEEE, Расширяющая Куайн-МакКласки для эксклюзивного или логического синтеза, аннотация:
Различные формы булевой минимизации были использованы в электронном инженерном образовании в качестве ключевой части учебной программы. Как правило, карты Карно и методы Куайна-МакКласки являются основными исчерпывающими методами поиска для цифровой минимизации на уровне бакалавриата, поскольку они просты в использовании и просты для понимания. Несмотря на популярность этих методов, они не очень подходят для типичных цифровых схем. Простыми примерами таких схем являются четность, сумматоры, генераторы серого кода и так далее. Общим фактором среди них является логический элемент Exclusive-Or. Эта проблема усугубляется растущей важностью Exclusive-Or в современном дизайне. В этой статье предлагается расширение метода Куайна-МакКласки, который успешно включает элементы Exclusive-Or в процесс минимизации. Ряд примеров приведен для демонстрации эффективности этого подхода. Эту технику легко освоить, так как ее можно рассматривать как расширение метода Куайна-МакКласки.
Я думал о том, как расширить метод, прежде чем я посмотрел это: вы должны быть в состоянии синтезировать приложения XOR, используя альтернативную версию разрешения, которая соответствует им. Например, для дизъюнктивного предложения F в CNF, который не содержит ни одного из атомов A, или же Bиз пунктов F | A | ~B а также F | ~A | Bтогда вы можете заменить их на F | XOR(A,B),
1) Рассматривали ли вы использование Superoptimization для выбора последовательности команд для вас?
Например, супероптимизатор GNU производит чрезвычайно короткие последовательности команд, которые вычисляют эквивалент функции, которую вы ему предоставляете. В вашем случае вы бы предоставили функцию, реализующую булево уравнение интереса.
Эти инструменты часто работают, перечисляя пространство возможных вычислений, начиная с наименьшего, и решая, соответствует ли отдельное вычисление вашей вычислительной цели. Они не могут обязательно предоставить решения (не говоря уже о оптимальных) для очень сложных инструкций, но если небольшое количество инструкций будет успешным, они часто находят (необычно!) И очень эффективную последовательность. XOR/NOR/ANDC легко входит в область действия супероптимизатора GNU.
2) Вы можете попробовать использовать алгебраический упрощитель, снабженный правильным набором алгебраических эквивалентностей. Мы использовали наш DMS Software Reengineering Toolkit, механизм преобразования программ, который принимает произвольные правила перезаписи и понимает коммутативные и ассоциативные законы, для реализации логических упрощателей, которые включают различные операторы, такие как XOR и NOR. Вам понадобится применение правила, алгоритм восхождения на гору (восхождение на гору с наименьшим количеством операторов) и алгоритм возврата. С помощью итеративного углубленного поиска в глубину вы можете найти оптимальное решение, если выражение не слишком сложное; с помощью поиска по ветвям и привязкам вы можете быстро найти решение, а затем попытаться минимизировать его размер. У вас даже есть относительно хорошая эвристическая мера: операнды до сих пор не включены в вычисления. Самая большая проблема с эквациональным упрощением заключается в том, что он не будет учитывать ограничения регистра или возможности, доступные в вашем конкретном наборе инструкций.
3) Вы можете реализовать свой собственный поиск (итеративное углубление, ветвление и связывание) по доступным вам наборам логических инструкций и включить ограничения. (Это возвращает нас к тому, что делают суперопероптимизаторы). Я сделал это, чтобы вычислить минимальные последовательности инструкций для реализации умножения на константу в x86, учитывая до 3 регистров и используя преимущества трех операндных инструкций, таких как (эффективный адрес загрузки) LEA X,[Y+K*Z] на регистрах X, Y, Z с константой K=1,2,4,8, ADD X,Y, SUB X,Y, MOV и NEG. Если вы кодируете это как рекурсивную программу на любом приемлемом языке, вы можете написать одну из нескольких сотен строк. (Это производит некоторые действительно короткие последовательности).