2006-02-04

近況

MapReduce の話を聞いたあと, 並列プログラミングについて妄想しつつウェブを徘徊していたら 国産の "SkeTo" というプロジェクトをみつけた. 研究の一環としてとして MPI をラップする C++ のライブラリを作っているらしい. 論文もいくつか追いてある.

"助っ人：構成的な並列スケルトンによる並列プログラミングライブラリ" は概要がコンパクトにまとまっていて良い. "A Compositional Framework for Developing Parallel Programs on Two Dimensional Arrays|http://www.ipl.t.u-tokyo.ac.jp/~emoto/metr05-09.pdf" はもう少し理論に踏み込んだ内容になっている.

SkeTo

SkeTo は MPI の上に作られた並列計算要のユーティリティライブラリ. C++ で書かれている. SkeTo ではあるいくつかのデータ構造を前提として, その構造の上をトラバースしながらユーザが定義した演算を呼出す. こういうアプローチを構成的なアルゴリズムと呼ぶそうだ. ruby でいうと 仮定している構造は Enumerable で map() の実装がライブラリの仕事, map() に渡す Proc オブジェクト(ブロック)がユーザ定義の演算ということになる. これらはもともと関数型言語の得意分野で, ああいう言語は古くから並列計算の題材によく使われている. 副作用の少なさや定義の明確さが並列化をする上で都合が良いらしい. 実際, SkeTo も形式化の部分には Haskell 互換の表記を採用している. (と書いてあった. 私は Haskell がどんなものか知らない.)

ここから下はしばらく論文の受け売りです.

構成的なアプローチではもっぱらリスト構造に対して 並列化されたトラバースのためのプリミティブ(これを "スケルトン" と呼ぶ) を用意する. SkeTo は ツリー構造に対してもスケルトンを用意しているのが特徴. 特に二分木だけではなく, 任意の数の子を持つ普通の木("薔薇木" と呼ぶ) に対して形式化と実装を行っている. 二分木に対しての並列化スケルトンは既に知られており, 薔薇木と二分木の間の変換を定義することで二分木用のスケルトンを 薔薇木にも適用可能にした.

スケルトンには以下の種類がある:

言葉で読むとわかりにくいが論文の図を見ると一瞬でわかる. 興味のある人はそっちを見たほうが早いかも.

木に対するアルゴリズムを並列化するための戦略についても解説されている. そのためには "Diffusion 定理" と呼ばれる一連の変換公式を駆使するらしいのだが, 例のごとく Haskell 記法で書かれておりさっぱりわからず悲しくなる. せっかく C++ で実装したんだから C++ の例も欲しい. とはいえこうして具体的な方法論として並列化の技術を示されると そのうち市井のプログラマにも並列プログラミングのできる時代が 来るような気分になってくる. 夢があるようでもあり, 恐しくもある. とりあえず心の積読(の最後尾)に MPL と Haskell を追加しておく.

実装

SkeTo はソースが公開されているので, 暇潰しついでに覗いてみた. せっかくなのでメモしておく. 私は MPI も Haskell もよくわからないため, 以下の話は色々間違っているかもしれない.

SkeTo は小さなライブラリだ. テストコードを入れると 2.3 万行, コードの大半はヘッダファイルで出来ている. (ヘッダファイルだけだと 1.7 万行) コンパクトでいい. 論文でも boost の bind などから影響をうけたとあるとおり, STL や boost のような路線だと思えばよい. doxygen 形式のコメントが入っており, API 文書も doxygen. 詳細度はそこそこ. 実装の詳細に複雑なところはあるけれど API の大筋はシンプルだから, 十分な量だと思う. サンプルコードはすくない またその多くは素朴なものだった. これは残念. どうせなら論文で紹介している XPath の実装なんかをつけてくれればいいのにね. (これは別枠で公開されているのかもしれないけれど, すぐには見当らなかった.) コードそのものはその性格上多くの部分がけっこうクリーン. ただ変数や型の名前がマセマチカルで辛い. 論文片手に読むようなかんじ.

ディレクトリ構成は以下のようになっている:

雰囲気を捕むには list と tree, 必要に応じて util を見るとよい. このへんは素朴でわかりやすい. matrix や rosetree はスケルトンの実装が複雑.

