2009年12月27日日曜日

バースト検知のアルゴリズム

松浦君の「ストリーム処理とバッチ処理の動的負荷分散」の研究に関連するが、バーストの検知アルゴリズムに関する研究が様々な分野において行われているが、もっとも有名なアルゴリズムが コーネル大学のJon Kleinberg (ホームページ)が2002 年に提唱したアルゴリズム。このアルゴリズムの強力さは、特にテキスト処理に限らない汎用性があること。

J. Kleinberg. Bursty and Hierarchical Structure in Streams. Proc. 8th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2002.

東工大の奥村先生のグループがこの Kleinberg をテキスト処理に応用した論文を出されているようなので参考にしましょう。

  • 「周期的に発生する burst の予測と抑制」藤木稔明、奥村学(PDF), 2004
  • 「document streamにおけるburst の発見」藤木稔明、奥村学, 2004
  • ブログ上での話題伝播に注目した重要語抽出、松尾さんなど, 2007
  • コールセンターのログデータを用いた製品等の不具合の早期発見,

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

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

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

2009年12月22日火曜日

ストリームコンピューティング@クラウド研究会

クラウド研究会にてストリームコンピューティングの講演をしてきました。急遽ライブデモのセッティングを老木くん、松浦くんにしてもらいましたが、ありがとうございました。

残念ながら、iphone経由だと回線が細いためか、さくさく動かなかったので断念しました。クラウド研究会ながら講演は割と受けたようで、以下のようなまともな質問を受けました。

GPUとの相性はどうか?
システム的にハンドルできない量のトラフィックがきたらどうなるか?
トランザクション、一貫性は保証されるか?
など、いろいろと質問がでました。

また二回目があるので、ぜひそのときはライブデモをしたいと思いますので、老木くん、よろしくお願いします。



2009年12月21日月曜日

CPU + CPU の有効活用と自動ウィンドウ調節

StreamGPU の落としどころとしては (A) と (B) の2つを考える。

(A) http://morita-k.blogspot.com/2009/10/sst-v2.htmlによると、GPU は 1024 に対して、圧縮なしの CPU と比較して 10倍くらいの差があるので、10倍の性能の コプロセッサが搭載されていると考えられる。ウィンドウサイズ 1024 の場合、1次元だと大体5秒以内で実現できているので、1分という異常検知の許容範囲があるとすると、12次元ぐらいまではリアルタイム(1分)の検知が可能になる。ただし、これらのデータは既に示されているので、さらに (B) により, Contribution を突詰める

(B) CPU と GPU の性能の非対称差、および CPU の有効活用を考える。つまり、たとえば、1分という異常検知の許容範囲を考えると、GPU では 1024 というウィンドウサイズを12次元測定でき、比較的長期間の異常検知の観測が可能になる。この間、CPU は、データを受信したり、CPU から GPU へのメモリ転送などの仕事があるのだが、基本的にはマルチコアの時代なので、アイドル状態のプロセッサが存在するので、それらを有効に活用したい。この空いた CPU を利用して、よりウィンドウサイズを小さくして、短期間および低レイテンシが要求される異常検知を行う。

次にやるべきことだが、 GPU 側は CULA で既に実現できてしまっているので、CPU を使った SST (IBM 高橋さんが実装済み)と合体して稼動させてみて性能特性を見る。CULA の SVD はブロッキングコールだと思われるので、スレッドから呼び出すように改良する。ただし、System S を使えば、CULA 呼び出し用 UDOP と CPU 上の SST 呼び出し UDOP 2つを独立に動かせば良いので、1つのストリームから Split させて同じデータを流し、Aggregate でためるウィンドウサイズを変え、両 UDOP に渡す実装にするだけで OK。まずは、これを実装する(両UDOP ができているので、基本的には実装コストは低いはず)。次に、性能特性を見る。特に、CPU 側の CPU 使用率を測定する。ここまではすぐに終わらせたい。肝心なのが次の実装と実験で、一番の Contribution と言える。

 最適なウィンドウサイズの自動化。SLA (Service Level Agreement) で規定されている異常検知の許容最大値を L 秒 (例:60秒)、1台で検知しなければならない次元数を D 次元とする. L と D はパラメータであり、可変。あらかじめ、学習モードによって、http://morita-k.blogspot.com/2009/10/sst-v2.htmlで得られるような数値データを取得し、1次元あたりに L/D 秒 以下で抑えられる最大のウィンドウサイズを GPU 側と CPU 側、両者で決定する。この学習は実行時前に行うことによって、ウィンドウサイズを自動的に決定し、1CPU+1GPU で処理できるようなウィンドウサイズを決定して、実行する。これらをすべて自動的に行う。

以上。あとは、口答で説明します。

2009年12月20日日曜日

松岡研究室忘年会

汐留カレッタの中華料理屋→松岡先生のマンションの最上階でのパーティー→松岡邸といういつものコースで、忘年会。前まではクリスマスパーティーという名前だったが、海外の学生がふえたので、名前を変えたらしい。

来週は鈴村研のランチ忘年会です。よろしく




2009年12月18日金曜日

老木君学会発表@インターネットアーキテクチャ研究会



インターネットアーキテクチャ研究会にて老木君の学会発表。会場は、東京タワーの目の前にある機械振興会館でした。

発表は非常に良かったと思いますし、こうやってひとつの仕事を論文としてまとめ上げる、世の中に公表することは大切なことだと思います。本当にお疲れ様でした!



 私はずっと学生時代より情報処理学会関連の学会にしか参加したことがなかったので、電子情報通信学会(通称: 信学会)に参加したのは初めてでした。

ひとつの収穫としては、Live E! プロジェクトの従事者たちとお知り合いになれたことでしょうか。Live E ! プロジェクトは、気象データや CO2 濃度を収集するセンサーを日本、世界中にばらまき、センサーネットワークを築き、高等教育や気象観測、防災などに役立てることを目指したプロジェクトです。東工大にも西7号館と西8号館の屋上に設置されたそうで、我々のストリームコンピューティングのターゲットアプリケーションになりそうです。

Live E! プロジェクトでは、非常に多くのセンサーをばらまくのが目標のようですが、1センサーの設置コストが最低でも6万ぐらいかかり、運用、保守が必要になります。私自身としては、このような形態は、結局、スケールしないのではないだろうかと思っています。例えば、ゲリラ豪雨などの突発的、かつ局所的なイベントに対しては、非常に密なセンサーネットワークの構築が必要ですが、このようなコストのかかるものだと検知できる範囲も限られるでしょう。

このような専用型センサーではなく、個人が既に持っている携帯電話や、既存のインフラを活用した方が、よりスケールに可能になるのは当然でしょう。例えば、自動車が携帯電話網とつながる ITS (Intelligent Transport System) があと数年で普及してと言われていますが、ワイパーの動きを検知して、降雨状態を把握するなどのアイデアが出されており、自動車会社と携帯会社が本気になれば、そのようなインフラがあっという間にできてしまいます。また、StreamTwitter のようにマイクロブログのような集合知を利用することで、より安価にかつスケーラビリティ高く実現できます。

ただし、やはり、Live E! のような、より精緻な気象観測を提供するような装置も結局、必要であり、相補的に使っていくのではないでしょうか。

2009年12月10日木曜日

卒論生のスケジュール

卒論生の皆さん(森田君、松浦君)

まずは直近の 1/19 の 全国大会と SACSIS 2009 には必ず出したいと思いますので、その心積もりでいてください。がんばりましょう。

- 1/15(金) 全国大会論文締め切り (日本語査読なし論文、2ページ)
- 1/19(金) : SACSIS 2009 (日本語査読論文, 8ページ)
- 2/9 (火) : 学士論文提出日
- 2/16-19 : 学士論文発表会
- 3/9-3/11 : 全国大会参加&発表
- 5/27-28 : SACSIS 2010 参加@奈良

2009年12月7日月曜日

森田君卒論、参考文献リスト

いろいろありますが、まずは以下を読みましょう。
http://suzumura-lab.blogspot.com/2009/11/on-gpu.html

2009年12月3日木曜日

老木君論文提出完了

老木君が、電気情報通信学会のインターネットアーキテクチャ研究会への論文提出を完了しました。大変、お疲れ様でした!

2009年12月1日火曜日

紅葉





2009年11月25日水曜日

巨大データのソーティング

超巨大なデータのソーティング研究. 特に Sort Benchmark では、Hadoop が頑張っている

SPsort: How to Sort a Terabyte Quickly, Jim Wyllie,
http://sortbenchmark.org/SPsort.pdf

Sort Benchmark Home Page(originally known as Terabyte Sort Benchmark)
http://sortbenchmark.org/

2009年11月18日水曜日

SVD の C実装と実行時間の内訳

StreamGPU の SVD (特異値分解)に関して。

とりあえず、森田君の SVD の CUDA 版移植に向けて、newmat (C++ベース) ではなく、C ベースの SVD を Numerical Recipes を参考に書いて実行してみました。上のグラフは、正方行列の 128 から 1024 までの実行時間の遷移です(newmat と比べてみたいですね)

また、実行時間の内訳を知るべく、1024 x 1024 の行列サイズの時の各ステージにおける割合を円グラフにしてみました。単位は秒で、Tesla で測定した結果です。思った以上に、各ステージがそれなりにかかっているので、一部分を CUDA に移植するだけではなかなか高速化できなさそうですね。


2009年11月16日月曜日

オンライン障害検知手法

Web 系システムからの特徴抽出とオンライン障害検知手法
井手剛
http://www.research.ibm.com/trl/people/ide/2004_IBIS_Ide.pdf

I-SVD の実装

http://www-is.amp.i.kyoto-u.ac.jp/lab/isvd/download/
にて I-SVD の実装を配布しているが、バイナリのみ。ソースコードが配布されていないのが残念
マルチコア環境において、OpenMP および pThread を用いて並列化している。

CUDA Profiler

CUDA Profiler の使い方に関しては、
http://gpu.fixstars.com/index.php/CUDA_Profiler%E3%82%92%E4%BD%BF%E3%81%86
に書いてありますね。森田君、チェックしてください。

------- 特にカーネル実行時のイベントは4つまでしか取れないことに注意

カーネル起動に関する情報は以下のものがあります。
  • timestamp : カーネル起動時のタイムスタンプ
  • gridsize : 起動したブロックの数
  • threadblocksize : 起動したスレッドの数
  • dynsmemperblock : 動的に割り当てられたsharedメモリのサイズ
  • stasmemperblock : 静的に割り当てられたsharedメモリのサイズ
  • regperthread : スレッドごとのレジスタ数
  • memtransferdir : cudaMemcpyのコピー方向(0: host->device, 1:device->host)
  • memtransfersize : cudaMemcpyのサイズ
  • streamid : カーネルを起動したstreamのid


