Elastic ScaleGraph

Elastic Graph Processing Library on X10 2.5 (Elastic X10) 

X10 ベースの大規模交通シミュレーション実行基盤

道路ネットワークを領域分割することによって複数ノードで高速化されることは明らかであり、TSUBAME 上での妥当な結果が出つつある。ただ、一部の領域においては非常に時間がかかっており、これは車両の経路が通る重要な道路の許容量が少ないから。現在出ている性能分析により、今後は、より研究としての落としどころをつめていかないといけませんが、「Work Stealing 機構によって、動的に混雑度の高い領域に X10 アクティビティを生成する方式」を実装することにより、研究としての価値が生まれるでしょう。

実時間・モバイル空間統計

以下のリンクの、モバイル空間統計はバッチで行われていると推測するが、Twitter データ (位置情報を含む。間引かれているので統計的な推定も必要) から、これをリアルタイムに3次元的に把握できるような可視化システムができると（デモ的には）良い。当然、リアルタイムに見せるだけでなく、時間軸を変更できるようなインタフェースも用意し、特定の日時、時間帯も見れると良い。

http://www.nttdocomo.co.jp/corporate/disclosure/mobile_spatial_statistics/

MOA Project

MOA: Massive Online Analysis
http://moa.cs.waikato.ac.nz/

Stream Mining のツールキット
http://cdnetworks-kr-1.dl.sourceforge.net/project/moa-datastream/documentation/StreamMining.pdf

研究テーマ

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

Network Design Problem

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

研究テーマ: 高生産性並列プログラミング言語X10を用いた大規模グラフ処理

高生産性並列プログラミング言語X10を用いた大規模グラフ処理
- 具体的には Graph500（最短路問題）のコードを X10 で実装する。必要に応じて GPU を使うのもよし
- 通信機構の最適化、アプリケーションレベルのチューニングが必須

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

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

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

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

GIM-V のGPU実装

松浦君の修論テーマの方向性が決まりました。
「大規模グラフ分析プログラミングモデル GIM-V の マルチ GPU による実現と高速化」

この研究の肝は以下の2つです。
(1) マルチノードでかつマルチ GPU 環境を十二分に活用した高速化.
(2) GIM-V のモデルを記述した論理実行モデルの提唱と最適化コード生成

　西井君のテーマである Incremental GIM-V （ストリーム計算）のテーマと大きく関係していますが、バッチ計算とストリーム計算を両方享受できるような統一的な実行基盤を作ることも当然視野に入れます。この統一的な実行基盤で欠かせないのはスケジューリング機構ですが、松浦君の「バッチ処理とストリーム処理のスケジューリング機構」と石井君の「ストリーム処理のクラウドへの委譲」に関する研究がその先駆け的な研究という位置づけになります。

あと不足しているのは、特に大規模グラフデータを格納する分散ファイルシステムへのアクセス機構とローカリティを意識したデータスケジューリングです。また、耐故障性も重要です。この点に関しては、新M1の新たな研究となるか、新B4の研究になるかは相談で決めていきましょう。

研究テーマ候補

研究テーマ候補のリマインド

1. メモリ使用量を考慮した実行時スケジューリング及びマイグレーション
http://suzumura-lab.blogspot.com/2010/07/blog-post_28.html

2. 階層的ストレージ構成を透過的に活用するデータストリーム処理系（例：大規模グラフ）
http://suzumura-lab.blogspot.com/2010/12/streamgraph_4464.htmlにおける以下の問題
メモリに載りきらないようなグラフストリームが到着した際に Persistent な分散ファイルシステムと協調し階層的にグラフ構造を格納、頻繁にアクセスされる部分グラフのみをオンメモリ上に確保するといった最適化手法、そしてそれらのグラフデータに対して開発者からシームレスにアクセスできるような処理基盤

3. GIM-V モデルのGPU実装
大規模グラフの処理モデルGIM-Vの処理系を GPU (+分散用に StreamScaleまたは System S) を用い、実装. 　関連研究→Mars

4. Incremental GIM-V 処理系の発展
- 耐故障性: ノード故障におけるマイグレーション・スケジューリング問題
- GPUを用いた高速化：完全に再計算すべきサブグラフのGPUによる処理

5. 超並列異機種混在計算機環境におけるX10を用いたグラフ処理の最適化
並列プログラミング言語 X10を用いて大規模グラフ処理を記述し、CPUとGPUから構成される超並列異機種混在環境（例：TSUBAME2.0) 上における性能最適化を実現する。また、そこに介在する様々な技術的課題（プログラマビリティ、性能、自動生成されるGPUコードなど）を特定し、X10の実行時処理系にその課題を解決する機能を実装し、性能向上を実現する.　グラフ処理に関しては、GIM-VのモデルをX10で記述するのも良いでしょう。

GPU における ゼロコピー通信

　昨日の議論で思い出したのだが、カーネル空間のソケットバッファからユーザー空間を経ずに直接 GPU のメモリにコピーするような機構が、データストリーム処理に対する GPU の適用には有効であるので、それを追求すれば良い。1年ぐらい前の議論になると思うが、再考する価値はあるでしょう。

