述語（コンピュータアーキテクチャ）

コンピュータ アーキテクチャにおいて、述語は条件付き分岐マシン命令によって実装される条件付き制御転送の代替手段を提供する機能です。述語は、条件付き (述語付き) 非分岐命令を述語と関連付けることによって機能します。述語は、命令がアーキテクチャ状態を変更できるかどうかを制御するために使用されるブール値です。命令で指定された述語が true の場合、命令はアーキテクチャ状態を変更します。それ以外の場合、アーキテクチャ状態は変更されません。たとえば、述語付き移動命令 (条件付き移動) は、述語が true の場合にのみ宛先を変更します。したがって、分岐が発生するかどうかを制御する述語に基づいて実行する命令または命令シーケンスを選択するために条件分岐を使用する代わりに、実行される命令がその述語に関連付けられ、その述語が true か false かに基づいて命令が実行されるか、実行されないかが決まります。^[1]

ベクター プロセッサ、一部のSIMD ISA ( AVX2やAVX-512など)、およびGPU は一般に、条件マスク ベクターの 1 ビットを処理対象のベクトル レジスタの対応する要素に適用する述語を多用しますが、スカラー命令セットのスカラー述語では 1 つの述語ビットのみが必要です。述語マスクがベクター処理で特に強力になるのは、条件コード (ベクター要素ごとに 1 つ)の配列が述語マスクにフィードバックされ、それが後続のベクトル命令に適用される場合です 。

ほとんどのコンピュータ プログラムには条件付きコードが含まれており、これは事前に決定できない要因 (たとえば、ユーザー入力) に応じて特定の条件下でのみ実行されます。プロセッサの大部分はシーケンス内の次の命令を単純に実行するので、従来の解決策は、プログラムを条件付きで別のコード セクションに分岐させ、シーケンス内の次のステップを変更できるようにする分岐命令を挿入することです。設計者が命令パイプラインを実装してパフォーマンスを改善し始めるまでは、これで十分でした。パイプラインは分岐によって速度が低下します。発生した問題の詳細な説明と一般的な解決策については、「分岐予測」を参照してください。

幸いなことに、分岐に依存する一般的なコードパターンの1つには、よりエレガントな解決策があります。次の疑似コードを検討してください。^[1]

条件が満たされた場合{何かを行う}それ以外の場合{他の何かを行う} 
    

    

条件分岐を使用するシステムでは、これは次のような機械語命令に変換される可能性があります。 ^[1]

    branch_if_condition_to label1 do_something_else branch_always_to label2 label1 : do_something label2 : ... 
    
     

    

    

述語では、すべての可能な分岐パスがインラインでコード化されますが、一部の命令は実行されますが、他の命令は実行されません。基本的な考え方は、各命令が述語（述語論理での使用法と同様にここで使用される単語）に関連付けられており、述語が真の場合にのみ命令が実行されるというものです。上記の述語を使用した例のマシンコードは、次のようになります。^[1]

(条件)何かを行う(条件ではない)他に何かを行う     
  

分岐がなくなるだけでなく、アーキテクチャが述語付き命令を提供している場合は、必要なコードの総量が少なくなります。これによって一般に実行速度が速くなることは保証されませんが、コードのdo_somethingおよびdo_something_elseブロックが十分に短い 場合は実行速度が速くなります。

述語の最も単純な形式は部分述語であり、アーキテクチャには条件付き移動命令または条件付き選択命令があります。条件付き移動命令は、述語の値が真の場合にのみ、1 つのレジスタの内容を別のレジスタに書き込みますが、条件付き選択命令は、述語の値に基づいて 2 つのレジスタのうちのどちらの内容を 3 番目のレジスタに書き込むかを選択します。より一般化された高機能な形式は、完全述語です。完全述語には、述語を格納するための述語レジスタのセットがあり (これにより、複数のネストされた分岐または連続した分岐を同時に排除できます)、アーキテクチャのほとんどの命令には、どの述語レジスタが述語を提供するかを指定するためのレジスタ指定子フィールドがあります。^[2]

プレディケーションの主な目的は、プログラム コードの非常に小さなセクションを飛び越えるのを回避し、パイプライン実行の効率を高め、キャッシュの問題を回避することです。また、より微妙な利点もいくつかあります。

• 従来は単純な算術演算とビット演算を使用して計算されていた関数は、述語命令を使用すると計算が速くなる場合があります。
• 異なる述語を持つ述語命令は、互いに混在させたり、無条件コードと混在させたりできるため、命令のスケジュール設定が改善され、パフォーマンスがさらに向上します。
• 不要な分岐命令を排除することで、分岐予測メカニズムの負荷が軽減され、ループを構成する分岐などの必要な分岐の実行が高速化されます。
• 深くパイプライン化されたアーキテクチャでは高くなる可能性がある分岐予測ミスのコストを排除します。
• 命令によって生成される包括的な条件コードを持つ命令セットでは、条件レジスタを述語として直接使用することで、コード サイズをさらに削減できます。

