はじめてのにき

_ あらゆる計算がDAGに見える

という病にかかっているように思う。まあ病といっても悪影響は特にないが

開始地点は…8年前とかで、 GNU gold なんかの記事を読んだあたりじゃないかと思う。まず、会社に入って、なるほど並列計算というのは色々難しいな、 asynchronous なサーバはこういう感じになるのか、などということを肌で感じた。で、 GNU gold がタスクをタスクキューに突っ込んでいって、終わったら依存が全部解決してるタスクが実行可能になって…みたいなモデルだと読んで、なるほどこれはバカパラレルでない計算についても最高速が出せる、完璧に正しいアプローチだなーとか思ったように思う

数年は完璧だと思ってたと思う。 Molatomium なんかが素晴らしそうだーと思ってた

http://jglobal.jst.go.jp/public/20090422/201102297100224901

実際、このモデルは計算の粒度が大きい、ビルドシステムみたいなところでは完全完璧に動く。ビルドシステムに色々な理由で関わって、この周りについてアレコレ考えたことは、病状の進行に間違いなく影響があったと思う。

でも、どこかの段階かで、銀の弾丸でないことに気付いていったと思う。実際、計算の粒度が細かいところで、このモデルで成功してる、つまり最高速に近い速度が出せてる計算環境は無いんではないかと思う。

理屈の上では完璧最強なDAGをワーカーどもが順番に取っていくモデル、なんで実際成功しないかというとデータのローカリティと同期のコストだと思う。つまり、理論上計算が完全に無駄なくスケジューリングされてるように見えて、粒度の細かさに反比例したロスが同期で起き、さらにデータのコアやマシン間のデータ移動でのロスも起きる。

僕が関わるようなシステム(つまりおおむね規模が大きく、計算よりはIOやメモリに律速されている)では、データのローカリティの方が特に大きかったように思う。例えばkatiで同時に計算できるから、こことここはパイプラインで…みたいなことをやったら、2倍弱くらいになって欲しいのに実際は1割かそこらしか速くならない、みたいなことがちょくちょく起きた。これなんかは非常に粒度が大きい並列化で、プログラムを書いた本人が、一番適切だと考えてる、つまり一番同期の回数が減るであろうと考えてる地点でブチっと切ってるにも関わらず、あまりうまくいかなかった。コードの見た目の裏で行なわれてる、キャッシュミスの影響がでかいということかなと思う。

こういう話をしてると、「今時のコンパイラは人間より賢いから〜」氏が湧いてきたりする。これはまあ…局所的なところでは正しいこともあるし、特に計算が律速してる世界では正しいことも多いと思うんだけど…データをどこに置くか的な話題はまだまだコンパイラにはできないように思う(もちろん研究はたくさんあるようだが)。というか、C言語をはじめとする現代のプログラム言語の抽象単位が、データへのアクセスを等速と考えすぎてて、なんかうまいこといく気が全くしない

でも、「今時のコンパイラは人間より賢いから〜」氏がそんなに論外なことを言ってるかというと、むしろ氏は結構正しくて、実際問題人間がとても効率的に動くデータ配置を考えてるうちに、機械が目的を達成してる、なんてことはまあ普通に起きるわけで。ここで最適化というのは、単に最速でリリースできるような結果が欲しいという話で、5年後に0.01秒でサーブできるシステムができるよりは、1年後に1秒でサーブできるシステムができる方がいい、っていう、ガチ最適化屋としてはつまらないであろうトレードオフがあり。まあつまり老人が言ってるイメージ、というかステレオタイプがある「結局機械の最適化は人間がやる最適化には勝てない」は、無限時間が経過した後では正しいのだけど、現実には無限の時間給料払ってられないので、まあトレードオフになる

さてそんなところにtensorflowです。これは完全にDAGをどうこうという計算モデルで…しかし人間が tf.device でどこで計算をするかを決めることができる。うーんなるほどという感じ。こいう計算モデルで計算時間的に最速のものが出来るとはとうてい思えないけど、まだまだどういうふうにやればいいか固まってないジャンルだけに、とにかく開発者が新しいモデルを実験する時間を最小化して、しかし年月単位とかでは待ちたくないので、ほどほどにスケールするようにする、てのはなかなか良い落としどころな気もする…

まあ、で、それはそうとDAGに戻ると、LLVMのバックエンドを見ると、これはこう、SSAしたコードてのは、最初っからDAGなわけです。TFのDAGも実質一個ループを入れてやれば十分にTuring完全なやつだろうし…うーんDAGてのは強力な物体だなあなどと思うわけです

CPUてこう、最終的には順番に並んだ命令を実行してるわけだけど、現代的のCPUは命令列からDAGというか依存関係を復元してたりするわけで、そもそも最初から命令セットは単なる配列じゃなくて、DAGであるべき…てことはないんですかねえ。現代的なコンパイラがDAGを作って命令列に落として、CPUが命令列からデータ依存を考えてる…てのはムダな気がするというか

PEZYの人たちとかが死ぬほど考えてそうな話題だとおもう

(02:12)