データの局所性。

先日のゼミで得られたことはかなり多い。今までメモリアクセスコストに対しての認識はあったのだが、知識の結びつきがうまくいっていなかったようだった。いまだに理解していない部分も多くあるだろうが、今までにない視点で高速化について見る事が出来るようになったと思う。

ここから先は最短路ソルバーを例に挙げての話になるが、一般的な話であるのでプログラムの高速化全般に適応できると思われる。

まず、実行を大まかに捉えると「入力データ→出力データ」である。ようするに、入力データに何らかの加工をして出力データを作成することになる。

最短経路問題では、入力データは「グラフデータ」で、出力データは「始点からの距離行列・直前隣接点」になっている。どちらも巨大である。さらに今回の場合、入力データは「加工せずに入力としてのみ用いるデータ」であり、出力データは「加工するデータ」である。入力データ、出力データはどちらも巨大で、もちろんキャッシュには載らない。

最短路ソルバーで用いているダイクストラ法では、入出力共に巨大ではあるが一度にすべてのデータを用いるのではなく、ある地点では少量のデータを用いて加工している。そのため、その少量の作業領域が十分小さければ、メインメモリではなく L2 キャッシュ以上に配置される。作業領域サイズを減らすことが高速化につながる。しかしながら演算量・データの再利用が少ない場合には、あまり効果がなく、結局メモリアクセスコストがボトルネックとなってしまうだろう。

以上のことは言うのは簡単だが、実際に行うのは難しい。ダイクストラ法では実際の演算の演算量・データの再利用が少ないので、探索候補点集合を格納するデータ構造の動きに大きく左右されるだろう。再利用性が多く、局所性が高いデータ構造を用いるとよい。そういう意味では、バケット法ではなく、ヒープ法の方に歩があるといえる。