[Exa] ロードマップ作成開始

　明日からエクサに向けた様々な研究領域（アルゴリズム、アプリケーション、システムソフトウェア、プログラミングモデル、アーキテクチャ）におけるロードマップ作成が始まります。SACSISの続きで、秋葉原で行われます。

国際的にも, 類似の会議が IESP (http://www.exascale.org/)で行われており、日本からも参加していますが、我々の研究室のようにシステムソフトウェアに従事するものはこのような動きの把握は重要です。企業ではこのようなトップダウンの戦略策定は毎年のように行われ、それが実際の研究開発プロジェクトにブレークダウンされるわけですが、企業とアカデミックの差は、そのブレークダウンしたプロジェクトの成果物を厳密に管理し、成果が振るわないプロジェクトはどんどん切っていくことでしょう。アカデミアでは、産業界におけるスピードの速さには勝てると思わないので、より目の前の利益だけに左右されないように、企業ではできない中長期的に解決すべき本質的な研究課題に取り組むべきかと思います。

[ElasticCloud] SACSIS 2011 石井君発表終了

　石井君、お疲れ様でした。次は CLOUD 2011 での英語発表ですが、頑張りましょう。

Network Design Problem

　最大フロー問題の前提は、ある頂点に着目したときに頂点の流入量と流出量は等しくなければならない。ただし、ストリーム処理においては、フィルタリング等あるので、基本的には流入量に対して流出量はある割合で小さくなる。ある頂点同士を結ぶ容量（バンド幅）が決まっており、最大フロー問題のように、ある頂点から複数の頂点に分岐して流すことも許す。また、複数のストリームプログラムが走っており、各ストリームプログラムを構成するオペレータの間引き率は決まっているとする。また、フローネットワーク（容量が決まっている）も事前に与えられるものとする。このような前提が与えれたときに、走らせられるジョブ（ストリームプログラム）の最大数を求めよ、というのが問題。間引き率が 1 のときは Network Design Problem として知られており、NP-Hard. 但し、当然、ネットワークが小さいときにはヒューリスティックが知られている。上記の問題はNetwork Design Problem よりも難しいので、NP-Hard. もし実用上問題なく動くような手法が考案できれば、我々の領域では新規性が高いだろう。

Graph500 Code Reading 第1回目

第1回目終了

GNU GLOBAL

ソースコードにタギングするツール GNU GLOBAL
現在、 C, C++, Yacc, Java and PHP4をサポート。

http://www.gnu.org/software/global/

Top500 の変遷の視覚化

http://www.top500minder.net/

[StreamGraph] インクリメンタル最短路問題

- On Dynamic Shortest Paths Problems
- Dynamic Shortest Paths Minimizing Travel Times and Costs
- http://www.science20.com/chatter_box/blog/shortest_path_problem_dynamic_network

[StreamGraph] 小規模行列に対する SVD の応用例

国際会議 IISWC のストーリー立てに関する続き。一つの concern は、ワークロードとしての汎用性が重要となるが、ストリームアプリケーションのワークロードに共通な行列計算として 小規模な行列に対する SVD 計算が様々な応用に使えるという主張をする。SST はもちろんだが、その他にも例が必要。画像特徴抽出などは典型的であるが、いくつかの論文を参照する必要がある。少し調べてみよう。

A fast SVD based video watermarking algorithm compatible with MPEG2 Standard
http://www.columbia.edu/itc/applied/e3101/SVD_applications.pdf

続きは後ほど

[ExaGraph] 大規模グラフ解析ベンチマーク Graph500 の性能特性

Target Conference: IISWC 2011

[Title]
Performance Characterization of Graph500 on a distributed-memory based Supercomputer

[Abstract]
Graph500 has emerged as a new benchmark of ranking supercomputers with the motivation that large-scale graph analysis is becoming greatly important application. It is well studied that Graph algorithms are suitable for shared-memory based supercomputers such as Cray XMT. Recent trend of Linpack-based supercomputer ranking shows that heterogeneous and distributed-memory based supercomputers with tremendous amount of GPGPUs greatly achieves top-ranked performance score. However, the performance characteristics of large-scale graph analysis like Graph500 on such a distributed-memory supercomputer has not yet been well investigated. This paper shows thorough study on the performance characteristics of Graph500 using 4th-ranked supercomputer, TSUBAME.

[StreamGPU] IISWC 2011

IISWC 2011 のストーリー立て。Workload Characterization に関する学会なので以下のようなストーリー構成にする。
(1) リアルタイムの異常検知・変化点検知は、データストリーム処理では非常に重要なアプリケーション(=Workload)の一つである
- 様々な異常検知・変化点検知機構が提案されているが、SST はノンパラメトリックな手法として強力な手法である
- 但し、計算量は O(n^3) であり、リアルタイム性を実現するのは困難である。
- 本論文では GPU による高速化に関する知見を示す。特に既存の CULA ライブラリを示したときの性能特性と、提案する GPU タスク並列による最適化を施した際の性能特性を示す
(2) CULA ライブラリによるナイーブな高速化→スケールしない＋小さい行列サイズで性能が出ない、という結果を示す
(3) GPU タスク並列手法による性能最適化＋評価結果

学会の性質上、より汎用性が重要。ある特定のアルゴリズムに関するワークロードに関する性能特性を測っただけでは難しい。書き方によるが、強調するのは上記の SST, SVD のアルゴリズムは１インスタンスの一つであり、他のストリーム＋GPUにも（ある程度）一般的に言える知見をこの論文によって提供できると主張することが重要。

DEBS に出した論文をベースに、上記の構成に変える作業を行う。既に、実験結果など（データ転送の内訳以外）はほぼ揃っているので、構成の改変と論文の完成度を上げるのみ。

TODO
- 小規模な行列サイズに対する SVD (Single Value Decomposition) ベースのアルゴリズムを調査する (できるだけ早く)

雑感

研究者は、どんなに日々の雑用や他の仕事で手一杯だろうが、研究成果を継続的に出していくことが重要。”Credibility” というのがどんなに研究者だけなく、社会で生きていく上で重要なことをわかって欲しい。Credibility を着実に得ていくのはそれなりに年月が必要だが、逆に失うのも早い。

未踏IT人材発掘・育成事業

2011年の未踏IT人材発掘・育成事業の公募がもうじき始まるので、要チェック
http://www.ipa.go.jp/jinzai/mitou/koubo_index.html

直近の学会情報

直近の学会情報

ICSOC 5/27 http://www.icsoc.org/
Middleware 2011 5/23 http://2011.middleware-conference.org/call-for-papers
IISWC http://www.iiswc.org/iiswc2011/index.html 6/10(abstract), 提出は 6/17
ICDE http://www.icde12.org/ 7/12
ASPLOS http://research.microsoft.com/en-us/um/cambridge/events/asplos_2012/ 7/18

IISWC は Workload characterization 系の学会なので、Graph500 の性能特性を TSUBAME2もしくは Amazon EC2 などで徹底的に取って技術的知見を論文にまとめれば、学会としては適切かと。鈴村＋渡部君で書く。
また、Call For Paper を見ると、”Stream-based computing workloads; web2.0/internet workloads”というのもある. Linear Road Benchmark, CDR, VWAP, Twitter を S4 及び System S で実装し、性能特性を比較する論文もあり。Miyuru君が始めているストリームアプリケーション用データ生成器 Stream Farm のアーキテクチャと実装に関しても言及する。Miyuru 君、グエン君、竹野君と共同で始める。論文の締め切りは 6/17.

Middleware (5/23) は Miyuru 君の Albatros.
上野君の GPU Task Parallelism（強力なブラッシュアップが必要）はASPLOS 向きか。

研究テーマ: 高生産性並列プログラミング言語X10を用いた大規模グラフ処理

高生産性並列プログラミング言語X10を用いた大規模グラフ処理
- 具体的には Graph500（最短路問題）のコードを X10 で実装する。必要に応じて GPU を使うのもよし
- 通信機構の最適化、アプリケーションレベルのチューニングが必須

[ExaGraph] DisNet: A Framework for Distributed Graph Computation

分散グラフ処理エンジンに関する論文が先ほどのマイクロソフトのものも含めて続々と出てきています。
DisNet: A Framework for Distributed Graph Computation
http://icensa.nd.edu/papers/asonam2011a.pdf

[ExaGraph] Surfer ：クラウド上の大規模グラフ処理エンジン

On the Efficiency and Programmability of Large Graph Processing in the Cloud, http://research.microsoft.com/pubs/131014/Surfer_tr.pdf

Large graph processing in the cloud,SIGMOD 2010

As the study of graphs, such as web and social graphs, becomes increasingly popular, the requirements of efficiency and programming flexibility of large graph processing tasks challenge existing tools. We propose to demonstrate Surfer, a large graph processing engine designed to execute in the cloud. Surfer provides two basic primitives for programmers - MapReduce and propagation. MapReduce, originally developed by Google, processes different key-value pairs in parallel, and propagation is an iterative computational pattern that transfers information along the edges from a vertex to its neighbors in the graph. These two primitives are complementary in graph processing. MapReduce is suitable for processing flat data structures, such as vertex-oriented tasks, and propagation is optimized for edge-oriented tasks on partitioned graphs.

To further improve the programmability of large graph processing, Surfer consists of a small set of high level building blocks that use these two primitives. Developers may also construct custom building blocks. Surfer further provides a GUI (Graphical User Interface) using which developers can visually create large graph processing tasks. Surfer transforms a task into an execution plan composed of MapReduce and propagation operations. It then automatically applies various optimizations to improve the efficiency of distributed execution. Surfer also provides a visualization tool to monitor the detailed execution dynamics of the execution plan to show the interesting tradeoffs between MapReduce and propagation. We demonstrate our system in two ways: first, we demo the ease-of-programming features of the system; second, we show the efficiency of the system with a series of applications on a social network. We find that Surfer is simple to use and is highly efficient for large graph-based tasks.

[ExaGraph/StreamGraph] Triangle Law

1. Spectra of "real-world" graphs: beyond the semicircle law

2. Practical algorithms for triangle computations in very large (sparse (power-law)) graphs

http://www-rp.lip6.fr/~latapy/Publis/triangles_short.pdf

[ExaGraph] CrayXMT の仕様

http://www.craysupercomputers.com/downloads/CrayXMT/CrayXMT_Datasheet.pdf

[ExaGraph/Twitter] GraphCT

Massive Social Network Analysis: Mining Twitter for Social Good

David Ediger, Karl Jiang, Jason Riedy, David A. Bader, Courtney Corley, Rob Farber and William N. Reynolds. ``Massive Social Network Analysis: Mining Twitter for Social Good,'' The 39th International Conference on Parallel Processing (ICPP 2010), San Diego, CA, September 13-16, 2010.

Social networks produce an enormous quantity of data. Facebook consists of over 400 million active users sharing over 5 billion pieces of information each month. Analyzing this vast quantity of unstructured data presents challenges for software and hardware. We present GraphCT, a Graph Characterization Toolkit for massive graphs representing social network data. On a 128-processor Cray XMT, GraphCT estimates the betweenness centrality of an artificially generated (R-MAT) 537 million vertex, 8.6 billion edge graph in 55 minutes and a realworld graph (Kwak, et al.) with 61.6 million vertices and 1.47 billion edges in 105 minutes. We use GraphCT to analyze public data from Twitter, a microblogging network. Twitter's message connections appear primarily tree-structured as a news dissemination system. Within the public data, however, are clusters of conversations. Using GraphCT, we can rank actors within these conversations and help analysts focus attention on a much smaller data subset.

[ExaGraph] 超大規模グラフに対する最短路問題

David Bader のチームは共有メモリ型並列計算機 Cray MTA-2 上の40プロセッサで並列最短路アルゴリズムを実行し、１億頂点、10億辺のスケールフリーグラフ（有向辺）を10秒以内に解く。逐次版と比較し、30倍のスピードアップ。

http://www.cc.gatech.edu/~bader/papers/ShortestPaths.html

彼らの主張は以下の通りである。Cray XMTのような超巨大共有メモリ並列計算機が高性能なグラフ処理を実現するハードウェアプラットフォームであると主張。

Implementations of PRAM graph algorithms for arbitrary sparse graphs are typically memory intensive, and the memory accesses are fine-grained and highly irregular. This often leads to poor performance on cache-based systems. On distributed memory clusters, few parallel graph algorithms outperform the best sequential implementations due to long memory latencies and high synchronization costs [Bader et al. 2005]. Parallel shared memory systems are a more supportive platform. They offer higher memory bandwidth and lower latency than clusters, and the global shared memory greatly improves developer productivity.

Bader, D., Cong, G., and Feo, J. 2005. On the architectural requirements for efficient execution of graph algorithms. In Proc. 34th Int’l Conf. on Parallel Processing (ICPP). IEEE Computer Society, Oslo, Norway.

http://www.cc.gatech.edu/~bader/papers/ListRankMTA-ICPP2005.pdf

一方、2010 年に発表された Pregel (Google) の論文ではトータルで300コアからなる分散メモリ計算機上、10億頂点、1270億辺に対して10分で最短路問題 (シングルソース）を解いている。大規模グラフの個々の物理マシンへのマッピングはランダムハッシュを用いており（トポロジー構成を考慮したマッピングは考えていない）、かつ⊿ステッピングのような最適化されたアルゴリズムも用いていない。ただ、このようなナイーブな実装でも、Parallel BGL で解いた問題サイズと実行時間と同等以上であることを主張している。

Parallel BGL (http://osl.iu.edu/research/pbgl/) は MPI をベースにした C++の 分散メモリ用並列グラフ処理ライブラリである。2005年の OOPSLA で発表された "Lifting Sequential Graph Algorithms for Distributed-Memory Parallel Computation" の論文に基本アイデアが書かれている。

並列単一最短路問題 Delta-stepping のアルゴリズムは以下の2本の論文に記載されている。
Meyer, U. and Sanders, P. 2003. Δ-stepping: a parallelizable shortest path algorithm. J. Algs. 49, 1, 114–152.
Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel single source shortest path algorithm. In ESA ’98: Proceedings of the 6th Annual European Symposium on Algorithms, pages 393–404. Springer-Verlag, 1998.

GPU を用いた最短路問題を解く研究は前にも紹介したが以下の論文がある。1000万頂点から成る平均6次数のランダムグラフに対してはBFSを1秒で SSSP を1.5秒で解くことに成功している。但し、スケールフリー性がある（一部の頂点の次数は非常に多い）グラフやDIMACS チャレンジの実道路ネットワーク、CPUに対する優位性がほとんど得られていない。

Accelerating large graph algorithms on the GPU using CUDA Pawan Harish and P. J. Narayanan

何れにしても、オンメモリ上にグラフデータが存在することが仮定であり、Graph500 で想定しているようなペタバイトレベルのグラフに関しては当然扱った研究はない。

[ExaScale] エクサ関連ワークショップ資料

http://www.exascale.org/mediawiki/images/5/54/Talk05-EESI_WP34-IESP_April2011.pdf

[PGAS] GASNet

UC Berkeley が開発しているPGAS言語用ハードウェア非依存の高性能通信プリミティブ。UPC (Unified Parallel C), Titanium, Co-Array Fortran をサポート。