2011.04.27(Wed.) 全体ミーティング メモ(+α)

今後の全体ミーティング

1回につき2人、1人あたり30分

良い論文を書くために

客観的な定量的評価、定性的評価

• マイクロベンチマーク
• 実アプリケーションによる評価
• マジックナンバーは3 (3種類のアプリケーションで評価)
• プロファイリングも重要 (oprofile, vmstat, ...)

論文はわかりやすく (異分野の人が読んでもわかるように)

• SACSISに採択された論文の書き方を参考に

ベースとなる手法自体はシンプルでも、十分な評価が行われていれば良い研究となる。

SACSIS 2011

1人2本、聴講してまとめて後で発表する。
(題目が他の人と被らないように、要相談)

Activity

• 大規模グラフストリーム処理(ganse, ueno)
• インクリメンタルグラフ処理(ganse,nishii)
• APU ストリームコンピューティング(matsuura)
• StreamScale/ElasticStream(miyuru,ueno,takeno,ishii)
• Automatic Optimization(miyuru)
• Graph500(watanabe,ueno)
• GPU グラフ処理(shirahata, ueno)

(グエンさんについての確認を忘れた)

助言教員

GWの予定

その他

投稿する論文の校正を、提出1日前などぎりぎりになってから出さないように。早めにすること。

全体ミーティング以外のメモ

データストリーム処理に向いたグラフアプリケーション

• k-means (クラスタリング)
• PageRank
• 最短路問題

リアルタイム処理の分類

• ハードRT
• ファームRT
• ソフトRT

CDR

IGIMV (DE版) バグ？

snk_managerに謎の出力が入る．バイナリファイル扱いされる．
stop_stream せずに連続して submit_stream cancel_stream を繰り返していると生じる？
igimv の方ではなく，gimv の方で生じている？

see:
/nfs/home/nishii/streamgraph/igimv/proto3/gimv/data/result_de_e-5/result-050-3
/nfs/home/nishii/streamgraph/igimv/proto3/gimv/data/result_de_e-5/result-050-4
など

StreamGraph(Incremental GIM-V) 現状と今後の方向性

Incremental GIM-V(以下、IGIMV)の現状としては、一応SPADE+UDOPで実装したものがあるが、これには以前の記事(Incremental GIM-V デバッグ中)に記したとおり、オペレータ（プロセス？）のタプルバッファによりデッドロックに似た現象が生じ、ある程度以上の数の辺を含むグラフを正常に処理できないという問題がある。
これを解決するために、作業オペレータを二種類に分割するよう実装する予定である。

実装から離れて、IGIMVの研究的な意味での貢献を考えてみる必要もある。現状では、Incremental PageRank(以下、IPR)の手法をPEGASUSのグラフ計算モデル(GIM-V)に当てはめようとはしているが、これが本当に効果的であるかは自明でない。PageRankへの有用性は、当然IPRの論文で触れられているが、それ以外についてはどうなるのか。
このあたりをはっきりとしないと、研究としての貢献が主張できない。

あまり計算モデルの一般化ということを考えずに、PageRank「など」のグラフ構造解析をストリーム的に効率的に行う、という方向で研究を進めるのはどうか、と考えている。

まず、元々のIPRは、データストリーム処理のための手法ではなく、バッチ処理を効率的に行うためのものであり、IPRはActual PageRank（全体を解析する手法）と同様の、「正しい」解析結果を得られる手法である。
ストリーム的には、このIPRのように完全な解析を行うのではなく、計算の範囲を構造変化から近い頂点（距離2,3程度？適切な距離はその頂点のページランクにも依存？）に限定して行い、完全な解析はバッチ処理(IPR)に任せる、などというのはどうだろうか。

ストリーム的に行うために、オンメモリ性を考える必要もある。頂点や辺のデータはファイルシステム上に保存しておき、計算に必要のないデータはメモリにロードしないようにする。

======

いずれにせよ、FIT(4/21〆切)までに貢献のある論文の形まで持っていくことは難しいような気がする……。
頑張って書こう！
Incremental GIM-V は、グラフ処理としても制限がきつく、データストリーム処理としてもまだ高速化（簡略化）の余地のある手法だけど、プロトタイプとしての提案である、という方向性で書く。

Incremental GIM-V は本当に有用なのか

Incremental PageRankが有用な手法であるのは、ウェブグラフの構造が、一部が変化してもそこから波及する範囲が狭いからである。

The key observation is that evolution of the Web graph is slow, with large parts of it remaining unchanged.
(Incremental Page Rank Computation on Evolving Graphs)

Incremental MethodをGIM-Vに一般化した場合に、それで適応できるアルゴリズムの実データが、実際にこのような性質を持っていない限り、大した効果がないのではないか。

論文にすることを考えるならば、Adaptive PageRank, Incremental PageRankなど、なぜ提案手法が有用であるのかセクションで述べているので、Incremental GIM-Vの場合でも、この手法を一般化しても有用であることを示す必要があるように思える。
それができないと、論文としての貢献が主張できない。
(PageRankだけ評価しても、それではIncremental PageRankの貢献およびPEGASUSの貢献を超えることができない)

SPADE:Stream Loop に関する注意

SPADEでUDOPを挟むループを記述することは可能。
ただし、あるループに含まれるオペレータのすべてが同一プロセスエレメントに含まれる場合、
正常に動作しなくなるらしい。

ループを構成するストリームの出力 submit0(), submit1() などを実行すると、そこで処理が止まってしまう。

対処法としては、適当にプロセスエレメントを分けるようにすること。
もし、同一のUDOPへのループを記述したい場合は、間に適当なFunctorを噛ませればよい。

Incremental GIM-V デバッグ中

igimv/proto3

submit_stream, ctcp_trigger.pyを実行
⇒ WorkerのprocessInput1 (stage==1) で、最初のmessageWW実行の後、処理が止まっている？

(追記)
PE の fusion を分けたらうまく動きそう。

(追記2)
4頂点5辺からなるグラフで、ページランクの計算に成功。

TODO:
・Managerの出力をみると、どこかでエラーが生じているらしい？要確認
・インクリメンタルに動作するかチェックする

(追記3 : 20110404 Mon.)
>Managerの出力をみると、どこかでエラーが生じているらしい？要確認
switch 文で break の書き忘れ。ログが冗長になるだけだったので、大した影響はなかった。
>インクリメンタルに動作するかチェックする
できた。

TODO:
・大きなグラフで実験（人工データ？作り方は、恣意的なものでよい？）
・igimv.dps をもとに gimv.dps を作成。動作比較

(追記4 : 20110404 Mon.)
頂点数10K, 辺数 448Kのグラフを、ワーカーノード4台で実行したところ、処理ができなかった。

理由を推測してみると、UDOPからUDOPに送るタプルが多すぎて、バッファが「デッドロック」のような状態に陥っているものだと思われる。

各Worker UDOPは同時に処理を開始し、一度の処理ブロックで最大で辺の数と同数のタプルを送る。
このとき、UDOPが送り先のオペレータの入力バッファが一杯になると、これ以上タプルを送れないので、バッファに空きができるまで待とうとする。
しかし、タプルを受け取ったオペレータはバッファの処理を行うことはない。
なぜならば、受け取った側のオペレータもまた、他のオペレータにタプルを送ろうとしている段階だからである。

===
MapReduceでは、MapとReduceが別スレッドで実行されている。
現状のigimv.dpsでは、Mapに相当する部分も、Reduceに相当する部分も、一つのUDOPにまとめてしまっているので、分けてしまうことで解決できるかも。