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 の併設ワークショップという位置づけだが、ストリーム関連の研究者が一同に介するので、結構良いでしょう。何を出しましょうね？１０ページ分の 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

あと４日

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

テロリストとTwitter

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

緯度経度情報

StreamTwitter

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

ワッサー

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

SACSIS 2010

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

ICWS 2010

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

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

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

鈴村自身は、Ajax アプリの高速化の話（２，３年前に考えていたアイデア）を論文化していないので、それを出す予定。

高速 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はここによると３万ぐらいみたいですね。もし、本気でこちらの方に興味があるなら、これを購入したいと思いますが、まあ、どれだけ、GUI にこだわるかですね。

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

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

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

下図は国別データです。０９年６月のデータで１１５０万人のユーザーを対象にしたものらしいです。やはり、圧倒的に 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% のアクティビティを行っているのだそうです。

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


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

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


土日はやはり少なめ。





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

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)

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

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

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

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

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

セカイカメラと Twitter の連動

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

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

拡張現実のライブラリ

なんと、セカイカメラのような拡張現実 (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/
プロファイルの一元管理

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 にアクセスしたときに、やはり線形に増加してしまうかを調査してください

→森田君（工大祭のあとね）

大規模知識処理特論２

大学院の「大規模知識処理特論２」で、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 用のアプリケーションとして、いくつか模索中。

StreamGPU 実験

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

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

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

[前提]
- 今 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 まで増加させていって、平均処理時間を観測してください。
　　- これで、あまり変わらないことが言えればベストです。１つの次元に対して、
　　　転送する行列サイズが 500x500 で float だと 1MB 程度。130次元でも
　　　GPU 上のメモリにのるはずです。

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

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


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

Mixi API

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