Cache-oblivious algorithm とは

計算では、キャッシュを無視するアルゴリズム(またはキャッシュ超越アルゴリズム)は、キャッシュのサイズ(またはキャッシュラインの長さなど)を明示的なパラメータとして使用せずにCPUキャッシュを利用するように設計されたアルゴリズムです。最適なキャッシュ忘却アルゴリズムは、キャッシュを最適に(漸近的な意味で、一定の因子を無視して)使用する、キャッシュを知らないアルゴリズムである。したがって、キャッシュを無視するアルゴリズムは、異なるキャッシュサイズを有する複数のマシン上で、または異なるサイズを有する異なるレベルのキャッシュを有するメモリ階層に対して、修正なしで良好に動作するように設計される。キャッシュを無視するアルゴリズムは、特定のキャッシュに対して最適なサイズのブロックに問題を明示的に分割するループネスト最適化のように、明示的なブロックとは対照的です。
Cooley-Tukey FFTアルゴリズム、行列の乗算、ソート、行列の転置、その他いくつかの問題では、最適なキャッシュを知らないアルゴリズムが知られています。これらのアルゴリズムは漸近的な意味でのみ最適なものであるため(一定の要素を無視して)、絶対的な意味でほぼ最適な性能を得るためには、さらに機械固有の調整が必要となることがあります。キャッシュを知らないアルゴリズムの目標は、必要な調整の量を減らすことです。
典型的には、キャッシュを知らないアルゴリズムは、問題がより小さいサブ問題に分割される再帰的除算および征服アルゴリズムによって作用する。最終的には、キャッシュサイズに関係なく、キャッシュに適合するサブ問題のサイズに達する。例えば、最適なキャッシュ忘却行列乗算は、各行列を掛け算される4つの部分行列に再帰的に分割し、深度優先方式で部分行列を掛けることによって得られる。特定のマシンのチューニングでは、最下位レベルで特定のキャッシュサイズに調整されたブロッキングを使用するハイブリッドアルゴリズムを使用することができますが、それ以外の場合はキャッシュを無視するアルゴリズムが使用されます。