2005-11-16

近況

情報処理学会誌に "skeletal paralell programming" というのが載っていて, よく読んでいないのだけれど要は並列計算のためのライブラリを 作りましょうという話のようだった. MPI を土台にしているらしい. Google の MapReduce が引用されており, そんなものがあったと思いだす. 読んでなかった. そういえば前回の ACM Queue も並列計算と CMP の特集. どうも並列計算が基本技能として要求される日は思ったより近い気がしてきた. 勉強しておいた方がよさそうだ. 手始めに "MapReduce: Simplified Data Processing on Large Clusters" を読んでみた.

MapReduce

MapReduce というのは並列計算のためのライブラリで, Google のインフラ(ファイルシステムやクラスタ管理など)に強く依存している. 設計も Google のアプリケーションに特化しているように見える. ユーザは Map と Reduce の二つの関数を実装して MapReduce のライブラリに渡す. MapReduce は Google のインフラの上でその関数を並列実行する. (ハードウェアの)エラー処理やスケジューリング, 排他処理, ファイル IO は MapReduce の中に隠れているので, プログラマは並列プログラミングを意識しなくてよい.

Map 関数はデータ(キーと値の対)をうけとり, 別のデータ(これもキーと値の対)を返す. Map の出力は MapReduce によってキーの値ごとにグループ可され, そのグループ(リスト)が Reduce() 関数に渡される. Reduce() はそのリストを処理した結果を出力する. 結果として, MapReduce は "キーと値の対" のリストを入力にとり, キーと "値のリスト" のリストを出力する. (出力の方法はもう少しバリエーションがある.) こんな制限されたプログラミングモデルで仕事ができるのかと思いきや, すくなくとも Google の中の仕事ではかなりの範囲をカバーできるという. 文書のインデクシング, grep, URL の登場頻度カウントなど いくつかの例が示されている.

庶民の分散コンピューティング

MapReduce の実装の話は非常によくできてるなと感心する一方, この技術を真似できる, 真似して意味のある人はそう多くなさそうにも見える. まず強力なインフラを作らなければいけないし, そもそも大規模な分散コンピューティングを業にする人の数は多くないだろうから. 庶民プログラマに求められているのは, CMP で有効な インプロセスで動くマルチスレッドプログラミング, いってみれば "小規模分散コンピューティング" だろう. プロセスをまたぐことを前提として grid 方面の路線を そのまま真似することはできない.

とはいえ先人に学ぶところも多い. たとえば, アプリケーションに特化して限定された並列プログラミングモデルを定義する アプローチが有効だということが MapReduce からわかる. 各プログラマが扱っている分野には, それぞれ固有の問題やアプローチ, ドメイン固有のパターンがあるだろう. それをいかに並列化し, かつ並列処理の部分をインフラとして隠蔽するか. それが世間のプログラマに要求される並列計算の技能なのだろう.

(前も似たようなことを書いた気もするが, 権威の裏付けがとれたことだし安心してくりかえしておく.)