記憶の曖昧さ解消

メモリの曖昧さ解消は、メモリアクセス命令(ロードおよびストア) をプログラム順序どおりに実行しない高性能アウトオブオーダー実行 マイクロプロセッサによって使用される一連の技術です。マイクロプロセッサ コア内のデジタル ロジックを使用して実装されるメモリの曖昧さ解消を実行するメカニズムは、実行時にメモリ操作間の真の依存関係を検出し、依存関係が侵害されたときにプロセッサが回復できるようにします。また、ロードおよびストアの安全なアウトオブオーダー実行を可能にすることで、不必要なメモリ依存関係を排除し、命令レベルの並列性を高めます。

命令を順不同で実行しようとする場合、マイクロプロセッサは命令間の真の依存関係を尊重する必要があります。たとえば、単純な真の依存関係を考えてみましょう。

1: $1、$2、$3 を加算します # R1 <= R2 + R3
2: $5、$1、$4 を追加 # R5 <= R1 + R4 (1 に依存)

この例では、レジスタR1 が行 2 の加算演算のソースオペランドaddであるため、行 2 の命令は行add1 の命令に依存しています。行 2 は行 1 が完了するまで実行できません。この場合、ソースと宛先がレジスタであるため、依存関係は静的であり、マイクロプロセッサによって簡単に判断できます。行 1 の命令の宛先レジスタ( ) は命令のエンコードの一部であるため、パイプラインのデコード ステージ中にマイクロプロセッサによって早い段階で判断できます。同様に、行 2 の命令のソース レジスタ(および) も命令自体にエンコードされており、デコード時に判断されます。この真の依存関係を尊重するために、マイクロプロセッサのスケジューラ ロジックはこれらの命令を正しい順序 (最初に命令 1、次に命令 2) で発行し、命令 2 で必要なときに命令 1 の結果が使用できるようにします。 addaddaddR1addR1R4

依存関係が静的に決定できない場合、複雑な問題が発生します。このような非静的依存関係は、オペランドの位置が命令エンコーディング自体で直接指定されるのではなく、レジスタ オペランドとして間接的に指定される可能性があるため、メモリ命令 (ロードおよびストア) で発生します。

1: $1、2($2) を保存 # Mem[R2+2] <= R1
2: $3、4($4) をロードします。# R3 <= Mem[R4+4] (1 に依存する可能性があり、上記と同じアドレスである可能性もあります)

ここで、ストア命令はアドレス (R2+2) の値で指定されたメモリ位置に値を書き込み、ロード命令はアドレス (R4+4) の値で指定されたメモリ位置の値を読み取ります。マイクロプロセッサは、これらの 2 つの命令で指定されたメモリ位置が異なるか、同じ位置であるかを実行前に静的に判断することはできません。これは、位置が R2 と R4 の値に依存しているためです。位置が異なる場合、命令は独立しており、順不同で正常に実行できます。ただし、位置が同じ場合、ロード命令は値を生成するためにストアに依存します。これは、あいまいな依存関係として知られています。

ロードとストアを順不同で実行すると、依存するロード/ストア ペアが順不同で実行された場合に、誤った結果が生成されることがあります。MIPS アセンブリで示されている次のコード スニペットを検討して ください。

1: マルチ $27、$27、$20
2: sw $27, 0($30)
3: lw $08, 0($31)
4: sw $26, 0($30)
5: lw $09, 0($31)

スケジューリング ロジックは、すべてのレジスタ オペランドの準備が整ったときに実行ユニットに命令を発行すると仮定します。さらに、レジスタ$30とが$31準備完了であると仮定します。レジスタとの値は$30かなり$31前に計算されており、変更されていません。ただし、レジスタは$27準備完了ではないと仮定します。レジスタの値はまだ命令によって計算中です。最後に、レジスタとが同じ値を保持しているとmul仮定します。したがって、スニペット内のすべてのロードとストアは同じメモリ ワードにアクセスします。 $30$31

この状況では、sw $27, 0($30)2 行目の命令はまだ実行準備ができていませんが、lw $08, 0($31)3 行目の命令は準備ができています。プロセッサがlwの前に命令の実行を許可するとsw、ロードはメモリ システムから古い値を読み取りますが、 によってそこに書き込まれたばかりの値を読み取る必要がありますsw。ロードとストアはプログラム順序どおりに実行されませんでしたが、それらの間には違反されたメモリ依存関係がありました。

