ANUChem

X10-based SDP など X10 関係者に関係するページ

計算化学に関係する X10 ベースの計算ライブラリ
http://cs.anu.edu.au/~Josh.Milthorpe/anuchem.html
ソースコードも公開されています。

上記に関係する論文は以下の IPDPSの論文。
X10 as a parallel language for scientific computation: practice and experience
http://cs.anu.edu.au/~Josh.Milthorpe/publications/Milthorpe2011_IPDPS.pdf

Near-term Target Conferences

IPDPS2012 併設ワークショップ
2012 International Workshop on High Performance Data Intensive Computing(HPDIC2012)
http://cloud.hdu.edu.cn/HPDIC2012/
締め切り：2012/01/08
Research Contents: StreamGPU (Matsuura)



IPDPS2012 併設ワークショップ
ParLearning 2012
https://researcher.ibm.com/researcher/view_project.php?id=2591
- Real-time solutions for learning algorithms on parallel platforms
Due: 2012/01/18
Notification: 2012/02/01
Research Contents:
- StreamGPU (Morita and Ueno)
- Bipartite Graph

SYSTOR 2012
http://www.research.ibm.com/haifa/conferences/systor2012/dates.shtml
Due: 2012/2/13
Notification: 2012/3/26


IEEE CLOUD 2012
- VCTLPerf + Linear Road Benchmark
- Graph500 on Amazon EC2
Submission Deadline: February 10, 2012
Full Paper Submission Due Date: February 15, 2012
Decision Notification (Electronic): March 15, 2012



HPDC 2012
http://www.hpdc.org/2012/home/important-dates/
- Graph500 (Ueno)
- StreamGPU : GPU Task Parallelism (Ueno)
Abstracts Due: 16 January 2012
Papers Due: 23 January 2012, 11:59 PM Pacific Standard Time
Author Notifications: 19 March 2012

SACSIS 2012 (Domestic Conference)
http://sacsis.hpcc.jp/2012/
- StreamGPU (Ueno)
- StreamAPU (Matsuura)
- I-GIMV (Ganse)
- Incremental Spectral Clustering (Nishii)
- SDP with X10 (Watanabe)
Due: 2012/1/20
Notification: 2012/3


PLDI X10 Workwhop
http://x10-lang.org/workshop
Paper submission deadline: February 28, 2012
Author Notification: March 28, 2012
- X10-based X10 : Watanabe
- Performance Evaluation of X10-based Graph Algorithms on TSUBAME: Hashikawa and Watanabe

EuroPar 2012
http://europar2012.cti.gr/
Deadline for abstracts: January 31, 2012
Deadline for full papers: February 7, 2012
Decision notification: May 11, 2012

Supercomputing 2012
http://sc12.supercomputing.org/
- Graph500 (Ueno) (It depends on the result of HPDC)

Winter Simulation Conference 2012
http://www.wintersim.org/futureconf.htm
- Due: 2012/4
- Notification: 2012/6
- X10-based Large simulation platform

ACM Middleware Conferece
http://2011.middleware-conference.org/
- Due: 2012/5

IEEE IISWC 2012
- Due: 2012/6

The Fourth Paradigm: Data-Intensive Scientific Discovery

昨今注目されている書籍
http://research.microsoft.com/en-us/collaboration/fourthparadigm/

Of Hammers and Nails: An Empirical Comparison of Three Paradigms for Processing Large Graphs

マイクロソフトの新たなグラフ処理の論文。

Of Hammers and Nails: An Empirical Comparison of Three Paradigms for Processing Large Graphs
http://research.microsoft.com/pubs/155533/paper.pdf

Many phenomena and artifacts such as road networks, social networks and the web can be modeled as large graphs and analyzed
using graph algorithms. However, given the size of the underlying
graphs, efficient implementation of basic operations such as connected component analysis, approximate shortest paths, and linkbased ranking (e.g.PageRank) becomes challenging.
This paper presents an empirical study of computations on such
large graphs in three well-studied platform models, viz., a relational
model, a data-parallel model, and a special-purpose in-memory
model. We choose a prototypical member of each platform model
and analyze the computational efficiencies and requirements for
five basic graph operations used in the analysis of real-world graphs
viz., PageRank, SALSA, Strongly Connected Components (SCC),
Weakly Connected Components (WCC), and Approximate Shortest Paths (ASP). Further, we characterize each platform in terms of
these computations using model-specific implementations of these
algorithms on a large web graph. Our experiments show that there
is no single platform that performs best across different classes of
operations on large graphs. While relational databases are powerful and flexible tools that support a wide variety of computations,
there are computations that benefit from using special-purpose storage systems and others that can exploit data-parallel platforms

2部グラフ関連性解析の高速化およびシステムプロファイリング

- GPGPU による高速化
- システムプロファイリング：どこにどのぐらい時間を費やしているのか？
- 下位の基盤をSystem S 非依存にし、TSUBAME で大規模実行できるようにする

アプリケーション屋の要件

アプリ屋の requirement および実際に使っている手法等を知るため、情報交換の場をセットしていきましょう。
候補としては、まず上がるのが、東大松尾先生、東大鹿島先生、東工大杉山先生、IBM TRLのデータマイニング屋でお客様案件を担当している研究者など。

MovieLens

土屋さんの指導教官：横浜国立大学の長尾先生
http://www.nlab.sogo1.ynu.ac.jp/ynu/members/nagao.html
ネット企業との共同研究

MovieLens (映画に対する Rating) というデータセットを使って協調フィルタリング＋ベイジアンネットを使って解析
http://www.grouplens.org/node/73

Random Walks on Directed and Undirected Graphs

http://www.math.ucsd.edu/~phorn/math261/

Random walk with restart に対する高速な Top-k 検索

Random walk with restart に対する高速な Top-k 検索
db-event.jpn.org/deim2011/proceedings/pdf/d3-1.pdf

An In-Depth Study of Stochastic Kronecker Graphs

ICDM に参加中の村田先生からのメッセージ。

"An In-Depth Study of Stochastic Kronecker Graphs"
C. Seshadhri, Ali Pinar, and Tamara G. Kolda,
Proceedings of the 11th IEEE International Conference on
Data Mining, pp.587-596, 2011.
http://arxiv.org/abs/1102.5046

タイトルの通り、(Graph500で用いられる)Kronecker Graphの研究です。発表を聞いただけで論文はまだ読んでいないのですが、
・次数分布はheavy tailでもpower lawでもなく、論文中の図の
ように何度もバウンドしたような曲線になる
・ノイズを入れたnoisy SKGになると次数分布が直線に近づく
・孤立点が多い。k=42で74%が孤立点
・coreのサイズは実ネットワークのそれより小さい

MLG 2010 Workshop

http://www.cs.purdue.edu/mlg2011/speakers.html

RAMGRAPH: large scale graph processing in RAMCloud

http://code.google.com/p/ramgraph/

Recently, the pay-as-you-go computing paradigm in public clouds such as Amazon EC2 offers users to execute their computational tasks on the rented virtualized computation resources. Due to the lower cost than hosting a private cloud, this paradigm has become popular for medium- and small-sized Web companies such as Alexa and SmugMug. Mining and processing the large web and social networks is one of the common regular tasks for those Web companies. For example, a search engine typically uses a graph-based ranking scheme such as PageRank to give an order to the pages. Moreover, those mining and processing tasks are highly customized with various user-defined logics applied on the entire graph. The requirement of high efficiency in large scale graph processing challenges existing tools. This is because, most of current tools such as MapReduce and Hadoop are disk-based, where the hard disk is typically 100-1000x slower than the main memory. The random access nature of graph processing further harnesses the performance of disk-based graph processing. The low efficiency of current disk-based systems limits the popularity of graph mining and business intelligence in Web companies, and can result in low utilization of existing investment and lose potential business opportunities.

To unleash the computation power of current cloud offerings, we propose Thunder, a large graph processing system in the main memories of hundreds or thousands of machines. Thunder stores and processes graphs entirely in the main memory, and uses hard disks only for backup and archrivals. The system provides APIs similar to Map and Reduce functions in MapReduce for users to implement their user-defined logics. These logics are automatically executed on the graph in a distributed manner.

The goal of designing and implementing Thunder is to exploit the advantage of in-memory processing, while remaining all the merits of conventional disk-based tools, namely excellent scalability, good fault-tolerance and ability of expressing arbitrary and complex customized logic. In particular, we are facing challenging issues like scalability, availability, complex memory management, network traffic reducing and so on.

Polonium: Tera-Scale Graph Mining and Inference for Malware Detection

http://siam.omnibooksonline.com/2011datamining/data/papers/052.pdf

We present Polonium, a novel Symantec technology
that detects malware through large-scale graph infer-
ence. Based on the scalable Belief Propagation algo-
rithm, Polonium infers every le's reputation,
agging
les with low reputation as malware. We evaluated
Polonium with a billion-node graph constructed from
the largest le submissions dataset ever published (60
terabytes). Polonium attained a high true positive rate
of 87% in detecting malware; in the eld, Polonium
lifted the detection rate of existing methods by 10 ab-
solute percentage points. We detail Polonium's design
and implementation features instrumental to its success.
Polonium has served 120 million people and helped an-
swer more than one trillion queries for le reputation.

Router: A Message Passing Model for Large-Scale Graph Mining

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6079403&tag=1

ABSTRACT

many parallel computational models have been employed in many papers to process the large-scale graph. In this paper, we propose a message passing model Router which could be invoked by most of current parallel computational models to process the large graph. The model is good at solving the multi-source traversal problem which often occurs in many complex graph algorithms. As the model can traverse the graph from different source at the same time, the multi-source traversal will finish in much less iteration than before. In this way, the total time of the algorithm involves multi-source traversal will be reduced in a large scale. Besides, the Router model is flexible enough to express a broad set of algorithms by implementing the Router's abstract method. Finally, the experiment shows the efficiency and scalability of the model.

Router: A Message Passing Model for Large-Scale Graph Mining

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6079403&tag=1

Large-Scale Graph Mining Using Backbone Refinement Classes

We present a new approach to large-scale graph mining
based on so-called backbone refinement classes. The method
efficiently mines tree-shaped subgraph descriptors under minimum frequency and significance constraints, using classes
of fragments to reduce feature set size and running times.
The classes are defined in terms of fragments sharing a common backbone. The method is able to optimize structural
inter-feature entropy as opposed to occurrences, which is
characteristic for open or closed fragment mining. In the
experiments, the proposed method reduces feature set sizes
by >90 % and >30 % compared to complete tree mining and
open tree mining, respectively. Evaluation using crossvalidation runs shows that their classification accuracy is similar to the complete set of trees but significantly better than
that of open trees. Compared to open or closed fragment
mining, a large part of the search space can be pruned due
to an improved statistical constraint (dynamic upper bound
adjustment), which is also confirmed in the experiments in
lower running times compared to ordinary (static) upper
bound pruning. Further analysis using large-scale datasets
yields insight into important properties of the proposed descriptors, such as the dataset coverage and the class size
represented by each descriptor. A final cross-validation run
confirms that the novel descriptors render large training sets
feasible which previously might have been intractable.