カーネル実行時のイベントは以下のものがあります。これらは同時に4つまでしか設定できません。

  • gld_incoherent : コアレスされなかったメモリロードの回数
  • gld_coherent : コアレスされたメモリロードの回数
  • gld_32b : 32-byte ロードした回数
  • gld_64b : 64-byte ロードした回数
  • gld_128b : 128-byte ロードした回数
  • gld_request : グローバルメモリからロードした回数
  • gst_incoherent : コアレスされなかったメモリストアの回数
  • gst_coherent : コアレスされたメモリストアの回数
  • gst_32b : 32-byte ストアした回数
  • gst_64b : 64-byte ストアした回数
  • gst_128b : 128-byte ストアした回数
  • gst_request : グローバルメモリにストアした回数
  • local_load : ローカルメモリからロードした回数
  • local_store : ローカルメモリにストアした回数
  • branch : 分岐した回数
  • divergent_branch : 分岐によってワープを分割した回数
  • instructions : 実行した命令数
  • warp_serialize : バンクコンフリクトによってシリアライズされた回数
  • cta_launched : 起動したスレッドブロックの数

2009年11月14日土曜日

東京医科歯科大学とのミーティング

小長谷先生と東京医科歯科大学の先生方、そしてオミックス医療学養成プログラムを受講されている方々と I2B2 (ハーバードが実装した Web ベースのデータベース)サーバー設置に関するミーティング。
VMWare ベースでイメージがあり、基本的にはそれを置くだけ。マシンのスペックが、メモリが 1GB しかないのが心配ですね。

Cutting the Electric Bill for Internet-Scale Systems

Cutting the Electric Bill for Internet-Scale Systems
http://ccr.sigcomm.org/online/files/p123.pdf

SIGCOMM2009の論文。まだちゃんと読んでいないが、非常に面白そうだ。

Energy expenses are becoming an increasingly important
fraction of data center operating costs. At the same time,
the energy expense per unit of computation can vary significantly
between two different locations. In this paper,
we characterize the variation due to fluctuating electricity
prices and argue that existing distributed systems should be
able to exploit this variation for significant economic gains.
Electricity prices exhibit both temporal and geographic variation,
due to regional demand differences, transmission inefficiencies,
and generation diversity. Starting with historical
electricity prices, for twenty nine locations in the US, and
network traffic data collected on Akamai’s CDN, we use simulation
to quantify the possible economic gains for a realistic
workload. Our results imply that existing systems may be
able to save millions of dollars a year in electricity costs, by
being cognizant of locational computation cost differences.

2009年11月13日金曜日

NS2: ネットワークエミュレータ

ネットワークエミュレーターNS2 :帯域幅やレイテンシをコントロールする
http://www.isi.edu/nsnam/ns/

プロセスの CPU 使用率をコントロールするプログラム

CPU の使用率をコントロールする Linux プログラム

http://cpulimit.sourceforge.net/

例えば、bigloop という実行プログラムを 40% の CPU 使用率に抑えたい場合には、
% cpulimit --exe bigloop --limit 40
とする。

また、プロセス ID として 2960 のプログラムを 55% の CPU 使用率にするには、
% cpulimit --pid 2960 --limit 55

ROCKS

松浦君の努力のおかげで、やっと、NPACI の ROCKS のインストール画面が起動しはじめました。





2009年11月12日木曜日

Fermi

Fermi に関する詳しい記事
http://www.realworldtech.com/page.cfm?ArticleID=RWT093009110932&p=2

大学院講義演習

徳田研の方2名、秋山研の方1名、村田研の方1名、合計4名が参加してくれました。
松浦くん、老木くん、お疲れ様でした。





2009年11月10日火曜日

EDBT2010: 13th International Conference on Extending Database Technology

http://lbd.epfl.ch/EDBTICDT/edbt-cfp.html

EDBT2010: 13th International Conference on Extending Database Technology

大体9月ぐらい
  • Research paper abstract submission: September 8, 2009, 11:59 pm PST (Pacific standard time)
  • Research Paper submission: September 15, 2009, 11:59 pm PST

2009年11月6日金曜日

Eucalyptus を活用したクラウド環境構築

クラウド研究会で「Eucalyptus を活用したクラウド環境構築」という講演を聞いてきました。


以下、トークのメモ。全く整理されていませんが。。。
-----------------------
- Iaas を実現する Amazon EC2 と互換性を持つオープンソースソフトウェア
- プライベートクラウド構築用
- Amazon EC2 互換とのインタフェースを持つメリット
- API 互換なため、ハイブリッドクラウドの実現が容易に
- RightScale は Amazon EC2 と Eucalyptus 双方に対応
- ライセンスは GPL v3
- 2009/11/05 現在のバージョンは V1.6.1. 09/1/1 の Amazon EC2 の仕様を満たす
- v1.5.2 のバグなどは fix. CLC と CC を同じノードに同居しなければいけなかったが、
   v1.6.1 では解消された
- v1.6.1 は 1.x では最終。これからは 2.x
- Ubuntu 9.10 に Eucalyptus が含まれている
- Eucalyptus の構成
- 3レイヤからなる。
- CLC, (Cloud Controller), CC (Cluster Controller), NC (Node Controller)
- CLC (クラウドコントローラ) :
- 下位のコントローラを制御するスーパースケジューラーみたいな位置づけ
- 簡易的な GUI を提供。ElasticFox から操作可能. ユーザーが VM を作る。IP アドレスが返ってくる
- インタフェースは SOAP, REST をサポート
- CC (Cluster Contoller)
- NC の状態監視 (NC の CPU コア数、メモリ使用量、ディスク使用量)
- スケジューリング .
状態監視につき、インスタンスをどの NC で実行するかを選択
以下のノード。GREEDY(順に割り当てる), ROUNDROBIN, POWERSAVE (VM が立ち上がっていないノードは落とす)
- 1秒単位で NC のリソースステータスを確認している。NC のスケーラビリティ
(Q) NC の数はスケールするか?
- SC というのがある: Storage Contoller: Walrus からイメージ、データを配る

  - NC (Node Contorller):
- insutans (VM)を管理する
- Hypervisor は KVM や Xen をサポート
- 6台、96VMぐらいまでは行ける?と、海外のベンダーは言っていた

- Walrus : Amazon のストレージサービス。S3 と互換性を持つ
- インスタンス(VMのイメージ)をマシンイメージの保管場所

- EBS (Elastic Block Store): アプリケーションやデータを保管する

- CLC, CC の負荷が高い。CLC からイメージ(数GB) がNCに配られ, かつ NC から CC, CLC へネットワーク
 が流れるので、非常に負荷が高い

- プライベートクラウド検証環境の検証
- Xen CentOS 5.3 を仕様
- Eucalyptus のモード. SYSTEM, STATIC, MANAGED, MANAGED-NOVLAN. =-> MANAGED モードを使用
- 1.5.1 スイッチポートでタグVLAN をサポートする必要があった

- v1.5.1 で発生した問題点
- MAC アドレス重複による不具合。
- CPU コア数がインスタンス数の上限? Xeon 4 core, だと4インスタンスだったが、
 Eucalyptus の設定ファイルで、その上限値を変更可能
  - EBS の不具合
- CC がいなくなると、NC の情報がすべてなくなる。冗長化できない。
- 課金の機能などもない。
- v.1.6.1 で一部は解決

- CSK システムズ社で、Eucalyptus をらっぷんぐした自動化基盤 (PaaS)を開発
- Web ブラウザ上から、仮想マシンの追加、削除、起動、停止、仮想マシンの一覧表示を行う
- Web 3層構造 Load Balancer,Web サーバー, DB サーバーを作る
- それぞれのVMインスタンスを用意し、それを追加し、各仮想サーバーを起動
- 外部 Disk (EBS) をアタッチする
- AppScale (Google App Engine のクローン?)が存在

- 最新バージョン v1.6.1
- 複数クラスタ環境をサポート
- Dynamic DNS をサポート。
- オープンソースの監視ツールでステータス確認が可能に。Ganglia と Nagios

- Eucalyptus での開発環境での活用を促進させる

- クラスタ単位は、VLAN という単位。管理の単位

- EMI (Eucalyptus の仮想イメージ)と AMI (Amazon 用) との互換性はない、変換ツールはない

- SLA は保障されるのか? Eucalyptus だけでは無理
- Eucalyptus のみでは商用化は難しい。何か加えないと駄目
- Monitoring の機能とかは商用レベルではない

ベンチマーク

ストリーム用ではないですが、以下のベンチマークに関する論文があります。DSMS 用のベンチマークは以前も書いたと思いますが、Linear Road Benchmark の論文以外はなく、Twitter を含めた様々なデータ特性、性能特性を持つアプリケーションを何種類か用意すれば、論文が一つ書けるでしょう。

A Benchmark Suite for Unstructured Data Processing
Clinton Wills Smullen, University of Virginia
http://www.cs.virginia.edu/~gurumurthi/papers/snapi07.pdf

Rodinia: A Benchmark Suite for Heterogeneous Computing,
IISWC 2009 (IEEE International Symposium on Workload Characterization)
http://www.cs.virginia.edu/~skadron/Papers/rodinia_iiswc09.pdf

次の実験

森田君が、タスク並列を実現できたようです。素晴らしい。
次は左のような実験を Cまたは UDOP でやってみましょう。






Cell Processor 上の 特異値分解高速化

森田君、必見。

Cell 上で SVD を高速化した論文(というか授業の課題?)があるようです。
論文: http://www.mc2.umbc.edu/docs/georgalas-araim.pdf
コード: http://code.google.com/p/cellsvd

ICDCS 2010(The 30th International Conference on Distributed Computing Systems )

ICDCS 2010(The 30th International Conference on Distributed Computing Systems )
http://icdcs2010.cnit.it/

Genoa (Italy) 2010年6月開催。我々と関係するとしたら、以下の2つのトピックでしょうか。

Topics of particular interest include, but are not limited to:

  • Algorithms and Theory
  • Data Management and Data Centers
  • Distributed Cyber-Physical Systems
  • Distributed Operating Systems and Middleware
  • Fault Tolerance and Dependability
  • Network/Internet Protocols and Applications
  • Privacy and Security
  • Sensor Networks and Ubiquitous Computing
  • Wireless and Mobile Computing
Paper Submission
Extended to November 25, 2009 - 12:00 pm, Hawaii time (GMT -10)
Author NotificationFebruary 8, 2010
Final Manuscript Due
March 15, 2010

PACT 2010 (Parallel Architectures and Compilation Techniques)

Parallel Architectures and Compilation Techniques (PACT)
Vienna, Austria, September 11-15, 2010

http://www.pactconf.org/

Abstract Submission March 20
March 27 Paper Submission, Workshop and Tutorial Proposal
Sept. 11-1Workshops and Tutorials
Sept. 13-15 Conference

トピックは以下。
  • Parallel architectures and computational models
  • Multicore, multithreaded, superscalar, VLIW and GPU architectures
  • Scalability and system architecture for parallel systems
  • Compilers and tools for parallel computer systems
  • Compiler exploitation of data- and thread-level parallelism
  • Generating parallel code for domain-specific languages
  • Support for concurrency correctness in hardware and software
  • Compiler/hardware support for managing memory hierarchies
  • Hardware and software support for power/heat-aware parallel computing
  • Parallel accelerators and reconfigurable computing
  • Dynamic translation and optimization for parallel systems
  • I/O issues in parallel computing and their relation to applications
  • Parallel programming languages, algorithms and applications
  • Middleware and run-time system support for parallel computing
  • Reliability and fault tolerance for parallel systems
  • Modeling and simulation of parallel systems and applications
  • Parallel applications and experimental systems studies
  • Case studies of parallel systems and applications
  • Non-traditional parallel computing systems topics

