Алгоритмы для оптимизации соединительных выражений нормальной формы для конкретных систем команд?
можно использовать веб-сервис для обнаружения мобильного просмотра как handsetdetection.com.
2 ответа
Наиболее известным алгоритмом минимизации булевых формул является алгоритм Куайна-МакКласки, который дает наименьшую формулу DNF, но требует больших вычислительных ресурсов (обязательно, поскольку проблема находится вне PTIME, см. Сложность минимизации булевой формулы, 2007 ). Есть грамотная реализация Java ; базовая концепция имеет решающее значение для Prolog, поэтому, если у вас есть какой-либо опыт работы с Prolog, идея должна прийти достаточно легко.
Postscript Есть статья, оплачиваемая IEEE, Расширение Quine-McCluskey для логики исключающего ИЛИ синтез , аннотация:
Различные формы булевой минимизации использовались в дипломах электронной инженерии как ключевая часть учебной программы. Обычно Карты Карно и методы Куайна-МакКласки являются основными методами исчерпывающего поиска для цифровой минимизации на уровне бакалавриата, поскольку они просты в использовании и понятны. Несмотря на популярность этих методов, они плохо подходят для типичных цифровых схем. Простыми примерами таких схем являются четность, сумматоры, генераторы кода Грея и так далее. Общим фактором среди них является логический вентиль Исключающее ИЛИ. Эта проблема усугубляется возрастающим значением Exclusive-Or в современном дизайне. В этой статье предлагается расширение метода Куайна-Маккласки, которое успешно включает вентили исключающего ИЛИ в процесс минимизации. Приводится ряд примеров, демонстрирующих эффективность этого подхода. Эту технику легко освоить, поскольку ее можно рассматривать как расширение метода Куайна-Маккласки.
Я думал о том, как расширить этот метод, прежде чем нашел это: вы должны быть в состоянии синтезировать приложения XOR. с помощью альтернативной версии разрешения, соответствующей им. Например, для дизъюнктивного предложения F в CNF, которое не содержит ни одного из атомов A , или B , из предложений F | А | ~ B и F | ~ A | B , то вы можете заменить их на F | XOR (A, B) .
F в CNF, которое не содержит ни атомов A , ни B , из предложений F | А | ~ B и F | ~ A | B , то вы можете заменить их на F | XOR (A, B) . для дизъюнктивного предложения F в CNF, которое не содержит ни атомов A , ни B , из предложений F | А | ~ B и F | ~ A | B , то вы можете заменить их на F | XOR (A, B) . 1) Рассматривали ли вы возможность использования Супероптимизации для выбора последовательности инструкций за вас?
Например, супероптимизатор GNU производит чрезвычайно короткие последовательности инструкций, которые будут вычислять эквивалент функции, которую вы ему предоставляете. В вашем случае вы должны предоставить функцию, реализующую интересующее логическое уравнение.
Эти инструменты часто работают, перечисляя пространство возможных вычислений, начиная с наименьшего, и решая, соответствует ли отдельное вычисление вашей вычислительной цели. Они не могут обязательно предоставить решения (не говоря уже об оптимальных) для очень сложных инструкций, но если небольшое количество инструкций будет успешным, они часто находят (необычно!) и очень четкая последовательность. XOR / NOR / ANDC легко попали бы в область супероптимизатора GNU.
2) Вы можете попробовать использовать алгебраический упрощитель, снабженный правильным набором алгебраических эквивалентностей. Мы использовали наш DMS Software Reengineering Toolkit , механизм преобразования программ, который принимает произвольные правила перезаписи и понимает коммутативные и ассоциативные законы, для реализации логических упрощителей, которые включают различные операторы, такие как XOR и NOR. Вам понадобится приложение, применяющее правила, и алгоритм восхождения на холм (восхождение на холм с наименьшим числом операторов) и алгоритм обратного отслеживания. С помощью итеративного углубленного поиска с приоритетом в глубину вы можете найти оптимальное решение, если выражение не слишком сложное; с поиском по ветке и по границе, вы можете быстро найти решение, а затем попытаться минимизировать его размер. У вас даже есть относительно хорошая геристическая мера: операнды пока не включаются в вычисления. Самая большая проблема с уравнительным упрощением заключается в том, что он не принимает во внимание ограничения регистров или возможности, доступные с вашим конкретным набором инструкций.
3) Вы можете реализовать свой собственный поиск (итеративное углубление, ветвление и граница) по наборам доступных вам булевых инструкций и включают ограничения. (Это немного похоже на то, что делают суперопероптимизаторы). Я сделал это, чтобы вычислить минимальные последовательности инструкций для реализации умножения на константу на x86, учитывая до 3 регистров и используя преимущества инструкций с 3 операндами, таких как (загрузить эффективный адрес) LEA X, [Y + K * Z] в регистрах X, Y, Z с константой K = 1,2,4,8, ADD X, Y, SUB X, Y, MOV и NEG. Если вы запрограммируете это как рекурсивную программу на любом разумном языке, вы можете код один из нескольких сотен строк. (Он производит некоторые действительно короткие последовательности).