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

[Exa] ロードマップ作成開始

　明日からエクサに向けた様々な研究領域（アルゴリズム、アプリケーション、システムソフトウェア、プログラミングモデル、アーキテクチャ）におけるロードマップ作成が始まります。SACSISの続きで、秋葉原で行われます。

国際的にも, 類似の会議が IESP (http://www.exascale.org/)で行われており、日本からも参加していますが、我々の研究室のようにシステムソフトウェアに従事するものはこのような動きの把握は重要です。企業ではこのようなトップダウンの戦略策定は毎年のように行われ、それが実際の研究開発プロジェクトにブレークダウンされるわけですが、企業とアカデミックの差は、そのブレークダウンしたプロジェクトの成果物を厳密に管理し、成果が振るわないプロジェクトはどんどん切っていくことでしょう。アカデミアでは、産業界におけるスピードの速さには勝てると思わないので、より目の前の利益だけに左右されないように、企業ではできない中長期的に解決すべき本質的な研究課題に取り組むべきかと思います。

[ElasticCloud] SACSIS 2011 石井君発表終了

　石井君、お疲れ様でした。次は CLOUD 2011 での英語発表ですが、頑張りましょう。

Network Design Problem

　最大フロー問題の前提は、ある頂点に着目したときに頂点の流入量と流出量は等しくなければならない。ただし、ストリーム処理においては、フィルタリング等あるので、基本的には流入量に対して流出量はある割合で小さくなる。ある頂点同士を結ぶ容量（バンド幅）が決まっており、最大フロー問題のように、ある頂点から複数の頂点に分岐して流すことも許す。また、複数のストリームプログラムが走っており、各ストリームプログラムを構成するオペレータの間引き率は決まっているとする。また、フローネットワーク（容量が決まっている）も事前に与えられるものとする。このような前提が与えれたときに、走らせられるジョブ（ストリームプログラム）の最大数を求めよ、というのが問題。間引き率が 1 のときは Network Design Problem として知られており、NP-Hard. 但し、当然、ネットワークが小さいときにはヒューリスティックが知られている。上記の問題はNetwork Design Problem よりも難しいので、NP-Hard. もし実用上問題なく動くような手法が考案できれば、我々の領域では新規性が高いだろう。

Graph500 Code Reading 第1回目

第1回目終了

GNU GLOBAL

ソースコードにタギングするツール GNU GLOBAL
現在、 C, C++, Yacc, Java and PHP4をサポート。

http://www.gnu.org/software/global/

Top500 の変遷の視覚化

http://www.top500minder.net/

[StreamGraph] インクリメンタル最短路問題

- On Dynamic Shortest Paths Problems
- Dynamic Shortest Paths Minimizing Travel Times and Costs
- http://www.science20.com/chatter_box/blog/shortest_path_problem_dynamic_network

[StreamGraph] 小規模行列に対する SVD の応用例

国際会議 IISWC のストーリー立てに関する続き。一つの concern は、ワークロードとしての汎用性が重要となるが、ストリームアプリケーションのワークロードに共通な行列計算として 小規模な行列に対する SVD 計算が様々な応用に使えるという主張をする。SST はもちろんだが、その他にも例が必要。画像特徴抽出などは典型的であるが、いくつかの論文を参照する必要がある。少し調べてみよう。

A fast SVD based video watermarking algorithm compatible with MPEG2 Standard
http://www.columbia.edu/itc/applied/e3101/SVD_applications.pdf

続きは後ほど

[ExaGraph] 大規模グラフ解析ベンチマーク Graph500 の性能特性

Target Conference: IISWC 2011

[Title]
Performance Characterization of Graph500 on a distributed-memory based Supercomputer

[Abstract]
Graph500 has emerged as a new benchmark of ranking supercomputers with the motivation that large-scale graph analysis is becoming greatly important application. It is well studied that Graph algorithms are suitable for shared-memory based supercomputers such as Cray XMT. Recent trend of Linpack-based supercomputer ranking shows that heterogeneous and distributed-memory based supercomputers with tremendous amount of GPGPUs greatly achieves top-ranked performance score. However, the performance characteristics of large-scale graph analysis like Graph500 on such a distributed-memory supercomputer has not yet been well investigated. This paper shows thorough study on the performance characteristics of Graph500 using 4th-ranked supercomputer, TSUBAME.