2011年4月27日水曜日

[StreamGraph] Incremental Graph Algorithms

インクリメンタルなグラフアルゴリズムに関する論文(一部)

Incremental Single Source Shortest Path (SSSP)
http://www.springerlink.com/content/y03426g56jl72732/

An Incremental Algorithm for a Generalization of the Shortest-Path Problem
Bounded Incremental Single Source Shortest Path

Fast Incremental Minimum-Cut Based Algorithm for Graph Clustering

Study Community Dynamics with an Incremental Graph Mining Algorithm

Parallel Incremental Graph Partitioning

On-line Hiearchical Graph Drawing





2011年4月22日金曜日

[StreamWeb] StreamWeb の論文が ICWS 2011 に採択されました

国際学会 ICWS 2011 (9th International Conference on Web Services) に出していた以下の論文が採択されました。採択率は 11%でした。

"StreamWeb: Real-Time Web Monitoring with Stream Computing" Toyotaro Suzumura and Tomoaki Oiki, ICWS 2011, Washington DC

道路ネットワークデータ

http://www.dis.uniroma1.it/~challenge9/download.shtml

[Graph] William Cook

TSPで著名な William Cook 氏のページ http://www.tsp.gatech.edu/index.html

グラフ生成モデル

Jure Leskovec らによる研究
  • Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, by Jure Leskovec, Jon Kleinberg, Christos Faloutsos, ACM KDD 2005
  • Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication, by Jure Leskovec, DeepayChakrabarti, Jon Kleinberg and Christos Faloutsos, PKDD 2005
  • Scalable Modeling of Real Graphs using Kronecker Multiplication, by Jure Leskovec and Christos Faloutsos, ICML 2007
  • Graph Evolution: Densification and Shrinking Diameters, by Jure Leskovec, Jon Kleinberg and Christos Faloutsos, ACM TKDD 2007
ICML 2009 のチュートリアル

2011年4月20日水曜日

演習課題 - Elastic StreamScale

石井、鈴村の「Elastic Stream Computing with Clouds」のアイデアを StreamScale 上でシームレスに実装し、性能評価を行う。

竹野君 ToDo
(1) 石井君の work 理解 --> "SACSIS 2011 論文とスライド読み”, 実験の再現
(2) Yahoo S4 理解(コードと論文)
(3) StreamScale のコード理解 (5/11 18:00 - )
(4) StreamScale の再設計と実装 (竹野、上野、鈴村で議論)
(5) 上記 Elastic Stream Computing のアイデアを StreamScale 上に実装

以上です

新メンバー演習課題 (2)- Yahoo S4 で 高速CDR 処理を実装

[演習課題]
- オープンソースの処理系 Yahoo S4 上で VWAP 及び CDR 処理を実装する。
- Yahoo S4 に関するシステム概要についてまとめる
- System S との性能比較、定性的なプログラミングモデル比較を行う。

[Yahoo S4 に関するサイト、論文]
サイト:http://s4.io/からコードをダウンロード。インストールしダウンロード。
論文:http://labs.yahoo.com/files/KDCloud%202010%20S4.pdf
必要に応じて Zookeeper や Spring フレームワークの文献を参照すること

[System S の VWAP 処理、CDR処理のコード]
- スケーラブルな VWAP アプリは松浦君に聞く (松浦君がインターンで最適化したコード)
- CDR 処理アプリ(簡易版)は Miyuru 君に渡したので聞く

[発表スライドにまとめる内容]
- Yahoo S4 に関する詳細な解説 (ソフトウェアのアーキテクチャ、プログラミングモデル、実行方法)
- Yahoo S4 と System S の比較(アーキテクチャ、プログラミングモデルなど)
- CDR と VWAP の定量的な性能比較 - スケーラビリティ、ボトルネック解析

新メンバー・演習課題(1)- Graph500

Graph500 に関する以下の論文を読み、なるべく詳細に PowerPoint にまとめよ。
http://www.graph500.org/
http://www.graphanalysis.org/benchmark/HPCS-SSCA2_Graph-Theory_v2.1.pdf

