Bingo Spatial Data Prefetcherの論文を読む (1. 概要)

データ・プリフェッチの技法であるBingoの論文を読んでいるので、概要をまとめる。

https://ieeexplore.ieee.org/document/8675188

Bingoは、空間データ・プリフェッチの技術で、TAGEにインスパイアされたプリフェッチ技法である。

TAGEというのは現代の最先端分岐予測手法で、複数の履歴テーブルを用いて最も長い履歴長のテーブルの情報を用いて予測を行う。複数のテーブルを持っているというのがミソで、プログラムの中に現れる短いパタンと長いパタンを別々のテーブルで捉えることによって、効率的かつ高い精度で分岐予測を行うことができるという技法である。

Bingoは似たような考えに基づき、メモリのアクセスパタンを、短いイベントと長いイベントの両方に関連付けることによって、両方のイベントから効率的にプリフェッチを引き出そうというものである。さらに、アクセスパタンの履歴テーブルを長いイベント用と短いイベント用に別々に確保するのではなく、履歴テーブルを1つで済ますことができるような方式を提案している。

結果として、Bingoのプリフェッチの性能は：

データプリフェッチを用いない場合と比較して60%のシステム性能向上
既存の空間データプリフェッチ手法と比較して11%のシステム性能向上

となった。

まず、空間データ・プリフェッチというものについて概観する。空間データ・プリフェッチは、メモリ空間をページと呼ばれる大きな空間(このときのページは、いわゆるオペレーティングシステムで用いられるページとは別物だが、だいたい2KB程度の空間のことを言う)に分割し、その中でのメモリ・アクセス・パタン(フットプリントつまり、アクセスの相関)を使用してプリフェッチを行う。

例えば、あるプログラムがページA内で{X,Y,Z}の位置にアクセスしたことがある場合、似たようなページにおいて再び{X,Y,Z}にアクセスする可能性が高いので、{X,Y,Z}をプリフェッチする。

具体的には空間データ・プリフェッチャは、ページ内のアクセスをすべて記録し、そのページと関連付けられる「イベント」を関連付けて記録する。イベントというのは、そのページへの最初のアクセスに起因する事象とすることが多いが、例えば最初にそのページへのアクセスを行った命令のプログラムカウンタなどを使用する。この場合、次に同じイベントが発生した場合(つまり、この場合は同じプログラムカウンタの命令が実行された場合)、プリフェッチャは、そのフットプリントを使用して、ページの将来のメモリ参照をプリフェッチすることになる。

また、空間データ・プリフェッチは、初期参照ミスを排除することができるというところである。過去のページで観測されたパタンを、新たなページに適用することで、データの初期アクセスによるキャッシュミスを抑制することができる。

ここでは、空間データ・プリフェッチャの種類を大きく2種類に分類する：

PPH (Per-Page History): 各ページのフットプリントを記録し、イベントと関連付け、メタデータテーブルに格納する。
SSH (Shared History): グローバルにすべてのアクセスを観察し、差分による履歴情報を共有メタデータに保存する。SPPプリフェッチャがこれに相当する。各ページでのパタンを記録するのではなく、すべての場所でのアクセスパタンを統一したストレージに保存するところがポイントである。

ここではPPHに着目して説明するが、あるページがアプリケーションによってはじめて使用された(トリガ・アクセス)すると、そのページが使用されなくなるまでアクセスを観測する。ページが使用されなくなると、フットプリントが記録され、イベントと関連付けられて履歴テーブルに保存される(<event, pattern>)。

pattern: ページのフットプリントをビットベクトルとして示したもの。あるブロックがページ内で使用されるとそのビットに1を設定し、そうでなければ0を設定する。
event: そのページを使用する動機となるイベント。通常はトリガ・アクセスを使用する。鳥がアクセスとして、例えばPC+Addressつまり鳥が命令のPCとアクセスアドレスを組み合わせたものである。他にも、PC+Offsetというものである。Offsetはページ内のオフセットを示したものである。

この方式の問題は、どのイベントが最良なのかというものである。PC+Addressの場合は、同じ命令が同じアドレスにタッチするというのを待つので、全く同じページアドレスが要求されなければならないので、初期配置キャッシュミスを補填することができない。一方でPC+Offsetはフットプリントの位置さえ同じであればイベントを駆動することができるが、あまりにも積極的でPC+Addressほど正確ではない。

本研究では、空間データ・プリフェッチャの性能もさりながら、ストレージ効率性というところにも焦点を当てている。このために、データ効率性を保ちつつ高い性能を達成できるTAGEに発想を得ているというところがポイントだ。

TAGEは、将来の事象を予測するために、単一の履歴テーブルを使用するのではなく、特定の情報を持つ複数の履歴テーブルを使用している。これらのテーブルには、長いイベントと短いイベントが独立に記録されている。長いイベントは、例えば「命令I5がページP2の3番目のキャッシュ・ブロックにアクセスする」といったものであり、短いイベントは「命令I5が実行される」といったものだ。

Bingoはこのような複数のイベントが発生する状態というのを考慮し、各ページのフットプリントを格納するときに、フットプリントに複数のイベントが関連付けられるようにする。イベントが発生すると、それに関連する最も長いイベントを見つけ、それに基づいたフットプリントを用いてプリフェッチを行う。

この方式では、素朴に実装すると大きなオーバヘッドが生じてしまう。空間データ・プリフェッチの場合には、各メタデータのテーブルがかなり冗長であることが多いので、このような冗長性を排除し統一テーブルを使用するための方式を提案する。