ノンブロッキングキャッシュ

アウトオブオーダ実行を行うと、最初のロード命令を発行しその実行が完了する前であっても、次のロード命令のアドレスが決定していれば、次のロード命令を発行することが可能になる。図8.1のように、最初のLoad1はキャッシュにヒット、2番目のLoad2がキャッシュをミスして完了に長い時間が掛かり、その後のLoad3、Load4はキャッシュヒットする場合、単純に順番に実行(インオーダ実行)すると全部のLoadが完了するには長い時間がかかる。

しかし、Load3、Load4がLoad2の結果に依存せずアドレスが求まっている場合は、Load3、Load4の実行開始はLoad2の完了を待つ必要は無い。そして図8.1の下側の図のようにLoad2のミスが判明した時点でLoad3を開始すれば、Load2のデータをメモリから読み出しているのと並行してLoad3、Load4を実行してしまえる。

図8.1 ロード命令のインオーダ実行とアウトオブオーダ実行

2番目のロード命令がキャッシュをミスすると、キャッシュはLRUで追い出すキャッシュラインを選択し、そのキャッシュラインが変更されている場合は、そのキャッシュラインをメモリに書き戻し、そしてアクセスされたキャッシュラインのデータをメモリから読み込む必要がある。ここで、キャッシュがこの作業に掛かりっきりになっているとすると、次のロード命令を処理することは出来なくなる。このロスを避けるため、最初のロード命令がキャッシュをミスしても次のロード命令の処理を止める(ブロックする)ことなく、処理が継続できる構造を採るキャッシュをノンブロッキングキャッシュと呼ぶ。

図8.2 ノンブロッキングキャッシュの構造

キャッシュミスが発生すると、そのキャッシュラインが変更されている場合にはメモリに書き戻す必要が出る。このため、図8.2のように、ミスしたアクセスのアドレスを保持してメモリをアクセスするためのロードアドレスキューに加えて、書き戻しを行うキャッシュラインとアドレスを保持するストアアドレスキュー、ストアデータキューを設ける。なお、図8.2では、説明を簡単にするために、キャッシュはダイレクトマップ方式とし、また、制御を簡単にするため、キャッシュアレイは読み出しと書き込みを独立して行える1R1Wタイプであるとしている。

キャッシュをアクセスしてミスした場合は、読み出されたデータがDirty(書き換えられている)であれば書き戻しが必要になる。したがって、このデータをストアデータキューに格納してしまえば、取り敢えずキャッシュラインを空け新しいデータを書き込むことができるようになるので、ミスしたアドレスをロードアドレスキューに入れて、メモリをアクセスする。

そして、メモリが読み出されロードアドレスとデータが得られると、キャッシュアレイの書き込みポートを使って、キャッシュに書き込む。また、同時にメモリからのデータは、ロードユニットに送られる。

一方、Dirtyラインのメモリへの書き戻しは、ストア側のアドレスとデータキューを使って実行される。ただし、この書き込みは急ぐ必要はないので、ロードキューの要求が無くなった時、あるいはストアキューに溜まった要求が一定数を超えた時に行えばよい。

このような構造にすると、ミスとなった2番目のロード命令をメモリユニットが処理している間に、次のLoad3、Load4命令の実行を開始し、それがキャッシュにヒットした場合はすぐにロードデータが得られる。したがって、アウトオブオーダ実行の場合は、Load3、Load4命令のロードデータに依存するがLoad2のデータには依存しない演算命令にデータを渡して処理を進めることができる。

このようなノンブロッキング処理を行う場合、書き戻すキャッシュラインを保持するストアキューのエントリ数は多い方が良いが、キャッシュラインは32バイトから大きいものでは512バイト程度とビット数が多いので、多数のバッファを設けるのはハード量の負担が大きい。必要なエントリ数は、ミスした場合にアクセスする下位のキャッシュやメインメモリのレーテンシにも依存するが、メインメモリに一番近いキャッシュの場合、16個~32個程度のエントリを持つのが一般的である。

また、図8.2では省略されているが、Dirtyなラインがメモリに書き戻される前にそのラインへのプロセサからのアクセスが入ってくる場合に備えて、ストアキューは単なるキューではなく、アドレスを比較して、後続のロード命令がこのキューに格納されているエントリにヒットしていないかどうかを監視し、ヒットした場合はキャッシュヒットと同様にロードユニットにデータを返す機構が必要である。

このようにノンブロッキングキャッシュは複雑でハードウェアの物量も多くなるが、性能的には大きなメリットがあり、アウトオブオーダ実行を行う最近のプロセサでは、ノンブロッキングキャッシュを用いるのが一般的である。