2009年11月4日水曜日

複数カーネル実行 on GPU

タスク並列を現在の CUDA でどのように効率的に行うかを論じた論文です。森田君の研究テーマに非常に関連しています。

PACT 2009 で行われたワークショップで発表された論文
First Workshop on Programming Models for Emerging Architectures (PMEA)

Marisabel Guevara, Enabling Task Parallelism in the CUDA Scheduler
http://www.cs.virginia.edu/~skadron/Papers/guevera_pmea09.pdf

以下、概要。
General purpose computing on graphics processing units (GPUs) introduces the challenge of scheduling task parallel workloads on devices designed for data parallel applications. This paper analyzes the problem, and presents a method for merging workloads such that they can be run concurrently on an NVIDIA GPU. Some kernels do not fully utilize the processing power of the GPU, and thus overall throughput will increase when running two kernels alongside one another. Our approach scans a queue of independent CUDA kernels (i.e., code segments that will run on the GPU), across processes or from within the same process, and evaluates whether merging the kernels would increase both throughput on the device and overall efficiency of the computing platform. Using kernels from microbenchmarks and a Nearest Neighbor application we show that throughput is increased in all cases where the GPU would have been underused by a single kernel. An exception is the case of memory-bound kernels, seen in a Nearest Neighbor application, for which the execution time still outperforms the same kernels executed serially by 12-20%. It can also be benefitial to choose a merged kernel that over-extends the GPU resources, as we show the worst case to be bounded by executing the kernels serially. This paper also provides an analysis of the latency penalty that can occur when two kernels with varying completion times are merged


また、NVida の Forum には、複数カーネル実行の議論が書かれています。
http://forums.nvidia.com/index.php?showtopic=84740

2009年11月2日月曜日

SIGMOD 2010

http://www.sigmod2010.org/index.shtml

SIMGOD2010 のスケジュールは以下のようでした。 来年6月にインディアナポリスで開催されるそうです。 論文投稿のスケジュールが WWW と完全に重なっていますね。

October 29, 2009: Abstract submission (research papers only) 11:30PM PST
November 5, 2009: Manuscript submission (research papers, industrial papers, demonstration proposals) 11:30PM PST
December 3, 2009: Tutorial and Panel proposals submission
February 15, 2010: Notification of acceptance
March 15, 2010: Final camera-ready papers due, 9AM EST

ICDE 2011

論文投稿は毎年6月頃. ICDE 2010 は 3月に Los の Long Beach.

昨年は以下のようなスケジュールだったようです。
Abstract submission deadline: June 10, 2009; 11:00 pm PST (research papers only)
Full paper submission deadline: June 17, 2009; 11:00 pm PST
Author feedback time window: August 4-10, 2009 (research papers only)
Notification of authors date: September 9, 2009
Camera-ready versions due: October 19, 2009

CBI 学会@韓国

CBI 学会 (Chem-Bio Infomatics Society: 情報計算化学生物学会) が明日から開催され、松浦君がポスター発表をします。彼にとって初の英語による学会発表ですので、大変だとは思いますが、頑張ってくださいね。発表ネタは、StreamDNA です。

WWW 2010 に論文提出完了

