6

Espresso ロジック ミニマイザーを使用して、一連のブール方程式の最小化された形式を生成しています。ただし、プログラマブル アレイ ロジック (Espresso が通常使用されるもの) のロジックを生成するのではなく、これらを標準のマイクロプロセッサに実装することを検討しています。問題は、Espresso が結合正規形で出力を生成することです。これは PAL には最適ですが、x86 または PPC には最適ではありません。

たとえば、Espresso は XOR を完全に無視します。以下の Espresso 出力では、部分式(!B0&!B1&B2&!B3) | (!B0&!B1&!B2&B3)は と同等(!B0&!B1&(B2^B3))です。この置換により、式のゲート深度/クリティカル パスが増加しますが、周囲の任意の CPU の実行リソースを完全に飽和させるのに十分な数の項を含む式を見ていることを考えると、ゲート深度を減らすためにゲート深度をトレードオフすることが合理的であるように思われます。全体の命令数。また、関心のある一部のプロセッサで利用可能な 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 のオプションまたは拡張機能を知っていますか?

PALのCNFを生成するだけでなく、さまざまなゲートタイプを理解する（または教えることができる）ブール論理最小化のためのツールを知っていますか？

上記のような CNF 式から、追加のタイプのゲートを使用した式に変換するアルゴリズムを知っていますか?

そのためのアルゴリズムを知らない場合、これを行う際に役立つヒューリスティックを知っていますか、または考えることができますか?

（そして、あなたがそれを提案しようとしていた場合に備えて-テストでは、GCCとICC（または、存在する他のCコンパイラー）は、CNF式からプロセッサー固有の最小化を行うほど賢くないことが示されています-それは本当に素晴らしいことですが、両方の -O3 -S の出力を調べると、XOR を使用できるケースをキャッチすることさえできないことがわかります)。

4

2 に答える 2

6

ブール式の最小化で最もよく知られているアルゴリズムはQuine-McCluskeyアルゴリズムです。これは、最小のDNF式を生成しますが、計算コストが高くなります（問題は、PTIMEの範囲外であるため、必然的に、ブール式の最小化の複雑さ、2007を参照）。読み書きのできるJava実装があります; 基本的な概念はPrologにとって非常に重要であるため、Prologの経験があれば、アイデアは簡単に思い浮かぶはずです。

追記IEEE-paywalledの記事、Extending Quine-McCluskey for Exclusive-または論理合成、要約があります：

シラバスの重要な部分として、電子工学の学位内でさまざまな形式のブール最小化が使用されてきました。通常、カルノー図とクワイン・マクラスキー法は、使いやすく理解しやすいため、学部レベルでのデジタル最小化のための主要な全数検索手法です。これらの方法は人気がありますが、一般的なデジタル回路にはあまり適していません。このような回路の簡単な例は、パリティ、加算器、グレイコードジェネレータなどです。これらに共通する要素は、排他的論理和論理ゲートです。この問題は、現代の設計における排他的論理和の重要性の高まりによって悪化しています。この論文では、最小化プロセス内に排他的論理和ゲートをうまく組み込むQuine-McCluskey法の拡張を提案します。このアプローチの有効性を示すために、いくつかの例が示されています。この手法は、Quine-McCluskey法の拡張と見なすことができるため、習得が容易です。

これを調べる前に、メソッドを拡張する方法を考えていました。XORのアプリケーションに対応する代替バージョンの解像度を使用することで、それらのアプリケーションを合成できるはずです。たとえば、CNFの論理和句の場合、句とのアトム、または、Fのいずれも含まない場合は、それらを。に置き換えることができます。ABF | A | ~BF | ~A | BF | XOR(A,B)

于 2009-12-14T10:21:48.800 に答える
3

1）スーパーオプティマイゼーションを使用して命令シーケンスを選択することを検討しましたか？

例として、GNUスーパーオプティマイザーは、提供する関数に相当するものを計算する非常に短い命令シーケンスを作成します。あなたの場合、あなたは興味のあるブール方程式を実装する関数を提供するでしょう。

これらのツールは、多くの場合、可能な計算のスペースを最小のものから列挙し、個々の計算が計算目標に一致するかどうかを判断することによって動作します。非常に複雑な命令の解決策（最適なものは言うまでもなく）を必ずしも提供できるわけではありませんが、適度な数の命令が成功した場合、（異常な！）非常に効率的なシーケンスが見つかることがよくあります。XOR / NOR / ANDCは、GNUスーパーオプティマイザーの範囲内に簡単に収まります。

2）適切な代数等価のセットを備えた代数単純化器を使用してみてください。DMSソフトウェアリエンジニアリングツールキットを使用しました、任意の書き換えルールを受け入れ、可換法則と結合法則を理解して、XORやNORなどのさまざまな演算子を含むブール単純化子を実装するプログラム変換エンジン。ルールアプライヤー、山登りアルゴリズム（オペレーターの数が最も少ない山登り）、およびバックトラッキングアルゴリズムが必要です。深さ優先の反復深化検索を使用すると、式がそれほど複雑でない場合に最適なソリューションを見つけることができます。分枝限定法検索を使用すると、解決策をすばやく見つけて、そのサイズを最小化することができます。比較的優れたヒューリスティックな尺度もあります。これまでのところ、オペランドは計算に含まれていません。等式シンプリファイアの最大の問題は、特定の命令セットで利用可能なレジスタの制約や機会が考慮されないことです。

3）使用可能なブール命令のセットに対して独自の検索（反復深化、分枝限定）を実装し、制約を含めることができます。（これは、スーパーオペラオプティマイザーの機能にいくらか戻ってきています）。これは、x86に定数による乗算を実装するための命令の最小シーケンスを計算するために行い、最大3つのレジスタを考慮し、（有効アドレスのロード）LEA X、[Y +K*などの3オペランド命令を利用します。 Z]レジスタX、Y、Zで、定数K = 1,2,4,8、ADD X、Y、SUB X、Y、MOV、およびNEG命令を使用します。これを任意の妥当な言語で再帰プログラムとしてコーディングすると、数百行で1つコーディングできます。（それはいくつかの本当にsquirrelyシーケンスを生成します）。

于 2009-11-04T03:13:37.750 に答える