Cache Obliviousの話

Cache Obliviousの話 @kumagi

科学と工学？ • どう違うの？ • ある工学者は言った。 「3以上の奇数は素数」 – 3,5,7が素数 – 9は誤差 – 11,13と素数だから5/6≒87%の精度で正しい！

これはひどい

特に • コンピュータの上は科学だよ派 – 世界は数学に身を任せればだいたい上手くいくよ • コンピュータの上は工学だよ派 – 世界は人力と経済と物理の果ての妥協だよ

個人的な好み→工学 • 「コンピュータ工学の世界に難問は２つしかな い。キャッシュの揮発と、変数の命名だ」 – 「珠玉のプログラミング」で読んだ – すごく工学っぽくて好きな言葉 • 逆に科学の人たち無限サイズのL1キャッシュ を想定し過ぎ – それで生み出される「計算量的には速いけど実 測は遅いアルゴリズム達」

計算量ェ… • 計算量の議論は「無限の大きさを扱う場合」 を仮定している

Sorry! • • • • 1000京円つぎ込もうが！ 100PBぐらいの大きさで！ 3Ghzぐらいの速度で！ 1クロックで動くL1キャッシュは作れない！

うちゅうのほうそくがみだれない！ • いかにプロセスが微細化してCPUが高性能化 してもCPUを流れる信号の速度は限界がある • 100年後のコンピュータであってもキャッシュ の階層構造からは逃れられない！

結果として • 無限のデータを相手にするプログラムは絶対 キャッシュミスする – そしてプリフェッチが間に合わない時にキャッシュ ミスが全体を律速する – 時間計算量だけを相手にしてる場合じゃない！ – 理論値と実測値の差を埋めるには？

キャッシュ構造をアルゴリズムに埋め込む • キャッシュへのアクセスを細かくチューニング したアルゴリズムを適宜作ればいいのでは？ • キャッシュ階層は今後も変わり続けるから 延々と追従していくつもり？

ケーススタディ • 長ーい配列から A B C D E F G H I J K L MN O P Q • (A*A)+(A*B)+(A*C)+(A*D)…..+ +(B*A)+(B*B)+(B*C)+(B*D)…..+ +(C*A)+(C*B)+(C*C)+(C*D)…. という値を並列化して高速に求めたいとする。

ケーススタディ • まとめるとこんな感じに計算していくのが普通 A B C D E F G H I J K L MN O P Q A*(A+B+C+D+E+F+G+H+I….) + A B C D E F G H I J K L MN O P Q B*(A+B+C+D+E+F+G+H+I….) + A B C D E F G H I J K L MN O P Q C*(A+B+C+D+E+F+G+H+I….)

ケーススタディ • 並列化すればいい A B C D E F G H I J K L MN O P Q A*(A+B+C+D+E+F+G+H+I….) CPU１ + A B C D E F G H I J K L MN O P Q B*(A+B+C+D+E+F+G+H+I….) CPU２ + A B C D E F G H I J K L MN O P Q C*(A+B+C+D+E+F+G+H+I….) CPU３

結果 • 縦軸が時間（下ほど速い）、横軸がコア数 • 赤線が理論速度、青線が実測 F a s t Core

遅い！

そこでCache Oblivious！ • Oblivious = ぼんやりとした • キャッシュの階層構造を想定しながらも、その 具体的なサイズや遅延時間は仮定しないア ルゴリズム設計技法 • 個人的に注目しているホットな分野 • 再帰的に分割統治するアルゴリズムが多い

Cache Oblivious • キャッシュ階層を簡略化してモデル化する – ライトバック・ライトスルーは気にしない – フルセットアソシアティブを仮定 – サイズや転送速度や階層数に仮定を置かない • CPUに近いほど高速で小型になる – むしろHDDすらも磁気テープやS3に対するキャッ シュとして考える

Cache Oblivious • モデル図はこんな感じ

Cache Oblivious • キャッシュに収まるよう問題を切り分ける

どうなるの？ A B C D E F G H I J K L MN O P Q A B C D E F GH I J K L Task

どうなるの？ A B C D E F G H I J K L MN O P Q A B C D E F GH I J K L 1/4Task 1/4Task 分割！ 1/4Task 1/4Task

どうなるの？ A B C D E F G H I J K L MN O P Q A B C D E F GH I J K L 1/16 Task 1/16 Task Task Task 分割！ 1/16 1/16 1/4Task 1/4Task 1/4Task

どうなるの？ A B C D E F G H I J K L MN O P Q A B C D E F GH I J K L 1/64 1/64 Task Task 分割！ 1/64 1/64 Task Task 1/16 Task 1/16 Task 1/16 Task 1/4Task 1/4Task 1/4Task

充分切り分けたら足していく • AA+AB+BA+BB A B + • CA+CB+DA+DB A B 1/64 Task • CC+CD+DC+DD + C D C D C D 1/64 Task C D A B A B 1/64 Task • AC+AD+DA+DB 1/64 Task +

結果 • 緑が理論値、黄色が実測値 F a s t Core

すごい！！

どこに感動したのか • これまで工学分野で相手にしてきた問題であ る「キャッシュ構造への最適化」 • モデル化して「科学の問題」に変えた • 数式が現れてなんか怖くなったけど

他にも • Cache Obliviousな – Sort – 行列転置 – 行列積 – 2分木（van Emde Boas） – B木 – グラフ – 線形リスト – まだまだ調べ中

Cache Oblivious on Hadoop • 巨大なクラスタ環境では各マシンのメモリや CPUが揃っていない事の方が普通 – つまりCache Awareなアルゴリズムを組み上げる コストが高い – これはCache Obliviousの時代が来るのでは？ （個人の感想であり効果・効能を約束する物ではありません）