近況

マルチGPU・マルチノード上の高速 MapReduce 処理系, そしてインクリメンタルグラフ処理の研究が本格的に始まり、非常に楽しみです。また、何度も書いてますが、大規模分散ファイルシステムとの統合、そして耐故障性も重要な研究要素なので、研究が一段落した人には是非取り組んで欲しいと思います。

石井君には, Yahoo S4 vs System S/SPADEの定性的（できれば定量的にも）比較を行う解説記事を書いてもらうことになりました。また、動的に変化するネットワークグラフを視覚化するアプリケーションも作ってもらうことになりました。研究のインパクトを視覚的に伝えるのも非常に重要なので、期待してます。

また、DEBSの学会の締切りに関しては、高データレートアプリケーションへのGPUタスク並列化の論文を、上野君が鋭意執筆してくれてます。

皆さん、それぞれこの調子で頑張ってください。

FAST 2011

http://www.usenix.org/events/fast11/tech/

MapReduce の GPU 処理系 Mars のマルチGPU・マルチノード化

松浦君の研究テーマの続き。

GIM-V 実装は MapReduce の一アプリケーションとして考えられるので、より汎用的に考えて、「MapReduce プログラミングモデルの GPU 処理系 Mars のマルチGPU・マルチノード化」をまず実現することが先決でしょう。

また、当然、HDFS/Gfarm などの分散ファイルシステムとの協調も重要ですが、これに関しては他のアプリケーションが重要でしょう。実装に関しては以下の3通りが考えられます。

(1) X10 で実装する。X10 はそもそも上記の目的を達成するための言語です。ただし、CUDA のコード生成を当然最適化する必要があるでしょう。
(2) CUDA を用いてスクラッチから実装する. 分散対応に関してはデザインが必要
(3) OpenCL を用いてスクラッチから実装する. 分散対応に関してはデザインが必要

大規模データグラフデータベース関連

InfiniteGraph
http://blog.infinitegraph.com/2010/07/26/infinitegraph-and-gogrid-to-enable-large-scale-graph-data-processing-and-discovery-free-for-qualified-startups/

Neo4J http://neo4j.org/

GIM-V on GPUs に関連する論文

まずは以下の論文を読みましょう。

1. Pegasus (GIM-Vの理解と Hadoop コード理解）: 過去のブログ参照
2. Mars (MapReduceのGPU実装）http://www.citeulike.org/group/1670/article/4009779
3. PageRank, RWR(http://suzumura-lab.blogspot.com/2010/12/streamgraph-rwr.html), HADIなどのGPU高速化に関する論文

GIM-V のGPU実装

松浦君の修論テーマの方向性が決まりました。
「大規模グラフ分析プログラミングモデル GIM-V の マルチ GPU による実現と高速化」

この研究の肝は以下の2つです。
(1) マルチノードでかつマルチ GPU 環境を十二分に活用した高速化.
(2) GIM-V のモデルを記述した論理実行モデルの提唱と最適化コード生成

　西井君のテーマである Incremental GIM-V （ストリーム計算）のテーマと大きく関係していますが、バッチ計算とストリーム計算を両方享受できるような統一的な実行基盤を作ることも当然視野に入れます。この統一的な実行基盤で欠かせないのはスケジューリング機構ですが、松浦君の「バッチ処理とストリーム処理のスケジューリング機構」と石井君の「ストリーム処理のクラウドへの委譲」に関する研究がその先駆け的な研究という位置づけになります。

あと不足しているのは、特に大規模グラフデータを格納する分散ファイルシステムへのアクセス機構とローカリティを意識したデータスケジューリングです。また、耐故障性も重要です。この点に関しては、新M1の新たな研究となるか、新B4の研究になるかは相談で決めていきましょう。

研究テーマ候補

研究テーマ候補のリマインド

1. メモリ使用量を考慮した実行時スケジューリング及びマイグレーション
http://suzumura-lab.blogspot.com/2010/07/blog-post_28.html

2. 階層的ストレージ構成を透過的に活用するデータストリーム処理系（例：大規模グラフ）
http://suzumura-lab.blogspot.com/2010/12/streamgraph_4464.htmlにおける以下の問題
メモリに載りきらないようなグラフストリームが到着した際に Persistent な分散ファイルシステムと協調し階層的にグラフ構造を格納、頻繁にアクセスされる部分グラフのみをオンメモリ上に確保するといった最適化手法、そしてそれらのグラフデータに対して開発者からシームレスにアクセスできるような処理基盤

3. GIM-V モデルのGPU実装
大規模グラフの処理モデルGIM-Vの処理系を GPU (+分散用に StreamScaleまたは System S) を用い、実装. 　関連研究→Mars

4. Incremental GIM-V 処理系の発展
- 耐故障性: ノード故障におけるマイグレーション・スケジューリング問題
- GPUを用いた高速化：完全に再計算すべきサブグラフのGPUによる処理

5. 超並列異機種混在計算機環境におけるX10を用いたグラフ処理の最適化
並列プログラミング言語 X10を用いて大規模グラフ処理を記述し、CPUとGPUから構成される超並列異機種混在環境（例：TSUBAME2.0) 上における性能最適化を実現する。また、そこに介在する様々な技術的課題（プログラマビリティ、性能、自動生成されるGPUコードなど）を特定し、X10の実行時処理系にその課題を解決する機能を実装し、性能向上を実現する.　グラフ処理に関しては、GIM-VのモデルをX10で記述するのも良いでしょう。

卒論提出完了

本日、4年生3人全員が無事に卒論提出を完了させました。それぞれ非常に良い論文に仕上がったと思います。とにかく、まずはお疲れ様です。次は、発表頑張りましょう。