ミドルウェア屋の任務

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

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

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

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

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

- 仮想マシンを用いた 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％のユーザーが９０％のトラフィックを生んでいるんだそうです。
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秒待つという意味. ０だったら待たない
- System S のバグで、第1列目は読み込んでもらえない
- vstream inputDatStream は使う次元数をあらわす。この場合だと次元数は 4
- for_begin で センサーの各次元に対する計算
- Aggregate は、49 個（49行）のセンサーデータを集めて、Col(data@i)
で @i 次元目のデータをすべて出力ストリームで返す。なので、型は FloatList

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

Dolly+の特徴

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

(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

- ネットワークのチューニングに関してはもちろん、いろいろあります。

• イーサネットのジャンボフレーム (9000-16000バイト) での送信
• http://www.psc.edu/networking/projects/tcptune/
• http://www.kagoshima-ct.ac.jp/kenkyu/kenkyu_houkoku2004/2kajisa.pdf

Quantitative Comparison of Xen and KVM

オープンソースのハイパーバイザとしては Xen と KVM (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 は散々たる結果となっている。

StreamTwitter の研究課題

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

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

などの他に

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

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

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

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

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

高速データ転送システム

高速データ転送システム 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 のようなアクセラレータを使用する汎用的な オペレータ はどのような形で提供すべきかを考察する

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月中旬が締め切り

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)

Personal Genome Project (PGP)

Personal Genome Project (http://www.personalgenomes.org/)

パーソナルゲノム医療を加速化するために１０万人の個人のゲノム情報を収集するプロジェクト

以下の YouTube のビデオが興味深いです。

GENOME : The Future is NOW WEBISODE 1

StreamTwitter

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

Google Charts API

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

Bootchart

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