プレディケーションの主な欠点は、エンコーディングスペースが増加することです。典型的な実装では、すべての命令は、その命令がどのような条件で効果を発揮するかを指定するためのプレディケート用のビットフィールドを予約します。組み込みデバイスのように利用可能なメモリが限られている場合、このスペースコストは法外なものになる可能性があります。ただし、 Thumb-2などの一部のアーキテクチャでは、この問題を回避できます（以下を参照）。その他の欠点は次のとおりです。^[3]

• プレディケーションは、クリティカルパスにロジックのレベルを追加することでハードウェアを複雑にし、クロック速度を低下させる可能性があります。
• 述語ブロックにはすべての操作のサイクルが含まれるため、パスが短いほど時間がかかり、ペナルティが課される可能性があります。
• 予測は通常は推測されず、より長い依存関係チェーンを引き起こします。順序付きデータの場合、予測可能な分岐と比較してパフォーマンスの低下につながります。^[4]

予測は、パスのバランスが取れている場合、または最長パスが最も頻繁に実行される場合に最も効果的ですが^{[3] 、}プロファイリング情報があっても、コンパイル時にそのようなパスを決定することは非常に困難です。

述語命令は、Mailüfterl ( 1955)、Zuse Z22 (1955)、ZEBRA (1958)、Electrologica X1 (1958) など、1950 年代のヨーロッパのコンピュータ設計で人気がありました。1967年のIBM ACS-1設計では、命令形式に「スキップ」ビットが割り当てられ、1976 年の CDC フレキシブル プロセッサでは、マイクロ命令形式に 3 つの条件付き実行ビットが割り当てられました。

Hewlett-PackardのPA-RISCアーキテクチャ (1986) には、ヌル化と呼ばれる機能があり、ほとんどの命令を前の命令によって述語化できました。IBMのPOWER アーキテクチャ( 1990) には条件付き移動命令がありました。POWER の後継であるPowerPC (1993) では、これらの命令は削除されました。Digital Equipment CorporationのAlphaアーキテクチャ (1992) にも条件付き移動命令がありました。MIPSは1994 年に MIPS IV バージョンで条件付き移動命令を獲得し、SPARC はバージョン 9 (1994) で整数レジスタと浮動小数点レジスタの両方に対する条件付き移動命令で拡張されました。

Hewlett-Packard / Intel IA-64アーキテクチャでは、ほとんどの命令が述語付きです。述語は 64 個の専用述語レジスタに格納され、述語レジスタの 1 つは常に true であるため、述語のない命令は単に値が true の述語付き命令になります。述語の使用は、IA-64 のソフトウェア パイプラインの実装に不可欠です。これは、プロローグとエピローグに別々のコードを記述する必要がなくなるためです。^{[説明が必要]}

x86アーキテクチャでは、条件付き移動命令のファミリ (CMOVおよび) がIntel Pentium ProFCMOV (1995) プロセッサによってアーキテクチャに追加されました。これらの命令は、フラグ レジスタの値によって提供される述語に応じて、ソース レジスタの内容を宛先レジスタにコピーします 。 CMOV

ARM アーキテクチャでは、オリジナルの 32 ビット命令セットが条件付き実行と呼ばれる機能を提供します。この機能により、ほとんどの命令は、前の命令によって設定された 4 つの条件コードの組み合わせに基づく 13 の述語のうちの 1 つによって述語化されます。ARM のThumb命令セット (1994) では、命令のサイズを 16 ビットに収めるために条件付き実行が削除されましたが、その後継のThumb-2 (2003) では、後続の 4 つの命令に述語を提供する以外の効果を持たない特別な命令を使用することでこの問題を解決しました。ARMv8-A (2011) で導入された 64 ビット命令セットでは、条件付き実行が条件付き選択命令に置き換えられました。

AVX2 などの一部のSIMD命令セットには、条件付き移動の並列形式である論理マスクを使用して値を条件付きでメモリにロード/保存する機能があり、並列操作を実行する個々の演算ユニットに個別のマスク ビットを適用することもできます。この手法は、Flynn の分類法では「連想処理」として知られています。

この形式の予測は、ベクター プロセッサや単一命令、複数スレッドのGPU コンピューティングでも使用されます。単一スカラー予測のすべての手法、利点、および欠点は、並列処理の場合にも同様に当てはまります。

• クレメンツ、アラン (2013)。「8.3.7 述語」。コンピュータの構成とアーキテクチャ: テーマとバリエーション。Cengage Learning。pp. 532–9。ISBN 978-1-285-41542-0。