Tools for Large Graph Mining

http://www.cs.cmu.edu/~deepay/thesis.pdf

Graphs show up in a surprisingly diverse set of disciplines, ranging from computer networks to sociology, biology, ecology and many more. How do such “normal” graphs look like? How can we spot abnormal subgraphs within them? Which
nodes/edges are “suspicious?” How does a virus spread over a graph? Answering
these questions is vital for outlier detection (such as terrorist cells, money laundering rings), forecasting, simulations (how well will a new protocol work on a realistic
computer network?), immunization campaigns and many other applications.
We attempt to answer these questions in two parts. First, we answer questions
targeted at applications: what patterns/properties of a graph are important for solving
specific problems? Here, we investigate the propagation behavior of a computer virus
over a network, and find a simple formula for the epidemic threshold (beyond which
any viral outbreak might become an epidemic). We find an “information survival
threshold” which determines whether, in a sensor or P2P network with failing nodes
and links, a piece of information will survive or not. We also develop a scalable,
parameter-free method for finding groups of “similar” nodes in a graph, corresponding
to homogeneous regions (or CrossAssociations) in the binary adjacency matrix of the
graph. This can help navigate the structure of the graph, and find un-obvious patterns.
In the second part of our work, we investigate recurring patterns in real-world
graphs, to gain a deeper understanding of their structure. This leads to the development
of the R-MAT model of graph generation for creating synthetic but “realistic” graphs,
which match many of the patterns found in real-world graphs, including power-law
and lognormal degree distributions, small diameter and “community” effects.

Workshop on Graph Mining

MLG 2011 : Ninth Workshop on Mining and Learning with Graphs
http://www.cs.purdue.edu/mlg2011/speakers.html


http://www.ourglocal.com/event/?eventid=10468%2C1
http://www.cs.umd.edu/mlg2010/
MLG2009

Temporal analysis of semantic graphs using ASALSAN ∗

http://csmr.ca.sandia.gov/~tgkolda/pubs/bibtgkfiles/ICDM07.pdf

ASALSAN is a new algorithm for computing three-way
DEDICOM, which is a linear algebra model for analyzing
intrinsically asymmetric relationships, such as trade among
nations or the exchange of emails among individuals, that
incorporates a third mode of the data, such as time. ASALSAN is unique because it enables computing the three-way
DEDICOM model on large, sparse data. A nonnegative version of ASALSAN is described as well. When we apply these
techniques to adjacency arrays arising from directed graphs
with edges labeled by time, we obtain a smaller graph on latent semantic dimensions and gain additional information
about their changing relationships over time. We demonstrate these techniques on international trade data and the
Enron email corpus to uncover latent components and their
transient behavior. The mixture of roles assigned to individuals by ASALSAN showed strong correspondence with
known job classifications and revealed the patterns of communication between these roles. Changes in the communication pattern over time, e.g., between top executives and
the legal department, were also apparent in the solutions.

Matching Structure and Semantics: A Survey on Graph-Based Pattern Matching

http://briangallagher.net/pubs/gallagher-aaaifall-2006.pdf

Find Me If You Can: Improving Geographical Prediction with Social and Spatial Proximity

http://cameronmarlow.com/media/backstrom-geographical-prediction_0.pdf

