2010年度のプロジェクトの構図

鈴村研究室の今年のプロジェクト体制の構図。黄色は昨年度からの継続またはほぼ確定しているプロジェクト、緑は可能性はあるが未確定のプロジェクト、オレンジは他の研究室との協業プロジェクトです。

SPECWeb2005 を用いた リアルタイム Web アクセスモニタリングの性能評価

　先日の大学院講義「大規模知識資源処理」の演習発表の中で、ミンハイさん（計算工学専攻・村田研究室４年生）が Web サーバーのアクセスログから、アクセスしてきたユーザーのクライアントの IP アドレスを取得し、そこから位置情報（緯度、経度）に変換し、Google Map に表示するアプリケーションを構築し、発表してくれました。

IP アドレスのリアルタイム検知はボットネット対策やマーケティングに応用できる可能性を秘めていますが、研究としての味づけをよりつけるには、このアプリケーションの性能評価をより徹底的に行う必要があります。

　Web 周辺のベンチマークは決まっていて、SPEC という標準化団体で策定している SPECWeb2005 (http://www.spec.org/web2005/) というものがあります。このベンチマークには、世の中の代表的な Web サイトのトラフィックや計算量を網羅的に示すために、Banking(SSL つきのオンラインバンキング）、E-Commerce（ショッピングサイト）, Support (ドライバーなどのダウンロード）の3つのシナリオから構成されています。

　SPECWeb2005 が吐き出すスコアは、スループットとレイテンシ（応答時間）がどのくらい満たされているかなどを複合的に考慮しているので、リアルタイムWeb モニタリングを導入することによって、そのスコアに対してどのくらいの影響があるかを考察すれば良いでしょう（もちろん、”ほとんどない”という結論が出るのがベストですが）。

データストリーム処理の標準ベンチマークに向けて

データストリーム処理の標準ベンチマーク策定に向けて、特性項目の洗い出しと、鈴村研究室において知識が蓄積しているアプリケーションに関してその特性項目に対する回答を書き出してみました。

特性項目に関してはもっと増やしていきたいのと、アプリケーションにおいても、音声処理や画像処理などの非構造化データも加えたいと思っています。

２０１０年度４月からの輪講内容

しばらく卒論作業のため輪講がありませんでしたが、４月から新たなメンバーも加わるので、以下のようなトピックを題材に、輪講をしていきたいと思います。

(1) SQL のデータストリーム処理への拡張言語 (StreamSQL, CQLなど）に関する調査
(2) ハイパーバイザー(準仮想化、完全仮想化）に関する調査
(3) ストリームアルゴリズム（One pass のみで解析するアルゴリズム）の調査
(4) データストリーム処理用のベンチマークに向けた、多方面のベンチマーク策定手法の調査
(5) ... など

ManyEyes

　様々なデータの可視化・視覚化を集合知的に集める IBM のプロジェクト ManyEyes
http://manyeyes.alphaworks.ibm.com/manyeyes/visualizations

既に約５万ほどの可視化データが登録されており、基本的にはデータさえアップロードし、視覚化する方法(円グラフ、棒グラフなどなど）を選択すれば登録完了です。

下記は CO2 の排出量を国別に視覚化したもの。

Flickr

　アカデミックな組織が、リアルなセンサーデータをどう安価にかつ大量に収集できるのかという問題意識が常にあるのだが、iPhone （センサー）のおかげで、Web サービスの融合が加速化されてきており、iPhone で取った画像も Flickr に貯められてきているようだ。Twitter と同じく制限があるだろうが、API は一応ある。Flickr の C API --> http://librdf.org/flickcurl/

　ただ、やはりもっといろんなデータが必要だ。Suica/Pasmo, CDR (Call Detail Record), 巨大Webサイトのアクセスログ、など。これらは NDA を結んだ本格的な共同研究契約を結ぶ必要があるだろう。StreamAR など、研究室自らが iPhone アプリケーションを構築し、センサーをばらまく作戦もあるが、”はやること”かつ”大量の意味のあるデータ”が到着することが必要なので、なかなか難しい。

そういえば、渋谷で実証実験をやっている pin@clip (http://pinaclip.jp/) のプロジェクトに参加させてもらうのも手であろう。まずはこちらにコンタクトを取って、どのようなデータが取れるかを調べてみます。

クラウド環境を利用した Elastic なデータストリーム処理の実現

　さて、卒論生はあと卒論作成と発表が待っていますが、いろいろ来年度のことを考えていきたいと思います。まず、以下の研究テーマに取り組む準備をしていきましょう。

「クラウド環境を利用した Elastic なデータストリーム処理の実現」

　松浦君の現在の研究テーマは、有限セットの計算資源を「ストリーム処理」と「バッチ処理」の2つを状況に応じて動的に負荷分散し、資源の有効活用を目標とした研究です。本研究では「この有限セット」という縛りがなく、クラウド環境を利用すれば事実上、処理をこなすために必要な計算資源を必ず確保できるという前提のもとに（しかし性能は確保されない）、Elastic なデータストリーム処理機構のを実現を目指します。

この研究テーマを遂行するにあたって必要な作業項目を列挙します。

[作業項目]

System S 用クラウド環境の構築

• クラウド環境 Eucalyptus の鈴村研究室への構築　(GSIC の滝澤さんなどやクラウド研究会の講演でのインストール苦労体験談もあったので、それも参考にする）
  
• ハイパーバイザー (KVM/Xen) 上に CentOS 5.2 をインストールし、System S を稼動させ、他ノードで動作することを確認

性能評価、オーバーヘッドの確認

• ハイパーバイザーの起動までの時間
• ハイバーバイザー上の System S のオーバーヘッドの調査：　ハイパーバイザー上での System S の性能評価。いくつかのアプリケーション(計算は軽いがネットワークに負荷がかかる VWAP (Volume Weight Average Price) 、計算負荷が高い DNA マッピングのストリーム処理）をターゲットに、どのぐらいの性能オーバーヘッドがあるかを調査
  

Elastic データストリーム処理の実装手法の考案

• クラウド環境 Eucalyptus を構築: ここでは Amazon のようなレイテンシが比較的大きなものを仮定しているので、Eucalyptus との環境もネットワークシミュレータ ns2 のようなものを使って擬似的にバンド幅及び高レイテンシを実現する必要がある
  
  
• クラウド環境のノードの nodepool への追加機構の実装：　到着データレートとレイテンシを監視し（ここは松浦君のモジュールを使用）、自分の計算資源で間に合うかどうかを精査。必要であったら、必要な数だけクラウド環境の VM イメージを立ち上げる。 System S の場合、~/bin/streams_get_available_hosts というコマンド (自作してもよい）から特定のフォーマットに従えばよいので、そのコマンドをクラウドの VM ノードも用いるような実装にすればよい。ただし、これは、ジョブのサブミット時にしか有効ではなく、ランタイムに動的にノードを増やすことはできないので、仕組みが必要。
  
  
• クラウド環境に対してノード追加・削除のコントロールを出す UDOP の開発 (REST API をたたくだけ？）: libvert という VMM を統一的に利用できる C バインディングがあるので、それを用いればできる。
  
  
• 負荷分散アルゴリズムの考案：　VM のオーバーヘッドが許容できない場合（予備実験によってある程度のオーバーヘッドは予測できる）、一部の処理を VM なしのノードで実行し、レイテンシが許容できる場合には VM ありのノードに割り振るようなスケジューリング方式を考案（←ここが一番大事）

本研究の貢献

• VMM の起動オーバーヘッドを加味した投機的な VMM 立ち上げ（タプル数や、時間的な周期がある場合には事前に立ち上げる）
• VMM に対するレイテンシを考慮した負荷分散アルゴリズム

性能評価のメトリックス

• レイテンシがどれくらい守れたか？
• VMMの起動オーバーヘッド

関連研究との違い

• 研究の評価は、新規性、実現性、Novelty（進歩性、革新性）が挙げられるが、前者の２つは容易に満たされる。最後の進歩性が客観的な指標がではないためなかなか難しいが、チャレンジする問題が非常に難しく、かつ実装自体も困難でかつ苦労したことが評価されれば良い。
• 参考になる論文は鈴村が調べる
  

SACSIS 2010

鈴村研究室から以下の論文を SACSIS 2010 に投稿しました。４年生の二人、大変お疲れ様でした。

• 松浦紘也、鈴村豊太郎 「データストリーム処理とバッチ処理の動的負荷分散」
• 森田康介、高橋俊博、鈴村豊太郎　「データストリーム処理と GPGPU を用いた実時間異常検知の実現」

StreamGPU: SACSIS 2010 参考論文

CPU と GPU の協調動作

• 尾形泰彦, 丸山直也, 遠藤敏夫, and 松岡聡. 性能モデルに基づくCPUおよびGPUを併用する効率的なFFTライブラリ. In 2008年ハイパフォーマンスコンピューティングと計算科学シンポジウム論文集(HPCS2008), pp. 107-114, (Jan,2007), 2008(PDF)
• Yasuhito Ogata, Toshio Endo, Naoya Maruyama, and Satoshi Matsuoka. An Efficient, Model-Based CPU-GPU Heterogeneous FFT Library. In the 17th International Heterogeneity in Computing Workshop (HCW'08), in conjunction with IPDPS 2008, Miami, FL, USA, Apr 2008, 2008.(PDF）
• 額田彰 and 松岡聡. CUDA GPU向けの自動最適化FFTライブラリ. In 先進的計算基盤システムシンポジウム SACSIS2009 論文集, May 2009., 2009.

　上記２本の論文が StreamGPU に大いに関係する論文なので読んでみてください。FFT （高速フーリエ変換）、信号処理、画像認識など様々な場面で出てくる 計算処理だが、性能モデルにもとづき、CPU と GPU とで協調的に計算することで高速化を実現する論文。StreamGPU で今取り組んでいる SST の計算においては、CPU または他のノード (GPU なし）をより短いスパンでの異常検知、GPU をより長いスパンでの異常検知を実現する。我々の場合は性能モデルを作るほど複雑なスケジューリングは必要なく、かつ SPADEという言語で簡便かつ柔軟にプログラムを組めるところが強みですね。

マルチ GPU に関する研究

• 渡辺祐也, 遠藤敏夫, and 松岡聡. 複数GPUにおけるセルフスケジューリングによる並列数値演算. In情報処理学会研究報告2008-HPC-111(SWoPP2008, Aug 5- Aug 7), 2008. (PDF)
  
  単一ノードにそれぞれが別々の性能を持つ GPU を複数持つ不均質な環境において （論文では4枚、GeForce 8800, 8800 GTX, 8800GT, 8600GTS) ,セルフスケジューリングというタスク分割手法を用いてアプリケーションを自動的に最適化する手法を提案。アプリケーションは計算がFFT などと比べてドミナントになり、通信がボトルネックとならない行列積を用いている。 StreamGPU において、複数次元をサポートするためにはマルチGPU が必須であり、このようなタスクスケジューリング機構も関係してくるだろう。

StreamDS : 関連研究論文

StreamDS (Dynamic Scheduler) の関連研究論文です。

• 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), Middleware 2008


• Karve, A., Kimbrel, T., Pacifici, G., Spreitzer, M., Steinder, M., Sviridenko, M., Tantawi, A.: Dynamic placement for clustered web applications. In: WWW Conference, Edinburgh, Scotland (May 2006)
  
  StreamDS の仮定と同じくある限られた計算資源上で異なる Web アプリケーション(例： AppA, AppB, AppC) が複数稼動している際に、均一に Web {A, B,C} をクラスタ上で稼動させると、例えば、AppA への負荷が突発的に高くなり、ある Service Level (例えば、レイテンシ）を満たさなくなる恐れが生じる。このような場合を想定して、負荷の状況に応じて、Web アプリケーションの配置を動的に変えるためのリアルタイムスケジューリングを提案。この論文で提案されている Placement Algorithm (アプリをどのように計算資源に配置すれば最適か）は参考になるが、StreamDS では、優先度として、バッチ処理＞＞＞ストリーム処理であり、もし計算資源に余裕がない場合にはバッチ処理は行わなくても良いし、また、ストリーム処理自体は statefull なオペレータ (Aggregate などのウィンドウ処理）も存在するので、stateless な Web アプリケーションとは解いている問題が若干異なる。
  
  
• Lin, B., Dinda, P.: VSched: Mixing batch and interactive virtual machines using periodic real-time scheduling. In: Proc. ACM/IEEE Supe1rcomputing, Seattle, WA (Nov. 2005)
  
  
• Ravindran, B., Jensen, E.D., Li, P.: On recent advances in time/utility function real-time scheduling and resource management. In: ISORC ’05: Proceedings of the Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC’05), Washington, DC, USA, IEEE Computer Society (2005) 55–60
  
  
• Balli, U., Anderson, J.S.: Utility accrual real-time scheduling under variable cost functions. IEEE Trans. Comput. 56(3) (2007) 385–401 Member-Haisang Wu and Senior Member-Binoy Ravindran and Member-E. Douglas Jensen.
  
  
• Chun, B.N., Culler, D.E.: User-centric performance analysis of market-based cluster batch schedulers. In: CCGRID ’02
  
  
• Carrera, D., Steinder, M., Whalley, I., Torres, J., Ayguad´e, E.: Utility-based placement of dynamic web applications with fairness goals. In: 11th IEEE/IFIP Network Operations and Management Symposium (NOMS 2008), Salvador Bahia, Brazil (2008)
  
  
• Urgaonkar, B., Shenoy, P., Roscoe, T.: Resource overbooking and application profiling in shared hosting platforms. In: Proc. Fifth Symposium on Operating Systems Design and Implementation, Boston, MA (Dec. 2002)

電力消費量関係

• Mark Blackburn, データセンターのサーバー電力消費量を削減する５つの方法, The Green Grid, http://www.thegreengrid.org/, White Paper (URL)

データ視覚化統合環境: Processing

Ben Fry 著の 「Visualizing Data」 (Amazon) という本を読んでいますが、MIT Lab で開発されている データ視覚化統合環境 Processing を使えば、高度なデータの視覚化を簡単に行えるようです。Java を簡素化した独自言語を使うようです。元々 Ben Fry が Computational Artの専門でもあり、Processing で作られたアートが、http://complexification.net/gallery/ に紹介されてます。

Processing の本家 → http://www.processing.org/

日本の Processing に関する情報サイト→ http://processing.jp/

また、ARToolkit を Processing から利用可能にする NyARToolkit というものがあるそうです。

http://processing.jp/2009/01/06/nyartoolkit-for-processing-is-released/

StreamDS: Hadoop との統合

金曜日に GSIC 佐藤さんとちょっとだけミーティングしましたが、松岡研究室の白幡君が卒論で、Hadoop のスケジュラー部分のコード(ジョブの記述情報を表現した JobConf オブジェクトがどのようにHadoop スケジューラに渡されるか？）を調べているので、松浦君の今やっている研究の発展系として、是非今年前半に、Hadoop との統合をやりましょう。今、現在は、松浦君のバッチシステムは、ストリーム処理と同じく System S を用いていますが、Hadoop などのシステムとして統合できるとより説得力が増すと思います

StreamGPU : 次の実験

　森田君が CPU と GPU の協調動作の実装を終え、パフォーマンス解析を行っている。彼の実験結果（ここを参照）によると、CPU / GPU 両方ともウィンドウサイズを285（？）にしたときに、oprofile を用いて CPU 使用率のブレークダウンを解析。Tesla (2コア）上での結果。

• GPU 関係：　OpenMP のランタイム (libgomp.so) が３７％。libcuda.so, libcula.so を合わせて15％。トータルで52％以上
• CPU 関係：　System S の PE 　RectMatrixRowCol::AddScaledRectMatrixRowCol::operator　という関数が両方合わせて38%. これらは newmat の行列演算関数
  

CULA では、SVD の計算で CPU 部分は OpenMP を用いて並列化しているようで、その割合が 37 %。CPU 単独においての異常検知計算を割りこませることにより、CULA 単独のパフォーマンスと比較してどのくらい落ちているのであろう。

異常検知許容時間を L、測定する次元数を D として, まずこれらのパラメータを固定化する。L を６０秒. GPU 版だと、前の森田君の実験によると、ウィンドウサイズ１０２４で５秒ぐらいであったので、D を１２次元に固定する。

この条件において、まず最初は、CPU 版を走らせず、GPU 版のみでD次元を終了するのにかかる時間を測定する。次に、CPU 版を追加し、小さいウィンドウサイズまでを試し、GPU 版の実行時間に対してどのくらいの影響を与えるかを観測する。まずは、４９などの小さいウィンドウサイズで、GPU 版がどのくらい遅くなっているかを見てみましょう。

仮に、GPU 版の空きが全くない状況においては、CPU 版を実行する隙間がないので、遅くなるでしょうが、それを確認しましょう。

もし CULA の SVD が CPU もフルに使い切ってしまう場合には以下の方向性での本研究の有効性を示せばよいのではないでしょうか？

• Tesla は２コアだが4コアにして、CULA が使用する CPU のスレッド数を限定する (ただし、卒論までに CPU を換装するのは困難なので、これはまずやらない）
• 他のクラスタ上のノードでスケールアウト処理。streams01-08 や sa のマシンを用いて、各ノード上で CPU を計算

まずは、全国大会の論文で忙しいと思うので、文書化を優先して、終わり次第、上記の実験をやりましょう。

StreamAR : 5 Barriers to a Web That's Everywhere

以下の記事に AR がメインストリームになるための５つの障害を述べています。参考にしてください。
http://www.readwriteweb.com/archives/augmented_reality_five_barriers_to_a_web_thats_eve.php

StreamAR ミーティング

　とりあえず、第１回目ということで石井君と少し Brain Storming をはじめました。まずは、１ヶ月程度 で、AR においてどのような点にフォーカスして研究するか、実装、および実装するデバイス等に関して議論し、プロジェクトとしての全体構想を２月中旬ぐらいにまとめて研究室の皆さんに話してもらおうと思っています。

　WWW2010 (World Wide Web) など最近の国際学会の傾向を見ると、巨大な実データを持つ Google, Yahoo などのデータ解析論文が台頭してきていますが、プロジェクトとしての方向性としては、自分達で AR のセンサーを構築・公開し、センサーを大量に受ける基盤を作ってしまうことが重要かと思います。当然、サービスを公開しトラフィックが増えると、東工大ネットワークに対して多大な負荷をかけてしまうので、その際には Amazon EC2 /S3 などのクラウド上でデータを受けるサービスを Elastic に稼動させていくことが重要になっていくでしょう。

まずは、本格的なプロジェクト開始に向けて、以下のような調査をまずは行っていきましょう。

1. セカイカメラなどの既存 AR システムの調査

• 現在、どのようなことができるか？テキスト情報の他に、音声や画像なども付加できるか？
• セカイカメラの他にどのような AR システムが世の中に存在するか？　日本の事例、世界の事例
  
• どのようなシステム構成、ソフトウェアアーキテクチャで作られていると推測するか？
  

2. 既存 AR システムの問題点とあるべき姿の提言

• どのような問題点があり、どのように解決すべきか？
  タグ情報の乱立によるユーザーインタフェースの欠如、情報の信頼性の欠如、パフォーマンスの問題など）、実装のデバイスへの強い依存性 (iPhone は ObjectC, Android は Java ?)
  

3. スクラッチから AR を構築するとして必要な要件の調査

• スクラッチから作る際のソフトウェアアーキテクチャおよび必要なコンポーネント
• 既存の AR Toolkit に関する調査。どこまで実現できているか？
• AR のデバイスの選択。iPhone , Andoroid or others ?
  
• 仮に iPhone を仮定して, First Step としてどのようなアプリケーションを作るか？　(iPhone を研究経費で借りれるかどうかは、鈴村が交渉中だが難しいかもしれない）
  

CPU Process Afinity on Linux

あるプロセスを CPU の特定のコアでのみ稼働させる仕方 -->
http://www.cyberciti.biz/tips/setting-processor-affinity-certain-task-or-process.html
上記の方法だとうまくいかないので、以下のようにやる
taskset -c -p 0 1234

最後は Process ID.

A Code Generation Approach to Optimizing High-Performance Distributed Data Stream Processing

現在の System S/SPADE の中身を最も忠実に反映している論文です。

A Code Generation Approach to Optimizing High-Performance Distributed Data Stream Processing(PDF) , Bu˘ gra Gedik

ACM CIKM 2009 (http://www.comp.polyu.edu.hk/conference/cikm2009/)
Conference on Information and Knowledge Management archive
Proceeding of the 18th ACM conference on Information and knowledge management table of contents

We present a code-generation-based optimization approach to　bringing performance and scalability to distributed stream processing　applications. We express stream processing applications using　an operator-based, stream-centric language called SPADE, which　supports composing distributed data flow graphs out of toolkits of　type-generic operators. A major challenge in building such applications　is to find an effective and flexible way of mapping the logical graph of operators into a physical one that can be deployed on a set of distributed nodes. This involves finding how best operators map to processes and how best processes map to computing nodes. In this paper, we take a two-stage optimization approach, where an instrumented version of the application is first generated by the SPADE compiler to profile and collect statistics about the processing and communication characteristics of the operators within the application. In the second stage, the profiling information is fed to an optimizer to come up with a physical data flow graph that is deployable across nodes in a computing cluster. This approach not only creates highly optimized applications that are tailored to the underlying computing and networking infrastructure, but also makes it possible to re-target the application to a different hardware setup by simply repeating the optimization step and re-compiling
the application to match the physical flow graph produced by the optimizer. Using real-world applications, from diverse domains such as finance and radio-astronomy, we demonstrate the effectiveness of our approach on System S – a large-scale, distributed stream
processing platform.

StreamAR における技術的チャレンジを考えよう

　石井君が StreamAR （Augmented Reality) に興味を示してくれたので、本プロジェクトを立ち上げる前に、技術的チャレンジや関連技術、関連研究についてまず調べていきましょう。

　３次元仮想デジタル空間 SecondLife の急激な失速を見ると、ビジネスモデルとして企業及びエンドユーザーにとってメリットがない限り、セカイカメラのような拡張現実の成功もないと思うので、２０１０年が勝負の年なのではないかと思います。そもそもユビキタスコンピューティング（IBM は Pervasive Computing と呼んでいた）が１０数年前から提唱されてきましたが、ここにきて似たようなモデルが再び脚光を浴び、少しばかり現実的になってきたのは、その世界を支えるインフラ（ネットワークやデバイス）が整備されたからに他ならないのは言うまでもないでしょう。
　
　もし、これらの拡張現実のモデルが世界の標準になった暁に必要になるソフトウェアのインフラ技術は何でしょうか？　現在流れているデータ量が１０倍、１００倍になったとき、従来の分散処理技術、アルゴリズムで実現できないことは何でしょうか？　ストリーム処理技術が必要不可欠な場面はどこでしょうか？　

　まずはセカイカメラでも良いですが、一つ拡張現実を実現するシステムの reverse engineering をして、現行のシステムの鳥瞰図を作るところから始めてみましょうか。

Xen と KVM の比較

オープンソースのハイバーバイザー Xen と KVM の比較　：　Quantitative Comparison of Xen and KVM（PDF), 2009/5

Java から GPU へのブリッジ

　Java から GPU のカーネルをユーザー透過に呼び出す仕組みがいずれ出てくるだろうと思っていたが、2009年の Europar という国際学会で発表されていたようだ。
Java プログラムから CUDA のカーネルを呼び出すように記述すると、プリプロセッサが自動的に Java と CUDA のブリッジコード（データ転送も含む）を生成する。どちらにしても、JNI コールを使っていると思われ、オーバーヘッドは存在するだろうが、ターゲットアプリケーションは無視できるのであろう。

JCUDA: A Programmer-Friendly Interface for Accelerating Java Programs with CUDA, 2009 (PDF)

A recent trend in mainstream desktop systems is the use of general-purpose graphics processor units (GPGPUs) to obtain order-of-magnitude performance improvements. CUDA has emerged as a popular programming model for GPGPUs for use by C/C++ programmers. Given the widespread use of modern object-oriented languages with managed runtimes like Java and C#, it is natural to explore how CUDA-like capabilities can be made accessible to those programmers as well. In this paper, we present a programming interface called JCUDA that can be used by Java programmers to invoke CUDA kernels. Using this interface, programmers can write Java codes that directly call CUDA kernels, and delegate the responsibility of generating the Java-CUDA bridge codes and host-device data transfer calls to the compiler. Our preliminary performance results show that this interface can deliver significant performance improvements to Java programmers. For future work, we plan to use the JCUDA interface as a target language for supporting higher level parallel programming languages like X10 and Habanero-Java.

StreamGPU 関連論文 - CPU と GPU の活用

以下の論文は CPU と GPU を協調的に利用した論文です。森田君の卒論、SACSIS , 今後の StreamGPU 関連の論文には参考文献として載せてください。あとは、異常検知アルゴリズムの GPUによる高性能化の関連論文も調べる必要がありますね。

実行時性能予測に基づく CPU と GPU の動的タスク割当ての検討、東北大学滝沢先生たちのグループ

近年の描画処理ユニット(GPU)を汎用計算に用いる研究(GPGPU)の成果により,高性能なCPUとGPUを搭載したPCをヘテロジニアスな並列処理計算システムとして活用できることが明らかになっている.一方でそれらのプログラミングは複雑になってきており,これを効率的に活用するために,CPUとGPU上 で動作するプログラム記述を統一化する研究がなされている.しかし,現在のGPGPUアプリケーション開発ツールの多くではプログラムを実行するプロセッ サを手動で静的に選択する必要がある.その適切な選択は実行時の情報に依存しているため,実行時に適切なものを動的に予測することで更なる効率化を図るこ とが可能である.本報告では,CPUとGPU上でのプログラムの実行時間の見積もりと実行プロセッサの切り替えのコストから適切なプロセッサを動的に予測することの有効性について検討した結果について報告する.実験による評価の結果,CPUとGPU問のデータ転送以外の両者の切り替えのコストは小さいことから、実行時間に対して予測誤差が十分小さい場合には動的切り替えによる性能向上が期待できる可能性が示された.

Harmony: an execution model and runtime for heterogeneous many core systems, HPDC 2008

The emergence of heterogeneous many core architectures presents a unique opportunity for delivering order of magnitude performance increases to high performance applications by matching certain classes of algorithms to specifically tailored architectures. Their ubiquitous adoption, however, has been limited by a lack of programming models and management frameworks designed to reduce the high degree of complexity of software development intrinsic to heterogeneous architectures. This paper proposes Harmony, a runtime supported programming and execution model that provides: (1) semantics for simplifying parallelism management, (2) dynamic scheduling of compute intensive kernels to heterogeneous processor resources, and (3) online monitoring driven performance optimization for heterogeneous many core systems. We are particulably concerned with simplifying development and ensuring binary portability and scalability across system configurations and sizes. Initial results from ongoing development demonstrate the binary compatibility with variable number of cores, as well as dynamic adaptation of schedules to data sets. We present preliminary results of key features for some benchmark applications.

CPU-GPU Hybrid Real Time Ray Tracing Framework

鈴村研究室の2010年の抱負

あけましておめでとうございます。今年も研究頑張りましょう。

さて、今年の研究室の目標を列挙しましょうか。まずは昨年から続いているプロジェクトを更に進展させ、きっちりと国際学会まで通しましょう

StreamGPU

• 卒論、情報処理学会全国大会、SACSIS 及び国際学会での発表
• 差分データ送信などのデータストリーム処理＋GPU ならでは最適化手法の考案と評価
• マルチ GPU における評価
• 新たなアーキテクチャ (Fermi) 上での評価
• SST 以外のアプリケーションを用いた評価
  

StreamDS (Dynamic Scheduler) :

• 卒論、情報処理全国大会、SACSIS 及び国際学会に通す.
• Hadoop との統合（松岡研究室との共同研究）
  

StreamTwitter

• パブリックなサービスとして公開する。国内学会、国際学会に通す
• トラフィックのパターン解析
• 意味付け（アメダスやインフルエンザ流行度合いなどのトレンド分析）

　次に４月から、新たに３名がメンバーとして加わると予想されますが、新たな研究テーマにも取り組んでいきたいと思っています。具体的には以下の通りです。特に現在では、実データとして Twitter のデータしかないという問題があります。この問題を打開すべく、今年は、鈴村研究室発のセンサーをばらまいて、より多くの実センサーデータを取得できる環境を作り、ミドルウェアの研究に役立てていきたいと思っています。

• StreamCloud : クラウド上におけるストリーム処理システム：　Amazon EC2 / Eucalyptus 上における Elasticity を利用したスケーラブルなストリーム処理システム。さらに Xen や Hypervisor 上での System S の性能特性を調べます。
• StreamShedder: Load Shedding 技術の追求：　SSD などの高速ストレージを用いた高負荷時におけるデータの退避技術。ターゲットアプリケーションとして Twitter などを例に評価すれば良いでしょう。これは松浦君の卒論でフォーカスしている StreamDS を強固にする技術として重要です。Zip の法則などのアプリケーションのセマンティクスを活用した Shedding 手法も考案できるでしょう。
• StreamAR: 拡張現実システムにおけるストリーム処理技術を用いたスケーラブルなソフトウェア基盤の構築。及び iPhone や Android 上での鈴村研究室発の AR アプリケーションの公開。
  
  
• StreamScript: ストリーム処理の開発生産性の向上：　現在の SPADE/System S では、ユーザーがカスタマイズしたコードを書く際には、別途 C++ でコードを書かなければならず、Agility が低いです。この問題点に対して、Python, Ruby などのスクリプト言語ベースでのユーザー定義オペレーターを記述できるように改良し、開発生産性を向上させます。実装としては、既に Java でユーザー定義のオペレータを作れる JavaUDOP というものがあるので、それを利用して、JVM (Java Virtual Machine) ベースで実装されたスクリプト言語処理系を呼び出すようなアーキテクチャになると思われます。
  

• ストリーム処理システムの実装： SPADE のシンタックスは踏襲し、 それを処理するシステムをスクラッチから構築する。
  

　上記の技術を探求する際に、現実的なアプリケーションを見据えることが重要です。今のところ、Twitter や異常検知のアルゴリズムは実アプリケーションですが、引き続き、キラーアプリケーションを探し、それらのアプリケーションをベースに研究を行っていく体制を確立していきたいと思います。現在、以下のアプリケーションが候補です。

• スケーラブルなリアルタイム音声処理への応用（新メンバー西井君に期待）
  
• 次世代 DNA シーケンサー及びバイオへの応用
• 楽天などの Web サイトのログ高速処理
  
• 環境関係：　Live E! プロジェクト, Boston 近郊の気象データ