WWW 2010 (http://suzumura-lab.blogspot.com/2009/10/www-2010-cfp.html) になんとか金曜日から4日連続で書き続け、submit まではこぎつけました。

2009年10月31日土曜日

pin@clip: AR実証実験@渋谷

http://pinaclip.jp/
このデータが研究用途として使えないかどうか、交渉しようと思います。

StreamAR

StreamAR (Augmented Reality) というカテゴリ&プロジェクトを作りました。

中身はないですが、構想をいろいろ練っていきましょう

SPSS 2010 (Scalable Stream Processing System)

http://research.ihost.com/ssps/dates.html
締め切りはDecember 14, 2009,  IPDPS の併設ワークショップという位置づけだが、ストリーム関連の研究者が一同に介するので、結構良いでしょう。何を出しましょうね?10ページ分の Full Paper が要求されているので、それなりにまとまったテーマが必要ですね。まだ、結果は出ていませんが、StreamGPU のネタを出したいですね。

Submission Deadline: December 14, 2009

Notification of Acceptance: January 15, 2010

Camera-Ready Copy Due: February 1, 2010

Workshop: April 23, 2010

2009年10月30日金曜日

あと4日

某国際学会、論文締め切りまであと4日。ここまで短期間で書くのは初ですが、まあ、とりあえず、やれるところまでやりましょう。

テロリストとTwitter

FAS (Federation American Scientists) が出す調査報告書(PDF URL)に Twitter のテロリストの悪用のシナリオが書かれていて、話題にな っているようですね。報告書の11ページに書かれています。

2009年10月29日木曜日

緯度経度情報

StreamTwitter

老木君、もうご存知だとは思いますが、US の City 名からの緯度経度情報は以下から取れるようです。
http://www.realestate3d.com/gps/latlong.htm

ワッサー

http://wassr.jp/
Twitter のクローンらしい

SACSIS 2010

SACSIS 2010、来年は奈良(5月27日から開催)です。1月19日登録締め切りで、26日が論文アップロード。ちょうど卒論のテーマがまとまるころだと思うので、森田君、松浦君と共に、これに出しましょう。国内ではレベルが高い学会なので、ちゃんとした成果が求められます。トラックは C ですね。
http://www.hpcc.jp/sacsis/2010/

ICWS 2010

http://conferences.computer.org/icws/2010/
によると、来年の ICWS (International Conference on Web Services) は7月に Florida で開催されるらしい。ICWS 2005 にも行ったが、そこと同じ会場でしょう。

論文投稿のスケジュールは以下のとおり。
Paper Submission Due Date: Feb. 15, 2010
Decision Notification (Electronic): April 15, 2010

LoadShedder を Twitterアプリに適応するところまでちゃんとできていたら、出したいですね。

鈴村自身は、Ajax アプリの高速化の話(2,3年前に考えていたアイデア)を論文化していないので、それを出す予定。

高速 JavaScript エンジン

StreamTwitter に関して

老木君、

ポストメッセージが多くなると、JavaScript による描画がボトルネックとなるとおっしゃっていましたが、Google Chrome の Browser で表示すると若干改善しませんか?
http://news.cnet.com/8301-1001_3-10030888-92.html


また、先日も言いましたが、JavaScript の JIT コンパイラがあり、最新の Firefox (3.5) にはそれが搭載されていると思います。
http://www.computerworld.jp/topics/browser/119609.html

ただ、それでも限界があると思われるので、Flash を試してみたいですね。開発環境 Adobe Flash CS4 Professional が良いようですが、Academic Editionここによると3万ぐらいみたいですね。もし、本気でこちらの方に興味があるなら、これを購入したいと思いますが、まあ、どれだけ、GUI にこだわるかですね。


日本の Twitter ユーザー数はわずか全体の 0.71%

老木君、以下の統計データに注目してください。すごく参考になりますよ。

http://tweeter.jp/2009/08/14/twitter-743.html
http://tweeter.jp/2009/08/14/twitter-731.html

下図は国別データです。09年6月のデータで1150万人のユーザーを対象にしたものらしいです。やはり、圧倒的に US が多いですね。日本はわずか 0.71%。まだまだですね。



所在地を記載している人の割合。



ちなみに、これらの統計情報は、Sysomos(http://www.sysomos.com/)という企業の Twitter に関する調査 (元ページ) が提供しているものですが、そこの冒頭を見ると、面白いことが書いてあります。

  • 72.5% of all users joining during the first five months of 2009
  • 85.3% of all Twitter users post less than one update/day
  • 21% of users have never posted a Tweet
  • 93.6% of users have less than 100 followers, while 92.4% follow less than 100 people
  • 5% of Twitter users account for 75% of all activity (see the report on analysis of top-5% users)
特に一番下のデータは、やはりパレートの法則が成り立っており、5% の Twitter ユーザーが 75% のアクティビティを行っているのだそうです。

また、この記事によると、06年の全世界のユーザー数は 4450万人だそうで、今年になって急激に伸びているようです。


他にも 以下の URL に統計データがあります。
http://www.sysomos.com/insidetwitter/

時間ごとのアクティビティ。昼時が一番でしょうか。


土日はやはり少なめ。





1日のつぶやき回数
"85.3% of Twitter users update less than once/day; while 1.13% Twitter users update more than average of 10 times a day" だそうだ。

2009年10月28日水曜日

Google Wave サーバークローン

最近注目されている Google Wave のサーバークローンがあるんですね。
http://code.google.com/p/pygowave-server/

Twitter Streaming API を使ったアプリケーション

http://blog.hidekiy.com/2009/06/twitter-live-streaming.html
に Twitter の Streaming API を用いたアプリケーションが公開されています。

そこで面白いのは、Orbited というサーバーデーモンを使っているところです。
Orbited: Real-time communication for the browser (URL)

2009年10月27日火曜日

StreamGPU - SVD 実装

StreamGPU プロジェクトに関して

森田君の実験によって、1次元に関しては行列サイズ 500 程度から GPU によりアクセラレーションされることがわかりました。

次のステップですが、結局、多次元を扱うには、CULA では期待されるパフォーマンスが得られません。やはり、SVD (Singular Value Decomposition) を CUDA 上で自分で実装することが後々、さまざまな制御ができるので、とりあえず自分たちで作ってしまうのがいいのではないかという方向性に行きつつあります。以下が、既存の C で書かれた SVD の実装のリンクです。Numerical Recipes という有名な本がありますが、3番目の TINA に含まれるものはそれそのもので最もシンプルです。

とりあえず、われわれとしては、正方行列の密行列のSVD のみが必要なので、CLAPACK などはオーバースペックで大変ですね。

- SVDPACK : 大規模疎行列用 http://www.netlib.org/svdpack/
- CLAPACK : netlib の有名ライブラリ http://www.netlib.org/clapack/
- SRC/sgesvd.c が SVD の C ソースだが、Fortran からの自動変換のため、
 大変読みずらい
- TINA: Open Source Image Analysis Environment:
http://www.tina-vision.net/tina4/
http://www.tina-vision.net/tina4/doxygen/html/svd_8c-source.html
上記のはほとんど "Numerical Recipes" に書いてあるアルゴリズムと同一


論文としては、以下の論文があります。
Singular Value Decomposition on GPU using CUDA, Sheetal Lahabar, IPDPS 2009
http://web.iiit.ac.in/~sheetal/NN.pdf

PyMW

Python の マスターワーカー用のライブラリ。昨日の計算機アーキテクチャの阪大の学生がこれを使って、Python の MapReduce 実装を発表していた。

http://pymw.sourceforge.net/

CUDPP - GPU 用 データ並列のプリミティブ

Parallel Sorting, Prefix Sum など, データ並列のプリミティブを用意する GPGPU 用ライブラリ
http://gpgpu.org/developer/cudpp
ソースも公開されている

2009年10月24日土曜日

工大祭 2009

皆さん、工大祭、お疲れ様でした。お陰様で、多くの見学者が来てくれましたし、「ストリームコンピューティング」の面白さを伝えられたのではないかと思います。

3年生の老木君、石井君には感謝、感謝です。とてもインパクトの高いデモだったと思います。研究としても、お互いに良い方向にいけそうなので、これからも頑張りましょうね。

4年生の松浦君、森田君、ポスター作り、設営、そして説明など大変だったと思いますが、本当にお疲れ様です。

そして、GSIC の佐藤さん、ポスターの件で強引に呼び出してしまってすみません。また、研究の議論しましょう。

セカイカメラと Twitter の連動

http://www.atmarkit.co.jp/news/200908/21/twitter.html

今日の工大祭で、東工大付属の高校生が iPhone を持っていて、セカイカメラを見せてくれました。私の環境では、iPhone OS 3.1 にすると支障が出るので試せないのが残念なのですが、カメラから写しだされた映像にふわふわ”タグ”が浮いているのが見えました。

2009年10月23日金曜日

拡張現実のライブラリ

なんと、セカイカメラのような拡張現実 (Augmented Reality) を実現するオープンソースライブラリがあるらしい。これを使って何か面白いことをやりたいですね。

http://blog.sohaya.com/2009/08/03/arkit-for-iphone/

セカイカメラと Twitter の連動

http://plusd.itmedia.co.jp/mobile/articles/0910/01/news114.html

IDDY

IDDY http://iddy.jp/
プロファイルの一元管理

2009年10月22日木曜日

CUDA Visual Profiler

CUDA の Visual Profiler があるではないか。これは使えそうだ。
http://gpu.fixstars.com/index.php/CUDA_Visual_Profiler%E3%82%92%E4%BD%BF%E3%81%86

上記のものは基本的に GUI ですが、松岡研究室の丸山さんから便利なプロファイルスクリプトをもらえそうです。

StreamGPU -次元数を高くしたときの性能劣化の問題

http://www.culatools.com/html_guide/index.html#thread-safety
の API を見ると、

typedef enum
{
culaNoError, // No error
culaNotInitialized, // CULA has not been initialized
culaNoHardware, // No hardware is available to run
culaFeatureNotImplemented, // The requested feature has not been implemented
culaInsufficientComputeCapability, // Available GPUs do not support the requested operation
culaInsufficientMemory, // There is insufficient memory to continue
culaArgumentError, // An invalid argument was passed to a function
culaDataError, // An operation could not complete because of singular data
culaBlasError, // A blas error was encountered
culaRuntimeError // A runtime error has occurred
}culaStatus;

と status が見えるので、NoError 以外のときはこれをデバッグで
まずは表示すべき

StreamGPU 実験

GPU 上での予備実験結果

[1次元でのデータ]

SVD に与える正方行列の行/列数 -- 10回の合計処理時間(秒数)
129 -- 8.07
229 -- 9.42
329 -- 12.32
429 -- 16.55
529 -- 19.39

行列サイズ 529 で1回につき2秒あたりなので、CPU だと1分以上かかっている
ので、非常によい結果となった。

[行列サイズ129での2次元以上の結果]
2次元にした結果: 22.31, 22.85 がそれぞれの時間
3次元にした結果: 一部は失敗
4次元にした場合: 48.12, 39.71, 37.52, 43.30 (1次元が8秒なので、大体5倍になっている)


次元数を大きくしても実行時間は線形で増加しないことが期待されるが、きれいに増加してしまっている。そもそも SPADE プログラムが、次元数を高くしたときに、各オペレータが各次元を独立に SVD 計算をしているのだが、各オペレータにすべての次元のデータが送信しているところも問題。

まずはこの問題を解決してみたが、それでもやはり実行時間の増加は変わらず。現在は、各オペレータがプロセスとなって、複数プロセスから CULA の SVD 関数を呼び出している形式。一応、遅いながらも結果は同時にはかれている。 GPU デバイスの状態をやはり、プロファイラで精査する必要があるだろう。

CULA の ドキュメントによると、マルチスレッドからのアクセスは可能と書いてあるが、本質的には同じ。
更なる調査が必要です. CUDA Visual Profiler を使って、System S のスタンドアローンバージョンを実行してみましたが、うまく動作せず。まあ、これは System S なしで確認できる事項なので、マルチスレッド・マルチプロセスにおいて同時に CULA の SVD にアクセスしたときに、やはり線形に増加してしまうかを調査してください

→森田君(工大祭のあとね)

大規模知識処理特論2

大学院の「大規模知識処理特論2」で、3人がストリームコンピューティングの演習を選択してくれた。トップダウンにテーマを与えるよりも、彼らの創造性に期待しよう。

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

以下、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 が使用できるか否か

機械学習リンク

機械学習リンク。オンラインの線形回帰の内積計算には GPU が効果があるはず。
http://ibisforest.org/index.php?%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92

Bitonic Sort

並列マシン用の並列ソーティングアルゴリズム"Bitonic Sort"
http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm
StreamGPU のアプリケーションとして
CUDA の実装が ここからダウンロードできる. StreamGPU 用のアプリケーションとして、いくつか模索中。

2009年10月21日水曜日

StreamGPU 実験

以下の実験をやってみましょう

SST-G (System S の SST GPU 版)
SST-C1 (System S の SST CPU 版, Matrix Compression なし)
SST-C2 (System S の SST CPU 版, Matrix Compression あり)

の3つを以下で比較してください

[前提]
- 今 5000 個のデータがありますが、600個ぐらいのデータに削減しましょう
(500個の時系列データを取るので、実際に計算するのはこれだと100回になります)

[1次元データのみ]
- SST-G : 1回の処理で1秒だとすると、大体100秒ぐらいで終わりますね。
 全体の総実行時間を処理回数で割って、1回の処理時間の平均、最大、最小を計算してください。

- SST-C1, SST-C2 でも SST-G と同様のことを行ってください。

- SST-G, SST-C1, SST-C2 の1回の平均処理時間の比較データを作成してください。
 リアルタイムの異常検知が1秒だとして、SST-C1, SST-C2 においてはその条件が満たせないことを
 示してください

[他次元データの場合]
- SPADE のプログラムを用いて、多次元で計測してください。まずは3次元データですね。
- SST-G :
  - 次元数を 1 から最大 130 まで増加させていって、平均処理時間を観測してください。
  - これで、あまり変わらないことが言えればベストです。1つの次元に対して、
   転送する行列サイズが 500x500 で float だと 1MB 程度。130次元でも
   GPU 上のメモリにのるはずです。

- SST-C1, SST-C2 において、ノード数(3つ)に増やすことによって、スケールすることを確認してください
- ただし、ノード数には限界があるので、SST-C1/SST-C2 が扱えるのは、うちの環境では8次元ぐらいまでですね

- 「次元数が多くても、GPU の場合はレイテンシを保ちつつ、スケールすることが可能」というメッセージが言えればいいですね。


まずは、上記の実験を完了させて、次はウィンドウサイズを可変 (512 ぐらいまで) にして同様の
実験を走らせて、グラフ化すればいいでしょうね。

Mixi API

http://developer.mixi.co.jp/

Borealis Project

2008年版のソフトウェアリリースがありソースが見れますので、 System S/SPADE と比較してみてください。GSIC 佐藤君が少し論文を読んでくれましたが、また、続きをやりましょう。
http://www.cs.brown.edu/research/borealis/public/#software

StreamGPU

森田君の System S なしの、CPU vs GPU の SVD の結果が出てきました。行列サイズ256 ぐらいから差が出てきて、行列サイズ 512 ぐらいだと、CPUが12秒、GPU が1秒以内と明らかな差があります。

次は System S ですが、Matrix Compression なしのバージョンで測定しますが、ウィンドウサイズをそのぐらいにすればさっくりと高速化できることが期待されますね。

しかも、センサーの次元数が今は130ぐらいまでデータとしてはありますが、現実的には CPU では 3までしかやっていません。GPU を使えば、130 ぐらいの次元数まで扱えることが期待されます。プログラミングモデル的にもそれは容易に書け、ただ単に SVD を呼び出す UDOP を呼び出すだけですね。

2009年10月20日火曜日

Quantum Leap

最近、良くメディアの登場する MIT の Media lab の石井教授が使っていた言葉。"Innovation", "Smarter ..." などより、遥かに含蓄のある良い言葉だ。

CULA に関する質問

CULA の SVD に関するドキュメントが少ないので、メールを打ってみた(ここは本当は私がやるべきではないのだが。。。)。 重要なのは、culaSVD がやはりブロッキングという点だ。

-----
Hello, to answer your questions
1) These are job codes which control what the routine calculates singular vectors and where they are returned. The code 'A' says to calculate the full U/Vt matrices. Users will typically use the code that calculates the minimum required results in order to lessen computation time.

CULA routines follow closely the LAPACK standard for routine naming and arguments. Full documentation of the routines will be in CULA 1.1, but in the meantime we can use this: http://www.intel.com/software/products/mkl/docs/webhelp/lse/functn_gesvd.html Note that our routines have cut the work and info parameters from the list.

2) culaSgesvd blocks. You will find that runtimes are sufficiently long that the blocking will not impair performance.

3) Yes, CULA is thoroughly threadsafed. The only function that can be adversely affected is culaGetErrorInfo() which returns the most recent Info code triggered by any thread (which may be a different thread from the one currently executing.) Info codes are normally errors in your data or arguments, so these can be debugged in a single-threaded environment most of the time.

For each thread you have three options -
1) Pre-bind each thread with a call to cudaSetDevice, using the CUDA toolkit. This is the most flexible, allowing you to choose which GPU each thread binds to.
2) Bind by calling culaInitialize() in each thread. CULA will bind to the GPU it determines is best, but this will result in each thread binding to the same GPU.
3) Do neither #1 nor #2 and accept CUDA's default binding, which is always device zero. Note that in order to use CULA, your first thread will still need to call culaInitialize().

Regards,
John

コールセンターにおけるリアルタイム検知

良く引き合いに出すコールセンターの例
http://09197218.at.webry.info/200905/article_71.html

ボットネット対策プロジェクト

総務省、経済産業省のボットネット対策プロジェクト
https://www.ccc.go.jp/

WWW 2010 CFP

Abstract は 10/26. ちょっと今年は難しそうかな。
http://www2010.org/www/authors/cfp/

StreamShedder 続き

松浦君の卒論テーマに関して。

このエントリ の論文では、オンラインとオフラインのジョブの resource sharing 手法を提案しています。この論文との差異を述べてください。

Flickr API

http://www.flickr.com/services/api/

回帰分析によるストリームデータのクラスタリング

以下の論文を読むべし

「回帰分析によるストリームデータのクラスタリング」、日本データベース学会

http://www.dbsj.org/Japanese/DBSJLetters/vol2/no3/papers/motoyoshi.pdf

論文概要: 局所的に異なる傾向を持つストリームデータにおけるクラスタリングについて述べる.このようなデータはそれぞれのクラスタが異なる線形関数で回帰すると考えられる.そこで,結合の基準として回帰式のF検定統計値を用いた階層的クラスタリングの差分方法を提案する.本手法により,解釈可能な数のクラスタを抽出でき,かつストリームデータに適応できることを検証する

オンライン線形回帰

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

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

SDP (Socket Direct Protocol) を用いた高速通信

大規模クラスタにおけるソケットダイレクトプロトコルSDP の性能評価, SWOPP 2005, 緑川先生(成蹊大学) (PDF)

