研究テーマ

以下、新規の研究テーマ
- BC (Betweenness Centrality), PageRank 等のグラフ処理を 高生産性並列言語 X10 を用いて実現し、超並列分散計算機システム(TSUBAME等) 上での性能評価、性能最適化を行う
- 外部記憶装置を用いた超大規模グラフ処理の実現

[StreamWeb] StreamTwitter デモ(日本語版)

日本語版StreamTwitterのコア部分のソースのディレクトリ
/nfs/home/oiki/spade/uryu/japantwitter

起動の仕方. まずrootで
/nfs/home/oiki/web/webserverの
./core.py
でWebサーバーを起動

次に
/nfs/home/oiki/spade/uryu/japantwitterの
./start_streams_streamtwitter.sh ; ./submitjob_streamtwitter.sh
でSystemS部分を起動

終了は./stop_streams_streamtwitter.shを実行し, core.pyをkill

Multithreaded Asynchronous Graph Traversal for In-Memory and Semi-External Memory

Multithreaded Asynchronous Graph Traversal for In-Memory and Semi-External Memory, SC2010

STING: 動的グラフの可視化

Spatio-Temporal Interaction and Network Graphs - an open source dynamic graph package for Intel Platforms, David Bader

仮想化環境における HPC Challenge Benchmark の性能評価

仮想化環境における HPC Challenge Benchmark の性能評価
Evaluation of the HPC Challenge Benchmarks in Virtualized Environments, ICL, 2011
http://icl.cs.utk.edu/news_pub/submissions/vhpc2011_ehbve.pdf

[Papers] Other Papers on Data Deluge

2020 Computing: Science in an exponential world
Data management in the worldwide sensor web

Apache Hadoop Goes Realtime at Facebook (SIGMOD2011)

以下、今年の SIGMOD 2011 で注目されている論文。必見。
http://borthakur.com/ftp/RealtimeHadoopSigmod2011.pdf

"The Data Deluge"

http://www.economist.com/node/15579717

[StreamWeb] デモの起動方法

demoにログイン.

StreamTwitterのコア部分のソース: ~oiki/spade/uryu/streamtwitter
Webサーバーのソース: ~oiki/web/webserver

[System S の 起動方法]
~/oiki/spade/uryu/streamtwitterの
% ./start_streams_streamtwitter.sh ;
%./submitjob_streamtwitter.sh
でSystemS部分を起動

[Web サーバーの起動]
% cd ~oiki/web/webserverの
% ./core.py


[停止方法]
% /stop_streams_streamtwitter.sh
- core.pyをkill

以下、老木君によるプログラム解説


streamtwitter.zip : System S 部分
web.zip : Webインターフェイス部分

プログラム間の通信は以下の流れで行われる。
1.ブラウザからWebインターフェイス。新しく補足する単語の指示や、単語の要求命令などが送られる。
2.WebインターフェイスからSystem S。新しく補足する単語の指示が送られる。
3.System SからWebインターフェイス。ポストデータが送られる
4.Webインターフェイスからブラウザ。ポストデータが送られる

streamtwitter:
streamtwitterにはSystem S関連のdpsファイルやソースファイルなどが含まれる。
streamtwitterの設定は以下のように変更する。

1.streamtwitter.dpsを変更する
nodepoolを変更することで配置するノードを変更したり、#define HTML_SERVERを変更することでWebインターフェイスを担当するノードを変更する

2.src/config.hを変更する
大量の#define文を変更することで細かい設定を変更できる。
重要なものとして、
GEOMETRY_FILE 経度・緯度変換情報を格納したファイル
COMMAND_PORT 通信2を受け取るポート

web:
webには３つのプログラムが含まれる。

・streammaker
Twitterのふりをするダミーサーバー。負荷テストに、用いる。これについては詳しく説明しない。

・html
Webサーバーによって公開されるフォルダ。現在のディレクトリは ~oiki/web/mimemapper/
index.htmlを代表とする画像やページやjavascriptが格納されている。
設定を変更するには、主にcore.jsを変更する。core.jsには設定用の変数が先頭で宣言されており、
periodtime : 通信4の頻度を設定する
zoom,centerpos : 地図の縮尺、場所

・webserver
Webサーバープログラム。apacheのように静的ファイルを外部に公開する機能と、SystemSからポストデータを受け取り、ブラウザからの要求に応じてそれを送信する機能を持つ。
設定はserver.confを変更することで行う。
html_base : 公開するフォルダ
html_port : 通信1を受け取るポート
post_port : 通信3を受け取るポート
server : System Sが起動しているノード
command_port : System Sが公開しているポート

またwebserverフォルダに含まれるCommander.pyを実行することで、ブラウザを用いることなく監視する単語を追加できる。
./Commander.py word といった風に用いる。
細かい使用法は-hオプションを参考にしてください。

起動手順:
start_streams_streamtwitter.sh,submit...を用いてSystem Sを起動し、webserver/core.pyを起動する。
なお、順番を気にする必要は無い。

補足：
かつてのバージョンでは場所によって、1時間中どれぐらい特定のキーワードが用いられたかを集計する機能が存在したが、InfoSphereStream1.2において、Aggregateオペレーターがtimebasedな場合、perGroupを用いることができなくなったため、現在は機能しない。

バグ：
長時間プログラムを実行させると、WebインターフェイスがSystem Sからポストデータを受け取るのに遅延が発生しはじめる。1時間あたり3分ほど？

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