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

コンピュータアーキテクチャにおいて、述語は条件分岐マシン命令によって実装される条件付き制御転送の代替手段を提供する機能です。述語は、条件付き（述語付き）非分岐命令を述語（命令がアーキテクチャ状態を変更することを許可するかどうかを制御するために命令が使用するブール値）に関連付けることによって機能します。命令で指定された述語が真の場合、命令はアーキテクチャ状態を変更します。そうでない場合、アーキテクチャ状態は変更されません。たとえば、述語付き移動命令（条件付き移動）は、述語が真の場合にのみ宛先を変更します。したがって、分岐が発生するかどうかを制御する述語に基づいて実行する命令または命令シーケンスを選択するために条件付き分岐を使用する代わりに、実行される命令はその述語に関連付けられ、その述語が真か偽かに基づいて実行されるか実行されないかが決まります。^{[ 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が十分に短ければ高速化につながります。

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

述語化の主な目的は、プログラムコードのごく小さな部分を飛び越える処理を回避し、パイプライン実行の効率を高め、キャッシュの問題を回避することです。また、他にもいくつかの微妙な利点があります。

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

述語の主な欠点は、エンコード領域が増加することです。一般的な実装では、すべての命令が、その命令がどのような条件下で効果を発揮するかを指定する述語のためにビットフィールドを予約します。組み込みデバイスのように利用可能なメモリが限られている場合、この領域コストは許容範囲を超える可能性があります。ただし、 Thumb-2などの一部のアーキテクチャでは、この問題を回避できます (下記参照)。その他の欠点は次のとおりです。^{[ 3 ]}

• 予測処理は、クリティカルパスにロジック層を追加することでハードウェアを複雑化させ、クロック速度を低下させる可能性がある。
• 述語ブロックにはすべての操作のサイクルが含まれるため、より短いパスでも時間がかかり、ペナルティが課される可能性があります。
• 追加のレジスタ読み取りが必要になります。述語なしのADD命令はレジスタファイルから2つのレジスタを読み取りますが、述語付きADD命令は述語レジスタファイルも読み取る必要があります。これにより、アウトオブオーダー実行時のハザードが増加します。
• 予測は通常推測されず、より長い依存関係チェーンを引き起こします。順序付きデータの場合、これは予測可能なブランチと比較してパフォーマンスの低下につながります。^{[ 4 ]}

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

述語付き命令は、Mailüfterl（1955年）、Zuse Z22（1955年）、ZEBRA（1958年）、Electrologica X1（1958年）など、1950年代のヨーロッパのコンピュータ設計で広く用いられた。 1967年のIBM ACS-1設計では、命令フォーマットに「スキップ」ビットが割り当てられ、1976年のCDC Flexible Processorでは、マイクロ命令フォーマットに3つの条件付き実行ビットが割り当てられていた。

ヒューレット・パッカードのPA-RISCアーキテクチャ (1986 年) にはヌル化と呼ばれる機能があり、ほとんどの命令を前の命令で述語化できるようにしていました。IBMのPOWER アーキテクチャ(1990 年) には条件付き移動命令がありました。 POWER の後継であるPowerPC (1993 年) ではこれらの命令が削除されました。デジタル・イクイップメント・コーポレーションのAlphaアーキテクチャ (1992 年) にも条件付き移動命令がありました。MIPS は1994 年に MIPS IV バージョンで条件付き移動命令を獲得し、SPARC はバージョン 9 (1994 年) で整数レジスタと浮動小数点レジスタの両方で条件付き移動命令が追加されました。RISC-V は当初述語化機能を持っていませんでしたが、非特権 ISA のバージョン 2.0 で条件付きゼロ化命令を含む拡張機能 (Zicond) により述語化機能を獲得し、条件付き算術と選択を合成できるようになりました。

ヒューレット・パッカード／インテルのIA-64アーキテクチャでは、ほとんどの命令に述語が付けられます。述語は64個の専用述語レジスタに格納され、そのうちの1つは常に真となるため、述語のない命令は単に真という値で述語が付けられた命令となります。述語の使用は、プロローグとエピローグのコードを別々に記述する必要性をなくすため、IA-64のソフトウェアパイプライン処理の実装において不可欠です。

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

ARMアーキテクチャでは、オリジナルの32ビット命令セットには条件付き実行と呼ばれる機能があり、ほとんどの命令は、前の命令によって設定された4つの条件コードの組み合わせに基づく13個の述語のいずれかによって述語付けされます。ARMのThumb命令セット（1994年）は、命令のサイズを16ビットに収まるように縮小するために条件付き実行を廃止しましたが、後継のThumb-2（2003年）は、後続の4つの命令に述語を提供する以外に効果のない特殊命令を使用することでこの問題を克服しました。ARMv8-A（2011年）で導入された64ビット命令セットは、条件付き実行を条件付き選択命令に置き換えました。

AVX2などの一部のSIMDレジスタ内（SWAR）命令セットは、論理マスクを使用して、条件付き移動の並列形式で、値をメモリに条件付きでロード/ストアする機能を備えています。また、並列演算を実行する個々の演算ユニットに個別のマスクビットを適用することもできます。SWARレジスタの各サブワード、または各ロード/ストア値に対して、1つの述語マスクビットが利用可能です。この形式のマルチビット述語は、ベクトルプロセッサの要素レベル（SWARサブワードと同義）でも使用されています。

SWAR (またはベクトル)の各(サブワードi )に対して、(条件マスクビットi )を登録し、(サブワードi )に対して何かを実行し、(条件マスクビットiでない場合)に対して別の何かを実行します。

マスキングは、 ILLIAC IVなどのアレイプロセッサの不可欠な部分です。アレイプロセッサは現在、単一命令複数スレッド（SIMT）として知られており、各処理要素（ PE）ごとに述語ビットがあり、これを使用して各処理要素をアクティブ化または非アクティブ化します。PEにレジスタ命令内にSIMDがない場合、各PEは個別に述語化できます。

各( PE j ) // 非 SWAR 同期並行配列( active - maskbit j )に対してbroadcast_scalar_instruction_to ( PE j )

最新のSIMT GPUは、（または以前は使用されていましたが、ILLIAC IVのドキュメントでは「分岐」と呼ばれていました）述語を使用して、個々の処理要素を有効/無効にし、さらに、任意のPEのSWAR ALU内のサブワードをマスクアウトします。

SIMT同期並行配列の各( PE j )について(アクティブマスクビットj ) { //アクティブなSWAR PEにのみブロードキャストするSWARレジスタの各(サブワードi )について( PE j ) (条件マスクビットi ) do_something (サブワードi ) (条件マスクビットi以外) do_something_else (サブワードi ) }

単一スカラー述語のすべての技術、利点、欠点は、分岐に関連する問題がはるかに複雑になる並列処理の場合にも同様に当てはまります。^{[ 5 ]}

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