汎用並列分散処理基盤としての 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 上で実行することができようになります。

データストリーム処理におけるメモリ消費量を考慮したジョブスケジューリング

　データストリーム処理のアプリケーションでは、Aggregate(条件にマッチするまでメモリ上に蓄えられる) や Join (複数ストリームの待ち合わせ) など、オンメモリ上にデータを蓄えて処理するような処理が必要になるものがある。このとき、Split オペレータなどによってデータのある属性のハッシュ値を元にデータを並列ノードに分散させる場合、データの偏りが生じ、物理メモリを使い果たす場合がある。例えば、CDR 処理においては、ある特定のユーザーの通話履歴が極端に多い場合、そのユーザーのハッシュ値を担当する物理ホストのメモリ量では賄い切れなくなる。このような問題に対応する為、実行時にデータの偏りとメモリ使用量を定期的に監視し、負荷の均衡が保たれなくなった場合には、負荷を実行時に動的に均等にする機構が必要となる。

　実行時に動的に均衡を適正に保つ上で、いくつかの条件を満たす必要があるが、その例を次に示す。

- 溜めていたデータはロスしてはならない。すべての溜めていたデータは正しくマイグレーション先に送られる。マイグレーション先への負荷を最小限に留める。

- データは留め止めなく流れてくるため、上流のオペレータのバッファで滞留しないように、瞬間的にマイグレーションできなければならない

Ethernetマルチリンクによる PCクラスタ向け高性能・耐故障ネットワーク