Geography and social relationships are inextricably inter-
twined; the people we interact with on a daily basis almost
always live near us. As people spend more time online,
data regarding these two dimensions { geography and so-
cial relationships { are becoming increasingly precise, allow-
ing us to build reliable models to describe their interaction.
These models have important implications in the design of
location-based services, security intrusion detection, and so-
cial media supporting local communities.
Using user-supplied address data and the network of asso-
ciations between members of the Facebook social network,
we can directly observe and measure the relationship be-
tween geography and friendship. Using these measurements,
we introduce an algorithm that predicts the location of an
individual from a sparse set of located users with perfor-
mance that exceeds IP-based geolocation. This algorithm
is e cient and scalable, and could be run on hundreds of
millions of users.

SIAM AN10 Minisymposium on Analyzing Massive Real-World Graphs

http://www.graphanalysis.org/workshop2010.html

10:30-10:55 People You May Know
Lars Backstrom, Facebook
Facebook's friend recommendation system helps people connect with their friends. Our system, called People You May Know, uses a combination of results from sociology and machine learning to make the best suggestions possible. We will look at some of the challenges involved in building a system that can handle the scale of Facebook and provide high quality recommendations. In this talk I will discuss both the algorithmic and machine learning challenges that we have faced and overcome in building this system.


11:00-11:25 Modularity and Graph Algorithms
Joe McCloskey, National Security Agency; David A. Bader, Georgia Institute of Technology
A number of graph partitioning algorithms are based on the concept of modularity. In particular Clauset, Newman and Moore (CNM) have developed a greedy agglomerative graph partitioning algorithm that scales well but is known to have several flaws. Fortunato and Barthelemy have performed a rigorous analysis of the CNM algorithm that elucidates it problems. More recently Berry, Hendrickson, Laviolette, and Phillips have derived a weighted variant of CNM that performs much better in practice. This talk will focus on a different version of the parent CNM algorithm based on a statistical re-interpretation of CNM that also addresses some of the issues with the original algorithm.
11:30-11:55 Exploiting Sparsity in the Statistical Analysis of Gene Expression Data
Padma Raghavan, Anirban Chatterjee, and Francesca Chiaromonte, Pennsylvania State University

12:00-12:25 Scalable Methods for Representing, Characterizing, and Generating Large Graphs
Ali Pinar, Sandia National Laboratories

Monday, July 12
4:00 PM - 6:00 PM
Room: Spirit of Pittsburgh B - Level 3

4:00-4:25 Hybrid Parallel Programming for Massive Graph Analysis
Kamesh Madduri, Lawrence Berkeley National Laboratory

4:30-4:55 Tools and Primitives for High-performance Graph Computation
John Gilbert, University of California, Santa Barbara

5:00-5:25 Practical Heuristics for Inexact Subgraph Isomorphism
Jon Berry, Sandia National Laboratories

5:30-5:55 Spectral Methods for Subgraph Detection
Nadya Bliss and Benjamin A. Miller, Massachusetts Institute of Technology; Patrick J. Wolfe, Harvard University
We describe a statistical test for subgraph detection and localization using spectral properties of the so-called modularity matrix, a type of residual under the Chung-Lu random graph model. We show that the resultant algorithmic procedure can be applied to very large graphs ($< 10^6$ vertices), with complexity dominated by that of standard sparse eigensolver methods, and can successfully isolate anomalous vertices in real data examples.
Workshop Organizer:

Graph-based technologies for intelligence analysis

Cyber Security

http://dl.acm.org/citation.cfm?id=971643
http://ngc.sandia.gov/assets/documents/IAProblemsNetworkFormulations_JICRD2010.pdf

A graph-theoretic analysis of the human protein-interaction network using multicore parallel algorithms

http://dl.acm.org/citation.cfm?id=1456988&CFID=73076166&CFTOKEN=19740521


Due to fundamental physical limitations and power constraints, we are witnessing a paradigm shift in commodity microprocessor architecture to multicore designs. Continued performance now requires the exploitation of concurrency at the algorithm level. In this article, we demonstrate the application of high performance computing techniques in systems biology and present multicore algorithms for the important research problem of protein-interaction network (PIN) analysis. PINs play an important role in understanding the functional and organizational principles of biological processes. Promising computational techniques for key systems biology research problems such as identification of signaling pathways, novel protein function prediction, and the study of disease mechanisms, are based on topological characteristics of the protein interactome. Several complex network models have been proposed to explain the evolution of protein networks, and these models primarily try to reproduce the topological features observed in yeast, the model eukaryote interactome. In this article, we study the structural properties of a high-confidence human interaction network, constructed by assimilating recent experimentally derived interaction data. We identify topological properties common to the yeast and human protein networks. Betweenness is a quantitative measure of centrality of an entity in a complex network, and is based on computing all-pairs shortest paths in the graph. A novel contribution of our work is the analysis of the degree-betweenness centrality correlation in the human PIN. Jeong et al. empirically showed that betweenness is positively correlated with the essentiality and evolutionary age of a protein. We observe that proteins with high betweenness, but low degree (or connectivity) are abundant in the human PIN. We have designed efficient and portable parallel implementations for the exact calculation of betweenness and other compute-intensive centrality metrics relevant to interactome analysis. For example, on the Sun Fire T2000 server with the UltraSparc T1 (Niagara) processor, we achieve a relative speedup of about 16 using 32 threads for a typical instance of betweenness centrality on a PIN, reducing the running time from nearly 312min to 13s.

Andy's work on dataflow language

http://datasys.cs.iit.edu/events/MTAGS09/a05-yoo-slides.pdf

Survey (2)

Closeness Centralityの高いノードを発見する高速アルゴリズム
http://www.ieice.org/ken/paper/20111021b0j3/

グラフマイニングとその統計的モデリングへの応用

グラフマイニングとその統計的モデリングへの応用

http://www.ism.ac.jp/editsec/toukei/pdf/54-2-315.pdf

逆探索法によるグラフ系列マイニングの高速化
http://db-event.jpn.org/deim2011/proceedings/pdf/b10-2.pdf


グラフ系列マイニング
http://latent-dynamics.net/02/13_Inokuchi.ppt.pdf

頂点により誘導される頻出グラフ系列パターンのマイニング
http://www-erato.ist.hokudai.ac.jp/html/php/seminar5_docs/inokuchi.pdf

多頻度グラフマイニングを利用した動画の解析
http://www.ieice.org/ken/paper/20081218kahU/
多頻度グラフマイニングとは，大量のグラフ構造から，頻出するグラフパターンを意味のあるものとして抽出する手法である．本研究では，多頻度グラフマイニングを動画像の解析に用いる．本稿では，監視カメラの前を移動物体が通過するような動画を対象に多頻度グラフマイニングを用いてグラフベースの背景除去手法を提案する．具体的には，各ビデオフレームを領域分割し，各領域を節点，各領域間の隣接関係を辺としてグラフ構造を作る．この時，背景部分が頻出パターンとなることを利用して背景除去を行
う．

非整列RNA配列群からの頻出パターンのマイニング
http://www.mizuho-ir.co.jp/publication/giho/pdf/001_10.pdf

ページ閲覧時間を考慮した Web ログマイニング手法の提案
http://www.aiet.ecei.tohoku.ac.jp/~mihara/reference/refICS148.pdf
近年，Web サイトの複雑化・大規模化に伴い，Web サイト管理者がユーザのニーズ
に合わせて Web サイトを適宜改善していく必要が高まっている．このユーザのニーズを
知る手がかりの一つとして有用なのが Web アクセスログである．Web アクセスログを解
析することで，ユーザの Web サイト内での行動の様子を知ることができる．本稿では，
Web アクセスログ解析にデータマイニングを応用する Web ログマイニングに関連して，
ユーザが各ページを閲覧した時間を考慮したアクセスパターンを抽出する手法を提案す
る．

グラフ分析を利用した文書集合からの話題構造マイニング
http://sc.chat-shuffle.net/paper/uid:110007380661

グラフマイニングを応用した系列データ解析
http://www.ai-gakkai.or.jp/jsai/conf/2008/program/pdf/100318.pdf

メタデータ付き推薦のためのグラフマイニング
https://kaigi.org/jsai/webprogram/2011/pdf/231.pdf


時系列データを用いたWebグラフマイニング
http://db-event.jpn.org/deim2009/proceedings/files/B9-2.pdf

背景の分割に対応したグラフマイニングベースの動画像からの背景除去
Graph Mining based Background Removal from Videos Solving Background Separation

グラフマイニングアルゴリズムを用いたギャップを含むコードクローン情報の生成
http://iss.ndl.go.jp/books/R000000004-I10809124-00
http://ci.nii.ac.jp/naid/110008584014


グラフマイニングを用いたブロードバンドサービスエリア分類手法の一考察
https://kaigi.org/jsai/webprogram/2010/paper-422.html

多段ＧＢＩツールを利用した化学物質の部分構造情報の有効利用
http://www.sccj.net/event/nenkai/2005au/program/abstract-pdf/2O-02.pdf

線形グラフのマイニングアルゴリズム
http://www-erato.ist.hokudai.ac.jp/html/php/symposium3_docs/tabei-preview-20101129.pdf

多頻度グラフマイニングの一般化

阪大・猪口先生 (元TRL) のご研究
http://www.ar.sanken.osaka-u.ac.jp/papers/2006-12/jsai_v19_n5.pdf

大規模社会ネットワーク分析の事例と展望

http://crev.jp/zinbun/zinbun_v094.pdf

TextGraphs-4: Graph-based Methods for Natural Language Processing

TextGraphs-4: Graph-based Methods for Natural Language Processing
http://www.textgraphs.org/ws09/index.html

Graph Crest Meeting @ 東工大

以下、渡部君議事録
--
CREST meeting

uno先生
情報学研究所
グラフネットワーク、離散構造アルゴリズムの研究
計算量（オーダ）、ビッグデータの高速処理


計算量 ( n=1億(現在)→10億(将来) )
｜NP-comp
｜n^3 ( 藤澤先生 )
｜
｜【n^2】 ← 重要 !!
｜ クラスタリング,etc..
｜ m*n^1/2
｜n log n ( Google )
｜n
｜log n
｜ web-service


データと問題
・系列データ
→具体的なタスクはなにか？定まっていない。
・離散＆グラフ (中心性やクラスタリング、直径)
→過去、最大流からクラスタリング、最小カットを求めるモデルもあったが…
→得られる解が求めたい解と食い違っていることが多々ある（グラフ全体に関して）。
→グラフ全体の評価よりも局所的な分析の方が重要性が高い。

藤沢先生、避難シュミレーションでは局所的なものよりグラフ全体によるものの影響が大きい？
→京都市などのグラフはグラフ全体が関与する（グラフの性質によるものである）
→全部が全部ではないが最大流、最小費用流がネットワークに役立ちにくい？

・マッチング問題（１対１の暗号化、匿名化 anonimization)（一対一）
→アルゴリズムの開発はされているがスケールが大きいと動かせない（せいぜい１万件程度？）
→暗号化をしても情報を公開してもよいのか？政治的問題。
鈴村先生、グラフの分割性は高いのでは？
→それほど並列性は高くない？
→sensitiveなものなのであまりデータがない

・最小費用流（マッチングの拡張）割り当てが解ける（多対多）　　　行列の最小固有値問題

→大規模スケールで有用な単純なアルゴリズムしかモデル化に利用されない（KMeans,BFS,etc…）
→目的解を得るためための様々なアルゴリズムの構築が必要
→高度なクラスタリングアルゴリズムなら目的解（グラフの性質、局所性）を見つけれる
→がオーダーが問題で大規模データに対応できない
→KMeansなら動くは動くが…十分な目的解は得られない...

脇田先生、スーパーノードを除外して考えてみるのは？

・大規模ストリーム処理
データ解析に時間の概念をいれる、
データを変化するものとして考えなければならない
データを捨てる。genom generator？爆発的なデータは？
→メモリ上にのらないデータはSSDなど。
→モデルによる。場合によりけり。

バッチならできる処理も（定数メモリに対して無限（高速）に流れてくるデータ）には対応できない
→ストリーム処理
誰が誰と通信を行っているか解析（sparseな行列ならば可能になる）
→あるデータにメモリで処理できる枠を決め、時間軸をずらせば実現できるので工学的にストリームと違いがない？
→ストリーミングアルゴリズムはあまり将来性がない？ ストリーミングでは粒度が細かすぎる、
問い合わせの頻度が高いものはインクリメンタルなアルゴリズムはおもしろい。

・大規模ストレージ
cps (cyber phisical system)
実システムにたくさんのセンサーを置いて、人間や経済の動向などを分析するシステム
アプリケーションによるが系列データとは限らない。
今まで見えなかったデータを見たいという要望（例：人の動向からどの程度運動不足の人がいるか）
事故が起きる→過去のデータは使わないが→cpsでどこの交差点で事故が起きやすいかがわかるようになる
時間の軸は

２次記憶を利用すると大規模データは手に負えない。
メモリとSSDの階層化はアルゴリズム屋は考えてない。理論の方向から難しいのでは？
メモリに収まっても時間がかかりすぎる場合も。
ネットワーク型のアルゴリズムは並列化がむずかしい

- - - - - - - - - -
集合の類似性を調べるアプリケーションについて
たくさん（１億）のデータから前後のつながり？から単語の意味が似ているなど。
頻度の高いデータを外すことで計算量を減らす→３,４日かかる
|A∩B| / |A∪B|
このような考えはグラフ解析そのものに用いるのではなくグラフに関するものの高速化アルゴリズムに使える？
- - - - - - - - - -

・グラフ視覚化
大規模なグラフに関してはあまり議論されていない（バネモデル）
ゲノムではドットプロット
上の類似性が調べられれば十分できる
大規模なデータを可視化しても人間には直感的に理解出来ないので
うまく表現できるようなモデル、方法を考える必要があるのではないか？

藤澤先生、グラフが理解できるような技術者を養成！訓練によって見えるようになるかも！
脇田先生、26日にitohさんがくる？

クリークぐらい密な情報は必要ない。密な情報は求められていない。


ネットフリックス
想像技術、作り込み
個々のデータを集めてきたパラメータを変えてチューニング→動いた人が勝ち？

雁瀬さん
グラフのデータを抜き出してきたときにそれが有用かそうでないかの判定は？
少なくとも、といった条件を抜き出しておく。主観の問題がある？
グラフ処理は並列化しにくいが、グラフに対して前処理を行う場合は？
→前処理を行っても2転3転計算し直し、速度があがらない場合がおおい

遠藤先生
コンピュータが大きくなってグラフ解析は有用になるか？
知識抽出の世界の人にはあまり全体を意識していない（局所的なものだけ）
グラフアルゴリズムは並列化しにくいものが多い
並列化によって精度が下がってしまうものは許容されるか？
アプリケーションによる。クラスタリングなら許容される？
近似は？
近似によって受け入れられないものもある（バイオ）一方ヒューリスティックな解法を使っていたり。
自然言語処理分野では結果のみを意識するので途中の近似による
TSUBAMEの運用、ネットワークの可視化

Stream Computing を用いたリアルタイム交通管理

http://sites.computer.org/debull/A10june/Anand.pdf

交通量予測アルゴリズム

TRL の加藤さんが書いた論文 http://www-06.ibm.com/ibm/jp/provision/no64/pdf/64_report.pdf
の 5.2 章参照

予測アルゴリズムは IBM ワトソンの Wanli が以下の論文で提唱。
http://transp-or2.epfl.ch/tristan/FullPapers/010wynter.pdf

Google Map 上のリアルタイム交通状況可視化

Android 携帯でユーザーが現在位置情報の機能を有効しているのみ Google のサーバーに送信。位置データと速度から交通状況を把握
http://googlejapan.blogspot.com/2011/12/google_09.html

グラフ可視化

http://www.kecl.ntt.co.jp/as/members/tatsushi/graphdrawing.html

IBM Parallel Debugger for X10 Programming

https://www.ibm.com/developerworks/mydeveloperworks/groups/service/html/communityview?communityUuid=e3fb8100-3ee3-4402-bf67-bf66b29797ea

NVIDIA ブースでの SC11 でのトーク

http://www.nvidia.com/object/sc11.html

Flume + Cassandra

http://www.slideshare.net/geminimobile/flume-cassandra-real-time-log-processing

Spectral Clustering

http://www.csie.ntu.edu.tw/~cjlin/papers/psc08.pdf
Parallel Spectral Clustering in Distributed Systems

Spectral clustering algorithms have been shown to be more effective in finding clusters than some traditional
algorithms such as k-means. However, spectral clustering suffers from a scalability problem in both memory use and
computational time when the size of a data set is large. To perform clustering on large data sets, we investigate two
representative ways of approximating the dense similarity matrix. We compare one approach by sparsifying the matrix
with another by the Nyström method. We then pick the strategy of sparsifying the matrix via retaining nearest neighbors
and investigate its parallelization. We parallelize both memory use and computation on distributed computers. Through
an empirical study on a document data set of 193; 844 instances and a photo data set of 2; 121; 863, we show that
our parallel algorithm can effectively handle large problems.


Parallelization of spectral clustering algorithm on multi-core processors and GPGPU
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4625449

Spectral clustering is a widely-used algorithm in the field of information retrieval, data mining, machine learning and many others. It can help to cluster a large number of data into several categories without requiring any additional information about the dataset or the categories, so that people can find information by categories easily. In this paper, we parallelize the algorithm proposed by Andrew Y. Ng, Michael I. Jordan and Yair Weiss. We provide two versions of implementation: one is parallelized in OpenMP; the other is programmed in the NVIDIA CUDA (compute unified device architecture), which is the environment provided by NVIDIA to program on its CUDA-Enabled GPGPUs (general-purpose graphic processing unit). We can achieve about three times speedup in OpenMP and around ten times speedup using CUDA in our experiments.


On a strategy for spectral clustering with parallel computation
VECPAR'10 Proceedings of the 9th international conference on High performance computing for computational science

pectral Clustering is one of the most important method based on space dimension reduction used in Pattern Recognition. This method consists in selecting dominant eigenvectors of a matrix called affinity matrix in order to define a low-dimensional data space in which data points are easy to cluster. By exploiting properties of Spectral Clustering, we propose a method where we apply independently the algorithm on particular subdomains and gather the results to determine a global partition. Additionally, with a criterion for determining the number of clusters, the domain decomposition strategy for parallel spectral clustering is robust and efficient.

Graph500 on Amazon EC2 (Cluster Computer Instances)

http://aws.amazon.com/jp/hpc-applications/

23 GB メモリ
33.5 EC2 Compute Unit（2 x Intel Xeon X5570、quad-core「Nehalem」アーキテクチャ）
1690 GB インスタンスストレージ
64ビット プラットフォーム
I/O 性能: 超高速（10 ギガビットイーサネット）
API 名: cc1.4xlarge

Cluster Compute Eight Extra Large を使用すると、1時間 2.40 $.
128 ノードを1時間使用すると、1ドル80円計算で 約 25000円.

Graph Stream Analytics : Pattern Matching

http://hpcdb.org/sites/hpcdb.org/files/choudhury_graphstreams.pdf
Large-Scale Continuous Subgraph Queries on Streams

Graph pattern matching involves finding exact or approximate matches for a query subgraph in a larger graph. It has been studied extensively and has strong applications in domains such as computer vision, computational biology, social networks, security and finance.The problem of exact graph pattern matching is often described in terms of subgraph isomorphism which is NP-complete. The exponential growth in streaming data from online social networks, news and video streams and the continual need for situational awareness motivates a solution for finding patterns in streaming updates. This
is also the prime driver for the real-time analytics market. Development of incremental algorithms for graph pattern matching on streaming inputs to a continually evolving graph is a nascent area of research. Some of the challenges associated with this problem are the same as found in continuous query (CQ) evaluation on streaming databases. This paper reviews some of the representative work from the exhaustively researched field of CQ systems and identifies important semantics, constraints and architectural features that are also appropriate for HPC systems performing real-time graph analytics. For each of these features we present a brief discussion of the challenge encountered in the database realm, the approach to the
solution and state their relevance in a high-performance, streaming
graph processing framework.

グラフマイニング

http://www.db.soc.i.kyoto-u.ac.jp/index.php/ja/component/content/article/104

GraphStream: A Dynamic Graph Library

http://graphstream-project.org/

静的・動的グラフの可視化ライブラリ. Version 1.1. YouTube のビデオあり
http://graphstream-project.org/doc/Gallery/

X10 ベースの大規模交通シミュレーション実行基盤

道路ネットワークを領域分割することによって複数ノードで高速化されることは明らかであり、TSUBAME 上での妥当な結果が出つつある。ただ、一部の領域においては非常に時間がかかっており、これは車両の経路が通る重要な道路の許容量が少ないから。現在出ている性能分析により、今後は、より研究としての落としどころをつめていかないといけませんが、「Work Stealing 機構によって、動的に混雑度の高い領域に X10 アクティビティを生成する方式」を実装することにより、研究としての価値が生まれるでしょう。

Graph Stream Mining

http://www.utdallas.edu/~hamlen/parveen-passat11.pdf

Insider Threat Detection using Stream Mining and Graph Mining

Evidence of malicious insider activity is often
buried within large data streams, such as system logs
accumulated over months or years. Ensemble-based stream
mining leverages multiple classification models to achieve
highly accurate anomaly detection in such streams even
when the stream is unbounded, evolving, and unlabeled.
This makes the approach effective for identifying insider threats who attempt to conceal their activities by
varying their behaviors over time. This paper applies
ensemble-based stream mining, unsupervised learning, and
graph-based anomaly detection to the problem of insider
threat detection, demonstrating that the ensemble-based
approach is significantly more effective than traditional
single-model methods.
Index Terms—anomaly d

Gremlin: グラフ解析特化型言語

https://github.com/tinkerpop/gremlin/wiki
http://www.infoq.com/jp/news/2010/01/Gremlin
http://www.youtube.com/watch?v=5wpTtEBK4-E

Graph database

http://blog.infinitegraph.com/2011/09/02/real-time-relationship-analytics-from-large-scale-graph-processing/


Neo4J
http://www.youtube.com/watch?v=UodTzseLh04&feature=related

Neo4J and Real Scenario
http://www.youtube.com/watch?v=UNH0JC0grOQ&feature=related

グラフ応用 - Cyber Security

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5482734&tag=1

Measure Large Scale Network Security Using Adjacency Matrix Attack Graphs

An Attack Graph capable of disclosing causal relationships between multiple vulnerabilities has become a desirable tool for administrators to analyze and locate potential risks to protect critical networked resources against internal or external multi-step attacks. However, probabilistic security metric computations, using currently applied attack graphs, have complexity problems due to their scale. It is hard or even impossible for current attack graphs to be applied to large scale networks. This paper proposes a novel approach that combines the advantages of exploit-dependency attack graphs and adjacency matrices, which results in quadratic complexity. We first give a motivating example to introduce the approach. We then define the adjacency matrix attack graphs. We show that computing probabilistic cumulative scores by means of adjacency matrix attack graphs is efficient and readily scalable.


http://research.microsoft.com/pubs/79413/botgraph.pdf
BotGraph: Large Scale Spamming Botnet Detection

Network security applications often require analyzing
huge volumes of data to identify abnormal patterns or
activities. The emergence of cloud-computing models
opens up new opportunities to address this challenge by
leveraging the power of parallel computing.
In this paper, we design and implement a novel system
called BotGraph to detect a new type of botnet spamming
attacks targeting major Web email providers. Bot-
Graph uncovers the correlations among botnet activities
by constructing large user-user graphs and looking for
tightly connected subgraph components. This enables us
to identify stealthy botnet users that are hard to detect
when viewed in isolation. To deal with the huge data
volume, we implement BotGraph as a distributed application
on a computer cluster, and explore a number of
performance optimization techniques. Applying it to two
months of Hotmail log containing over 500 million users,
BotGraph successfully identified over 26 million botnetcreated
user accounts with a low false positive rate. The
running time of constructing and analyzing a 220GB Hotmail
log is around 1.5 hours with 240 machines. We believe
both our graph-based approach and our implementations
are generally applicable to a wide class of security
applications for analyzing large datasets.

グラフ応用

http://www.indiana.edu/~cortex/networks_nrn.pdf

Complex brain networks: graph theoretical analysis of structural and functional systems

Recent developments in the quantitative analysis of complex networks, based
largely on graph theory, have been rapidly translated to studies of brain network organization.
The brain’s structural and functional systems have features of complex networks — such as
small-world topology, highly connected hubs and modularity — both at the whole-brain
scale of human neuroimaging and at a cellular scale in non-human animals. In this article, we
review studies investigating complex brain networks in diverse experimental modalities
(including structural and functional MRI, diffusion tensor imaging, magnetoencephalography
and electroencephalography in humans) and provide an accessible introduction to the
basic principles of graph theory. We also highlight some of the technical challenges and key
questions to be addressed by future developments in this rapidly moving field.

Madduri's work

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

Parallel Shortest Path Algorithms for Solving Large-Scale Instances

We present an experimental study of the single source shortest path problem with non-negative edge weights (NSSP) on largescale graphs using the Delta-stepping parallel algorithm. We report performance results on the Cray MTA-2, a multithreaded parallel computer. The MTA-2 is a high-end shared memory system offering two unique features that aid the efficient parallel implementation of irregular algorithms: the ability to exploit fine-grained parallelism, and low-overhead synchronization primitives. Our implementation exhibits remarkable parallel speedup when compared with competitive sequential algorithms, for low-diameter sparse graphs. For instance, Delta-stepping on a directed scale-free graph of 100 million vertices and 1 billion edges takes less than ten seconds on 40 processors of the MTA-2, with a relative speedup of close to 30. To our knowledge, these are the first performance results of a shortest path problem on realistic graph instances in the order of billions of vertices and edges.

HPC Graph Analytics

http://www.graphanalysis.org/benchmark/GraphAnalysisBenchmark-v1.0.pdf

Distributed Graph Analytics

http://dl.acm.org/citation.cfm?id=958940
Δ-stepping: a parallelizable shortest path algorithm

The single source shortest path problem for arbitrary directed graphs with n nodes, m edges and nonnegative edge weights can sequentially be solved using O(n ċ log n + m) operations. However, no work-efficient parallel algorithm is known that runs in sublinear time for arbitrary graphs. In this paper we present a rather simple algorithm for the single source shortest path problem. Our new algorithm, which we call Delta-stepping, can be implemented very efficiently in sequential and parallel setting for a large class of graphs. For random edge weights and arbitrary graphs with maximum node degree d, sequential Δ-stepping needs O(n + m + d ċ L) total average-case time, where L denotes the maximum shortest path weight from the source node s to any node reachable from s. For example, this means linear time on directed graphs with constant maximum degree. Our best parallel version for a PRAM takes O(d ċ L ċ log n + log2 n) time and O(n + m + d ċ L ċ log n) work on average. For random graphs, even O(log2 n) time and O(n + m) work on average can be achieved. We also discuss how the algorithm can be adapted to work with nonrandom edge weights and how it can be implemented on distributed memory machines. Experiments indicate that already a simple implementation of the algorithm achieves significant speedup on real machines.


Single-Source Shortest Paths with the Parallel Boost Graph Library
http://www.dis.uniroma1.it/~challenge9/papers/edmonds.pdf
The Parallel Boost Graph Library (Parallel BGL) is a library of graph algorithms and data structures for distributed-memory computation on large graphs. Developed with the Generic Programming
paradigm, the Parallel BGL is highly customizable, supporting various graph data structures, arbitrary
vertex and edge properties, and different communication media. In this paper, we describe the implementation of two parallel variants of Dijkstra’s single-source shortest paths algorithm in the Parallel BGL.We also provide an experimental evaluation of these implementations using synthetic and real-world benchmark graphs from the 9th DIMACS Implementation Challenge.


http://eecs.wsu.edu/~cs460/cs550/parallelShortestPath.pdf
A Parallel Shortest Path Algorithm Based on Graph-Partitioning and Iterative Correcting, 2010
In this paper, we focus on satisfying the actual demands of quickly finding the shortest paths over real-road networks in an intelligent transportation system. A parallel shortest path algorithm based on graph partitioning and iterative correcting is proposed. After evaluating the algorithm using three real road networks, we conclude that our graph- partitioning and iterative correcting based parallel algorithm has good performance. In addition, it achieves more than a 15-fold speedup on 16 processors in an IBM cluster over these real road networks.


http://scidok.sulb.uni-saarland.de/volltexte/2004/207/pdf/UlrichMeyer_ProfDrKurtMehlhorn.pdf
Design and Analysis of Sequential and Parallel Single–Source Shortest–Paths Algorithms, Ulrich Meyer

e study the performance of algorithms for the Single-Source Shortest-Paths (SSSP) problem on graphs with nodes and edges with nonnegative random weights. All previously known SSSP algorithms for directed graphs required superlinear time. We give the first SSSP algorithms that provably achieve linear average-case execution time on arbitrary directed graphs with random edge weights. For independent edge weights, the linear-time bound holds with high probability, too. Additionally, our result implies im- proved average-case bounds for the All-Pairs Shortest-Paths (APSP) problem on sparse graphs, and it yields the first theoretical average-case analysis for the “Approximate Bucket Implementation” of Dijkstra’s SSSP algorithm (ABI–Dijkstra). Furthermore, we give con- structive proofs for the existence of graph classes with random edge weights on which ABI–Dijkstra and several other well-known SSSP algorithms require superlinear average- case time. Besides the classical sequential (single processor) model of computation we also consider parallel computing: we give the currently fastest average-case linear-work parallel SSSP algorithms for large graph classes with random edge weights, e.g., sparse random graphs and graphs modeling the WWW, telephone calls or social networks.


http://www.cse.psu.edu/~madduri/papers/ThorupSSSP-MTAAP07.pdf


http://www.sandia.gov/~sjplimp/papers/pc11.pdf
MapReduce in MPI for Large-scale Graph Algorithms, 2010

We describe a parallel library written with message-passing (MPI) calls that allows algo- rithms to be expressed in the MapReduce paradigm. This means the calling program does not need to include explicit parallel code, but instead provides “map” and “reduce” functions that operate independently on elements of a data set distributed across processors. The library performs needed data movement between processors. We describe how typical MapReduce functionality can be implemented in an MPI context, and also in an out-of-core manner for data sets that do not fit within the aggregate memory of a parallel machine. Our motivation for creating this library was to enable graph algorithms to be written as MapReduce opera- tions, allowing processing of terabyte-scale data sets on traditional MPI-based clusters. We outline MapReduce versions of several such algorithms: vertex ranking via PageRank, triangle finding, connected component identification, Luby’s algorithm for maximally independent sets, and single-source shortest-path calculation. To test the algorithms on arbitrarily large artifi- cial graphs we generate randomized R-MAT matrices in parallel; a MapReduce version of this operation is also described. Performance and scalability results for the various algorithms are presented for varying size graphs on a distributed-memory cluster. For some cases, we com- pare the results with non-MapReduce algorithms, different machines, and different MapReduce software, namely Hadoop. Our open-source library is written in C++, is callable from C++, C, Fortran, or scripting languages such as Python, and can run on any parallel platform that supports MPI.


Apache HAMA http://blogs.apache.org/hama/


http://homepages.dcc.ufmg.br/~tmacam/publications/macambira2010middleware.pdf
A middleware for parallel processing of large graphs, 2010
With the increasing “data deluge” scientists face today, the analysis and processing of large datasets of structured data is a daring task. Among such data, large graphs are gaining particular importance with the growing interest on social networks and other complex networks. Given the dimensions considered, parallel pro- cessing is essential. However, users are generally not experts in writing parallel code to handle such structures. In this work we present Rendero, a middleware that makes it possible to easily de- scribe graph algorithms in a form adequate for parallel execution. The system is based on the Bulk-Synchronous programming model and offers a vertex-based abstraction. Our current implementation offers good speed-up and scale-up results for large graphs ranging from tens of thousands to millions of vertices and edges in some cases.


http://www.cslab.ntua.gr/~anastop/files/papers/mtaap09dijkstra.pdf
Early Experiences on Accelerating Dijkstra’s Algorithm Using Transactional Memory

In this paper we use Dijkstra’s algorithm as a challenging, hard to parallelize paradigm to test the efficacy of several par- allelization techniques in a multicore architecture. We consider the application of Transactional Memory (TM) as a means of concurrent accesses to shared data and compare its perfor- mance with straightforward parallel versions of the algorithm based on traditional synchronization primitives. To increase the granularity of parallelism and avoid excessive synchro- nization, we combine TM with Helper Threading (HT). Our simulation results demonstrate that the straightforward par- allelization of Dijkstra’s algorithm with traditional locks and barriers has, as expected, disappointing performance. On the other hand, TM by itself is able to provide some performance improvement in several cases, while the version based on TM and HT exhibits a significant performance improvement that can reach up to a speedup of 1.46.

GPU-based SSSP

http://www.ijcaonline.org/volume10/number10/pxc3871992.pdf
Performance Improvement in Large Graph Algorithms on GPU using CUDA: An Overview, 2010

The basic operations on the graphs with millions of vertices are common in various applications. To have faster execution of such operations is very essential to reduce overall computation time. Today’s Graphics processing units (GPUs) have high computation power and low price. This device can be treated as an array of Single Instruction Multiple Data (SIMD) processors using CUDA software interface by Nvidia. Massively Multithreaded architecture of a CUDA device makes various threads to run in parallel and hence making optimum use of available computation power of GPU. In case of graph algorithms, vertices of the graphs are processed in parallel by mapping them to various threads on device. By making thousands of threads to run in parallel, computation time required for these algorithms is drastically decreased as compared to their CPU implementation.
We studied different parallel algorithms for Breadth first search, all pairs shortest path that are carried out on GPU using CUDA and make their comparative study with respect to execution time, data structure used, input data etc. In the paper, we presented overview of various parallel methods carried out on GPU using its multithreaded architecture for BFS, APSP by various authors.


http://ppl.stanford.edu/papers/ppopp070a-hong.pdf
Accelerating CUDA Graph Algorithms at Maximum Warp, 2007
Graphs are powerful data representations favored in many compu- tational domains. Modern GPUs have recently shown promising re- sults in accelerating computationally challenging graph problems but their performance suffers heavily when the graph structure is highly irregular, as most real-world graphs tend to be. In this study, we first observe that the poor performance is caused by work imbal- ance and is an artifact of a discrepancy between the GPU program- ming model and the underlying GPU architecture. We then propose a novel virtual warp-centric programming method that exposes the traits of underlying GPU architectures to users. Our method signif- icantly improves the performance of applications with heavily im- balanced workloads, and enables trade-offs between workload im- balance and ALU underutilization for fine-tuning the performance.
Our evaluation reveals that our method exhibits up to 9x speedup over previous GPU algorithms and 12x over single thread CPU execution on irregular graphs. When properly configured, it also yields up to 30% improvement over previous GPU algorithms on regular graphs. In addition to performance gains on graph algo- rithms, our programming method achieves 1.3x to 15.1x speedup on a set of GPU benchmark applications. Our study also confirms that the performance gap between GPUs and other multi-threaded CPU graph implementations is primarily due to the large difference in memory bandwidth.


http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F6067545%2F6075092%2F06075214.pdf%3Farnumber%3D6075214&authDecision=-203
A modified parallel approach to Single Source Shortest Path Problem for massively dense graphs using CUDA, 2011
Today's Graphics Processing Units (GPUs) possess enormous computation power with highly parallel and multithreaded architecture, and the most attractive feature being their low costs. NVIDIA's CUDA provides an interface to the developers to use the GPUs for General Purpose Parallel Computing. In this paper, we present a modified algorithm of Single Source Shortest Path Problem on GPU using CUDA. First, we modify the standard BELLMAN-FORD algorithm to remove its drawbacks and make it suitable for parallel implementation, and then implement it using CUDA. For dense graphs, our Algorithm gains a speedup of 10×–12× over the previously proposed parallel algorithm. Our Algorithm also accept graphs with negative weighted edges and can detect any reachable Negative Weighted Cycle, which widens its scope to accept generalized problems.


http://www.springerlink.com/content/a254839r565r176p/
CUDA Solutions for the SSSP Problem
We present several algorithms that solve the single-source shortest-path problem using CUDA. We have run them on a database, composed of hundreds of large graphs represented by adjacency lists and adjacency matrices, achieving high speedups regarding a CPU implementation based on Fibonacci heaps. Concerning correctness, we outline why our solutions work, and show that a previous approach [10] is incorrect.


http://ldc.usb.ve/~vtheok/cursos/ci6323/pdf/lecturas/Accelerating%20Large%20Graph%20Algorithms%20on%20the%20GPU%20Using%20CUDA.pdf
Accelerating Large Graph Algorithms on the GPU Using CUDA, Pawan Harish and P.J. Narayanan,

Largegraphsinvolvingmillionsofverticesarecommoninmanyprac- tical applications and are challenging to process. Practical-time implementations using high-end computers are reported but are accessible only to a few. Graphics Processing Units (GPUs) of today have high computation power and low price. They have a restrictive programming model and are tricky to use. The G80 line of Nvidia GPUs can be treated as a SIMD processor array using the CUDA pro- gramming model. We present a few fundamental algorithms – including breadth first search, single source shortest path, and all-pairs shortest path – using CUDA on large graphs. We can compute the single source shortest path on a 10 million vertex graph in 1.5 seconds using the Nvidia 8800GTX GPU costing $600. In some cases optimal sequential algorithm is not the fastest on the GPU architec- ture. GPUs have great potential as high-performance co-processors.


----

http://sc.chat-shuffle.net/paper/uid:110006828689
CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
本論文では全点対最短経路(APSP:All-Pairs Shortest Path)問題をGPU(Graphics Processing Unit)を用いて高速化した結果を述べる.提案手法は,GPUで動作するプログラムをGPU向けの開発環境CUDA(Compute Unified Device Architecture)を用いて記述する.アルゴリズムには単一始点最短経路を繰り返し求める手法(SSSP反復法)を用いる.問題全体での逐次処理を減らしてより高い速度向上を得るために,1っのSSSP問題を1つのタスクとし,それらのタスクを並列処理する.さらに,共有メモリを用いてタスク間でデータを共有し,グローバルメモリの参照を削減する.結果,既存手法よりも3.5〜18倍高速であった.また,SSSP反復法の性能がグラフの特性に依存して変動することを示す.
http://hagi-www.ics.es.osaka-u.ac.jp/research/papers/200812_t-okuyam_ispa.pdf

Graph500 with FPGA

http://insidehpc.com/2011/11/28/video-convey-computer-rocks-the-graph500-at-sc11/

Graph500 with Fusion I/O

http://institutes.lanl.gov/isti/summer-school/cluster_network/projects-2011/2011%20Red%20Team_OutofCorePoster.pdf

Graphity

http://architects.dzone.com/articles/graphity-how-retrieve

[Graph500] Graph500 on Amazon EC2

Graph500 on Amazon EC2 に関して

- Amazon EC2 のクラスタインスタンスの仕様
Amazon EC2 supports Cluster instance"
Xeon X5570 (2.95GHz), 23 GB of RAM, 1690 GB of local
storage, and 10 Gbps network, all for $1.60 per hour  recently GPU (Tesla Fermi) is available
(2010年後半の仕様なので変化があるはず）

- 研究内容
- 仮想化環境において Graph500 を実行し、bare metal の環境との性能特性を行う
- ベンチマークを完遂させることを目的としない。BFS を何回か、validation は実行しない。
- Scale は 1ノードにつき Scale 26でいけるので、TSUBAME で取った性能プロファイルと比較できる
- マイクロベンチマークを実行し、ネットワークトポロジー予測を行う（関連研究があるはずなので調査）
- CPU 課金が１時間単位なのでノード数を少なくできるか？
- 予測トポロジーに応じて、MPI のランク最適配置を計算し、性能を向上させる
- 128ノードを用いて12時間走らせて約20万円
- 上記研究内容をもとに、Amazon が Graph500 にサブミッションするかどうかは別の話し
- Target Conference: IEEE Cloud 2012 締め切りは 2012年1月後半

[参考文献]
http://www.stratosphere.eu/files/TopologyInferenceEnd2End_11.pdf

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5948654

http://dl.acm.org/citation.cfm?id=1833691
The impact of virtualization on network performance of amazon EC2 data center, InfoCOM 2010

Cloud computing services allow users to lease computing resources from large scale data centers operated by service providers. Using cloud services, users can deploy a wide variety of applications dynamically and on-demand. Most cloud service providers use machine virtualization to provide flexible and costeffective resource sharing. However, few studies have investigated the impact of machine virtualization in the cloud on networking performance.

In this paper, we present a measurement study to characterize the impact of virtualization on the networking performance of the Amazon Elastic Cloud Computing (EC2) data center. We measure the processor sharing, packet delay, TCP/UDP throughput and packet loss among Amazon EC2 virtual machines. Our results show that even though the data center network is lightly utilized, virtualization can still cause significant throughput instability and abnormal delay variations. We discuss the implications of our findings on several classes of applications.

Meeting w/ Andy Yoo (LLNL)

Here are the minutes of the meeting we had with Andy,

-------------------------------------

There is no MatLab code or MPI code. Miyuru need to create an MPI implementation of the graph generator.

The reason why current methods (e.g. RMAT) not good is there is a low level of clustering coefficient. We need a generator that creates data set with very high clustering coefficient of data points.

The proposed method starts with Quasi Cliques. There are non-zero elements in the Matrix.

Miyuru should read the look for Chung-Lu model. There is a paper published around 2001-2002.

The basic idea is given a degree distribution the implementation should extract the model out of it.
So the main activities are,

- Create a MatLab model of the generator
- Port MatLab code to MPI
- Do experiments of the graph generator with Tsubame

[Graph500] 住元さんとの議事録

SC2011 にて住元さんとミーティング。以下、上野君が取ってくれた議事録

通信性能は、１本あたり4.7GB/5GB。１ノード全部で14.7GB。
ジョブごとにセグメントを分けている
6次元なのでホップ数はx,y,zにそれぞれ+2したもの
K用のプロファイリングツールがある
６次元での位置や故障ノードのなどの情報はユーザに見せていない
３次元では遠いノードでも、６次元なのでショートカットが存在する
３次元で遠いノードほど、ショートカットがある
実行中にノードが故障したら割り当て範囲内で再配置して実行
キャッシュセグメント？（明示的にキャッシュを制御する？）
プログラムからはローカルディスクしか見えない
ローカルディスクは32ノードに対して１RAIDシステム
15000回転のHDD 16台のRAID 4+1
接続はFiberChannel
メモリのデータをすべてダンプするだけの容量くらいはもちろんある
キャッシュインジェクションにより低レイテンシ（Infinibandにはない）
RDMAなので、最終的にはメモリに書き込まれる
普通はDMAでメモリに書き込まれたらキャッシュはフラッシュされる
キャッシュラインに全部書き込めばメモリから読み込まれることはない
通信モジュールは入出力合わせて100GB/s
富士通のユーザフォーラム SSけん HPC forum おいなが

Andy Yoo's Talk at Google

http://youtu.be/PBLgUBGWcz8

Rodinia: A Benchmark Suite for Heterogeneous Computing

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.8883

This paper presents and characterizes Rodinia, a benchmark suite for heterogeneous computing. To help architects study emerging platforms such as GPUs (Graphics Processing Units), Rodinia includes applications and kernels which target multi-core CPU and GPU platforms. The choice of applications is inspired by Berkeley’s dwarf taxonomy. Our characterization shows that the Rodinia benchmarks cover a wide range of parallel communication patterns, synchronization techniques and power consumption, and has led to some important architectural insight, such as the growing importance of memory-bandwidth limitations and the consequent importance of data layout. I.

X10 sample program

http://www.ipsj.or.jp/07editj/supplement/5203.html

GBASE: a scalable and general graph management system

GBASE: a scalable and general graph management system
http://dl.acm.org/citation.cfm?id=2020408.2020580&coll=DL&dl=ACM

Graphs appear in numerous applications including cyber-security, the Internet, social networks, protein networks, recommendation systems, and many more. Graphs with millions or even billions of nodes and edges are common-place. How to store such large graphs efficiently? What are the core operations/queries on those graph? How to answer the graph queries quickly? We propose GBASE, a scalable and general graph management and mining system. The key novelties lie in 1) our storage and compression scheme for a parallel setting and 2) the carefully chosen graph operations and their efficient implementation. We designed and implemented an instance of GBASE using MapReduce/Hadoop. GBASE provides a parallel indexing mechanism for graph mining operations that both saves storage space, as well as accelerates queries. We ran numerous experiments on real graphs, spanning billions of nodes and edges, and we show that our proposed GBASE is indeed fast, scalable and nimble, with significant savings in space and time.

