キャッシュ非依存アルゴリズム

コンピューティングにおいて、キャッシュ非依存アルゴリズム（またはキャッシュ超越アルゴリズム）とは、キャッシュのサイズ（またはキャッシュラインの長さなど）を明示的なパラメータとせずに、プロセッサのキャッシュを活用するように設計されたアルゴリズムです。最適なキャッシュ非依存アルゴリズムとは、キャッシュを最適に利用する（定数係数を無視した漸近的な意味で）キャッシュ非依存アルゴリズムのことです。したがって、キャッシュ非依存アルゴリズムは、キャッシュサイズが異なる複数のマシン、または異なるサイズのキャッシュを持つ異なるレベルのメモリ階層において、変更を加えることなく良好なパフォーマンスを発揮するように設計されています。キャッシュ非依存アルゴリズムは、与えられたキャッシュに対して最適なサイズのブロックに問題を明示的に分割する明示的なループタイリングとは対照的です。

最適なキャッシュ非依存アルゴリズムは、行列乗算、行列転置、ソート、その他いくつかの問題で知られています。クーリー・テューキーFFTなどのより一般的なアルゴリズムの中には、特定のパラメータ選択の下で最適なキャッシュ非依存となるものもあります。これらのアルゴリズムは漸近的な意味でのみ最適（定数係数を無視した場合）であるため、絶対的な意味でほぼ最適なパフォーマンスを得るには、マシン固有のさらなる調整が必要になる場合があります。キャッシュ非依存アルゴリズムの目標は、このような調整の必要性を減らすことです。

一般的に、キャッシュ非依存アルゴリズムは、再帰的な分割統治アルゴリズムによって動作します。このアルゴリズムでは、問題がより小さな部分問題に分割されていきます。最終的には、キャッシュのサイズに関係なく、キャッシュに収まる部分問題のサイズに到達します。たとえば、最適なキャッシュ非依存行列乗算は、各行列を再帰的に乗算対象の4つの部分行列に分割し、深さ優先で部分行列を乗算することによって得られます。特定のマシンに合わせて調整する場合、最下層では特定のキャッシュサイズに合わせて調整されたループタイリングを使用し、それ以外ではキャッシュ非依存アルゴリズムを使用するハイブリッドアルゴリズムを使用する場合があります。

キャッシュ非依存アルゴリズムのアイデア（および名称）は、1996 年という早い時期にCharles E. Leisersonによって考案され、 1999 年にHarald Prokopがマサチューセッツ工科大学の修士論文で初めて発表しました。 ^{[ 1 ]}通常は特定の問題を分析する多くの先行研究があり、これらは Frigo et al. 1999 で詳細に議論されています。引用されている初期の例としては、再帰的高速フーリエ変換に関する Singleton 1969、同様のアイデアの Aggarwal et al. 1987、行列乗算と LU 分解に関する Frigo 1996、Blitz++ライブラリの行列アルゴリズムに関するTodd Veldhuizen 1996 などがあります。

一般的に、プログラムはキャッシュをより意識するようにすることができます。^{[ 2 ]}

• 時間的局所性：アルゴリズムが同じメモリ領域を複数回フェッチする。
• 空間的局所性、つまり後続のメモリアクセスが隣接または近傍のメモリアドレスである。

キャッシュ非依存アルゴリズムは、通常、キャッシュの理想化モデル（キャッシュ非依存モデルと呼ばれることもある）を用いて解析されます。このモデルは、実際のキャッシュの特性（複雑な連想性、置換ポリシーなどを持つ）よりもはるかに解析が容易ですが、多くの場合、より現実的なキャッシュのパフォーマンスと定数倍の範囲内に収まることが証明されています。キャッシュ非依存アルゴリズムはブロックサイズやキャッシュサイズを知らないため、外部メモリモデルとは異なります。

特に、キャッシュ非依存モデルは抽象マシン（つまり、計算の理論モデル）です。これは、チューリングマシンの無限テープを無限配列に置き換えたRAMマシンモデルに似ています。配列内の各位置は、${\displaystyle O(1)}$実際のコンピュータのランダムアクセスメモリと同様に、時間も考慮されています。RAMマシンモデルとは異なり、キャッシュも導入されています。キャッシュは、RAMとCPUの間の第2レベルのストレージです。2つのモデルのその他の違いは以下のとおりです。キャッシュ非対応モデルでは、次のようになります。

• メモリはブロックに分割され、${\displaystyle B}$それぞれがオブジェクトです。
• メインメモリとCPUレジスタ間のロードまたはストア処理は、キャッシュから行うことができるようになった。
• キャッシュからロードまたはストアが処理できない場合、それはキャッシュミスと呼ばれます。
• キャッシュミスが発生すると、メインメモリからキャッシュに1ブロックがロードされます。具体的には、CPUがワードにアクセスしようとした場合です。${\displaystyle w}$そして${\displaystyle x}$行には${\displaystyle w}$、 それから${\displaystyle x}$キャッシュにロードされます。キャッシュが以前に満杯だった場合は、1行が削除されます（下記の置換ポリシーを参照）。
• キャッシュには${\displaystyle M}$オブジェクト、${\displaystyle M=\Omega (B^{2})}$これは「高キャッシュ仮定」とも呼ばれます。
• キャッシュは完全連想型です。各行はキャッシュ内の任意の場所にロードできます。^{[ 3 ]}
• 置換ポリシーは最適です。言い換えれば、キャッシュはアルゴリズム実行中のメモリアクセスの全シーケンスを受け取るものと想定されます。ある時点でラインを追い出す必要がある場合${\displaystyle t}$将来の要求のシーケンスを調べて、最初のアクセスが最も遠い将来の回線を追い出します。これは、オフラインの最適な置換戦略の小さな定数係数の範囲内にあることが示された、最近使用頻度の低いポリシーで実際にエミュレートできます^{[ 4 ] [ 5 ] 。}