ソケットダイレクトプロトコルSDP は,伝統的なソケットストリームAPIを提供しつつ,RDMA プロトコルに直接マッピングすることにより高性能な通信を可能にするプロトコルである.この論文では、Infiniband 上に実装された SDP の通信性能をクラスタ上で評価し、ギガビットネットイーサネットと IPoIB とを比較している。結論としては、SDP は小さなメッセージサイズに対しては優位性がないが、大きなメッセージサイズに対してはレイテンシおよびスループットで有利という。
ストリーム処理における高速データ転送に参考になる論文だ。

2009年10月19日月曜日

SVD の C実装

特異値分解の C 実装は以下にあります。

http://www.netlib.org/svdpack/

file svdpackc.tgz
for C version of SVDPACK for computing the SVD of large
, sparse real matrices
by Michael W. Berry et al.
ref M. Berry et al., "SVDPACKC (Version 1.0) User's
, Guide", Univ. of Tennessee Tech. Report CS-93-194,
, April 1993 (Revised October 1996)

特異値分解 on GPU

名古屋大学の研究者の仕事のほかに、SVD の GPU 上での高速化の論文が IPDPS 2009 で発表されているようです。この論文によると、やはり、256x256 ぐらいまでの行列では、CPU 版の方が速く、それより大きな行列サイズでの GPU 版での高速化が見られています。我々の戦略としては、まず、Matrix Compression なしに、行列サイズをできるだけ大きくし、CPU 版と勝負しましょう。

また、複数のセンサーデータを同時に計算することによって、レイテンシ及びスループットを稼ぐこと。そのためには、ブロッキングしないようにすべき。現状の CULA を見ると、ブラックボックス化しているため、よくわからない。やはり、Next Step としては、CUDA API を使って実装すべきだろう。

Singular value decomposition on GPU using CUDA (PDF)
http://portal.acm.org/citation.cfm?id=1587556

Linear algebra algorithms are fundamental to many computing applications. Modern GPUs are suited for many general purpose processing tasks and have emerged as inexpensive high performance co-processors due to their tremendous computing power. In this paper, we present the implementation of singular value decomposition (SVD) of a dense matrix on GPU using the CUDA programming model. SVD is implemented using the twin steps of bidiagonalization followed by diagonalization. It has not been implemented on the GPU before. Bidiagonalization is implemented using a series of Householder transformations which map well to BLAS operations. Diagonalization is performed by applying the implicitly shifted QR algorithm. Our complete SVD implementation outperforms the MATLAB and Intel ®Math Kernel Library (MKL) LAPACK implementation significantly on the CPU. We show a speedup of upto 60 over the MATLAB implementation and upto 8 over the Intel MKL implementation on a Intel Dual Core 2.66GHz PC on NVIDIA GTX 280 for large matrices. We also give results for very large matrices on NVIDIA Tesla S1070.

Google Social Graph API

http://code.google.com/intl/ja/apis/socialgraph/docs/

Google Wave

最近注目されている Google Wave
http://code.google.com/intl/ja/apis/wave/guide.html

Google Wave

最近注目されている Google Wave
http://code.google.com/intl/ja/apis/wave/guide.html

Google Data API

Google 上のサービスに触る様々な API セット。例えば、Bloggerなどのブログをフェッチできる
http://code.google.com/intl/ja/apis/blogger/docs/2.0/developers_guide_protocol.html#RetrievingMetafeed

StreamShedder

松浦君が行っている StreamShedder の研究へのコメント

■ SSD にどのくらいデータを退避させれば良いか.
データ受信部の CPU とネットワークがぎりぎり耐えられるぐらいのデータ量が学習モードで把握できるはずなので、その分 SSD に退避させればよい

■ SSD に退避できないぐらいのトラフィックがきたときは
  どうするか?
- 捨てる?

■ 負荷情報はどのように具体的に何からとるか?
- 実装は何を使う? vmstat ?
- 突発的な負荷の変化以外に、学習していけばどのような周期でデータレートが変化するかがわかるはずなので、それも活用すべき

■ 高頻度に、”高データレート”→”低データレート”、”低データレート”→”高データレート”のモードを
 を繰り返すときに、ナイーブに実装すると、処理が「ストリーム処理」と「バッチ処理」の切り替えが頻繁におきてしまう。どのように対処するか? マクロ的なスケジューリングも大事

■ ストリーム処理→バッチ処理、バッチ処理→ストリーム処理にコンテキスト切り替えするときの、どのように状態を保存するか?特に、バッチ処理の途中で、モードが変化してはまずい

■ この階層型の Load Shedding がどのようなタイプのアプリケーションに効果的かをはっきりさせるべき。例えば、SSD による退避で、後か結果を知っても意味のないタイプのアプリケーションがあるはず。
どのようなアプリに効き、どのようなアプリに効かないかを明らかにすべき

■ この研究の定量的な評価をどのように行うか?アプリケーションとしては、Twitter のほかには何を使うか?

2009年10月18日日曜日

Google Trend

現在、もっともホットなキーワードを表示するアプリ、Google Trend.
http://google.co.jp/trends/hottrends?sa=X

インフルエンザの流行を検索キーワードから予測するサービス Google Flu Trend.
http://cotoha.jp/2009/10/google-flu-trend-jp.html

老木が今行っている Twitter を用いた降雨情報をより汎用化し、かつ Twitter だけでなく、様々な情報ソースを利用すれば、Google と同じようなサービスを提供できるはずですね。

最近は何でも Google ですが、我々のような公的機関からも、世界を変えるサービスを提供していきたいですね。

2009年10月16日金曜日

リアルタイム経済動向

例えば、以下のような求人情報を提供する RSS を用いれば、政府が出す失業率などの情報よりもいち早く、経済動向を提供することができるでしょうね。私としては、究極的にはリアルタイム GDP が実現できれば、非常にインパクトが強いと思っています。

http://rikunabi-next.yahoo.co.jp/rnc/docs/ci_s00910.jsp?html_nm=rss_guide/rss_guide.html

Web API をセンサーデータに

各企業の Web API も、使い方によってはセンサーに。単一のセンサーだけでなく、RSS や下記の Web API をセンサーと見立てれば、いろんなことができるでしょうね。

写真共有サイト Flickr の API
http://www.flickr.com/services/api/

Yahoo Web API
http://developer.yahoo.co.jp/webapi/map/

Amazon Web Services
http://aws.amazon.com/

RSSをセンサーに

ある程度リアルタイムに取得できる情報源としては、Twitter などもありますが、昨今、さまざまなサイトが RSS を公開しているので、世界のあらゆる RSS をストリームとして扱ったもいいでしょうね。

RSS ナビ
http://www.rssnavi.jp/

Twitter と SMS

Twitter がSMS 送受信に対応するようになるようだが、こうなると、そのメッセージ数も更に膨大になるであろう。
http://jp.techcrunch.com/archives/20091014striving-for-four-billion-mobile-users-twitter-strikes-sms-deal-with-largest-indian-carrier/

Facebook Streaming API

SNS サイト Facebook も Streaming API を以下のサイトで公開しはじめたようだ。こちらも我々のアプリケーションとして使えそうだ.

Facebook の Stream とは、Twitter のようなコメントの他に、写真のアップロードやプロフィールなどの
アップデートをさすらしく、Stream を受けるには ユーザーの許可が必要だそうだ。これでは、あまり使い物にならないですね。

http://wiki.developers.facebook.com/index.php/Using_the_Open_Stream_API
http://jp.techcrunch.com/archives/20090427facebook-opens-up-its-stream-api-to-developers/

Twitter の統計情報