Graph500 のリファレンスコード を理解し、鈴村研究室の計算機環境上(sc4台) で実行。TEPS値を求めよ。

また、以下の STINGER の論文も読むこと
http://cass-mt.pnnl.gov/docs/pubs/pnnlgeorgiatechsandiastinger-u.pdf

2011年4月14日木曜日

Status

4/14 時点での研究室メンバーの論文投稿予定のまとめ

石井君→ SACSISカメラレディ投稿完了 / IEEE Cloud 2011 カメラレディ投稿完了(4/15予定)
雁瀬君・上野君→ ACS 論文誌第2回判定用論文投稿完了(4/14 予定)
上野君→ 高データレート FIT 査読付き論文(4/21締切り), GPUタスク並列(ACS論文誌 5/11)
西井君→ FIT 査読付き論文 (4/21 締切り)
Miyuru君→ IFIP Performance (4/20 締切り)
白幡君(松岡研)→ SACSIS 2011 Poster (4/15 締切り)
松浦君→プロトタイプができ次第投稿

以上

SOCC

SOCC: ACM Symposium on Cloud Computing
http://socc2011.gsd.inesc-id.pt/
Submission Deadline: April 30, 2011
Acceptance Notification: July 11, 2011

2011年4月11日月曜日

[StreamGraph] Incremental Graph Processing 関連

Studying Community Dynamics with an Incremental Graph Mining Algorithm
http://www.tanjafalkowski.de/downloads/FalBarSpi08.pdf

Incremental Graph Matching for Situation Awareness
http://isif.org/fusion/proceedings/fusion09CD/data/papers/0341.pdf

[Info] Watson

今週土曜日4月16日の0時(金曜深夜)より、NHK教育TV「サイエンスZERO」が2回にわたりWatsonを特集するようです。 http://www.nhk.or.jp/zero/schedule/index.html

新メンバー演習課題

第1回目演習
期間:4月11日〜5月11日
成果発表会:5月11日の夕方発表

[メンター]
- 渡辺君(B4) →上野君(M1)
- グエン君→ 雁瀬君 (M1)

[研究室環境整備]
- 研究室アカウント作成/SSH鍵作成、OS(Windows7)/MS Office/プリンタ/VNC設定/SSH Terminal/,....,
- 西8号館電子鍵
- Google関係 (カレンダー、ML, 研究室(内部向け), ブログ作成)
- 研究室計算機環境使用ポリシーの理解
- 情報処理学会 学生会員申込み
- 卒業研究題目提出
- SACSIS 2011 申込み

