[StreamGraph] 超大規模ネットワークの高速コミュニティ検知手法

Fast unfolding of communities in large networks, Vicent D. Blondel, 2008

[StreamGraph] グラフアルゴリズムのベンチマーク

コミュニティ検知アルゴリズムの比較に用いられるベンチマークグラフの提案
Benchmark graphs for testing community detection algorithms, Andrea Lancichinetti et.al , 2008
http://pre.aps.org/abstract/PRE/v78/i4/e046110

[StreamGraph] Networks, Crowds, and Markets: Reasoning About a Highly Connected World

"Networks, Crowds, and Markets: Reasoning About a Highly Connected World", David Easley and Jon Kleinberg, http://www.amazon.co.jp/Networks-Crowds-Markets-Reasoning-Connected/dp/0521195330

Dive into A Data Deluge

http://diveintodata.org/

[StreamGraph] MapReduce 上でのグラフ処理

Graph Twiddling in a MapReduce World, Jonanthan Cohen, 2009
(PDF)

A Peta-Scale Graph Mining System - Implementation and Observations, 2009
(Slides)

[StreamGraph] グラフデータベース

グラフデータベース
http://www.infoq.com/jp/articles/graph-nosql-neo4j

[StreamScale] ビルド、コード管理など

- ビルド ant
- コード管理 sourceforge + SVN
- パフォーマンス測定ツール: JMeter
- ログ: Log4J

[StreamScale] JVM リモート監視

JMX を使いましょう

http://nadeausoftware.com/articles/2008/03/java_tip_how_get_cpu_and_user_time_benchmarking#UsingaSuninternalclasstogetJVMCPUtime
など

[StreamScale] 通信レイヤ

Apache MINA

MINA is a simple yet full-featured network application framework which provides:

Unified API for various transport types:
TCP/IP & UDP/IP via Java NIO
Serial communication (RS232) via RXTX
In-VM pipe communication
You can implement your own!
Filter interface as an extension point; similar to Servlet filters
Low-level and high-level API:
Low-level: uses ByteBuffers
High-level: uses user-defined message objects and codecs
Highly customizable thread model:
Single thread
One thread pool
More than one thread pools (i.e. SEDA)
Out-of-the-box SSL · TLS · StartTLS support using Java 5 SSLEngine
Overload shielding & traffic throttling
Unit testability using mock objects
JMX managability
Stream-based I/O support via StreamIoHandler
Integration with well known containers such as PicoContainer and Spring
Smooth migration from Netty, an ancestor of Apache MINA.

[StreamScale] DB

StreamScale のランタイムですが、Apache プロジェクトで利用できるコンポーネントは積極的に使っていきましょう。

