xhl list - 昏論会ウィキ

Kotha+ 2010 (MICRO 43): "Automatic Parallelization in a Binary Rewriter"

http://portal.acm.org/citation.cfm?id=1934997

x86バイナリコードを自動並列化します。

• ターゲットベンチマークは行列積とかのloop intensive/regular accessな奴。
• 実装上はLLVM IR経由。
• 使われているのは古典的なDependence Testingで、論文自体の主眼はsourceではなくbinaryからどのように必要な情報を抽出するか。

読んだ感じでは、

1. induction variableの検出とかはbinaryでも大体できるので、loop variableの検出、for(int i = 0; i < n; i ++) for(double *p = &A[i][0]; p < &A[i][m]; ++ p) *p = hoge; 的なループとアクセスパターン検出はできる、という感じらしい。
2. Alias Analysisは、たとえばセグメントが違うとか(!)、実行時に簡単にaliasテストができるなら実行時テストして「Aliasありの場合」と「Aliasなしの場合」で分岐するとか、そんな感じ。
3. scalar variable上でのdependenceもある程度見切る模様

性能は結構出てる。多くのベンチマークでsourceから自動並列化するのと同じくらい。理由としては

• single threadでも性能が元の0.9倍以上がほとんど(>0.95とか>0.99もかなり多い)ので、 binary->LLVM->binaryによるオーバーヘッド自体もかなり少なさげ。
• たぶんinputはsingle thread限定で、別のスレッドが何かアクセスするとかは考えてない感じ。
• covarianceベンチマークは配列がlinearlizeされてるから2次元配列解析できるsource levelにくらべ性能が出てない(というか並列化して速くなってない)と書いてあるけど、まぁこれはbinaryの問題じゃなく今回用いた Dependence Testingのせい。
• binaryだったから何か本質的なことを解析できなくて並列化できなかったとかはないのかな?
• ぱっと見あまりたいしたことやっていない気がするけど、つまり情報自体はbinaryからでも割と楽に取れるということなのかな。変態的binary hackとかにはたぶん対応してないとかはあるんだろうけど。