論文斜め読みの記事もここに乗っけてこうかな。斜め読みなんだけど、斜め読み以上のことはしないと思うので。

さて、これは先月やっていたFAST15の論文で、なんとなくタイトルに惹かれて最初に通勤電車で読んだもの。全部の論文をまとめてEPUBで配布してくれるのがありがたいですよね。まあ気になったものはもっと読んでこうと思ってはいますが、どこまで読めるかは分からない。

ひとことで言えば、グラフの処理をSSD Arrayをうまく使ってやった話。全体的には、さすがにFASTだけあってよく書けていると思った。文章も読みやすいと思う。

まあ一般的にはSSDで性能が足りればSSDに置いたほうが数倍安くなる。これまでのシステムはメモリ分散派とディスクI/O何とかする派があったわけだが、中間を狙うことになる。単にディスクI/O派のディスクをSSDにしたり、メモリ派でスワップをSSDに置いたというのとは異なるところをどこまで見せられるか。このシステムではノード情報をメモリに置いてエッジ情報をSSDに置いた。そこがキモっぽい。使ったテクニックがいろいろ書いてあって面白い。

例えば、このシステムはSAFS(Set Associative File System)というuserlandのFSを使っている。これは並列性を稼ぐためかな。SAFSの詳細は良く分からない(別論文)が興味深いのは事実なので、SAFSのやつは次に読む論文リストに入れておこう。で、XFSの書き込み時のロックのせいで並列性がうまくいかないケースというのがあって、それを解決するには云々、みたいな話もある。

使ったマシンは4ソケットのXeon(2.2GHz, 合計32コア)に512GBのメモリ、それに3つのHBAをつないでOCZのSSDを15台くっつけている。ベンチマークは、、、

• 幅優先探索(BFS)
• Betweenness Centrality(BC)
• PageRank(PR)
• Weakly connected components(WCC)
• Triangle Counting(TC)
• Scan statistics(SS)

といったもの。当然ながら、性能は良好というグラフが誇示されている。グラフDBにあまり詳しくないのでこのチョイスが妥当なのかはよく分からないけど、たぶんまともなんじゃないかと直感的に思う。グラフ系の理論も抑えておきたいなぁと昔から思ってはいるんだけど…

そこそこ大きいデータセット(タイトルにもなっているbillion nodes)を使っていて、最適化もけっこう頑張って性能を出しているみたいな感じ。ソースもgithubに置いてある。Rから使えるようになってるみたいですね。