- Apache Derby : RDB (Pure Java)
- Apache MINA : 効率的な通信レイヤの実装用
- APR (Apache Portable Runtime Project)
- Cassandra (http://cassandra.apache.org/)

[StreamScale] Java と Infiniband

StreamScale のノード間通信に重要


Efficient Java Communication Libraries over InfiniBand

Guillermo L. Taboada

http://www.computer.org/portal/web/csdl/doi/10.1109/HPCC.2009.87

This paper presents our current research efforts on efficient Java communication libraries over InfiniBand. The use of Java for network communications still delivers insufficient performance and does not exploit the performance and other special capabilities (RDMA and QoS) of high-speed networks, especially for this interconnect. In order to increase its Java communication performance, InfiniBand has been supported in our high performance sockets implementation, Java Fast Sockets (JFS), and it has been greatly improved the efficiency of Java Direct InfiniBand (Jdib), our low-level communication layer, enabling zero-copy RDMA capability in Java. According to our experimental results, Java communication performance has been improved significantly, reducing start-up latencies from 34μs down to 12 and 7μs for JFS and Jdib, respectively, whereas peak bandwidth has been increased from 0.78 Gbps sending serialized data up to 6.7 and 11.2 Gbps for JFS and Jdib, respectively. Finally, it has been analyzed the impact of these communication improvements on parallel Java applications, obtaining significant speedup increases of up to one order of magnitude on 128 cores.

[StreamScale] 機能

先日の機能要件で抜けている機能要件の一部。全部は最初は実装しないので、要件を一通り洗い上げて、最初のバージョンでどれを実装すれば良いかを選択するようにしましょう。

エンジン (SSR)
- データレート、CPU 使用率の計測

可視化ツール
- ストリームモニタリングツール（ちゃんとタプルが流れているかどうかを可視化する）
- どのオペレータがどのノードに今アサインされているかを可視化
（最初はテキストベースでも良いでしょうが、ないと不便でしょう）

[StreamScale] SSR (StreamScale Runtime) のリモート起動

自前でシェルスクリプトなどを用意するのでも良いが、GXP を使えばよいだろう。ただ、ちゃんとポータブルな実装になっているかどうかを確認する必要があるが。


リモートの JVM の監視ツールとしては以下のようなツールも存在する。
jps - Java Virtual Machine Process Status Tool
http://download.oracle.com/javase/6/docs/technotes/tools/share/jps.html

[StreamScale] 実装時に参考になるであろう情報

Efficient data transfer through zero copy
http://www.ibm.com/developerworks/library/j-zerocopy/

[StreamScale] 設計

概要設計(10月中いっぱいまでを予定）：2週間程度

第1回目： Programming Model / API (2010/10/13)
第2回目： Runtime Architecture (2010/10/18)
第3回目： 第1回目、第2回目のまとめ、他に必要な機能の議論

詳細設計：2週間程度 (11月1週目、2週目）
- API および SPI 決定

実装（第1ラウンド：11月中旬～12月下旬）
- 分担
- テストケース： Test First の思想に基づく

Agile な開発方式をするので、
まず第一プロトタイプを年内に完成させるのが目標

PGAS 2010

並列分散プログラミング言語 X10 は PGAS (Partitioned Global Address Space) と呼ばれる部類に入る言語ですが、PGAS のワークショップが開催されています。

以下が、採択された論文リストですが、まだダウンロードはできません。いくつか興味深い論文があります。


http://groups.google.com/group/pgas10/web/list-of-accepted-papers


The following papers (listed in no particular order) have been accepted for the conference:

Mads Ruben Burgdorff Kristensen and Brian Vinter. Numerical Python for Scalable Architectures
Vikas Aggarwal, Changil Yoon, Alan George, Herman Lam and Greg Stitt. Performance Modeling for Multilevel Communication in SHMEM+
Stefano Markidis and Giovanni Lapenta. Development and performance analysis of a UPC Particle-in-Cell code
Filip Blagojevic, Paul Hargrove, Costin Iancu and Kathy Yelick. Hybrid PGAS Runtime Support for Multicore Nodes
Megan Vance and Peter M. Kogge. Introducing mNUMA: An Extended PGAS Architecture
Nakao Masahiro, Lee Jinpil, Boku Taisuke and Sato Mitsuhisa. XcalableMP Implementation and Performance of NAS Parallel Benchmarks
Deepak Eachempati, Hyoung Joon Jun and Barbara Chapman. An Open-Source Compiler and Runtime Implementation for Coarray Fortran
Max Billingsley III, Beth Tibbitts and Alan George. Improving UPC Productivity via Integrated Development Tools
Nicholas Edmonds, Douglas Gregor and Andrew Lumsdaine. Extensible PGAS Semantics for C++
Montse Farreras and George Almasi. Asynchronous PGAS runtime for Myrinet networks
Han Dong, Shujia Zhou and David Grove. X10-Enabled MapReduce
Jithin Jose, Miao Luo, Sayantan Sur and Dhabaleswar K. Panda. Unifying UPC and MPI Runtimes: Experience with MVAPICH
Bill Scherer, Laksono Adhianto, Guohua Jin, John Mellor-Crummey and Chaoran Yang. Hiding Latency in Coarray Fortran 2.0

MapReduce 関係の最適化

Speeding Up Distributed MapReduce Applications Using Hardware Accelerators, Yolanda Becerra, ICPP 2009
http://personals.ac.upc.edu/dcarrera/papers/ICPP09.pdf


Phoenix Rebirth: Scalable MapReduce on a Large-Scale Shared-Memory System, Richard M. Yoo
http://csl.stanford.edu/~christos/publications/2009.scalable_phoenix.iiswc.pdf

Phoenix Project at Stanford University
http://mapreduce.stanford.edu/
Phoenix Project Slides

Deduce : 前のエントリ

オープンソースの LP Solver

LP (Linear Programming) の有名なソルバーでは、商用の CPLEX (AMPLという言語を通じて使用) が最も有名であるが、オープンソースのものでは、以下のソルバーが有名らしいです。石井君、参考にしてください。

COIN-ORプロジェクトのCLP: https://projects.coin-or.org/Clp
GNUのGLPK http://www.gnu.org/software/glpk/
性能比較: http://plato.asu.edu/ftp/lpfree.html

近況

　すっかりブログの更新をしていませんでしたが、皆さんはちゃんと更新お願いします。

最近は、来年度に向けた政府系予算取りに向けたプロポーザル作成に忙殺されています。採択された暁には、皆さんにご報告します。

10月下旬に行われるインターネットカンファレンス 2010 （査読つき）には、上野君、西井君、石井君の3人が採択されました。また、国際学会 DASFAA 2011 には西井君と松浦君が論文を投稿しました。

授業など忙しいと思いますが、やはり、論文、というのは単位や学士・修士論文以上に、個人の業績として一生残るものです。研究を大いに進めて、自分の大学での研究成果を積み重なっていってください。