[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 には西井君と松浦君が論文を投稿しました。

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

[StreamGraph] Proximity Tracking on Time-Evolving Bipartite Graphs

Hanghang Tong, Spiros Papadimitriou, Philip S. Yu, Christos Faloutsos, Proximity Tracking on Time-Evolving Bipartite Graphs, SDM 2008, Atlanta, USA. [PDF]   Best paper award

http://www.siam.org/proceedings/datamining/2008/dm08_64_Tong.pdf


Given an author-conference network that evolves over time,
which are the conferences that a given author is most closely
related with, and how do they change over time? Large
time-evolving bipartite graphs appear in many settings, such
as social networks, co-citations, market-basket analysis, and
collaborative filtering.
Our goal is to monitor (i) the centrality of an individual
node (e.g., who are the most important authors?); and
(ii) the proximity of two nodes or sets of nodes (e.g., who
are the most important authors with respect to a particular
conference?) Moreover, we want to do this efficiently and
incrementally, and to provide “any-time” answers. We propose
pTrack and cTrack, which are based on random walk
with restart, and use powerful matrix tools. Experiments on
real data show that our methods are effective and efficient:
the mining results agree with intuition; and we achieve up to
15∼176 times speed-up, without any quality loss

[StreamGraph] グラフアルゴリズムの GPU による高速化

Accelerating large graph algorithms on the GPU using CUDA
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf


fast GPU algorithm for graph connectivity
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5470817

Collaborative Filtering with Temporal Dynamics

http://research.yahoo.com/pub/2824 こちらも必見

Collaborative Filtering with Temporal Dynamics
Authors:
Koren, Y.
Source:
KDD 2009, ACM, Paris, France (2009)
Abstract:
Customer preferences for products are drifting over time. Product perception and popularity are constantly changing as new selection emerges. Similarly, customer inclinations are evolving, leading them to ever redefine their taste. Thus, modeling temporal dynamics should be a key when designing recommender systems or general customer preference models. However, this raises unique challenges. Within the eco-system intersecting multiple products and customers, many different characteristics are shifting simultaneously, while many of them influence each other and often those shifts are delicate and associated with a few data instances. This distinguishes the problem from concept drift explorations, where mostly a single concept is tracked. Classical time-window or instance-decay approaches cannot work, as they lose too much signal when discarding data instances. A more sensitive approach is required, which can make better distinctions between transient effects and long term patterns. The paradigm we offer is creating a model tracking the time changing behavior throughout the life span of the data. This allows us to exploit the relevant components of all data instances, while discarding only what is modeled as being irrelevant. Accordingly, we revamp two leading collaborative filtering recommendation approaches. Evaluation is made on a large movie rating dataset by Netflix. Results are encouraging and better than those previously reported on this dataset.
Notes:
Won KDD'09 Best Research Paper award

[StreamGraph] Pregel: a system for large-scale graph processing

SIGMOD 2010で発表された Google の論文。必見。

http://portal.acm.org/citation.cfm?doid=1807167.1807184

Many practical computing problems concern large graphs. Standard examples include the Web graph and various social networks. The scale of these graphs - in some cases billions of vertices, trillions of edges - poses challenges to their efficient processing. In this paper we present a computational model suitable for this task. Programs are expressed as a sequence of iterations, in each of which a vertex can receive messages sent in the previous iteration, send messages to other vertices, and modify its own state and that of its outgoing edges or mutate graph topology. This vertex-centric approach is flexible enough to express a broad set of algorithms. The model has been designed for efficient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier. Distribution-related details are hidden behind an abstract API. The result is a framework for processing large graphs that is expressive and easy to program.

有害 Tweet リアルタイム監視

データストリーム処理が応用できる例

http://japan.internet.com/busnews/20100831/5.html

"利用者のツイートが掲載される企業のキャンペーンページなどに無関係な宣伝や公序良俗に反するツイートが投稿された際は、リアルタイムでブロックしたり、メールでアラート"
"オプションで、ハッシュタグや一般キーワードの監視、商品購入を薦めるフレーズなどの自動ピックアップ機能"

DEDUCE: at the intersection of MapReduce and stream processing

System S のランタイム上で MapReduce 処理系を作った話。必見。

DEDUCE: at the intersection of MapReduce and stream processing
Proceedings of the 13th International Conference on Extending Database Technology 2010
Vibhore Kumar(IBM)

http://portal.acm.org/citation.cfm?id=1739120

[StreamGPU] Singular Value Decomposition for Collaborative Filtering on a GPU

協調フィルタリング用 特異値分解の GPU 用による高速化
----
Singular Value Decomposition for Collaborative Filtering on a GPU, 2010

A collaborative ltering predicts customers' unknown preferences from known preferences. In a computation of the collaborative ltering, a singular value decomposition (SVD) is needed to reduce the size of a large scale matrix so that the burden for the next phase computation will be decreased. In this application, SVD means a roughly approximated factorization of a given matrix into smaller sized matrices. Webb (a.k.a. Simon Funk) showed an e ffective algorithm to compute SVD toward a solution of an open competition called "NetixPrize". The algorithm utilizes an iterative method so that the error of approximation improves in each step of the iteration. We give a GPU version of Webb's algorithm. Our algorithm is implemented in the CUDA and it is shown to be effi cient by an experiment.


http://iopscience.iop.org/1757-899X/10/1/012017/pdf/1757-899X_10_1_012017.pdf

---

Collaborative Filtering 関連の参考論文

A Survey of Collaborative Filtering Techniques, 2009
http://www.hindawi.com/journals/aai/2009/421425.html

Yunhong Zhou, Large-scale Parallel Collaborative Filtering forthe Netflix Prize
http://www.hpl.hp.com/personal/Robert_Schreiber/papers/2008%20AAIM%20Netflix/netflix_aaim08(submitted).pdf

戦略的高性能計算システム開発に関するワークショップ

8月上旬に金沢で行われた「戦略的高性能計算システム開発に関するワークショップ」の資料が以下にアップされています。
http://www.open-supercomputer.org/workshop/

汎用並列分散処理基盤としての SPADE / System S

System S の処理系及び SPADE のプログラミングモデルは、元々、低レイテンシを第一の目的にするデータストリーム処理の基盤及び言語として設計されてはいるものの、実際にはスループットを最大化する汎用的な分散並列処理基盤として活用することができます。実際に、鈴村が関わっている商用システムの構築プロジェクトにおいては、そのような使われ方がされつつあります。

　このような使われ方はむしろ迎合すべきもので、後者の計算モデルをバッチ型計算モデルと呼ぶとすると、データストリーム処理モデルと同様のプログラミングモデルとしてシステムを記述することができる利点があります。また、研究としては、このような考えを元に SPADE というデータフロー型のプログラミング言語を捉えると、以下の2つのアイデアが浮かんできます。

1.「SPADE プログラムから CPU/GPU (or Multi-GPU) 上で効率的に稼動するコードを生成する技術」
関連研究は以下の論文でMapReduce プログラムを GPU 上で稼動させる研究です。
Mars: A MapReduce Framework on Graphics Processors by Bingsheng He , Naga K. Govindaraju

2.「MapReduce プログラミングモデルを SPADE プログラムにコード変換する技術」
MapReduce プログラミングモデルで記述されたコードは Hadoop だけでなく、汎用の分散並列処理基盤としての System S 上で実行することができようになります。

Ricardo: Integrating R and Hadoop

SIGMOD 2010 の Industry Truck に採択された IBM Almaden の論文。

Ricardo: Integrating R and Hadoop (URL)

Sudipto Das University of California, Santa Barbara, USA
Yannis Sismanis IBM Almaden Research Center, San Jose, USA
Kevin S. Beyer IBM Almaden Research Center, San Jose, USA
Rainer Gemulla IBM Almaden Research Center, San Jose, USA
Peter J. Haas IBM Almaden Research Center, San Jose, USA
John McPherson IBM Almaden Research Center, San Jose, USA

[StreamScale] 実装時の参考文献、参考技術

[スケーラビリティ]
- Doug Lea による Java NIO を用いたサーバーサイド実装のスライド "Scalable IO in Java"
http://gee.cs.oswego.edu/dl/cpjslides/nio.pdf

- JDK 6 の NIO パッケージの新機能 http://download.oracle.com/javase/6/docs/technotes/guides/io/enhancements.html#6
java.nio.channels.SelectorProvider クラスの実装が、Linux Kernel 2.6 から導入された epoll システムコールを使用するように書き換えられている

- Distributed computing using Java: A comparison of two server designs

- NPTL (Native Posix Threading Library) : POSIX スレッドのアプリケーションをOS レベルで効率的に動作させる機能。Linux Kernel 2.6 以降から導入されたが、Java の Non-Blocking IO などの必要不可欠性が薄まりつつある可能性もある

[コンポーネント化]
- Apache Cocoon: Spring ベースのソフトウェアコンポーネント化ライブラリ。Matt Welsh の SEDA (Staged Event Driven Architecture) を踏襲. OSGi とも類似している

[StreamSR] 国際会議

国際会議ですが、マルチメディア系の分散並列処理関係の会議に出すのが適切ではないかと思います。以下、候補ですが、アップデートする予定。どの会議に出すかは吟味するとして、次のテーマに移るべく9月中旬までには英語化を完成させましょう。

DASFAA 2011 (投稿予定日：9月中旬, 12月10日採択通知）

ICME (International Conference on Multimedia & Expo) （投稿予定日：2011年1月）
http://www.icme2010.org/dates.html (ICME 2010)

DMS (International Conference on Distributed Multimedia Systems) (投稿予定日：2011年3月30日）
http://www.ksi.edu/seke/dms11.html

DASFAA 2011

松浦君の StreamDS の成果を以下の国際会議に投稿予定
http://www.cintec.cuhk.edu.hk/DASFAA2011/index.html

インターン報告会

　Ｍ浦君のインターン報告会。行った課題も研究室のテーマに関連しており、かつ彼のこれからの研究プロジェクトにも強く関連してくるので、非常に良いインターンだったのではないでしょうか。特に M1 のうちに、こういう経験をすることは非常に重要です。

IBM SUR Award

　本年度、我々の研究室が IBM の SUR (Shared University Relationship) Award という賞をもらうことが決定し、サーバー機器が贈呈されることになりました。日本からは2件の受賞です。

SWoPP 2010

HPC (High Performance Computing), OS（Operating System) , Arch （計算機アーキテクチャ）分野の研究者が毎年一同に会する学会 SWoPP 2010 に参加してきました。我々の研究室からの参加者は、鈴村と上野君。HPC 研究会の前半は特に GPU 関連の研究が非常に多くありました。

鈴村は BoF セッションでのパネリストとして参加。特に昨今、博士課程に進学することを非常に間違った解釈でとらえている人がいるので、そのような学生向けに、民間企業の研究所の立場としてお話ししました。前に3年生の授業で話したことがありますが、もし興味があったらいつでも話します。