同様に、レジスタが準備完了$26 であると仮定します。4sw $26, 0($30)行目の命令も実行準備完了であり、lw $08, 0($31)3 行目の命令より先に実行される可能性があります。これが発生すると、ロードが実行される前に、後のストア命令がそこに値を書き込むため、lw $08, 0($31)命令はメモリ システムから間違った値を読み取ります。

メモリ依存関係には次の 3 種類があります。

• 書き込み後読み取り(RAW) 依存関係: 真の依存関係とも呼ばれる RAW 依存関係は、ロード操作が、同じアドレスへの最新のストア操作によって生成されたメモリから値を読み取るときに発生します。
• 書き込み後読み取り(WAR) 依存関係: 反依存関係とも呼ばれる WAR 依存関係は、ストア操作によって、先行するロードによって読み取られたメモリに値が書き込まれるときに発生します。
• 書き込み後書き込み(WAW) 依存関係: 出力依存関係とも呼ばれる WAW 依存関係は、2 つのストア操作が同じメモリ アドレスに値を書き込むときに発生します。

3 つの依存関係は、前述のコード セグメントに示されています (わかりやすくするために再現されています)。

1: 27ドル、20ドルを割ります
2: sw $27, 0($30)
3: lw $08, 0($31)
4: sw $26, 0($30)
5: lw $09, 0($31)

• 3 行目の命令は 2 行目の命令lw $08, 0($31)に RAW 依存関係がありsw $27, 0($30)、lw $09, 0($31)5 行目の命令は 4 行目の命令に RAW 依存関係がありますsw $26, 0($30)。両方のロード命令は、前のストアが書き込んだメモリ アドレスを読み取ります。ストアはそのメモリ アドレスへの最新のプロデューサーであり、ロードはそのメモリ アドレスの値を読み取っています。
• 4 行目の命令は、前のロードが読み取るメモリ アドレスを書き込むため、3 行目の命令sw $26, 0($30)に対して WAR 依存関係があります。lw $08, 0($31)
• 両方のストアが同じメモリ アドレスに書き込むため、4 行目の命令は 2 行目の命令に対してsw $26, 0($30)WAW 依存関係を持ちます。sw $27, 0($30)

現代のマイクロプロセッサは、ハードウェアに実装された次のメカニズムを使用して、あいまいな依存関係を解決し、依存関係に違反したときに回復します。

ストア命令からの値は、実行時にメモリ システム (最新のマイクロプロセッサではCPU キャッシュ) にコミットされません。代わりに、メモリ アドレスとストア データを含むストア命令は、リタイア ポイントに到達するまでストアキューにバッファリングされます。ストアがリタイアすると、その値がメモリ システムに書き込まれます。これにより、上記のコード スニペットに示されている WAR および WAW の依存関係の問題 (前のロードの前に後のストアの実行が許可されたために、前のロードがメモリ システムから誤った値を受け取る) が回避されます。

さらに、ストアをリタイアするまでバッファリングすることで、プロセッサは、例外を生成する可能性のある命令(不正なアドレスのロード、ゼロ除算など) または方向 (実行されるか実行されないか) がまだ不明な条件付き分岐命令に続くストア命令を投機的に実行できます。例外を生成する命令が実行されていない場合、または分岐方向が誤って予測された場合、プロセッサは「間違ったパス」で命令をフェッチして実行します。これらの命令はまったく実行されるべきではありません。例外条件は、投機的命令のいずれかが実行される前に発生するか、分岐が反対方向に進み、別の命令がフェッチされて実行される必要があります。プロセッサは、例外または分岐の誤予測を検出すると、不正なパスの投機的に実行された命令からのすべての結果を「破棄」する必要があります。ストアの場合、不正なパスまたは誤予測されたパスにあるストアは、その値をメモリ システムにコミットすべきではないという点が複雑です。ストアが値をコミットした場合、そのコミットを「破棄」することは不可能となり、実行されるべきではなかったストア命令のデータによってマシンのメモリ状態が破損することになります。

したがって、ストア バッファリングがなければ、例外の原因となる可能性のある以前のすべての命令が実行され (例外は発生せず)、以前のすべての分岐方向が判明するまで、ストアは実行できません。分岐方向と例外が判明するまでストアを強制的に待機させることで、アウトオブオーダーの積極性が大幅に低下し、ILP (命令レベルの並列性) とパフォーマンスが制限されます。ストア バッファリングを使用すると、ストアは例外の原因となる分岐命令や未解決の分岐命令よりも先に実行され、そのデータはストア キューにバッファリングされますが、値はリタイアするまでコミットされません。これにより、予測ミスや不正なパスにあるストアが値をメモリ システムにコミットするのを防ぎながら、ストアの完全なアウトオブオーダー実行による ILP とパフォーマンスの向上を実現できます。