[Stream Computing に関する文献読み]
- IBM Professional 論文「ストリームコンピューティング時代を開く基盤ソフトウェア IBM InfoSphere Streams
- Landfall 2011年4月号号「鈴村研究室の紹介ページ」
- ストリームコンピューティング概要に関する次の資料を読む(ドキュメント1)(ドキュメント2

[研究室の研究プロジェクト理解](外向け研究室ページを参照。無い物は担当学生に問い合わせ)
- 石井君「クラウドを利用したElastic なデータストリーム処理」SACSIS 2011
- 松浦君「データストリーム処理系System SとHadoopの統合実行環境」COMSYS 2010
- 雁瀬君「大規模2部グラフのデータストリーム処理」ACS 論文誌読み(もうすぐ完成なので雁瀬君に問い合わせ)
- 上野君 SACSIS 2011 に提出した論文

[国際学会論文読み]
読む論文は後でメール・ブログで連絡

[Stream Computing のプログラミング演習]
- System S
- インストール、SPADE 理解, ドキュメント読み、サンプル動作確認
- 自前で作成アプリケーションを考え、UDOP (User-Defined Operator)を含めたアプリケーションを実装
- Yahoo S4 (http://s4.io/) / StreamScale (上野君)
- System S と同様のアプリケーションを Yahoo S4 に移植
---> 演習発表会時に発表)

[5月11日(水) 発表内容]
- 英語論文紹介 (PowerPoint を用いる)
- プログラミング演習の成果発表 (PowerPoint を用いる)

[第1回目演習発表後のプラン]
- 研究テーマ設定
- SACSIS 2011 参加

2011年4月10日日曜日

[CPS] Cyber-Physical Systems

Cyber-Physical Systems: A Case for Soft Real-Time, Ulrich Kremer
http://www.research.rutgers.edu/~uli/Sarana/documents/CPS-Uli.pdf

[IOT] IEEE/ACM International Conference on Internet of Things 2011

http://www.linggantek.com/IoT2011/IOT2011%20CFP.pdf
締切りは 5月1日。

トラックは以下の通り。

• Track 1: Architecture and Infrastructure
• Track 2: System Design, Modeling and Evaluation
• Track 3: Intelligent Data Processing
• Track 4: Networks and Communications
• Track 5: Reliability, Security, Privacy and Trust, chaired by Isaac
• Track 6: Applications, Business and Social Issue

Streaming Particle Filter

Real-Time Particle Filter, 2004

http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.657

Particle filters estimate the state of dynamical systems from sensor information. In many real time applications of particle filters, however, sensor information arrives at a significantly higher rate than the update rate of the filter. The prevalent approach to dealing with such situations is to update the particle filter as often as possible and to discard sensor information that cannot be processed in time. In this paper we present real-time particle filters, which make use of all sensor information even when the filter update rate is below the update rate of the sensors. This is achieved by representing posteriors as mixtures of sample sets, where each mixture component integrates one observation arriving during a filter update. The weights of the mixture components are set so as to minimize the approximation error introduced by the mixture representation. Thereby, our approach focuses computational resources (samples) on valuable sensor information. Experiments using data collected with a mobile robot show that our approach yields strong improvements over other approaches. 1

[StreamGraph] Kronecker Graph

Graph500 にも採用されいているが、実グラフの近似モデルとして最近注目されている Kronecker Graph
http://www.graphanalysis.org/SIAM-PP08/Leskovic.pdf
http://www.cs.cmu.edu/~jure/pubs/kronFit-icml07.pdf
http://arxiv.org/abs/0812.4905

[StreamGraph] Massive Streaming Data Analytics: A Case Study with Clustering Coefficients

D. Ediger, K. Jiang, J. Riedy, and D.A. Bader, ``Massive Streaming Data Analytics: A Case Study with Clustering Coefficients,'' 4th Workshop on Multithreaded Architectures and Applications (MTAAP), Atlanta, GA, April 23, 2010.
http://www.cc.gatech.edu/~bader/papers/StreamingCC.html

We present a new approach for parallel massive graph analysis of streaming, temporal data with a dynamic and extensible representation. Handling the constant stream of new data from health care, security, business, and social network applications requires new algorithms and data structures. We examine data structure and algorithm trade-offs that extract the parallelism necessary for high-performance updating analysis of massive graphs. Static analysis kernels often rely on storing input data in a specific structure. Maintaining these structures for each possible kernel with high data rates incurs a significant performance cost. A case study computing clustering coefficients on a general-purpose data structure demonstrates incremental updates can be more efficient than global recomputation. Within this kernel, we compare three methods for dynamically updating local clustering coefficients: a brute-force local recalculation, a sorting algorithm, and our new approximation method using a Bloom filter. On 32 processors of a Cray XMT with a synthetic scale-free graph of 224 ≈ 16 million vertices and 229 ≈ 537 million edges, the brute-force method processes a mean of over 50,000 updates per second and our Bloom filter approaches 200,000 updates per second.

ストリーム処理用クエリ言語 CQL と StreamSQL の比較

ストリーム処理用クエリ言語 CQL と StreamSQL の比較
http://www.it.uu.se/research/group/udbl/Theses/RobertKajicBSc.pdf

[Exa] Research Towards Exascale Systems

http://www.exascale.org/

[Graph500] An effective GPU implementation of breadth-first search

An effective GPU implementation of breadth-first search

Breadth-first search (BFS) has wide applications in electronic design automation (EDA) as well as in other fields. Researchers have tried to accelerate BFS on the GPU, but the two published works are both asymptotically slower than the fastest CPU implementation. In this paper, we present a new GPU implementation of BFS that uses a hierarchical queue management technique and a three-layer kernel arrangement strategy. It guarantees the same computational complexity as the fastest sequential version and can achieve up to 10 times speedup.

Costs of DNA Sequencing Falling Fast

Costs of DNA Sequencing Falling Fast
http://singularityhub.com/2011/03/05/costs-of-dna-sequencing-falling-fast-look-at-these-graphs/

[IOT] Internet of Things Survey

Internet of Things: A Survey

Luigi Atzori, Antonio Iera, and Giacomo Morabito. 2010. The Internet of Things: A survey. Comput. Netw. 54, 15 (October 2010), 2787-2805. DOI=10.1016/j.comnet.2010.05.010 http://dx.doi.org/10.1016/j.comnet.2010.05.010


This paper addresses the Internet of Things. Main enabling factor of this promising paradigm is the integration of several technologies and communications solutions. Identification and tracking technologies, wired and wireless sensor and actuator networks, enhanced communication protocols (shared with the Next Generation Internet), and distributed intelligence for smart objects are just the most relevant. As one can easily imagine, any serious contribution to the advance of the Internet of Things must necessarily be the result of synergetic activities conducted in different fields of knowledge, such as telecommunications, informatics, electronics and social science. In such a complex scenario, this survey is directed to those who want to approach this complex discipline and contribute to its development. Different visions of this Internet of Things paradigm are reported and enabling technologies reviewed. What emerges is that still major issues shall be faced by the research community. The most relevant among them are addressed in details.

2011年4月9日土曜日

[ElasticStream] システム構成と実験方法

以下石井君の ElasticStreamシステムの構成と実験方法です。

//---------------------------------------------------------------------------------
// ElasticStream システム 構成と実験方法
// 2011/04/08 石井
//---------------------------------------------------------------------------------

- se01 を esther から wake-on-lan で起動 --> /usr/local/bin/wol.py se01
- se01 (このノードだけ外部からのコネクションを受け付ける。萩原さんにお願いしている。有効期限は2011年3月まで)を wake-on-lan で起動

<初期ディレクトリ構成>
ElasticStreamSystem
-elasticStream //ローカルに配置する設定ファイル群。今までは/tmp/elasticStream の様に配置
-spade //SPADE用プロジェクトファイル
-ec2 //Amazon EC2に関するデータ、及びRubyスクリプト群。

上記ディレクトリをコピー。
ec2/*.id の権限は注意


<ノード定義>
se01: *.dpsを実行するノード。、ResultGetterもこのノードで起動
st系など: 計算ノードとして使う。

<事前準備>
・elasticStreamフォルダ(入力ファイル、出力ファイル、設定ファイル)を /tmp/elasticStream のようにローカル上に配置。
・spade/data/result -> <ローカル上に配置したelasticStreamディレクトリへのパス>になるようにリンクを設定。

このような感じで、.bashrcにパスを通しておく
目的はEC2-API-toolへのパス、鍵・証明書の場所、デフォルトのリージョンの場所など

//---------------------------------------------------------------------------------
以下の環境変数を .bashrc に追加
export EC2_HOME=$HOME/ec2/ec2-api-tools
export PATH=$PATH:$JAVA_HOME/bin:$EC2_HOME/bin:/usr/local/cula/bin:/usr/local/cuda/bin
export EC2_PRIVATE_KEY=$HOME/ec2/pk-D4I5F3YSJGEX46MXYBRSGAEWPZTIF5BD.pem
export EC2_CERT=$HOME/ec2/cert-D4I5F3YSJGEX46MXYBRSGAEWPZTIF5BD.pem
export EC2_URL="https://ec2.us-west-1.amazonaws.com" ### デフォルトリージョン。東京のデータセンターに書き換えるときは Amazon EC2 のサイトを参照。明示的に API でリージョンを指定する必要がある。現在は Ruby スクリプトに書いている。


// ※鍵は同梱のec2フォルダに入っているのでそれへのパスを与える。
  // デフォルトのリージョンはこの場合はUS-West
//---------------------------------------------------------------------------------

<設定ファイル解説>
//---------------------------------------------------------------------------------
sla.dat (/tmp/elasticStream/input/に存在。他の設定ファイルも同様の場所に存在)
//---------------------------------------------------------------------------------
  動作の設定ファイル
[1行目]
  ・SLAとなるレイテンシ(マイクロ秒)(今回は使わない)
[2行目]
  ・TimeSlotの時間幅
[3行目]
  ・スタンドアローンモードで起動するか否か(1:スタンドアローン, 0:非スタンドアローン)
  ※スタンドアローンモードではVM Managerを起動せず、クラウド環境を利用しなくなる。

//---------------------------------------------------------------------------------
node_[local/cloud]_*.dat
//---------------------------------------------------------------------------------
  計算資源のホスト名のリスト(インスタンスタイプのカテゴリ毎にある)
各行がホスト名。
#でコメントアウト可能。
*** あらかじめ EC2 上でノードを立ち上げている場合には、node_cloud にそのホスト名を指定
//---------------------------------------------------------------------------------
setting.dat
//---------------------------------------------------------------------------------
  各種設定ファイル。
[1行目]
  ・TimeSlotの時間幅(予想済みデータレートを与えるので使用しない)
[2行目]
  ・データレートの時系列変化を表す入力ファイル名(ファイルの中は1秒ごとのタプル送信数のcsv)
[3行目]
  ・入力ファイル名
[4〜8行目]
  ・データレートの振り分け比率の初期値
  (インスタンスタイプのカテゴリ毎: local_1, local_2, Cloud_1, Cloud_2, Cloud_3 の順番)


*** 前準備
- コンソールを4つ(?)起動 (3つは se01, 1つは st07 (ローカルの計算ノード))
//---------------------------------------------------------------------------------

<起動方法>
・ローカルの各計算ノードでElasticStreamSystem/ec2/4regex.rb(Stableな計算スクリプト)を実行(引数は0(↑のインスタンスタイプのカテゴリの番号), 5000(内部の負荷forループの周回数))
※0,5000は以前の実験で使った値なので基本的には0,5000を引数として与えれば良いです。
# ruby 4regex.rb 0 5000
(ポート番号 10101 でコネクションを待っている状態になる)

・システム起動ノードでresultGetter.rbを起動(引数は10101(入力ポート), 12000(出力ポート, System S の Source (client) オペレータに渡すポート))
# ruby resultGetter.rb 10101 12000
** System S が起動するのを待つ

・deus.rbを起動(引数なし)(各TimeSlotの平均データレートを与えるスクリプト。FutureDetectionの代わり)
# ruby deus.rb
System S の Optimizer オ (UDOP) の前の Source のポート番号 11111 に接続

・xVMManager.rbを起動(引数なし)(VM管理スクリプト)
# ruby xVMManager.rb

・以上のすべての起動を確認したら、submit_job*.shでSystem Sのジョブを起動
 ※クラウド環境との通信は、xVMManager.rbが自動で行ってくれる(はず)(2011/04/08時点では未テスト)
** ./start_streams.....sh を最初に起動
** ./canceljob__.sh
** 5分経過するとクラウドにつなぐ
** Amazon EC2 のVMインスタンスはマニュアルで停止する必要があるときがあるので注意
・終了する場合は、cancel_job*.shでSystem Sのジョブを止めた後、残りのRubyスクリプトを落とす


//---------------------------------------------------------------------------------

<実験結果>
・結果はすべて、<ローカルのelasticStreamディレクトリ>/data 以下に出力される

//---------------------------------------------------------------------------------
DataRate.csv
//---------------------------------------------------------------------------------
System S側で測定したデータレート

//---------------------------------------------------------------------------------
FutureDetection.csv
//---------------------------------------------------------------------------------
FutureDetection コンポーネント(現在はSDARアルゴリズム)の出力

//---------------------------------------------------------------------------------
Latency_*****.csv
//---------------------------------------------------------------------------------
レイテンシの実測値。各タプルのレイテンシの、1秒ごとの平均。
  ALLはすべてのタプル、Local_*, Cloud_*はローカル計算資源、クラウド資源ごとの平均。
実験データとしてはALLを用いた。

//---------------------------------------------------------------------------------
Log_***.csv
//---------------------------------------------------------------------------------
各コンポーネントのログ出力。
エラー出力などもここに出力される。

//---------------------------------------------------------------------------------
Result.csv
//---------------------------------------------------------------------------------
正規表現マッチングでヒットしたタプル(JSONファイル)の"text"要素の出力
正常動作の確認用。

// SSH の設定 - パスフレーズの設定
.ssh/config というファイルを作り、以下の内容を書き足す
host *
StrictHostKeyChecking no

// AWS 管理コンソール
suzucommon@gmail.com /

Region を US West に指定
インスタンス:
stop(使い回す, pending/resume、EBSから消去しない. ただ EBSのストレージ使用量はかかる) ではなく、terminate(EBSからVMインスタンスを消去する)の状態にする.
./cancel したら terminate する。



2011年4月7日木曜日

Smarter Planet Case Study

あまり研究とは関係ないが、事例
http://www-06.ibm.com/innovation/jp/smarterplanet/casestudy.shtml

Graph500:ペタレベルの大規模グラフを解く

2010年10月で発表された Graph500 のリストでは、頂点サイズが 140TB, 1.1PB の問題に関しては解けていない。メインメモリに収まりきるほどのサイズではないので、当然、ディスク (SCM も含めて)も活用しなければいけない。

「基本的な戦略は多段階。1段階目ではメモリに載りきるだけ代表点だけを抜き出して、そのレベルで最短経路探索を行う。2段階目では1段階で求まった最短経路の各辺の中での最短経路を求める。2段階目でもメモリに載りきらない場合には更に上記のステップを繰り返す」 

上記アルゴリズムの他に、「メモリ-SSD-HDD-分散ファイルシステム」を透過的に見せるデータストアの設計・開発が必要。

2011年4月6日水曜日

IPDPS 2011 Program

今年5月16日から20日まで US で開催される IPDPS 2011 のプログラムが以下に掲載されました。
http://www.ipdps.org/ipdps2011/2011_advance_program.html

非常に興味深い論文が多いのですが、公開されたら以下の論文を読みましょう。
  • Multi-GPU MapReduce on GPU Clusters
  • X10 as a parallel language for scientific computation: practice and experience
  • Communication Optimizations for Distributed-Memory X10 Programs
  • Graph Partitioning with Natural Cuts
  • A Scalable and Elastic Publish/Subscribe Service
  • CATCH: A Cloud-based Adaptive Data Transfer Service for HPC
  • DryadOpt: Branch-and-Bound on Distributed Data-Parallel Execution Engines
  • Profiling Heterogeneous Multi-GPU Systems to Accelerate Cortically Inspired Learning Algorithms
  • PHAST: Hardware-Accelerated Shortest Path Trees
  • Using Shared Memory to Accelerate MapReduce on Graphics Processing Units
  • Computing Strongly Connected Components in Parallel on CUDA
  • Fast Community Detection Algorithm With GPUs and Multi-core Architectures
  • The Weighted Byzantine Agreement Problem
  • Automated architecture-aware mapping of streaming applications onto GPUs
  • Tolerant Value Speculation in Coarse-Grain Streaming Computations
  • A Performance and Area Efficient Architecture for Intrusion Detection Systems
  • Communication-Avoiding QR Decomposition for GPUs
  • Architectural constraints to attain 1 Exaflop/s on three scientific application classes

iDB 2011 Workshop

http://db-event.jpn.org/idb2011/index.htm
査読あり

2011年4月4日月曜日

2011年4月2日土曜日

[StreamCloud] IEEE Cloud 2011

石井君の論文が IEEE CLOUD 2011 (The 4th International Conference on Cloud Computing) に採択されました。おめでとうございます!採択率は 36/196 (18%) でした。