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日火曜日

紅葉