ストアをリタイアするまでバッファリングすると、WAW と WAR の依存関係は回避されますが、新しい問題が発生します。次のシナリオを考えてみましょう。ストアが実行され、そのアドレスとデータがストア キューにバッファリングされます。数命令後に、ストアが書き込んだのと同じメモリ アドレスから読み取るロードが実行されます。ロードがメモリ システムからデータを読み取ると、前のストアによって上書きされた古い値が読み取られます。ロードによって取得されたデータは不正確になります。

この問題を解決するために、プロセッサはストア キューを使用したスト​​アからロードへの転送と呼ばれる手法を採用しています。ストアをリタイアするまでバッファリングすることに加えて、ストア キューは、完了しているがまだリタイアしていない (「インフライト」) ストアから後のロードにデータを転送するという 2 番目の目的も果たします。ストア キューは単純なFIFOキューではなく、実際にはメモリ アドレスを使用して検索されるコンテンツ アドレス可能メモリ (CAM)です。ロードが実行されると、ストア キューで、プログラム順序で論理的に前の同じアドレスへのインフライト ストアを検索します。一致するストアが存在する場合、ロードはメモリ システムではなくそのストアからデータ値を取得します。一致するストアがない場合、ロードは通常どおりメモリ システムにアクセスします。前の一致するストアは、すでにリタイアして値をコミットしている必要があります。この手法により、プロデューサ ストアが完了しているがまだリタイアしていない場合に、ロードは正しいデータを取得できます。

ロードのメモリ アドレスへの複数のストアがストア キューに存在する場合があります。このケースを処理するために、ストア キューは優先順位エンコードされ、プログラム順序でロードより論理的に早い最新のストアが選択されます。どのストアが「最新」であるかを判断するには、命令がフェッチされてデコードされるときに何らかのタイムスタンプを命令に添付するか、ストア キュー内の最も古いストアと最も新しいストアに対するロードの相対的な位置 (スロット) を知る必要があります。

最新のアウトオブオーダー CPU は、RAW 依存関係違反を検出するためにさまざまな手法を使用できますが、すべての手法では、実行からリタイアまで実行中のロードを追跡する必要があります。ロードが実行されると、メモリ システムやストア キューにアクセスしてデータ値を取得し、そのアドレスとデータはリタイアまでロード キューにバッファリングされます。ロード キューは構造と機能がストア キューに似ており、実際に一部のプロセッサでは、ロード ストア キュー( LSQ)と呼ばれる単一の構造でストア キューと結合される場合があります。次の手法が、RAW 依存関係違反を検出するために使用されているか、提案されています。

この手法では、ロード キューはストア キューと同様に、メモリ アクセス アドレスを使用して検索される CAM であり、実行中のすべてのロードを追跡します。ストアが実行されると、ロード キューを検索して、プログラム順序で論理的に後の同じアドレスからの完了したロードを探します。このような一致するロードが存在する場合、ストアの前に実行されたため、メモリ システム/ストア キューから誤った古い値が読み取られたことになります。ロードの値を使用した命令も、不正なデータを使用しています。このような違反が検出された場合、回復するために、ロードはリタイアメント バッファーで「違反」としてマークされます。ストアはストア キューとリタイアメント バッファーに残り、正常にリタイアし、リタイア時にその値をメモリ システムにコミットします。ただし、違反したロードがリタイアメント ポイントに達すると、プロセッサはパイプラインをフラッシュし、ロード命令から実行を再開します。この時点で、以前のすべてのストアの値がメモリ システムにコミットされています。ロード命令はメモリ システムから正しい値を読み取り、依存する命令は正しい値を使用して再実行されます。

この手法では、ストア実行ごとにロード キューの連想検索が必要となり、回路電力を消費し、大きなロード キューの場合はタイミング パスが困難になる可能性があります。ただし、追加のメモリ (キャッシュ) ポートは必要なく、実行中の他のロードやストアとのリソース競合も発生しません。