Open Street Map (OSM)

世界の道路ネットワークデータ Open Street Map
http://www.openstreetmap.org/

データの形式は OSM (XML) か、以下の PBF 形式で提供
http://wiki.openstreetmap.org/wiki/PBF_Format

研究室には、/nfs/data0/roadnetwork/ にダウンロードしています。PBF フォーマットで 9GB ぐらいあります。

Solving Large, Irregular Graph Problems using Adaptive Work-stealing

X10 のワークスティーリングフレームワーク XWS。Sun Niagara 上で BFS/DFS を X10+XWS で実行し、Cilk に対する優位性を示す。

http://gee.cs.oswego.edu/dl/papers/icpp08.pdf

Solving large, irregular graph problems efficiently is challenging. Current software systems and commoditymultiprocessors do not support fine-grained, irregular parallelism well. We present XWS, the X10 Work Stealing framework, an open-source runtime for the parallel programming language X10 and a library to be used directly by application writers. XWS extends the Cilk work-stealing framework with several features necessary to efficiently implement graph algorithms, viz., support for improperly nested procedures, global termination detection, and phased computation. We also present a strategy to adaptively control the granularity of parallel tasks in the work-stealing scheme, depending on the instantaneous size of the work queue. We compare the performance of the XWS implementations of spanning tree algorithms with that of the hand-written C and Cilk
implementations using various graph inputs. We show that XWS programs (written in Java) scale and exhibit comparable or better performance.