データストリーム処理においてデータの到着レートに対してネットワークがボトルネックとなることがあるが、Infiniband を用いることによって 1Gbs の Ethernet と比較して数倍のスループットを達成できるアプリケーションがある。HPC (High Performance Computing) においても、MPI (Message Passing Interface) のノード間通信の性能を最適化するために様々な研究が行われてきており、帰着する問題としてはほぼ等しい。例えば、筑波大の朴先生のグループでは、ユーザーレベルでの Ethernet カードの Bonding (束ねること）による性能向上の研究を2006年に行っている。

- Ethernet カードのボンディングによるネットワーク性能の最適化に関する論文(PDF)。

データストリーム処理における適応的なウィンドウ処理

以下、StreamGPU に関係するアイデア。森田君、注目。

以下は、GPU がなくても成立する研究テーマではあるのだが、GPU を使ってストリーム処理が高速化できたというのは、今の状態だと、CULA のライブラリに頼っているだけ。方向性としては、特異値分解のように如何にも効果がありそうなアプリケーションではないところに適応すること、もしくは、以下のような数理的なモデルを用いて味付けするかどちらかだ。

タイトル：　データストリーム処理における適応的なウィンドウ処理

[前提条件]
- アプリケーションは異常検知などレイテンシが critical なものを想定するが、あらかじめ何秒以下に反応すべき、という情報が与えられているものとする。
- また、レイテンシも重要だが、異常検知の精度も重要であり、それがウィンドウサイズとウィンドウのスライドサイズに依存する
- システムは動的に、ジョブや到着タプル数などが変化するものと仮定し、すべてのノードを使えるものとは限らない
- システムは異機種混在環境で複数ノード、複数コアから成り立つ。また、いくつかのノードには GPGPU などのアクセラレータが搭載されているとする

[我々の提案手法]
システム全体の利用可能なリソース状況（ジョブ数、ネットワーク、到着タプル数）
によって、アプリケーションによって与えられたレイテンシを満たす中で、異常検知の精度を最大化する、つまり、
- 動的にウィンドウサイズを最大化し、かつ、
- スライドサイズを小さくする
ことを動的に行う仕組みを構築する。

[実装方法：　数理的モデルの構築と更新]

まず、重回帰分析によって数理的なモデルを構築する。
変数 Y = f(x1, x2) (a1*x1 + a2*x2)

- Y : 1回の平均処理時間（レイテンシ） （平均だけでなく、最大値も見たいが）
- x1: ウィンドウサイズ (大きくできれば長いスパンでのトレンドが見れるので、大きい方が良い。SST の場合、CPU と GPU とで 512 以上のとき平均処理時間に大きな差が現れるので、もし 512 以上のときには GPU が使用できる場合にはそちらを用いる)
- x2: ウィンドウをスライドさせるサイズ（細かい粒度で異常がわかるので、サイズは小さい方がよい）

このモデルは以下に与える外部の制約条件（特に動的情報）によって、変化するので、実行時に定期的に更新する。

外部から与える制約条件は以下の通り
- 1秒間に到着するタプル数（1タプルのバイト数）
- 1回の計算処理時間
- クラスタ全体のジョブの数他のジョブがどのぐらい走っているか
- クラスタに関するスペック情報(静的に取得可能)
(ノード数、コア数、GPU あり/なし、ネットワーク、ストレージ）

また、上記のモデルは CPU と GPU でそれぞれ数理的なモデルを構築する

[ 最適なウィンドウサイズ・スライドサイズを調節し、動的にシステム状況が変化する中でスループットを最大化する]

重回帰分析によって、CPU 使用率、ウィンドウサイズ、スライドサイズ, GPU の使用有無を指定すると、得られるスループットが予測できる。 T = f(CPU utilization, Window Size, Slide Size、GPU or CPU)

グラフとしては、
CPU Utilization と GPU/CPU は与えられるものなので、上記のグラフができれば、最大のスループットをえる

パラメータとして、
- GPU が使えるか否か (0/1)
- 他のジョブが使用しているCPU 使用率はいくつか？
という制約条件が与えられているときに、最大のスループットを出すために、
ウィンドウサイズ、スライドサイズを動的に調節し、かつ、GPU を使うか否かを
動的に選択する。


目的関数: T (スループット) ＋SW + 1/SS
ウィンドウサイズ SW →最大化 (1024 ぐらいまでの中で最大化) 、スライドサイズ SS →最小化

制約条件:
- レイテンシ L < α（ある値以下）
- ウィンドウサイズ SW < 1024 で最大
- その他のジョブのCPU 使用率
- GPU が使用できるか否か

オンライン線形回帰

StreamGPU プロジェクトの次の策を考えている。CULA だとブラックボックス化されているので、我々としては自分たちでCUDA 上で実装した方が良い。

System S + GPU の組み合わせで有効な機械学習のアルゴリズムとして、さくっとできそうなのがオンラインの線形回帰アルゴリズム。 センサーデータが来たら、インクリメンタルにGPU デバイス上の行列データをアップデートして、内積計算すればよい

来年以降の研究テーマ一覧

今卒論でやっているもの以外に、データストリーム処理周辺の研究ネタをいくつか書いてみます。ストリームコンピューティングに特化した研究室にするつもりはないのですが、ある程度のまとまった成果が出るまでは、この分野に注力していきたいと思っています。

[システムソフトウェアよりの研究]

- 仮想マシンを用いた Elastic な データストリーム処理システム: Xen や KVM などの仮想マシン上でデータストリーム処理システムのインスタンスを稼動させ、負荷に応じてインスタンスの数を増減させる仕組み

- 動的なスケジューリングの最適化: 複数のクエリ・ジョブが稼動している状況でのダイナミックなオペレータ配置機構

- GPGPU などのアクセラレータを用いた更なる最適化: CPU と GPU を組み合わせたストリーム処理

- ポータブルな軽量データストリーム処理システムの実装. 現在の System S は 様々なパッケージ（特に PerlやCORBA) に依存しており、かつシステムが巨大である。我々の足回りを軽くするためにも、Java などのポータブルな処理系を用いて実装する。Engineering 的な側面が高いのが難点

- 簡便なプログラミングモデル: PHP, Python, Ruby などのスクリプト言語や統計言語 R などで Agile にストリームアプリケーションを簡便に記述できるようにする. UDOP のようなカスタマイズコードもささっと書くことができる

[アプリケーションよりの研究]
- 音声データからのキーワード検出 (古井研・西井君に期待) : 演習の時間

- データストリーム処理用ベンチマークシステム
- StreamDNA/StreamBIO: ストリーム処理の科学技術計算への応用

[アルゴリズムよりの研究]
- ストリームアルゴリズムの研究: 　処理系の研究ばかりでなく、アルゴリズムの研究も. Click Fraud Detection などが応用例。
- データストリーム処理における Privacy Preserving Data Mining

High Performance Web Server Using GPU

Web アプリケーションサーバーの性能の中で、重い部分は SSL 処理なのだが、これに対して、専用のアクセラレータカードなどが１００～２００万円ぐらいで売られていたりする。SSL の根幹を成す暗号アルゴリズムの暗号、復号処理を GPU でやらせたら、どうなるか？

RSA 処理を GPU で速くする研究は Andrew Moss 等[PDF]がやっているらしいが、統合的に Web サーバーでどのくらい効果があるかは誰もやっていない。WWW ２００９には良いテーマである。

評価に用いるアプリケーション及びデータ

今まで公開されている DSMS 関連の論文が弱いところは、リアルアプリケーションを使った評価が少なく、用いているデータが人工的であること。我々は、実データはさすがに使えなくても、現実的なケースに基づくデータを用いて評価していきたいものである。以下が考えられるデータの候補。

• 通信携帯会社の通話記録データ CDR (Call Data Record)：　誰が誰に何分通話したか？を記録したデータ。インドの携帯契約者は増加の一途を辿っており、その処理が追いつかないと言われる。このデータに関してはある程度ランダムに生成できるであろう
• ライフログデータ：　携帯電話の GPS データなど。各ユーザーの緯度、経度情報は何らかのユーザーの動きのモデルを作らないといけないが、サーバーの性能だけ考えるとあまりそれらの情報は重要ではなく、ランダムで良い
• Web データ：　楽天などのオンラインショッピングにログデータ。これは老木君が創作演習で作っている
• テキストデータ： ニュースの RSS フィードなど巷に沢山ある
• 環境に関するデータ：　ハーバード大学のデータは実際に使える
  

RDMA (Remote Direct Memory Access)

RDMA (Remote Direct Memory Access) を利用したオペレータ間通信の最適化