Web サイトの統計情報を提供するサイト Alexa では、Twitter のアクセス数は、13位。 ちなみに、40% が US からのトラフィックで Japan はわずか 3% (http://www.alexa.com/siteinfo/twitter.com).
Top 10 は、Google, Facebook, Yahoo, YouTube, WindowsLive, Wikipedia, Blogger.com Microsoft Network, Baidu, Yahoo カテゴリ, MySpace, Google India 、そして Twitter. 日本は、
http://www.alexa.com/topsites/countries/JP を参照。

Twitter 社自身が提供する統計情報サイト
http://twittercounter.com/

- "Featured User" としてお金を払えば、そのユーザーがこのサイトで Feature される。目的としては、たとえば、現在トップに表示されているのは、不動産屋の人。口コミなどでの、マーケティングや広告効果があるのであろう.
- 超有名人、たとえば、Britney Spears Barack Obama なども存在。Follower 数は 300万人以上
 http://twittercounter.com/britneyspears
- CNN や New York Times などのニュースサイトなどもサイトへの誘導などにあるのか。
Follower 数 360万人 http://twittercounter.com/cnnbrk


Twitter100: ある特定の Follower の Top 100 を表示するアプリ
http://twitter100.com/

Twitter の自分の発言を時間軸に表示する Web アプリ
http://teahut.sakura.ne.jp/timeline/twitter/?user=takemaru_jp

2009年10月15日木曜日

PHPグラフ化ツール

PHPでかっこよくグラフ化するツール
http://www.maani.us/charts/index.php

セカイカメラ



- 非常に気になるのは、セカイカメラのサーバーアーキテクチャと仕様。まだユーザー数は少ないだろうが、これが爆発的に流行りだすとそれなりの台数が必要だろう。

- 位置の取得は、屋内では、WiFi からのシグナル強度(3点)から推定しているらしい。

- Open Air API というものが11月に公開されるらしい。ストリームとの組み合わせで何か面白いことができそうかもしれない

TAG A Tiny Aggregation Service

TAG A Tiny Aggregation Service, OSDI 2002
http://db.csail.mit.edu/madden/html/madden_tag.pdf

この論文は読むべし

Live E! プロジェクト

http://www.live-e.org/wgroup/index.html
12カ国に設置された計 100台を超えるセンサー(気温、温度、気圧、雨量、風向き、
風速, CO2 濃度など)がリアルタイムに取得可能。奈良先端の砂原先生などがリード.
利用方法は以下
- 雨量センサ情報をリアルタイムに流通させ、コンビニエンスストアへの
 利用促進と書かれている
- ヒートアイランド現象の解析
- ゲリラ豪雨の検出
- 大気汚染の実態把握
- データの呼び出しインタフェースは
http://www.live-e.org/pdf/live-e-spec_dataprovider200901.pdf
に記載されている。
- SOAP の Web インタフェースが用意されているので、実際のデータを取得することができる

このように専用のセンサーデバイスを分散させるのが国家プロジェクトとして多いが、Twitter や iPhoneのアプリなどの集合知を利用する方法が個人的には好きだ

経営戦略

下記エントリ「ミドルウェアの任務」に関係します。

私は ご存知の通り, IBM に勤めていますが、IBM はできるだけ汎用のミドルウェアを作って、それを横展開することで業を営んでいます。IBM の顧客としては、金融、通信、電機、航空宇宙、製造などあらゆる業界を相手にしていますが、大事なのは、汎用的なミドルウェア(これには莫大な投資をする が)を作るが、あとの業界に特化した知識なりその処理アルゴリズムは、顧客(もしくは顧客が雇うソフトウェアベンダー)に書かせるという戦略を取っていま す。若い人はご存知ないかもしれませんが、IBM は1990年代初頭に会社がつぶれるくらいに業績が落ち込んだ時期があり、その頃何千人ものリストラをしています。しかし、その後、「アプリケーションに は手を出さない」「利益が少ないコモディティハードウェア」は売らないという思い切った経営戦略を取ることで、見事に復活しました(ハーバードビジネスス クールなどの MBA などのプログラムでは、その復活劇が教科書に出てくるらしいです)。この戦略が功を奏してか、IBM におけるソフトウェアビジネスの全体の利益に対する貢献は年々高くなっていっています。

ミドルウェア屋の任務

 国立情報学研究所の佐藤先生の「クラウド時代の到来でコンピュータサイエンスは終わった」(URL) というセンセーショナルな記事がありますが、佐藤先生が言わんとしているところは、情報科学は、社会の現実社会の問題をちゃんと解く研究をするべきだ、ということを言っています。これは正に念頭に置くべきで、我々ミドルウェア屋さんの任務は、それらの要件を徹底的にまずは調べて (インタビューしたり)、それを汎用化したときにどのようなソフトウェア処理系が必要か、プログラミングモデルが必要かを考えることです。なので、最近停滞気味ですが、前、楽天に行ったようにいろいろなユーザーの声を聞いていきたいと思います(研究に支障のない程度に)。

 このように、 現実的なアプリケーションを見据えた処理系の拡張、および性能最適化を行っていくことが極めて重要であると感じるので、この1、2年は実際のアプ リケーションを Twitter だけでなく、他にも増やしたいと思います。ただ、バイオの例にあるように、我々がアプリケーション分野にどっぷり漬からないことが味噌かもしれません。どちらかというと、ユーザー(アプリケーションの知識を持っている人)をこちらのミドルウェアを使ってもらうというスタンスがベストですね。

2009年10月14日水曜日

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

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

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

- 仮想マシンを用いた 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

Twitter 関連

Twitter のタグクラウドが表示されるページ
http://www.twitscoop.com/

Twitter 統計

Harvard Business School の記事によると、10%のユーザーが90%のトラフィックを生んでいるんだそうです。
http://blogs.harvardbusiness.org/cs/2009/06/new_twitter_research_men_follo.html

松浦君卒論

松浦君の卒論ですが、

今3年生が精力的に進めている Twitter をアプリケーションとして、

Load Shedding SSD/RamDisk への退避 + (Online+Offline の融合)

をやっていくことになりました。金曜日に彼に詳細を話してもらいます。

参考エントリ
http://suzumura-lab.blogspot.com/2009/08/offline-online-sharing.html
http://suzumura-lab.blogspot.com/2009/06/blog-post_17.html
http://suzumura-lab.blogspot.com/2009/05/power-law.html

卒論の方向修正

松浦君の卒論テーマですが、方向修正することになりました。

 といっても、StreamDNA や StreamBIO 関係のプロジェクトが終焉するという意味ではなく、このプロジェクトに並々ならぬ興味を持つ4年生が入ってくるか、もしくは、我々の研究室以外のバイオ系の学生で興味がある学生がいたら、是非やってもらいたいとは思っています。
 
 

SST

森田君が見ている高橋さんの DPS コードに関する説明

- Input.csv の見方

- 各行は、センサーデータそのものをあらわす。一応 130 次元まで対応するように、130個あるが、実際に高橋さんが実験をしたのは 16, 32 次元ぐらいまで
-第1列目が到着する間隔をあらわす。5 だったら、
 5秒待つという意味. 0だったら待たない
- System S のバグで、第1列目は読み込んでもらえない
- vstream inputDatStream は使う次元数をあらわす。この場合だと次元数は 4
- for_begin で センサーの各次元に対する計算
- Aggregate は、49 個(49行)のセンサーデータを集めて、Col(data@i)
で @i 次元目のデータをすべて出力ストリームで返す。なので、型は FloatList

- CPU のスケールアウト数を変える方法
- GeneralPool[] の 1 とノード数に変更する
- Makefile のノード数を変更する必要あり
- 時間は、開始時刻と最終時刻の引き算を実行

2009年10月13日火曜日

Dolly+の特徴

Dolly+ の特徴は以下の通り。高速化の要点は以下の3つ。

(1) コピー対象ホストをマスターホスト(コピーされるイメージを持つホスト) を先頭としたリング状に接続し、パイプライン転送をおこなう。

(2) マスターホストでのボトルネック発生を回避し、 送信と受信を同時に行える 全2重通信 (Full Duplex) のネットワークスイッチの性能を最大限に活かす (** 我々の Linux クラスタで Full duplex 通信可能なように設定する必要あり)

(3) ネットワークからデータを受け取るスレッド、データをディスクに書き込むスレッド、データをネットワークに書き出すスレッドの3スレッドを同時に実行し、かつ、巨大なファイルを 4MB ずつのチャンクに分けてコピーすることによって、高速化。
(詳細は http://matsu-www.is.titech.ac.jp/paper/takamiya/sacsis2003.pdf の3.3.1 章参照)

データ配信最適化

松浦君に関係するものです。

- 以下の論文、要チェックです。
  • A Stable Broadcast Algorithm, Kei Takahashi, CCGrid
  • A pipeline technique for dynamic data transfer on a multiprocessor grid
  • トポロジを考慮しソース選択を行うデータ転送スケジュラー(PDF)
  • FastReplica: Efficient Large File Distribution with Content Delivery Network , USENIX, 2003
  • A Fast Topology Inference - A building block for network-aware parallel computing, HPDC 2007
  • Exploiting Hiearchy in Parallel Computer Networks to Optimize Collective Operation Performance, 200
  • Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks, SIGCOMM 2004
  • An approach to communication-efficient data redistribution, 1994,
  • グリッド環境におけるクラスタ間データ転送の評価 (松岡研 小倉)
  • Spring-8 からの画像転送。2003年のスライドだが、我々と少し関係がある
    http://www.biogrid.jp/project/j/event/seminor/inoue/pdf/biogrid2003Telescience.pdf
- ネットワークのチューニングに関してはもちろん、いろいろあります。

Quantitative Comparison of Xen and KVM

オープンソースのハイパーバイザとしては XenKVM (Kernel-Based Virtual Machine) が有名だが、その定量的比較を行った論文。
"Quantitative Comparison of Xen and KVM" (PDF)

以下、論文の中身。

- benchvm というオープンソースのハイパーバイザ用のベンチマークソフトが存在

- Linux のカーネルのコンパイルが CPU も I/O も程よく使うので、この手の世界ではコンパイル時間で比較を行っている。KVM も Xen も 仮想化なしに比べて半分以下の性能。仮想化なしを 1.0 とすると、Xen は0.487, KVM は 0.384 という結果。

- CPU のみを使う場合は、仮想化なしに比べて Xen も KVM もほとんど変わりなしで、やはり I/O が一番仮想化のオーバーヘッドが効いている。

- また、複数の VM が実行される状況で、 Performance Isolation (互いに性能への影響を与えない)がうまくいっているかどうかのテストをしている。メモリや Fork, CPU Disk, そしてネットワークの送信、受信それぞれの比較を行っているが、ネットワークに関しては Xen も KVM に関してもどちらもよろしくない。 System S のようなデータストリーム処理で使用するには不向きだが、逆に言うと、いろいろ最適化ポイントがありそうだ。

- 最後に何個の VM を立ち上げられるかをテストしているが、Xen の方が圧倒的に上回っており、KVM は散々たる結果となっている。

2009年10月11日日曜日

StreamTwitter の研究課題

StreamTwitter に関して、パブリックに取得できる莫大なデータとして、データストリーム処理の研究を行う上での絶好のアプリケーションと言える。ブログやその他の Web ページからの抽出と比較して、130文字という制約があるので、システム的に解析がしやすいという特徴も持っている。

老木君、石井君が今まさに実装している
「リアルタイム降雨情報」
「類似ユーザー検索」

などの他に

「リアルタイム地震検知」
「最もホットなキーワード Top 10」
「リアルタイム経済指標」(消費者物価指数、失業者数。。。)
「リアルタイム選挙速報」
「リアルタイムな商品情報」→販売戦略の見直し
「リアルタイムな企業情報」→株価への反映→投資銀行などの自動売買への利用
...
など Twitter のデータを用いて、様々なリアルタイム解析が可能になるだろう。

ストリームコンピューティングの研究としては、如何にこれらのアプリケーション用の汎用プログラミングモデル(すなわち汎用オペレータ)を定義し、Bursty な状況でも適切に有用な答えを返すかが重要な研究課題となる。

特に、上記の複数の解析が混在する可能性があり、それぞれの解析のプライオリティも異なるはずであろう。Bursty な状況で、ただ単に解析をストップするだけでなく、確率的に処理を行い、ある程度の精度を持って解析をすることによって負荷を小さくしたり、類似度計算に必要なベクトル計算などは GPGPU を用いることもできる。

また、さらに、Twitter だけのデータを用いるのではなく、より信頼性のあるデータソースと組み合わせることで、結果の精度を高めることもできるであろう。

来年以降のテーマであるが、期待したい

2009年10月9日金曜日

高速データ転送システム

高速データ転送システム Dolly+
http://corvus.kek.jp/~manabe/pcf/dolly/index_J.htm

松岡研究室の滝澤さんの研究
http://matsu-www.is.titech.ac.jp/slides/takizawa/swopp04slides_takizawa.pdfMHg

工大祭

工大際まで約2週間となりました。そろそろ何を展示するかを考えていきましょう。

(0) 鈴村研究室概要 (by 鈴村)
- 研究室概要
- ストリームコンピューティング概要

(1) StreamBIO プロジェクト (by 松浦君)
- スライドを完成させてください. 1枚 Version と Long Version を作成してください。
- Long Version に関しては、韓国の学会でも使用することを想定して作ってください
   (英語でもいいです)
- 「データストリーム処理におけるデータ配信技術の最適化」という情報科学としての技術的な貢献も書くと良いと思います。
- できるだけ間に合う

(2) StreamGPU プロジェクト (by 森田君)
- スライドを完成させてください. 1枚 Version と Long Version を作成してください
- GPU に詳しくない人も来るはずなので、その説明チャートも用意しておいてください。
- 頑張って、「GPU を使うとこれだけ速くなるんだ」という性能評価結果を載せてください

---- 以下は Optional です。非常に面白いものとなるので、できれば、展示してくれるとうれしいです。

(3) プロジェクト雨流 (by 老木君)
- (間に合えば)デモと概要スライドをお願いします。
- せっかくなので、IBM の Intern で行った 「System S を用いた Web サーバーの構築」も 概要スライドを張っておきましょう。

(4) Twitter上の 類似ユーザ探索bot (by 石井君)
- (間に合えば) デモと概要スライドをお願いします。
- System S へのポーティングが間に合えばそれを、間に合わなくても現状のも石井君が創作演習で作ったものを見せてくれれば良いと思います。

データストリーム処理における大規模データ配信技術

 松浦君のテーマは 「データストリーム処理における大規模データ配信技術に関する研究」という技術的なコアを基盤にして、たんぱく質の立体構造解析、次世代 DNA シーケンサー, 電波天文学、そして街中の監視カメラなどから出力される大量(画像)データへの高速処理に寄与する、といった研究のまとまりができつつある。

 ただ、これに関しては、グリッドやネットワーク、画像配信, CDR (Contents Delivery Network) などでの豊富な研究があるので、如何にデータストリーム処理ならではの問題を掲げ、それに対する解決策を提案しないと ”情報科学”としての 新規性や進歩性にかける。今考えている、「リレー方式によるデータ配信」、「UDP によるマルチキャスト配信」などがあるがこれらは既知の技術であるので、我々としての技術的な貢献を考えていきましょう。

まず既知の技術の性能評価をするのが First Step ですが、その次に以下のことを考えていきましょう。
(1) ゼロコピー通信
(2) 実行環境に応じて、最適な配信方式、トポロジーを(プロファイルデータなどから)自動的に決定する仕組み

Next Step for StreamGPU

森田君のStreamGPU プロジェクトに関して、そろそろ CULA 版が動き出しそうな感じなので次のステップを書こう。

(1) CULA SST (CULAの SVD 関数を使うバージョン) を完成させる(あともうすぐ)

(2) SST (高橋さんのオリジナルバージョン) と (1) の CULA SST の性能比較を行う。このとき、ウィンドウサイズをいろいろ変更していって、どのような性能差が得られるかをグラフ化する。 このとき、SST 版は1ノードだけでなく、多ノードを用いてスケールアウトのデータを出す。
- データに関しては、スループットだけでなく、1データあたりのレイテンシを求められるようにする
- また、newmat の Matrix 型から 1次元配列、そしてその反対のコストがパフォーマンスのボトルネックになることを確かめるため、スタンドアローンバージョン (-T でコンパイル)で実行し、oprofile でプロファイルを取る。translate/detranslate の関数が CPU をあまり使用していないことを確認する


(3) SST は特異値分解が重いため、高橋&井手バージョンでは、 Matrix Compression をして、与える行列サイズを小さくしている。GPU を用いることにより、そのような Compression をしなくても、それなりの性能が得られる可能性が得られるため, そのバージョン(これは高橋さんから既に頂いている)を 再び CULA の SVD 関数を使うように移植し、(2) との比較を行う。結果として、Matrix Compression などの工夫を行わなくても、GPU を用いれば十分に高速化できることを示す

(4) 以下の状況下において最適な条件を数理的なモデルを用いて自動的に決定できるようにする。
- 1ノードのみ (CPU と GPU)
- 複数ノード と 1GPU
- 複数ノードと マルチ GPU (マルチGPU は松岡研究室の GPU クラスタを使用させてもらう)
また、モデルを用いて、どのような条件下では GPU を使うか、

(5) System S / SPADE において、GPU のようなアクセラレータを使用する汎用的な オペレータ はどのような形で提供すべきかを考察する

2009年10月8日木曜日

SWOPP

http://www.hpcc.jp/swopp/
毎年8月開催
査読なし

情報処理学会全国大会

http://www.ipsj.or.jp/10jigyo/taikai/72kai/index.html
2010年3月 東大本郷キャンパスで開催。
発表申し込み締め切りは11月27日。

SC (Super Computing)

Super Computing に関する学会および巨大な展示会
http://sc09.supercomputing.org/

来年は是非ここでデモンストレーションをやりたい。

ACS 論文誌

http://www.hpcc.jp/acs/

電気情報通信学会 データ工学研究会

http://www.ieice.org/iss/de/jpn/
いまいちアクティブではない(?)

WebDB Forum 2009

http://db-event.jpn.org/webdbf2009/index.html

情報処理学会データベースシステム研究会

http://www.ipsj-dbs.org/

査読なし。毎年3回開催。

以下、Webページから抜粋。

データベースシステム研究会は、主に、DBMS (Database Management System) 技術、データモデリング、情報検索、ハイパーテキスト・ハイパーメディア、マルチメディアデータベース、データベース高度応用などの分野を対象として研究 会活動を行ってきております。データベース系の他の団体との共催イベントを毎年 3 回程度(7月,11月,3月)開催しています。

インターネット・イントラネットとマルチメディア技術の進展により、データベースシステム技術の重要性と関心が一層大きくなるとともに、ネットワー ク・マルチメディア時代の新しい情報共有の基盤ソフトウェアとしての新しいデータベースシステム像が求められています。実際、これに関する研究活動が活発 化しており、研究会としても積極的にこの分野を取り上げていきたいと考えています。データベース技術の需要は増える方向にあり、今後も学会活動に積極的に 取り組んでいきたいと考えております。

日本データベース学会

http://www.dbsj.org/Japanese/event/index.html

CIDR

CIDR(The biennial Conference on Innovative Data Systems Research)
http://www.cidrdb.org/cidr2009/

学会開催は1月。論文締め切りは毎年9月ごろ

INSS International Conference on Networked Sensing Systems

ストリーム関係の国際学会
INSS(International Conference on Networked Sensing Systems)
http://www.inss-conf.org/2009/cfp.shtml
2010 年は1月中旬が締め切り

2009年10月6日火曜日

Twitter を用いた研究

国際会議 WWW などを調べてみたが、Twitter いわゆる Microblogging を使った研究はまだまだ手をつけられていない。自然言語処理または Web データマイニングの方面から攻めるか、データストリーム処理との組み合わせでシステムソフトウェア+パフォーマンスの方面から攻めるか。

前者だと、通常のブログのマイニングが盛んに研究されているため、マイクロブログならではの性質を活かした新たな手法を提案する必要があるであろう。後者は、新規性十分なので、ちゃんと実験して書けば通るでしょう。

以下、ざっと調べた結果。

Twitter のトラフィックに関する記事
http://blog.compete.com/2008/05/15/twitter-traffic-growth-usage-demographics/
http://siteanalytics.compete.com/twitter.com/?metric=uv


Why we twitter
: understanding microblogging usage and communities
International Conference on Knowledge Discovery and Data Mining (KDD 2007)
(Download PDF) : この論文の参考文献も参考になります

「Twitterとパンデミックデマに関する研究
http://www.geekpage.jp/blog/?id=2009/8/28/1

Beyond Microblogging: Conversation and Collaboration via Twitter
(Download PDF)

2009年10月3日土曜日

Personal Genome Project (PGP)

Personal Genome Project (http://www.personalgenomes.org/)
パーソナルゲノム医療を加速化するために10万人の個人のゲノム情報を収集するプロジェクト

以下の YouTube のビデオが興味深いです。
GENOME : The Future is NOW WEBISODE 1

2009年10月2日金曜日

StreamTwitter

とりあえず命名。石井君は類似ユーザーの自動検索プログラムをポーティング、老木君はアメダスを System S で実装することになりました。非常に面白いですね。楽しみにしてます。

2009年10月1日木曜日

Google Charts API

Google が提供するグラフ作成サービス。URL に パラメータを指定すると、作成された PNG グラフが返される。System S の 最終結果を可視化するためのツールとして使えるだろう。
http://code.google.com/intl/ja/apis/chart/#chart_type

Bootchart

http://www.bootchart.org/
基本的には、サーバ起動時の負荷状況やプロセスの推移をグラフ化するためのツールだが、多分、boot 時でなくてもできるはず。割ときれいな可視化ができそうです。

2009年9月28日月曜日

System S の Discussion Forum

アクセスするには ID を登録する必要があります。
http://www.ibm.com/developerworks/forums/forum.jspa?forumID=1664

高速プロセス通信

老木君のインターンは明日で終了ですが、System S に関する様々な最適化ポイントが浮き彫りになってきました。一つはプロセス間通信(例:Linux KernelのIPC)の重さですが、その最適化として様々な手法が提案されています。

はてなのシステム内部

はてなブックマークのシステム内部アーキテクチャに関する解説
http://www.slideshare.net/naoya1977/ss-1983437

2009年9月27日日曜日

統計情報を用いた性能モデル

以下、StreamGPU プロジェクトで参照すべき性能モデルに関する論文(の一部)です。
  • 性能予測モデルの学習と実行時性能最適化機構を有する省電力化スケジューラ, 金井、Comsys 2007 (PDF)
  • 尾形 泰彦,遠藤 敏夫,丸山 直也,松岡 聡. 性能モデルに基づくCPU及びGPUを併用する効率的なFFTライブラリ. 情報処理学会論文誌コンピューティングシステム,Vol.1,No.1 (ACS 22), pp. 40-50,2008年6月.

2009年9月26日土曜日

2009年9月22日火曜日

Optimization Idea

GPGPU を DSMS にどのように活かすか、アイデアを以下に書いてみました。今度、説明します。
http://sites.google.com/site/suzumuralab/streamgpu/StreamGPU-suzumura-20090922.ppt?attredirects=0

WikiCFP

WikiCFP(http://www.wikicfp.com/cfp/home): CFP (Call For Paper) をコミュニティベースで集めたサイト. 鈴村研究室の CFP を suzumuralab というユーザーで作成しました。

2009年9月20日日曜日

Eucalyptus

Amazon EC2 互換の Eucalyptus を調査中。
参考サイト: http://blog.kirie.net/date/2009/05

2009年9月19日土曜日

Google App Engine

先日のクラウド研究会で聞き逃したので、「Google App Engine for Java [実践]クラウドシステム構築 (WEB+DB PRESS plus) (Amazon)」を読んだ。

 Google の巨大なインフラを用いたアプリケーションホスティングで、Jetty (オープンソースのサーブレットエンジン)上で稼動する。既存のホスティングと異なるのは以下の点。
  • データストアとして、RDB (MySQL など) ではなく、BigTable ( Key-value ストア)を用いること. Memcache API として、高速キャッシュ機構が使えること
  • 認証としては、Google の認証フレームワーク (Google アカウントが必要)を用いること
  • Google の様々なサービス (Google Calender, Google Docs, ... etc) が GData 経由で使えること
  • 指定された時間に実行される Cron ジョブが設定できること
そして、決定的に異なる点は以下の点
  • ある一定量のトラフィックまでは無料
  • それを越えると、従量課金性に設定することにより、自動的にスケールすること
非常に面白いが、印象としては、データセンターなどで既に稼動しているウェブアプリケーションを、GAE (Google App Engine) にポーティングするコストが高いため、スクラッチから書くものの他に、どのくらいこれから出てくるのかは疑問。既存のアプリケーションがそのまま動く、または、部分的にでも改変すれば動くぐらいのスタンスだったら、移行が進むのではないかと思われる。

 PHP も実験的のようだが使えるらしく、実行系としてはQuercus (Java VM 上で稼動する PHP 実行処理系) を使っているらしい。PHP は Web アプリケーションの実装言語として広く使われており、資産も多い。今後、シームレスに GAE に移行するツールまたは実行基盤を作ることが、GAE を爆発的にはやらす鍵となるかもしれない。。(いや、G社は広告モデルで十分に食べていけるので、そこまでこの GAE の収益のことは考えていないのだろう)

Twitter

後期の大規模知識特論の演習課題を考えています。何か学生が楽しんで取り組める課題がありそうでしたら、教えてください。

- Twitter の "public timeline" を用いて、リアルタイムにキーワードランキングを表示する (例: Google Trends)
- Twitter の "public timeline" を用いて、人間グラフをリアルタイムに表示する
- このエントリにも書いたが、ボストン市街のセンサーデータを用いて街の状況 (CO2 濃度、騒音など)をリアルタイム表示する

System S クラスタ構築

HP ML115 のクラスタ(8台構成)へSystem S のインストール作業が完了しました。松浦君、森田君、お疲れ様です。NIS/NFS の設定は松浦君にお願いしていますが、それが済んだらいよいよ研究環境が整います。

2009年9月18日金曜日

CULA Programming Guide

CULA Programming Guide : http://www.culatools.com/html_guide/index.html
CUDA Visual Profiler :(URL)
CUDA on Fedora (URL)

SST (Single Spectrum Transformation)

行列の圧縮による変化点検出の高速化 (URL)

2009年9月17日木曜日

Meeting with IBM高橋さん

森田君が TRL に来てくれて、TRL の高橋さんと StreamGPU プロジェクトのミーティングをしました。GPU は、一定のドメインにおいては、スループットを向上することが明らかになっていますが、我々の興味としては、スループットも重要ですが、レイテンシも重要です。GPU を”適切”に用いることによって、この両者をうまい具合に引き出せるようにしていきたいですね。そして、この”適切”にというのが、定式化モデルを用いて、自動的に導き出せればベストです。

2009年9月14日月曜日

SVD on CULA

StreamGPU プロジェクトですが、CULA を使った SVD (特異値分解)が動き出したようです。大きな一歩ですね。

GSIC 佐藤さん輪講

今日は、GSIC の佐藤さんがいらっしゃって、Borealis の論文を紹介していただきました。ありがとうございます!

今度は、System S Hands-on 講習会をやりましょう、ということになりました。サンプルアプリケーションをみんなで作りましょう。

HPCS 2010

2010年1月14日~15日で都内で開催。論文登録受付は 9月25日。
http://www.hpcc.jp/hpcs/

GPU コンピューティング研究会

GPU コンピューティング研究会に入会してください
http://gpu-computing.gsic.titech.ac.jp/index-j.html

SIGMOD 2009 の論文

以下の論文必見。至る所に、Michael Stonebraker (Postgres の生みの親)が出てくる

- Query Processing Techniques for Solid State Drives
Dimitris Tsirogiannis (University of Toronto)
Stavros Harizopoulos (Hewlett-Packard Laboratories)
Mehul A. Shah (Hewlett-Packard Laboratories)
Janet L. Wiener (Hewlett-Packard Laboratories)
Goetz Graefe (Hewlett-Packard Laboratories)

- A Comparison of Approaches to Large-Scale Data Analysis (PDF)
Andrew Pavlo (Brown University)
Erik Paulson (University of Wisconsin)
Alexander Rasin (Brown University)
Daniel J. Abadi (Yale University)
David J. DeWitt (Microsoft Inc.)
Samuel Madden (Massachusetts Institute of Technology)
Michael Stonebraker (Massachusetts Institute of Technology)

2009年9月13日日曜日

パフォーマンス解析

卒論生二人とも、性能特性、性能最適化が主なテーマであるので、パフォーマンス解析に関する便利なツールを覚えていってもらいたい。以下、思いつくものを列挙。

CPU使用率、メモリ使用量、ネットワーク解析
Disk I/O の解析
  • systat に含まれる iostat
プロファイル
  • oprofile
    ライブラリレベル、関数レベルで、どのくらい CPU を消費しているかがわかる。必要であればコールグラフも. カーネルの中も見る必要がある場合が多いが、その場合にはデバッグのシンボル情報をインストールする必要あり. また、イベントタイプを指定することにより、Instruction Cache miss, Data Cache Miss などが観察できる
ネットワークバンド幅計測

James Hamilton

IBM (DB2のアーキテクト)--> Microsoft --> Amazon と job hopping する James Hamilton 氏

CIDR 2009での講演(PDF)
2008年の講演 "Internet Scale Service Efficiency" (PDF)

Cooperative Expendable Micro-slice servers (CEMS) プロジェクト
http://perspectives.mvdirona.com/2009/01/23/MicrosliceServers.aspx

2009年9月12日土曜日

HadoopDB

HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads http://db.cs.yale.edu/hadoopdb/hadoopdb.pdf

VLDB 2009 (8月開催)で発表された Yale 大学のグループの論文。以前のエントリにも書いたが、SIGMOD 2009 に書かれた先行研究を基にしている。

テクニカルな肝は 5.2.4 を見ればすぐにわかるが、SQL クエリを MapReduce のプログラムに自動変換し、並列に実行。Vertix や DBMS-X といった並列データベースと比較して優位性を示している。

この論文では、1章の Introduction が面白い. Facebook など商用の世界においても、ペタバイト級のデータ量になってきており、データ分析の高速化が益々重要になってきていることを述べている。


ICDE 2009 報告

ICDE 2009 の国際会議報告 (PDF)。今、一番ホットなキーワードは「ストリーム」

以下がストリーム関係の論文(後半は short paper を含む)。ストリームアルゴリズムのネタが多く、ランタイムはあまりない。我々にとっては、大きなチャンスと言える。

A Framework for Clustering Massive-Domain Data Streams
Charu Aggarwal, IBM

Sequence Pattern Query Processing over Out-of-Order Event Streams
Mo Liu, Worcester Polytechnic Institute; Ming Li, Worcester Polytechnic Institute; Denis Golovnya, Worcester Polytechnic Institute; Elke Rundensteiner, Worcester Polytechnic Institute; Kajal Claypool, Lincoln Labs, Massachusetts Institute of Technology

On Efficient Query Processing of Stream Counts on the Cell Processor
Dina Thomas, Stanford University; Rajesh Bordawekar, IBM Watson Research Center; Charu Aggarwal, IBM; Philip Yu

Access Methods for Markovian Streams
Julie Letchner, University of Washington; Christopher Re, University of Washington; Magdalena Balazinska, University of Washington; Matthai Philipose, Intel Research Seattle

Continuous Subgraph Pattern Search over Graph Streams
Changliang Wang, HKUST; Lei Chen, HKUST

Sketching Sampled Data Streams
Florin Rusu, University of Florida; Alin Dobra, university of Florida

Probabilistic Inference over RFID Streams in Mobile Environments
Thanh Tran, UMass Amherst; Charles Sutton, UC Berkeley; Richard Cocci, UMass Amherst; Yanming Nie, UMass Amherst; Yanlei Diao, Umass; Prashant Shenoy, UMass Amherst

Sketch-based Summarization of Ordered XML Streams
Veronica Mayorga, UCSC; Neoklis Polyzotis, UCSC

Self-Tuning, Bandwidth-Aware Monitoring for Dynamic Data Streams
NAVENDU JAIN, Univ. of Texas, Austin; Praveen Yalagandula, HP Labs; Mike Dahlin, Univ. of Texas at Austin; Yin Zhang, Univ. of Texas at Austin

Supporting Generic Cost Models for Wide-Area Stream Processing
Olga Papaemmanouil, Brandeis University; Ugur Cetintemel, Brown University; John Jannotti, Brown University

Forward Decay: A Practical Time Decay Model for Streaming Systems
Graham Cormode, AT&T Labs--Research; Vladislav Shkapenyuk, AT&T Labs - Research; Divesh Srivastava, AT&T Research; Bojian Xu, Iowa State

On High Dimensional Projected Clustering of Uncertain Data Streams
Charu Aggarwal, IBM

Scalable Keyword Search on Large Data Streams
Lu Qin, CUHK; Jeffrey Yu, Chinese University of Hong Kong; Lijun Chang, CUHK; Yufei Tao, Chinese Univ. of Hong Kong

Scheduling Updates in a Real-time Stream Warehouse
Lukasz Golab, AT&T Labs - Research; Theodore Johnson, AT&T Labs - Research; Vladislav Shkapenyuk, AT&T Labs - Research

Web Monitoring 2.0: Crossing Streams to Satisfy Complex Data Needs
Louiqa Raschid, University of Maryland; Avigdor Gal, Technion; Haggai Roitman, IBM Haifa Research Labs and Technion

Efficient Query Evaluation over Temporally Correlated Probabilistic Streams
Bhargav Kanagal, University of Maryland; Amol Deshpande, University of Maryland

CoTS: A Scalable Framework for Parallelizing Frequency Counting over Data Streams
Sudipto Das, UCSB; Shyam Antony, UCSB; Divyakant Agrawal, U. of California - Santa Barbara; Amr Abbadi, UC Santa Barbara

Oracle Streams: a High Performance Implementation for Near Real Time Asynchronous Replication
Lik Wong, Oracle; Nimar Arora, Oracle; Thuvan Hoang, Oracle; Lei Gao, Oracle; Jingwei Wu, Oracle

Scale-up Strategies for Processing High-Rate Data Streams in System S
Henrique Andrade, IBM; Bugra Gedik, IBM; Kun-Lung Wu, IBM; Philip Yu, UIC

2009年9月10日木曜日

大規模センサーデータの活用

最近、多くのお客様にストリームコンピューティングのお話しをしますが、益々、今取り組んでいるこのテーマの面白さと可能性を感じています。

GPS などの位置情報を利用したLocation-Based Service、携帯電話の加速度センサーを利用した人間行動の把握、通信携帯会社が持つ 通話記録データ (CDR), SUICA / Pasmo のデータ、など巨大な数のセンサーから出る爆発的なデータをどう活用していくか。これが、現在、産業界が抱えている課題のひとつです。アカデミックな研究では、科学技術計算にばかり目がいきがちですが、このような産業界が抱えている問題にも目を向けていくべきでしょう。

われわれとしては、是非、そのような世の中で現実に欲されている課題に挑戦していき、現実世界へのインパクトを出しつつ、かつリサーチ的なインパクトも出していきたいと思います。

セカイカメラ

注目を浴びているセカイカメラ
http://support.sekaicamera.com/

2009年8月28日金曜日

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 なので、すんなり動くはずだったのですが。。。

2009年8月27日木曜日

HP ML115 G5

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

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

2009年8月25日火曜日

Parallel Sorting

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

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

StreamGPU: 特異値分解

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

2009年8月24日月曜日

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)

2009年8月21日金曜日

Stream Computing 輪講

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

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 の3つのアルゴリズムがポーティングターゲット
- System S 上の実装は IBM 高橋さんが実装中

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

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

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

2009年8月19日水曜日

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)

2009年8月17日月曜日

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

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

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

2009年8月14日金曜日

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 マシン1台とで性能はどうか、を知りたい

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) は1000ノードでスケールする、と主張しているが、Interactive Media などの企業でも40ノード弱であり、 eBay は Teradataという製品を使っており、72 ノードのみを使用しており、現実的にはそんな巨大なマシンは使っていない

2009年8月11日火曜日

院試がんばってください

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

RedHat Enterprise Linux

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

2009年8月10日月曜日

High Performance Web Server Using GPU

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

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

2009年8月7日金曜日

Amazon EC2/S3 互換システム Eucalyptus

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

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

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

2009年8月5日水曜日

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

今まで公開されている 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 パケットに収まるぐらい。例えば、画像も解像度を低くするなど)の2つを用意しておき、過負荷時には軽量版の HTML ファイルをクライアントに返す方法などがある。

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

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

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

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

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