この手法では、順序どおりに実行されなかったロード命令は、リタイアメント ポイントに到達したときに再実行されます (メモリ システムに再度アクセスし、そのアドレスから値を読み取ります)。ロードはリタイアする命令になったため、実行中の命令に依存しません。その前のすべてのストアは値をメモリ システムにコミットしているため、メモリ システムから読み取られる値は正しいことが保証されます。再実行時にメモリから読み取られた値は、ロードが最初に実行されたときに取得された値と比較されます。値が同じ場合、元の値は正しく、違反は発生していません。再実行値が元の値と異なる場合、RAW 違反が発生しており、ロードに依存する命令が誤った値を使用しているため、パイプラインをフラッシュする必要があります。

この手法は概念的にはロード キュー検索よりも単純で、2 番目の CAM とその電力を大量に消費する検索が不要になります (ロード キューは単純な FIFO キューで済みます)。ロードはリタイア直前にメモリ システムに再アクセスする必要があるため、アクセスは非常に高速でなければなりません。そのため、この方式では高速キャッシュに依存します。ただし、キャッシュがどれだけ高速であっても、アウトオブオーダー ロード命令ごとに 2 回目のメモリ システム アクセスが発生するため、命令リタイアのレイテンシが増加し、プロセッサが実行する必要があるキャッシュ アクセスの総数が増加します。リタイア時の追加のキャッシュ アクセスは、既存のキャッシュ ポートを再利用することで対応できますが、これにより、プロセッサで実行しようとしている他のロードやストアとのポート リソース競合が発生し、パフォーマンスが低下する可能性があります。または、ロードの曖昧さを解消するためだけにキャッシュ ポートを追加することもできますが、これによりキャッシュの複雑さ、電力、および領域が増加します。最近の研究 (Roth 2005) では、RAW 依存関係違反が発生していないことがわかっている場合に、多くのロードを再実行からフィルターする方法が示されています。このような技術は、このような遅延やリソースの競合を軽減または排除するのに役立ちます。

この方式の小さな利点 (ロード キュー検索と比較した場合) は、RAW 依存性違反の原因となるストア (ストアのアドレスが実行中のロードのアドレスと一致する) に、キャッシュ内に既に存在するデータ値と一致するデータ値がある場合、RAW 依存性違反としてフラグが立てられず、パイプライン フラッシュがトリガーされないことです。ロード キュー検索方式では、このようなパイプライン フラッシュを防ぐために、ロード キュー検索ハードウェアに追加のデータ比較を追加する必要があります。

ロードとストアのアウトオブオーダー実行を完全にサポートする CPU は、RAW 依存関係違反が発生したときにそれを検出できる必要があります。ただし、多くの CPU は、すべてのロードとストアを強制的にインオーダーで実行したり、アウトオブオーダーのロード/ストア実行を限定的にサポートしたりすることで、この問題を回避しています。このアプローチでは、完全なアウトオブオーダーのロード/ストア実行をサポートする場合に比べてパフォーマンスは低くなりますが、実行コアとキャッシュの複雑さを大幅に軽減できます。

最初のオプションは、ロードとストアを順序どおりに実行することです。これにより、ロードがそのプロデューサー ストアの前に実行されて不正なデータを取得する可能性がなくなるため、RAW 依存関係を回避できます。もう 1 つの可能性は、ロードとストアを、アドレス生成とキャッシュ アクセスという 2 つの操作に効果的に分割することです。これら 2 つの別個の操作がリンクされているため、CPU は、以前のすべてのロードとストアのアドレスが生成されて LSQ にバッファリングされた場合にのみ、ロードとストアがメモリ システムにアクセスできるようにします。アドレス生成後、すべてのアドレスがわかっているため、あいまいな依存関係はなくなり、従属するロードは対応するストアが完了するまで実行されません。このスキームでは、ある程度の「順序外」が許容されます。つまり、実行中のロードとストアのアドレス生成操作は順序外に実行でき、アドレスが生成されると、各ロードまたはストアのキャッシュ アクセスは、(現在わかっている) 真の依存関係を尊重する任意の順序で実行できます。

アウトオブオーダーのロード/ストア実行を完全にサポートするプロセッサは、メモリ依存性予測と呼ばれる追加の関連技術を使用して、ロードとストアのアドレスが判明する前に、それらの間の真の依存性を予測しようとすることができます。この技術を使用すると、プロセッサは、実行中のストアに依存すると予測されるロードが、そのストアが完了する前に実行されるのを防ぐことができ、RAW 依存性違反を回避し、パイプライン フラッシュとそれに伴うパフォーマンスの低下を回避できます。詳細については、メモリ依存性予測の記事を参照してください。

• 命令パイプライン
• アウトオブオーダー実行
• CPUキャッシュ
• メモリ依存予測