WWW 2012

2本提出予定 (雁瀬君ACS論文誌＋Wikipedia の実験、西井君＋雁瀬君のインクリメンタルグラフ処理)

http://www2012.org/

November 1st, 2011 Abstracts for papers due
November 7th, 2011 Papers due
January 30th, 2012 Paper notifications out

[Graph500] 最適化に向けて

Network Coding や、Stream Algorithms の Lossy Count による最適化。
如何にメモリに載り切らない大規模グラフを扱うか。 スケールフリー性を利用し、記憶装置の各階層に記憶,などなど。

2011年上半期まとめ

最近の新たな論文としては以下の通り。

Yahoo S4 vs. System S: Miyuru & Takeno
Graph500 on TSUBAME: Suzumura & Ueno

もうすぐ7月になり、授業関係で忙しくしていた人も研究に没頭しましょう。上野君は、「クロネッカーグラフのスケールフリー性を利用した頂点配置による性能最適化」を。雁瀬君は インクリメンタル最短路問題を Incremental GIM-V 処理系（西井君開発）上に実装し、評価。
4年生の渡部君は Graph500 の日本語まとめを6月下旬まで。7月から4年生は院試勉強へ。勉強に集中してください。

M2は中間発表が 8/1 なので、それまでに結果を出しましょう。国際学会の論文もそろそろ出さねば。

Top500 - 京1位、TSUBAME2 5位

神戸の京が一位に。

Graph500 の発表も楽しみだ。

[Graph500] 90%

IISWC への論文投稿に向けて、土日のほとんどの時間、書き続け、完成度は90%ぐらいになった。今週の平日は来週からの出張に向けていろいろごたごたしているので、ペースは下がるが、提出できそうだ。

Running Large Graph Algorithms - Evaluation Of Current State-Of-The-Art And Lessons Learned

"Running Large Graph Algorithms - Evaluation Of Current State-Of-The-Art And Lessons Learned"
http://highscalability.com/blog/2010/3/30/running-large-graph-algorithms-evaluation-of-current-state-o.html

LLNL の Andy Yoo のトーク

[Graph500] 論文仕上げ

　今日の目標はデータを差し替える以外はすべて完成させること。

