System S on CentOS 5.3

現在、System S は Redhat Enterprise Linux (4.4 32 bitと 5.2 64 bit) のみをサポートしているのですが、CentOS 5.3 (64 bit) 上で System S を稼動させることに成功しました。まあ、理論上は CentOS は RHEL の互換 OS なので、すんなり動くはずだったのですが。。。

HP ML115 G5

最近毎日チェックしていましたが、NTT-X Store でHP ML115 G5 (4577670-AJKV) の予約が始まったので、8台の購入予約を完了しました。松岡研究室の遊休マシン（IBM eServer 26台) を頂くことになっていますが、こちらは純粋に System S の計算ノードとして使いたいと思います。

HP のマシンはいろいろ拡張性が高いので、System S だけでなく、管理系サーバーなどいろんな用途に使えそうです。

Parallel Sorting

並列ソーティングに関する論文

Hiroshi Inoue(IBM), AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors, PACT 2007 (PDF)

StreamGPU: 特異値分解

森田君、SVD のプログラムですが、行列サイズは ２のべき乗(2の５乗から１０乗ぐらいまで) の正方行列、密行列、各行列要素は double (float でも良い）でテストしてみてください。

CULA

LAPACK (この中に SVD が含まれている）を CUDA で書き直した CULA
というものがリリースされたようです。
http://www.multicoreinfo.com/2009/08/cula-tools-gpu-accelerated-lapack/

どの程度、速いのでしょうね。

SST (Singular Spectrum Transformation) : 特異スペクトル変換法

SST (Singular Spectrum Transformation) 特異スペクトル変換法 の発表資料はここ (PPT) にあります。

http://www.siam.org/proceedings/datamining/2007/dm07_054ide.pdf
なども参考になります。

本質的には, 特異値分解 (SVD) が重く、オリジナルの SST on System S では、以下の Matrix Library の SVD 関数を使っています.
http://www.robertnz.net/nm10.htm#refer

特異値分解を GPU で高速化する話は、「正方行列向け特異値分解のCUDAによる高速化」(PDF) や
これ(PDF) などいろいろあるようですが、我々はストリーム処理のコンテキストでの性能評価をやります。特に、ウィンドウサイズを適切に設定しないと、GPU の恩恵を受けられない可能性があり、その辺の指針が得られると良いでしょう。

森田君、いろいろ調べてみてください

StreamGPU: matrix inversion on GPU

GPU で逆行列計算を高速化する話が以下の論文にのっています。
http://www-user.tu-chemnitz.de/~benner/pub/BenRQ_HeteroPar09.pdf

StreamDNA の関連研究

StreamDNA の関連研究としてはPDF にあるように、グリッド上の計算機を束ねてスループットを実現する研究が山ほどあります。StreamDNA ではこのスループットも重要ですが、よりレイテンシを重要視します。

松浦君、論文ではこのあたりも触れる必要があるので、見ておいてください。

Next-generation DNA sequencing, Nature

Nature で発表された昨年の論文。必見。

Jay Shendure (Univ. of Washington), et.al, "Next-generation DNA sequencing", Nature biotechnology, 2008/10 (PDF)

Stream Computing 輪講

以下、Stream Computing 輪講の第１回目、第２回目の内容です。

Bu˘gra Gedik, "SPADE: The System S Declarative Stream Processing Engine" (PDF), ICDE 2008
担当：　松浦君

Lisa Amini, "SPC: A Distributed, Scalable Platform for Data Mining", (PDF)
担当：　森田君

ToDos for StreamGPU

実装作業は以下の順番でやっていきましょう。目安としては、(1) から (6) までを 10月下旬までに出来ればと思います。

(1) SST の根幹を成す逆行列問題を CUDA 上で実現する (BLAS CUDA などで逆行列計算ルーチンがあれば、それを使ってもよい）
(2) System S の UDOP から CUDA API をたたけるようにする
(3) (1) と (2) を融合し、System S 上から 逆行列計算を実現できるようにする
(4) IBM 高橋さんの SST アルゴリズムと (3) とを融合する
(5) (4) の性能評価
(6) (5) の性能解析＆チューニング

森田君卒論

StreamGPU (森田君卒論）に関するメモ

- SST, Particle Filter, LASSO の３つのアルゴリズムがポーティングターゲット
- System S 上の実装は IBM 高橋さんが実装中

- 森田君が卒論で行うのは、重い計算部分を GPGPU へポーティング
- 重い計算部分を 一つの UDOP オペレータとして分離し、GPU 上で実行する
　　オペレータ、CPU 上で実行するオペレータとして flexible に分けられるようにする
- ポーティング順番は SST --> Particle Filter --> LASSO の順番で行う
- CPU 版と GPU 版を比較し、チューニングなども行う

- GPU での高速化研究はあるので、DSMS 上で GPU を活用する際の様々な工夫を言えるとよい（リアルタイム性を確保する方法等)

調査すべき関連研究
- DSMS の基礎 (System S とは。その他の DSMS システム)
- GPU による数値計算の高速化論文（山ほどあるはずなので、特に機械学習の世界における関連研究を調べる)

Target Conference

ACM SIGCOMM　(2010 New Dehli) 1月締め切り
ASPLOS, 8月締め切り
IMC (Internet Measurement Conference) (2009) Paper 5月締め切り11月開催
ICDCS (2009) 11月締め切り, 2010年6月にイタリアで開催
ICDE　6月締め切り
IEEE INFOCOM
IFIP PERFORMANCE
IPDPS
OSDI
SIDMOD/PODS
SOSP
SC
USENIX Annual Technical Conference
VLDB
WWW
Middleware
OOPSLA
PACT
PLDI
RECOMB : International Conference on Research in Computational Molecular Biology (2010), 10月締め切り, 2010年4月ポルトガル開催
MEDINFO : World Congress on Medical and Health Informatics (Medical Informatics)
MICCAI : Medical Image Computing and Computer-Assisted Intervention (Medical Informatics)

ICDE 2011

2010年6月

VLDB 2011

2010年3月

SIGMOD 2010

締め切り： 2009年10月下旬。WWW 2010 とほぼ同じ。
http://www.sigmod2010.org/calls_papers_important_dates.shtml

WWW 2010

Paper Due: 2009年10月26日：
http://wwwconference.org/www2010/

院試お疲れ様でした

お疲れ様でした。タフな院試だったようですが、まあ、明日の結果を待ちましょう。

GPU 上の MapReduce

GPU 上の MapReduceの論文

Bingsheng He (Hong Kong Univ), "Mars: A MapReduce Framework on Graphics Processors"
PACT 2008, (PDF)

StreamGPU のアプリケーション候補： 相関異常の検出

StreamGPU プロジェクトの GPU へのポーティング対象。
IBM 井出さんの論文「疎な相関グラフの学習による相関異常の検出」 (PDF)

変化点検出を GLASSO アルゴリズムを用いて実現。行列の固有値分解 (Eigenvalue Decomposition) は重いため、Krylov subspace technique という技術によって、計算コストを下げている。GPU を用いると更に高速化が期待できる。

GPU 関連の論文

GPU 関連の論文

• Naga K. Govindaraju,"Fast and approximate stream mining of quantiles and frequencies using graphics processors",SIGMO 2005 [PDF]
  
• Rui Fang, et.al, "GPUQP: query co-processing using graphics processors", SIGMOD 2007, [PDF]
  
• Pedro Trancoso, "Data parallel acceleration of decision support queries using Cell/BE and GPUs, Conference On Computing Frontiers 2009
  
• Hadi Moradi, "A Real-Time GPU-Based Wall Detection Algorithm for Mapping and Navigation in Indoor Environments",
• Streaming Algorithms for Biological Sequence Alignment on GPUs
• Designing Efficient Sorting Algorithms for Manycore GPUs, IPDPS2009
• Offloading IDS Computation to the GPU, 2006
• GPU-Accelerated Text Mining, SIGMOD2005
• Using Graphics Processors for High-Performance IR Query Processing, WWW2008
• The GPU on biomedical image processing for color and phenotype,
• GPU Accelerated Radio Astronomy Signal Convolution,
• Scalable Clustering Using Graphics Processors (PDF)
  
• GPU-based computation of distance functions on road networks with
  
• VLDB 2006 Tutorial , "Query co-Processing on commodity processors" (PDF)
  
• A Fast Similarity Join Algorithm Using Graphics Processing Units, M. D. Lieberman, ICDE 2008, (PDF)
  

StreamGPU Project

StreamGPU というプロジェクトを立てました。

タイトル

データストリーム処理におけるGPU利用の性能特性に関する研究

詳細

• 背景　
• GPGPU
  
• 動機
• どのような種類のアプリケーションが GPU に適しているかは定かではない
• 性能特性を見たい
• 研究
• いくつかの種類のアプリケーションを GPU + DSMS を用いて実装し、性能特性を見る
• アプリケーション候補
  
• Web ログデータ
  
• 移動平均などの簡単計算
  
• IBM 高橋さんの異常検知アプリケーション
• 行列計算の部分を GPU に置き換えることによって性能特性を見る
• GPU と CPU のメモリコピーのコストを考えると、ウィンドウサイズを大きくしないと速くならないはず
• この点をいろいろ試してみる
• StreamDNA の 画像認識部分および Smith-Waterman 法
  
• 音声認識（西井さんに期待）
• 本研究の Contribution
• DSMS に対して、GPU を適用し、その性能特性をみるという研究は初めて
• GPU を用いることで、リアルタイム処理ができなかったことができるようになったこと
  
• 幅広いアプリケーションを用いて評価をしたこと
  
• 本研究の広がり
• 性能モデルの定式化
  
• 上記の異常検知アプリケーションのウィンドウサイズのチューニングを自動でやれるとうれしい
• クラスタ環境において、GPU なしの場合と、GPU マシン１台とで性能はどうか、を知りたい

Google の内製サーバー

今まで明かされなかった Google の内製サーバーの仕様。
http://news.cnet.com/8301-1001_3-10209580-92.html

MapReduce と DBMS の比較

SIGMOD 2009 の "A Comparison of Approaches to Large-Scale Data Analysis" (PDF)

DBSM 界の巨匠である Michael Stonebraker が 昨今のMapReduce 騒ぎに、一石を投じる論文。Hadoop と 並列 DBMS を比較し, Parallel DBMS の方が速いという。しかし、Hadoop は Java ベースで、並列 DBMS は C/C++ で書かれているだろうが、あまり fair な比較ではないところが甘い。

詳細は以下の通り。

- 並列 DBMS は 100ノードにおいて、MR よりも 3.1 ～ 6.5 倍高速
- MR(MapReduce) は１０００ノードでスケールする、と主張しているが、Interactive Media などの企業でも40ノード弱であり、 eBay は Teradataという製品を使っており、72 ノードのみを使用しており、現実的にはそんな巨大なマシンは使っていない

院試がんばってください

院試、もうすぐですね。体調を整えて、万全の体制でのぞんでください。応援してます！

RedHat Enterprise Linux

RHEL の Academic Edition があることが判明したので、鈴村研に導入することにします。System S を動かす可能性のあるマシンをすべて RHEL に変えましょう。

High Performance Web Server Using GPU

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

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

Amazon EC2/S3 互換システム Eucalyptus

Eucalyptus の論文を読んだ。リサーチとしての貢献に関して、新規性、実用性、進歩性を考えると、新規性、進歩性は低いが、実用性は突出している。恐らく、今後多くの論文に引用されるであろう

- API は REST または SOAP
- Xen ベース。VMWare, KVM は今後サポート。
- クラスタ内はもちろんのこと、複数のクラスタ上にクラウド環境を構築するような設計になっているのが特徴的
- Walrus が Amazon S3 にあたるストレージサービス。VM Image の管理やアプリケーションデータの格納場所として使用する

あと、一番気になったのは、DSMS を クラウド環境上で稼動させたときに、VM Image 間で通信を頻繁に発生させるようなケースがあるが、Eucalyptus では、native のネットワークドライバをたたいているため、仮想化のオーバーヘッドが低いと主張している。ここも良い。

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

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

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

Offline + Online の Sharing

USENIX主催の Middleware 2008 で発表された論文

Enabling Resource Sharing between Transactional and Batch Workloads Using Dynamic Application Placement
David Carrera (Technical University of Catalonia - Barcelona Supercomputing Center, Spain)
Malgorzata Steinder (IBM Research, United States)

Eucalyptus の論文

以下の論文を読むこと

The Eucalyptus Open-source Cloud-computing System, Daniel Nurmi, Rich Wolski, Chris Grzegorczyk, Graziano Obertelli, Sunil Soman, Lamia Youseff, Dmitrii Zagorodnov, in Proceedings of 9th IEEE International Symposium on Cluster Computing and the Grid, Shanghai, China
PDFファイル

SEDA の論文（続き）

このエントリのさらに続き

- Matt Welsh による SEDA の過負荷時の制御手法について論じた論文. DSMS における Load Shedding に関しても大いに関係してくる。
Matt Welsh and David Culler, "Adaptive Overload Control for Busy Internet Servers"

- SEDA の肝は 2.2 章に書かれているが、ソフトウェアをステージに分割し、開発者に明示的にキューのコントロールを許すことによって、アプリケーションに特化したパフォーマンスコントロールが可能になること。System S 自身はキュー自身は見えていないので、その部分は UDOP (User-Defined Operator) で実装する必要がある。また、ステージ化することのその他の利点は、パフォーマンスのボトルネックを発見するのが容易になること。ステージごとのキューの状態（常に満杯になっているか？）を監視することで、容易にボトルネックがわかるし、そこのキューだけを制御しさえすれば良くなる。

- ニュースサイトなどではある突発的な事故などが起きると、システムの想定するリクエスト数の百倍、千倍のリクエストが到着することがある (これを Slashdot Effect とかつては呼んでいた）。しかし、これらを想定して Capacity Planning していては Over Spec なシステム構築となる。よって、ソフトウェア的にそれらを回避する必要がある。

- 回避方法としては、コネクション数やスレッド数の上限を設定しておき、リクエストを受け付けない方法と、もう一つは、結果のクオリティを下げる方法がある。後者は例えば、HTML を通常版と軽量版 (Ethernet パケットに収まるぐらい。例えば、画像も解像度を低くするなど）の２つを用意しておき、過負荷時には軽量版の HTML ファイルをクライアントに返す方法などがある。

- この従来の手法は、コネクション数とスレッド数をサーバー管理者が Web サーバーの設定ファイルなどに設定する必要があるが、これは経験的に決められたものであり、必ずしも最適値にならない。よって、低い値にしまいすぎて、スループットが出なかったり、大きくしすぎると、常にシステムが満杯状態で、すべてのリクエストに対してレスポンスタイムが悪くなるという事態に陥ってしまう。

- このようなケースは、Web サイトの運営者側からすると宜しくない状況で、レスポンス時間が長いと、顧客が離れていってしまう恐れが高まる。運営者からすると、平均的にすべてのユーザーに悪いレスポンスタイムを返すよりも、一部のユーザー（例えば１０％）には、きっぱりと、「今は混んでるから後から来てね」と断り、他の90％に対して、それなりに acceptable なレスポンスを返してしまった方が良いだろう。

- この論文では、上記のような問題に対して、パフォーマンスコントロールを柔軟に可能にするフレームワークを SEDA 上に構築。Web Mail システム Arashi を構築して評価している。

- SEDA のキューに入ってくるメッセージの処理時間（レスポンスタイム）をモニタリングし、その傾向によって性能制御する仕組みを設計。例えば、レスポンスタイムが悪くなってきたら、ある一定数の確率でリクエストを Drop したり、他のサーバーに割り振ったりする。

- キューを監視するコントローラを設定し、リクエストがキューに入った時間と、処理を完了し、クライアントに結果を返すまでの end-to-end の時間を測定。その TAT (Turn around time) がある閾値以上になったときには、Load Shedding アルゴリズムを発動させ、一部のリクエストを優先して処理し、一部はあきらめることによって、全体のレスポンスタイムの中央値を良くする手法を提案。

Stream Computing SIG

Stream Computing SIG で読む論文をリストアップします。卒論生は9月からこれらの論文を一つずつ読み進めていくこと。


実行処理系

以下の5つの流派があるので、それぞれについて読む.

IBM System S
Aurora/Borealis (論文リスト）
Telegraph(Berkeley)
STREAMS(Stanford)
Gigascope (AT&T)

クエリ言語/プログラミングモデル

Arvind Arasu (Stanford), The CQL Continuous Query Language: Semantic Foundations andQuery Execution: http://www.cs.uwaterloo.ca/~david/cs848/stream-cql.pdf
スタンフォードの STREAMS で実装された連続クエリ言語 CQL. Oracle CEPもこの CQL を採用されており、大きな影響を受けている。

StreamSQL :Aurora プロジェクト(2001-2003) から生まれたクエリ言語。StreamBase 社の製品も実装している

RDMA (Remote Direct Memory Access)

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

松岡研/GSIC 佐藤さん来訪

　佐藤さんに、TSUBAME で Hadoop を動かすためのツール TSUDOOP などの最近の研究動向について話してもらいました。「数理モデルを用いたストリーム処理における最適化スケジューラ」の話は、協業できそうですね。Middleware 2008 の SODA の論文はまずは参考になるので、次回紹介します。

佐藤さんを含め、Stream Computing SIG (Special Interest Group) を非公式に作りたいと思います。まずは、SIG の活動の一環として、9月から輪講をやりましょう。