イメージとしては STL の <algorithm> に似ている. その MPI 版. 分散環境なので iterator はないし, データ構造の操作もかなり限定されている. たとえば list だと push_back() や remove() のような要素の追加/削除はできない. コンストラクタでえいやとサイズを決める.

skelton の実装の大枠は, まずノード(単一の計算単位)内での計算済ませ, それを隣接ノードに伝播するというもの. きっと MPI のイディオムなんだと想像. ノード内での計算は local_xx(), 隣接ノードとの通信を含む部分は global_xx() という風に名前がついている. xx() では local_xx() と global_xx() を 順に実行することで skelton 全体の計算を行う. (実際はもう少し面倒.)

その他, 素人(私)にわかる範囲で面白いと思ったのは 分散二分木である dist_tree のデータ構造. 二分木全体が部分木に分割され, 各部分木は別々の計算機に割り振られる. またその計算機も二分木の接続関係をもつ. つまり計算機が二分木を構成し, 個々の計算機の中に部分木である二分木が入れ子になっている. 分散ツリーはこういう風に分割するのかと感心した. ちょっとしゃれてるね. また, 薔薇木を二分木として表現する理由も何となくわかってくる. その方が問題を単純にできるだけでなく, 並列度もあげやすいからだ. 実装を見る限り, ツリー上のある要素の子要素を処理する部分はシーケンシャルになってしまう. こんなかんじ:

 void Node::doSomething()
 {
    foreach (c : children) {
      c.doSomething(); /* foreach 内は並列化されない */
    }
 }

がんばって foreach の部分を並列化しようとすると, 各計算主体の中はシーケンシャルに動くという(おそらくは MPI の) 計算モデルに違反してしまう. 二分木だと子は高々二つだからこういう心配はない. だから多少無理をしてでも薔薇木を二分木に変換する動機はあるのかと納得.

そのほか所感

命名規則が一貫していなかったり, boost の影響を受けたといいつつ boost を使わず再発明をしていたりと細かいところにケチをつけることはできるが, 今風の C++ で並列計算をやるとこうなるのかと勉強になった. それに木構造を標準で用意していると色々使いでがありそう. この路線でライブラリを充実させていくのは野心的だが面白い.

一方で, MapReduce を見たあとだと物足りなさもある. 特に入出力が弱いのとソートがないのは実用を考えると苦しい気がする. MapReduce は, Map と Reduce の間の謎の空白期間で要素をソートする. 分散ソートはとても素人に実装できる代物ではない(分散じゃなくてもよく間違う) から, ライブラリで用意しておいて欲しい.

入出力の弱さはより深刻かも知れない. SkeTo の入出力は全て普通の fstream で, 並列化されていない. しかし並列計算したいような巨大なデータを二次記憶からシーケンシャルに読むのは 計算時間全体のボトルネックになりうる. 伝統的な HPC のアプリケーションである各種数値計算は メモリに読み込んだ後の計算時間がとても長いから問題にならないのかもしれないが, 並列計算をもう少しお手軽に使おうとするなら 入出力にボトルネックが移ってくるだろう.

ただ, 分散された入出力というのがどんなものなのか, 私にはいまいちピンとこない. 一般的に入出力というのはシーケンシャルだから. MapReduce で使う GFS 強力な仕組みだが 並列入出力という視点で見るとけっこう素朴だ. シーケンシャルでない入出力(ストレージ)として まっさきに思いつくのはデータベース. RDB ほどごっつい必要はないから, Berkley DB みたいなものに分散機能があれば良いのかもしれない. 要は DHT か ... 世の研究者は何か作っているだろうし, そのうちまた見かけたら調べてみることにしよう.

それにしても分散コンピューチングって庶民には試せないのが悲しい. 思えば大学にいた頃は計算機室に山ほどワークステーションが並んでいたのに, それを活用することはなかったなあ. 惜しいことをした. 大学の計算資源をじゃんじゃか使うプログラムを書くのは 学生ハッカーにとって挑戦しがいのある遊びに違いない.

私が計算機室でしていたことといえば, リモートでログインしてビジーループのあるプロセスを動かし SNES エミュレータで遊んでいる学生のを邪魔するスクリプトを作るなど, どちらかというと学生クラッカーっぽいことだったなあ. はずかしいことを思いだしてしまった...

洋書道

当り前だが知らない話は読むのが遅い. AOP のところはけっこう遅かった. RTR はアルゴリズムの説明で悩むと時間がかる. それ以外は平易.