HipG: parallel processing of large-scale graphs

汎用グラフ処理システム HipG. 強連結成分分解を実装し、PBGL (Parallel Boost Graph Library) と hand-written の C/MPI を用いて速度的な優位性を示す。

http://dl.acm.org/citation.cfm?id=2007185

Distributed processing of real-world graphs is challenging due to their size and the inherent irregular structure of graph computations. We present HipG, a distributed framework that facilitates programming parallel graph algorithms by composing the parallel application automatically from the user-defined pieces of sequential work on graph nodes. To make the user code high-level, the framework provides a unified interface to executing methods on local and non-local graph nodes and an abstraction of exclusive execution. The graph computations are managed by logical objects called synchronizers, which we used, for example, to implement distributed divide-and-conquer decomposition into strongly connected components. The code written in HipG is independent of a particular graph representation, to the point that the graph can be created on-the-fly, i.e. by the algorithm that computes on this graph, which we used to implement a distributed model checker. HipG programs are in general short and elegant; they achieve good portability, memory utilization, and performance.

大規模グラフストリーム処理系

graph crest のプロジェクトのスコープの一つとして、大規模グラフストリーム処理系があります。インクリメンタルな汎用グラフ処理モデルは、西井君・雁瀬君が追求してもらっていますし、今それぞれ案を出してもらっている graph database for stream computing のあるべき姿もこの範疇に入ってきます。上野君と Miyuru 君のStreamScale をベースにするかどうかも再度議論する必要がありますが、オープンソースとして公開可能な汎用的な「大規模グラフストリーム処理系」を構築する必要があります。また、雁瀬君、上野君、竹野君の動的二部グラフの関連解析処理も、この処理系の上で動く必要がありますし、その他のアプリケーションでも使用可能に成り得る機能は、処理系が提供すべきものです。また、当然、バッチ処理系とのインタフェースも必須となってくるでしょう。

