2010年09月30日

HLPP参加記

HLPP参加記。例によって辛口。

Dr.Hu 招待講演(NII)

  • 電車を一本逃したので途中から参加。USの列車に期待してはならない。
  • Homomorphismを使ってプログラムをバリバリ変換するお話。
  • 変換のために便利なのがweak inverse. この手の変換をするには逆関数が非常に重要。
  • 全単射ではないので変換結果が正しくなるような関数群のうちの一つを使う
  • Non-trivialな問題をMap-reduce型とかに変換できる。


J. Enmyren. SkePU Multi-GPU programming library

  • SkePUというマルチGPUのskeleton programing library. 話者はSkeep-youと発音。
  • 関数をマクロで定義する。 BINARY_FUNC(plus, double, a, b, return a + b;) みたいに。
  • 普通のスケルトン並列ライブラリ。新しいところはMulti-GPUサポート。
  • 実は時間を一番食うのはHost-GPU間のデータ転送。メモリ転送をlazyに実行することで隠蔽するよう頑張る。
  • 実例: ODEソルバ。手書きCUDAと比較して10%程度のオーバーヘッドで計算。
    www.ida.liu.se/~chrke/skepu
  • 質問: Non-uniform memory accessにどうやって対処するつもりか?
    本人は問題を把握しているようだが、回答がよく分からなかった。今回はGPUで扱いやすい問題をメインに扱うから問題ない?


K. Matsuzaki. Lessens from Implementing the BiCGStab Method with SkeTo Library

  • "Real application experience report".
  • Sparse matrixの形状が決まっている。高速な計算が可能か?
  • SkeTo はC++/MPIの普通のskeleton並列ライブラリ。
  • SkeToはC++のテンプレートを大活用してskeletonを融合する。ループ操作を纏めるとかそう言う感じ。
  • 知見: flexible data reallocation / shiftはライブラリ内でサポートしておくべき。
  • stencilで分解するとfusionが足りないので自力でoptimizationを色々やる必要がある。今回はmanual fusionしたけど本当はライブラリでやって欲しいよね
  • データのコピーオーバーヘッドが問題に。今回はsmart pointerを用いてコピーを節約するようにSkeToを改造


O. Lobachev. Estimating Parallel Performance, A Skeleton-Based Approach.

  • "Parallel penalty" の計測を考える。T(n)/p + A(n, p)
  • A(n, p)を計測して実際に掛かる時間を予測する
  • Amdahl's law に近いが単純に/pするだけじゃなくて、Divide & Conquerの時とかはコスト関数の和を真面目に考える。
  • どんな関数で補外するのが良いかも調べる。


BSP-WHY

  • Loop invariantとかを表示することでBSPのプログラムをverify.
  • 並列を直列実行でシミュレート。
  • 要はCPU1台でマルチタスクのプログラムを走らせたと思えば。
  • モデルがBSPだから確かに何とかなる気がする。
  • 並列をfor proc in 1..p の形のループにしてしまう。
  • loop variant / invariantをannotationとして入れる。
  • いろんな証明器に対応。あるinvariantが1つのプログラムで証明できなくても他の証明器で証明できるかが調べられる。
  • 質問: annotation必要なのはどーよ? Loop終了の判定とかは全自動で出来ないの?
  • 質問: ループの順番を変えても大丈夫であることはこの方法では証明できないのではないか?
  • 質問への回答は聞き取れず(French-Englishは非常に辛い。。。)


SymGrid-Par:

  • Computational Algebra (Mathematica etc.)のparallelization
  • socket経由で分散計算して回収したい。
  • 問題点: この並列はdynamic(コンパイル時にタスクサイズが決まらない)でかつ並列度がタスクごとに大きく異なる
  • Parallel Haskellバックボーン
  • 中身はよくあるskeleton並列
  • prefetch付きのidiomを導入。prefetchにより遅延を隠蔽するなど。


Parallel Greedy Graph Matching

  • Maximum cardinality matchingを考える。
  • Greedy algorithmをどう並列にするか? "find Best" "add edge" "remove edge" ... なんか並列化しづらそうですよ?
  • Karp-Sipser algorithmを実装。意外とどうにかなるものである。
  • Vertex based distribution (1D distribution) / Edge based distribution (2D distribution)
  • BSP based parallel modelling。BSPはうまく実装するとちゃんとロードバランシングできるらしい。。。
  • 確かに、待ち時間を調べてメッセージ交換すると出来るような気がする。
  • ユースケース紹介だが、得られた知見はmatching問題特有のもので今ひとつよく分からず。


Hybrid Bulk Sychronous Parallelism Library for Clustered SMP Architectures

  • BSP modelのライブラリ in C++ (BSML (gava:09) のObject-oriented versionC++)
  • C++ lambda support
  • BSP_SECTIONで開始。ま た マ ク ロ か !
  • BSPは(まぁ当然ですけど)OpenMPに比べて8倍ぐらいsync速度が遅いです
  • Hybrid BSP: 同じコードでMPI / OpenMP.
  • OpenMPはsyncのコストが問題に。False sharingが起きるとMPIの方が早いケースも。。。
  • 割と試してみたいと思う。が、C->C++以上の新奇性は?


全体感想:

  • 率直な外野からの感想からすると割とショボい。
  • 何がショボいかというと色々あるんだけれど、同じようなアプローチを同じようにみんなで実施して同じような問題を抱えているようにしか見えない。Eccentricな提案がない。
  • 計算のモデルが計算機に合わなくなってきている。今では計算そのものよりも通信やメモリ領域などがネックになりつつあるのに、そういう計算モデルを持ってきた人は皆無で、現在のHPCの人たちの問題意識などと著しく解離しているなーという気がする。かといってpost map-reduce型の計算を何か模索しているのかと思うとそうでもない。
  • つまり現実にも適合してなければ理論的に現実の先や現実にないマシンを見ているわけでもない。
  • 割とこの分野は熱的死に陥ってないか。今のやり方は過去(Flat parallelism; Map-Reduce; Calculation cost > memory transfer cost)に合わせているだけである。未来どころか現在にすら合っていない。
  • 新しい血が必要という感想。

posted by chun at 00:30| 日記