15:00 残りはabstract, イントロ、関連研究の半分、Graph500概要(グラフ生成の部分）

[TSUBAME] Installing MVAPICH2

TSUBAME 上にインストールされている MVAPICH2のバージョンは 1.5.1 と古いので、1.6をホームにインストール
% ./configure --prefix=$HOME/packages/mvapich-1.6 --with-rdma=gen2; make; make install

α版だが、1.7a2 もインストール
% ./configure --enable-smpcoll --with-rdma=gen2

Oprofile

下記、Oprofile の使い方の例。Sleep 時間(プロファイリング取得時間）、CPU イベントタイプ、カーネルのデバッグシンボル（VMLINUX) の場所は適当に変えてください。CPUイベントの種類は "opcontrol --list-events " で確認できます。

#!/bin/bash

if [ $# -eq 1 ];
then
  DIR=$1
else
  DIR=results
fi

if [ ! -e $DIR ];
then
  mkdir $DIR
fi

# sc02 の場合
VMLINUX=/usr/lib/debug/lib/modules/2.6.18-92.el5/vmlinux

#opcontrol --setup --no-vmlinux
opcontrol --setup
opcontrol --shutdown
opcontrol --setup --vmlinux=$VMLINUX
opcontrol --reset
opcontrol --separate=none


opcontrol --event=default
## opcontrol --event=PM_INST_CMPL_GRP1:100000:0:1:1 --event=PM_RUN_CYC_GRP1:100000:0:1:1 --event=PM_INST_DISP_GRP1:100000:0:1:1 
opcontrol --start
sleep 30
opcontrol --shutdown
opreport > $DIR/cycle.out
opreport -l > $DIR/cycle_l.out
#opreport --callgraph > $DIR/callgraph.out
#opreport --symbols > $DIR/symbols.out
opcontrol --reset




[Graph500] IISWC 2011

目標としては明日の早朝までに 1/3 ぐらいまでに仕上げる予定。但し、作業開始時間は午後7時頃から.

The Economist の記事

経済誌に珍しく並列プログラミングに関する記事が掲載.
http://www.economist.com/node/18750706

[Graph500] Code reading

　渡部君、上野君が頑張っていますが、Graph500のリファレンス実装の中身が段々と分かってきました。直近のワークとしては、性能特性を調べることですが、「クロネッカーグラフの特性を活用した頂点配置を実行し、通信最適化による性能向上を達成する」が一つの研究テーマになるでしょう。

論文

IISWC に向けて、まずは上野君の GPU Task Parallelism の論文はあと少し。13日(月)にやれば終わるでしょう。

もう一本は、System S vs. Yahoo S4. 締切りが1週間延びたので、Linear Road Benchmark まで評価アプリケーションを増やせると論文としては強くなるでしょう。論文の主張ポイントをもう少し強くしないと駄目。

国内の学会の方は、白幡君が精力的に Mars 上での GIM-V を実装して、PEGASUS と評価している。こちらの方の締切りは24日(金).

あと、雁瀬君のACS 論文の英語化を。学会は7月締切りの ICDE などがターゲットでしょうか。

松浦君の APU もまずは一区切り評価を取って、国内の学会に出すべきでしょう。

[TSUBAME] Ganglia

各ノードのモニタリングページ
http://ganglia.g.gsic.titech.ac.jp/ganglia/

[TSUBAME] 利用ガイド

利用手引き。MVAPICH などの各種ソフトウェアのガイドなどが少し書かれているらしいです。
http://tsubame.gsic.titech.ac.jp/user-guides

Current status

最近、様々な仕事が舞い込んできており、鬼のように忙しい日々が続くのだが、急遽講演のため6月下旬に韓国。7月前半はUSに。そんな中、嬉しいニュースもいくつか。昨年やっていた某通信事業会社へのストリームコンピューティングを基盤にしたシステムの稼働が本格的に始まり、イチローがコマーシャルで宣伝している。雁瀬・上野コンビの論文が某論文誌に採択されたのも大変喜ばしい。

IISWC の方は、Miyuru君、竹野君が奮闘してくれているので、なんとか Submission まで辿りつけるだろう。Graph500 に関しては、是非 IISWC と思っていたが、他のタスクのバランスを考えると厳しい。雁瀬君、上野君の論文も英語化するべきだろうが、ICSOC 2011 も考えられるが、それも締切りが来週。もう少し学生もそろそろ主体的に英語の論文を書いていくべき時期だろうが、こればっかりは本人の努力がものを言う。頑張ってほしい。

[ExaGraph] SGRACE: Streaming Graph Clustering Algorithm

LLNL (Lawrence Livermore National Laboratory) の研究者 Andy Yoo による大規模グラフ解析に関する研究

Evaluating Use of Data Flow Systems for Large Graph Analysis, Andy Yoo
http://dsl.cs.uchicago.edu/MTAGS09/a05-yoo-slides.pdf

A New Benchmark For Evaluation Of Graph-Theoretic Algorithms, CORR2010
Parallel Generation of Massive Scale-Free Graphs, CORR2010
Scalable Analysis of Massive Graphs on a Parallel Data Flow System, HICSS2010


Google での講演: http://www.youtube.com/watch?v=PBLgUBGWcz8

[ExaGraph] Graphs and HPC: Lessons for Future Architecture

Graphs and HPC: Lessons for Future Architectures, Bruce Hendrickson (Sandia)

http://science.energy.gov/~/media/ascr/ascac/pdf/meetings/oct08/hendrickson_ascac.pdf

Cray のアーキテクチャに偏ったスライド. BlueGene/L との比較も少しあり。

グラフ解析問題の特徴
Runtime is dominated by latency
Potentially random accesses to global address space
Perhaps many at once, but parallelism is fine-grained
Essentially no computation to hide memory costs
Access pattern is data dependent
Prefetching unlikely to help
Usually only want small part of cache line –
levels of memory all Potentially abysmal locality at hierarchy

以上のグラフ解析の要件を満たすアーキテクチャ
Low latency / high bandwidth for small messages!
Latency tolerant
Light-weight synchronization mechanisms
Global address space
- Obviate the need for partitioning –
- Avoid memory-consuming profusion of ghost-nodes –
- No local/global numbering conversions –
- Support fine-grained parallelism –
- One machine with these properties is the Cray MTA-2, XMT

[Graph500] Scalable Graph Exploration on Multicore Processors

必見。これは非常に良い論文だ。TSUBAME上でも検証すべき。
Scalable Graph Exploration on Multicore Processors, David Bader と Watsonチーム
http://www.cc.gatech.edu/~bader/papers/ScalableGraphMulticore-SC10.pdf

外部記憶装置を用いたグラフ探索

External Memory Breadth-First Search with Delayed Duplicate Detection on the GPU

We accelerate breadth-first search by delegating complex operations to the graphics processing unit (GPU). The algorithm exploits external memory: if the state space becomes too large to be kept in main memory, it is maintained I/O-efficiently on disk.
As in many other approaches for external memory graph search, we apply delayed duplicate detection. The search proceeds in breadth-first layers with increasing minimum distance from the start state. For each layer stored on disk, we load chunks into the systems memory, which are forwarded to the memory on the graphics card. Here we test if outgoing transitions are enabled and generate all successors. Finally, we eliminate duplicates delayed by sorting on the GPU. Even facing the overhead of I/O access, noticeable overall speed-ups are obtained.

並列幅優先探索 - level-synchronized BFS

Graph500 のリファレンスコードに使用されている BFS の並列化アルゴリズム。以下、Cray 及び BlueGene/L のアーキテクチャに向けた改良アルゴリズムの提案。

Desigining Multhreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2, David Bader

A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L, Andy Yoo

Parallel Boost Library

http://www.boost.org/doc/libs/1_41_0/libs/graph_parallel/doc/html/breadth_first_search.html