MAGMA: LAPACK for HPC on Heterogeneous Architectures

MAGMA の 1.0 が先月末に公開されたようです。
http://icl.cs.utk.edu/magma/news/news.html?id=274

Gremlin- Graph Traversal Language

https://github.com/tinkerpop/gremlin/wiki

2011/08/22 Lab Meeting Agenda

明日の研究室ミーティングの Agenda
- Crest プロジェクトに関して(30分ほど）
- 物品購入など
- 個別の研究進捗(4年生は院試報告と今後の方向性)
- 全体ミーティング、個別ミーティングの日程
- 各自の後期授業日程 (10月以降)
- ソフトウェア科学会チュートリアル(沖縄)・チューター決め
- IT 管理者,引継ぎに向けて
- 工大祭コンテンツ決め：ポスター作り、デモ内容、昨年のフィードバック
- SuperComputing 2011
- New member に関して (10月から、来年4月から)
- その他

実時間・モバイル空間統計

以下のリンクの、モバイル空間統計はバッチで行われていると推測するが、Twitter データ (位置情報を含む。間引かれているので統計的な推定も必要) から、これをリアルタイムに3次元的に把握できるような可視化システムができると（デモ的には）良い。当然、リアルタイムに見せるだけでなく、時間軸を変更できるようなインタフェースも用意し、特定の日時、時間帯も見れると良い。

http://www.nttdocomo.co.jp/corporate/disclosure/mobile_spatial_statistics/

[論文] Erik Zeitler,Tore Rischなどによるストリーム処理系の研究

スウェーデンの研究者Erik Zeitler とTore Rischによるストリーム処理系に関する論文

Scalable Splitting of Massive Data Streams, DASFAA2010,
http://www.it.uu.se/research/group/udbl/publ/DASFAA2010.pdf

Processing high-volume stream queries on a supercomputer
http://user.it.uu.se/~torer/publ/zricde2006.pdf

Using stream queries to measure communication performance of a parallel computing environment
http://www.computer.org/portal/web/csdl/doi/10.1109/ICDCSW.2007.88

MOA Project

MOA: Massive Online Analysis
http://moa.cs.waikato.ac.nz/

Stream Mining のツールキット
http://cdnetworks-kr-1.dl.sourceforge.net/project/moa-datastream/documentation/StreamMining.pdf

国土地理院 国土数値情報ダウンロード

http://nlftp.mlit.go.jp/ksj/index.html

Bagel: Pregel のオープンソース実装

汎用グラフ処理モデル Pregel オープンソース実装が出ているようです。グラフ関係者は要チェック。http://d.hatena.ne.jp/smly/20110730/1312022963
https://github.com/mesos/spark/pull/48

国際高等セミナーハウス

国立情報学研究所(NII) のセミナーハウス。Crest プロジェクト等、合同研究室のゼミ合宿には良さそうです。
http://www.nii.ac.jp/about/seminar-house/

研究テーマ

以下、新規の研究テーマ
- BC (Betweenness Centrality), PageRank 等のグラフ処理を 高生産性並列言語 X10 を用いて実現し、超並列分散計算機システム(TSUBAME等) 上での性能評価、性能最適化を行う
- 外部記憶装置を用いた超大規模グラフ処理の実現

[StreamWeb] StreamTwitter デモ(日本語版)

日本語版StreamTwitterのコア部分のソースのディレクトリ
/nfs/home/oiki/spade/uryu/japantwitter

起動の仕方. まずrootで
/nfs/home/oiki/web/webserverの
./core.py
でWebサーバーを起動

次に
/nfs/home/oiki/spade/uryu/japantwitterの
./start_streams_streamtwitter.sh ; ./submitjob_streamtwitter.sh
でSystemS部分を起動

終了は./stop_streams_streamtwitter.shを実行し, core.pyをkill

Multithreaded Asynchronous Graph Traversal for In-Memory and Semi-External Memory

Multithreaded Asynchronous Graph Traversal for In-Memory and Semi-External Memory, SC2010

STING: 動的グラフの可視化

Spatio-Temporal Interaction and Network Graphs - an open source dynamic graph package for Intel Platforms, David Bader

仮想化環境における HPC Challenge Benchmark の性能評価

仮想化環境における HPC Challenge Benchmark の性能評価
Evaluation of the HPC Challenge Benchmarks in Virtualized Environments, ICL, 2011
http://icl.cs.utk.edu/news_pub/submissions/vhpc2011_ehbve.pdf

[Papers] Other Papers on Data Deluge

2020 Computing: Science in an exponential world
Data management in the worldwide sensor web

Apache Hadoop Goes Realtime at Facebook (SIGMOD2011)

以下、今年の SIGMOD 2011 で注目されている論文。必見。
http://borthakur.com/ftp/RealtimeHadoopSigmod2011.pdf

"The Data Deluge"

http://www.economist.com/node/15579717

[StreamWeb] デモの起動方法

demoにログイン.

StreamTwitterのコア部分のソース: ~oiki/spade/uryu/streamtwitter
Webサーバーのソース: ~oiki/web/webserver

[System S の 起動方法]
~/oiki/spade/uryu/streamtwitterの
% ./start_streams_streamtwitter.sh ;
%./submitjob_streamtwitter.sh
でSystemS部分を起動

[Web サーバーの起動]
% cd ~oiki/web/webserverの
% ./core.py


[停止方法]
% /stop_streams_streamtwitter.sh
- core.pyをkill

以下、老木君によるプログラム解説


streamtwitter.zip : System S 部分
web.zip : Webインターフェイス部分

プログラム間の通信は以下の流れで行われる。
1.ブラウザからWebインターフェイス。新しく補足する単語の指示や、単語の要求命令などが送られる。
2.WebインターフェイスからSystem S。新しく補足する単語の指示が送られる。
3.System SからWebインターフェイス。ポストデータが送られる
4.Webインターフェイスからブラウザ。ポストデータが送られる

streamtwitter:
streamtwitterにはSystem S関連のdpsファイルやソースファイルなどが含まれる。
streamtwitterの設定は以下のように変更する。

1.streamtwitter.dpsを変更する
nodepoolを変更することで配置するノードを変更したり、#define HTML_SERVERを変更することでWebインターフェイスを担当するノードを変更する

2.src/config.hを変更する
大量の#define文を変更することで細かい設定を変更できる。
重要なものとして、
GEOMETRY_FILE 経度・緯度変換情報を格納したファイル
COMMAND_PORT 通信2を受け取るポート

web:
webには３つのプログラムが含まれる。

・streammaker
Twitterのふりをするダミーサーバー。負荷テストに、用いる。これについては詳しく説明しない。

・html
Webサーバーによって公開されるフォルダ。現在のディレクトリは ~oiki/web/mimemapper/
index.htmlを代表とする画像やページやjavascriptが格納されている。
設定を変更するには、主にcore.jsを変更する。core.jsには設定用の変数が先頭で宣言されており、
periodtime : 通信4の頻度を設定する
zoom,centerpos : 地図の縮尺、場所

・webserver
Webサーバープログラム。apacheのように静的ファイルを外部に公開する機能と、SystemSからポストデータを受け取り、ブラウザからの要求に応じてそれを送信する機能を持つ。
設定はserver.confを変更することで行う。
html_base : 公開するフォルダ
html_port : 通信1を受け取るポート
post_port : 通信3を受け取るポート
server : System Sが起動しているノード
command_port : System Sが公開しているポート

またwebserverフォルダに含まれるCommander.pyを実行することで、ブラウザを用いることなく監視する単語を追加できる。
./Commander.py word といった風に用いる。
細かい使用法は-hオプションを参考にしてください。

起動手順:
start_streams_streamtwitter.sh,submit...を用いてSystem Sを起動し、webserver/core.pyを起動する。
なお、順番を気にする必要は無い。

補足：
かつてのバージョンでは場所によって、1時間中どれぐらい特定のキーワードが用いられたかを集計する機能が存在したが、InfoSphereStream1.2において、Aggregateオペレーターがtimebasedな場合、perGroupを用いることができなくなったため、現在は機能しない。

バグ：
長時間プログラムを実行させると、WebインターフェイスがSystem Sからポストデータを受け取るのに遅延が発生しはじめる。1時間あたり3分ほど？

WWW 2012

2本提出予定 (雁瀬君ACS論文誌＋Wikipedia の実験、西井君＋雁瀬君のインクリメンタルグラフ処理)

http://www2012.org/

November 1st, 2011 Abstracts for papers due
November 7th, 2011 Papers due
January 30th, 2012 Paper notifications out

[Graph500] 最適化に向けて

Network Coding や、Stream Algorithms の Lossy Count による最適化。
如何にメモリに載り切らない大規模グラフを扱うか。 スケールフリー性を利用し、記憶装置の各階層に記憶,などなど。

2011年上半期まとめ

最近の新たな論文としては以下の通り。

Yahoo S4 vs. System S: Miyuru & Takeno
Graph500 on TSUBAME: Suzumura & Ueno

もうすぐ7月になり、授業関係で忙しくしていた人も研究に没頭しましょう。上野君は、「クロネッカーグラフのスケールフリー性を利用した頂点配置による性能最適化」を。雁瀬君は インクリメンタル最短路問題を Incremental GIM-V 処理系（西井君開発）上に実装し、評価。
4年生の渡部君は Graph500 の日本語まとめを6月下旬まで。7月から4年生は院試勉強へ。勉強に集中してください。

M2は中間発表が 8/1 なので、それまでに結果を出しましょう。国際学会の論文もそろそろ出さねば。

Top500 - 京1位、TSUBAME2 5位

神戸の京が一位に。

Graph500 の発表も楽しみだ。

[Graph500] 90%

IISWC への論文投稿に向けて、土日のほとんどの時間、書き続け、完成度は90%ぐらいになった。今週の平日は来週からの出張に向けていろいろごたごたしているので、ペースは下がるが、提出できそうだ。

Running Large Graph Algorithms - Evaluation Of Current State-Of-The-Art And Lessons Learned

"Running Large Graph Algorithms - Evaluation Of Current State-Of-The-Art And Lessons Learned"
http://highscalability.com/blog/2010/3/30/running-large-graph-algorithms-evaluation-of-current-state-o.html

LLNL の Andy Yoo のトーク

[Graph500] 論文仕上げ

　今日の目標はデータを差し替える以外はすべて完成させること。

15:00 残りはabstract, イントロ、関連研究の半分、Graph500概要(グラフ生成の部分）

[TSUBAME] Installing MVAPICH2

TSUBAME 上にインストールされている MVAPICH2のバージョンは 1.5.1 と古いので、1.6をホームにインストール
% ./configure --prefix=$HOME/packages/mvapich-1.6 --with-rdma=gen2; make; make install

α版だが、1.7a2 もインストール
% ./configure --enable-smpcoll --with-rdma=gen2

Oprofile

下記、Oprofile の使い方の例。Sleep 時間(プロファイリング取得時間）、CPU イベントタイプ、カーネルのデバッグシンボル（VMLINUX) の場所は適当に変えてください。CPUイベントの種類は "opcontrol --list-events " で確認できます。

#!/bin/bash

if [ $# -eq 1 ];
then
  DIR=$1
else
  DIR=results
fi

if [ ! -e $DIR ];
then
  mkdir $DIR
fi

# sc02 の場合
VMLINUX=/usr/lib/debug/lib/modules/2.6.18-92.el5/vmlinux

#opcontrol --setup --no-vmlinux
opcontrol --setup
opcontrol --shutdown
opcontrol --setup --vmlinux=$VMLINUX
opcontrol --reset
opcontrol --separate=none


opcontrol --event=default
## opcontrol --event=PM_INST_CMPL_GRP1:100000:0:1:1 --event=PM_RUN_CYC_GRP1:100000:0:1:1 --event=PM_INST_DISP_GRP1:100000:0:1:1 
opcontrol --start
sleep 30
opcontrol --shutdown
opreport > $DIR/cycle.out
opreport -l > $DIR/cycle_l.out
#opreport --callgraph > $DIR/callgraph.out
#opreport --symbols > $DIR/symbols.out
opcontrol --reset




[Graph500] IISWC 2011

目標としては明日の早朝までに 1/3 ぐらいまでに仕上げる予定。但し、作業開始時間は午後7時頃から.

The Economist の記事

経済誌に珍しく並列プログラミングに関する記事が掲載.
http://www.economist.com/node/18750706

[Graph500] Code reading

　渡部君、上野君が頑張っていますが、Graph500のリファレンス実装の中身が段々と分かってきました。直近のワークとしては、性能特性を調べることですが、「クロネッカーグラフの特性を活用した頂点配置を実行し、通信最適化による性能向上を達成する」が一つの研究テーマになるでしょう。

論文

IISWC に向けて、まずは上野君の GPU Task Parallelism の論文はあと少し。13日(月)にやれば終わるでしょう。

もう一本は、System S vs. Yahoo S4. 締切りが1週間延びたので、Linear Road Benchmark まで評価アプリケーションを増やせると論文としては強くなるでしょう。論文の主張ポイントをもう少し強くしないと駄目。

国内の学会の方は、白幡君が精力的に Mars 上での GIM-V を実装して、PEGASUS と評価している。こちらの方の締切りは24日(金).

あと、雁瀬君のACS 論文の英語化を。学会は7月締切りの ICDE などがターゲットでしょうか。

松浦君の APU もまずは一区切り評価を取って、国内の学会に出すべきでしょう。

[TSUBAME] Ganglia

各ノードのモニタリングページ
http://ganglia.g.gsic.titech.ac.jp/ganglia/

[TSUBAME] 利用ガイド

利用手引き。MVAPICH などの各種ソフトウェアのガイドなどが少し書かれているらしいです。
http://tsubame.gsic.titech.ac.jp/user-guides

Current status

最近、様々な仕事が舞い込んできており、鬼のように忙しい日々が続くのだが、急遽講演のため6月下旬に韓国。7月前半はUSに。そんな中、嬉しいニュースもいくつか。昨年やっていた某通信事業会社へのストリームコンピューティングを基盤にしたシステムの稼働が本格的に始まり、イチローがコマーシャルで宣伝している。雁瀬・上野コンビの論文が某論文誌に採択されたのも大変喜ばしい。

IISWC の方は、Miyuru君、竹野君が奮闘してくれているので、なんとか Submission まで辿りつけるだろう。Graph500 に関しては、是非 IISWC と思っていたが、他のタスクのバランスを考えると厳しい。雁瀬君、上野君の論文も英語化するべきだろうが、ICSOC 2011 も考えられるが、それも締切りが来週。もう少し学生もそろそろ主体的に英語の論文を書いていくべき時期だろうが、こればっかりは本人の努力がものを言う。頑張ってほしい。

[ExaGraph] SGRACE: Streaming Graph Clustering Algorithm

LLNL (Lawrence Livermore National Laboratory) の研究者 Andy Yoo による大規模グラフ解析に関する研究

Evaluating Use of Data Flow Systems for Large Graph Analysis, Andy Yoo
http://dsl.cs.uchicago.edu/MTAGS09/a05-yoo-slides.pdf

A New Benchmark For Evaluation Of Graph-Theoretic Algorithms, CORR2010
Parallel Generation of Massive Scale-Free Graphs, CORR2010
Scalable Analysis of Massive Graphs on a Parallel Data Flow System, HICSS2010


Google での講演: http://www.youtube.com/watch?v=PBLgUBGWcz8

[ExaGraph] Graphs and HPC: Lessons for Future Architecture

Graphs and HPC: Lessons for Future Architectures, Bruce Hendrickson (Sandia)

http://science.energy.gov/~/media/ascr/ascac/pdf/meetings/oct08/hendrickson_ascac.pdf

Cray のアーキテクチャに偏ったスライド. BlueGene/L との比較も少しあり。

グラフ解析問題の特徴
Runtime is dominated by latency
Potentially random accesses to global address space
Perhaps many at once, but parallelism is fine-grained
Essentially no computation to hide memory costs
Access pattern is data dependent
Prefetching unlikely to help
Usually only want small part of cache line –
levels of memory all Potentially abysmal locality at hierarchy

以上のグラフ解析の要件を満たすアーキテクチャ
Low latency / high bandwidth for small messages!
Latency tolerant
Light-weight synchronization mechanisms
Global address space
- Obviate the need for partitioning –
- Avoid memory-consuming profusion of ghost-nodes –
- No local/global numbering conversions –
- Support fine-grained parallelism –
- One machine with these properties is the Cray MTA-2, XMT

[Graph500] Scalable Graph Exploration on Multicore Processors

必見。これは非常に良い論文だ。TSUBAME上でも検証すべき。
Scalable Graph Exploration on Multicore Processors, David Bader と Watsonチーム
http://www.cc.gatech.edu/~bader/papers/ScalableGraphMulticore-SC10.pdf

外部記憶装置を用いたグラフ探索

External Memory Breadth-First Search with Delayed Duplicate Detection on the GPU

We accelerate breadth-first search by delegating complex operations to the graphics processing unit (GPU). The algorithm exploits external memory: if the state space becomes too large to be kept in main memory, it is maintained I/O-efficiently on disk.
As in many other approaches for external memory graph search, we apply delayed duplicate detection. The search proceeds in breadth-first layers with increasing minimum distance from the start state. For each layer stored on disk, we load chunks into the systems memory, which are forwarded to the memory on the graphics card. Here we test if outgoing transitions are enabled and generate all successors. Finally, we eliminate duplicates delayed by sorting on the GPU. Even facing the overhead of I/O access, noticeable overall speed-ups are obtained.

並列幅優先探索 - level-synchronized BFS

Graph500 のリファレンスコードに使用されている BFS の並列化アルゴリズム。以下、Cray 及び BlueGene/L のアーキテクチャに向けた改良アルゴリズムの提案。

Desigining Multhreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2, David Bader

A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L, Andy Yoo

Parallel Boost Library

http://www.boost.org/doc/libs/1_41_0/libs/graph_parallel/doc/html/breadth_first_search.html

[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 をサポート。

[StreamGraph] Incremental Graph Algorithms

インクリメンタルなグラフアルゴリズムに関する論文（一部）

Incremental Single Source Shortest Path (SSSP)

http://www.springerlink.com/content/y03426g56jl72732/

An Incremental Algorithm for a Generalization of the Shortest-Path Problem

Bounded Incremental Single Source Shortest Path

Fast Incremental Minimum-Cut Based Algorithm for Graph Clustering

Study Community Dynamics with an Incremental Graph Mining Algorithm

Parallel Incremental Graph Partitioning

On-line Hiearchical Graph Drawing

[StreamWeb] StreamWeb の論文が ICWS 2011 に採択されました

国際学会 ICWS 2011 (9th International Conference on Web Services) に出していた以下の論文が採択されました。採択率は 11%でした。

"StreamWeb: Real-Time Web Monitoring with Stream Computing" Toyotaro Suzumura and Tomoaki Oiki, ICWS 2011, Washington DC

道路ネットワークデータ

http://www.dis.uniroma1.it/~challenge9/download.shtml

[Graph] William Cook

TSPで著名な William Cook 氏のページ http://www.tsp.gatech.edu/index.html

グラフ生成モデル

Jure Leskovec らによる研究

• Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, by Jure Leskovec, Jon Kleinberg, Christos Faloutsos, ACM KDD 2005
• Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication, by Jure Leskovec, DeepayChakrabarti, Jon Kleinberg and Christos Faloutsos, PKDD 2005
• Scalable Modeling of Real Graphs using Kronecker Multiplication, by Jure Leskovec and Christos Faloutsos, ICML 2007
• Graph Evolution: Densification and Shrinking Diameters, by Jure Leskovec, Jon Kleinberg and Christos Faloutsos, ACM TKDD 2007

ICML 2009 のチュートリアル

http://videolectures.net/icml09_leskovec_msain/

演習課題 - Elastic StreamScale

石井、鈴村の「Elastic Stream Computing with Clouds」のアイデアを StreamScale 上でシームレスに実装し、性能評価を行う。

竹野君 ToDo
(1) 石井君の work 理解 --> "SACSIS 2011 論文とスライド読み”, 実験の再現
(2) Yahoo S4 理解（コードと論文）
(3) StreamScale のコード理解 (5/11 18:00 - )
(4) StreamScale の再設計と実装 (竹野、上野、鈴村で議論)
(5) 上記 Elastic Stream Computing のアイデアを StreamScale 上に実装

以上です

新メンバー演習課題 (2)- Yahoo S4 で 高速CDR 処理を実装

[演習課題]
- オープンソースの処理系 Yahoo S4 上で VWAP 及び CDR 処理を実装する。
- Yahoo S4 に関するシステム概要についてまとめる
- System S との性能比較、定性的なプログラミングモデル比較を行う。

[Yahoo S4 に関するサイト、論文]
サイト：http://s4.io/からコードをダウンロード。インストールしダウンロード。
論文：http://labs.yahoo.com/files/KDCloud%202010%20S4.pdf
必要に応じて Zookeeper や Spring フレームワークの文献を参照すること

[System S の VWAP 処理、CDR処理のコード]
- スケーラブルな VWAP アプリは松浦君に聞く (松浦君がインターンで最適化したコード)
- CDR 処理アプリ（簡易版）は Miyuru 君に渡したので聞く

[発表スライドにまとめる内容]
- Yahoo S4 に関する詳細な解説 (ソフトウェアのアーキテクチャ、プログラミングモデル、実行方法）
- Yahoo S4 と System S の比較（アーキテクチャ、プログラミングモデルなど）
- CDR と VWAP の定量的な性能比較 - スケーラビリティ、ボトルネック解析