キャッシュ非依存モデル内で実行されるアルゴリズムの複雑さを測定するために、アルゴリズムが経験するキャッシュミスの数を測定します。このモデルは、キャッシュ内の要素へのアクセスがメインメモリ内の要素へのアクセスよりもはるかに高速であるという事実を捉えているため、アルゴリズムの実行時間は、キャッシュとメインメモリ間のメモリ転送の数のみによって決まります。これは、上記のすべての機能を備えた外部メモリモデルに似ていますが、キャッシュ非依存アルゴリズムはキャッシュパラメータに依存しません（${\displaystyle B}$そして${\displaystyle M}$) ^{[ 6 ]}このようなアルゴリズムの利点は、キャッシュ非依存マシンで効率的なものが、特定の実際のマシンパラメータに合わせて微調整することなく、多くの実際のマシンで効率的である可能性が高いことです。多くの問題では、最適なキャッシュ非依存アルゴリズムは、2 つ以上のメモリ階層レベルを持つマシンでも最適になります。^{[ 4 ]}

Frigo らによって提示された最も単純なキャッシュ非依存アルゴリズムは、アウトオブプレース行列転置操作です (転置のためのインプレースアルゴリズムも考案されていますが、非正方行列の場合ははるかに複雑になります)。m × n 配列 A と n × m 配列 B が与えられたとき、Aの転置をBに格納したいとします。素朴な解決策では、一方の配列を行優先順で、もう一方の配列を列優先順で走査します。結果として、行列が大きい場合、列方向の走査の各ステップでキャッシュミスが発生します。キャッシュミスの総数は${\displaystyle \Theta (mn)}$。

キャッシュ非依存アルゴリズムは最適な作業複雑度を持つ${\displaystyle O(mn)}$最適なキャッシュの複雑さ${\displaystyle O(1+mn/B)}$基本的な考え方は、2 つの大きな行列の転置を、小さな (部分) 行列の転置に縮小することです。これは、行列をより大きな次元に沿って半分に分割し、キャッシュに収まるサイズの行列の転置を実行するだけで済むようになるまで繰り返します。キャッシュのサイズはアルゴリズムに知られていないため、この後も行列は再帰的に分割され続けますが、これらの分割はキャッシュに格納されます。次元mとn が十分に小さくなり、サイズの入力配列が${\displaystyle m\times n}$そしてサイズが${\displaystyle n\times m}$キャッシュに収まるため、行優先と列優先の両方のトラバーサルで、${\displaystyle O(mn)}$仕事と${\displaystyle O(mn/B)}$キャッシュミス。この分割統治法を用いることで、マトリックス全体の複雑さを同レベルに抑えることができます。

（原理的には、1 × 1のベースケースに到達するまで行列を分割し続けることも可能ですが、実際には、再帰サブルーチン呼び出しのオーバーヘッドを償却するために、より大きなベースケース（例えば16 × 16）を使用します。）

ほとんどのキャッシュ非依存アルゴリズムは、分割統治法に基づいています。キャッシュのサイズに関係なく最終的にキャッシュに収まるように問題を縮小し、関数呼び出しのオーバーヘッドやキャッシュとは無関係な最適化によって決定される小さなサイズで再帰処理を終了させ、その後、キャッシュ効率の良いアクセスパターンを使用して、解決済みの小さな問題の結果を統合します。

外部メモリモデルにおける外部ソートと同様に、キャッシュ非依存ソートは、マージソートに似たファンネルソートと、クイックソートに似たキャッシュ非依存分布ソートの2つのバリアントで可能です。外部メモリモデルと同様に、どちらも実行時間は${\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}$これは下限値に一致するため、漸近的に最適である。^{[ 6 ]}

優先度キューを実装する2つのRAMベース、1つのキャッシュ認識、および2つのキャッシュ非認識アルゴリズムの経験的比較により、次のことがわかった。^{[ 7 ]}

• データがメインメモリに収まる場合、キャッシュ非依存アルゴリズムはRAMベースおよびキャッシュ認識アルゴリズムよりもパフォーマンスが劣った。
• キャッシュを考慮したアルゴリズムは、キャッシュを考慮しないアルゴリズムと比べて実装が著しく複雑になるようには見えず、本研究でテストしたすべてのケースで最高のパフォーマンスを示した。
• データサイズがメインメモリのサイズを超えた場合、キャッシュ非依存アルゴリズムはRAMベースのアルゴリズムよりも優れた性能を発揮した。

別の研究では、ハッシュテーブル（RAMベースまたはキャッシュ非対応）、Bツリー（キャッシュ対応）、および「ベンダーセット」と呼ばれるキャッシュ非対応のデータ構造を比較しました。実行時間とメモリ使用量の両方で、ハッシュテーブルが最も優れており、次にBツリー、すべての場合においてベンダーセットが最も劣っていました。すべてのテストのメモリ使用量はメインメモリを超えませんでした。ハッシュテーブルは実装が容易であると説明されている一方、ベンダーセットは「正しく実装するにはより多くの労力が必要」でした。^{[ 8 ]}

• キャッシュ非依存型分散ソート
• 外部メモリアルゴリズム
• ファネルソート