destination

CUDA 8.0 : nvGRAPHの概要と
プログラミング
2016-1014
16:20-16:45
1F ペガサスA
επιστημη
NVIDIA CUDA Ambassador, Microsoft MVP for Visual Studio & Development Technologies
世の中はグラフで溢れている
• 鉄道網・道路網
• 通信網
• Social Network
• Web
• …etc.
2
用語
Vertex : 頂点
weight(重み)
0.3
0
destination(出口)
Edge : 辺
4
source(出口)
Edge = (source, destination)
Topology = Edge の集合
Graph = 重みつきのTopology
※ nvGRAPH では:
• Edge は重複しない
• weight > 0
3
Graph = Topology + 重み
0
0
0.3
4
0.4
4
1
0.1
0.1
1
0.2
0.2
0.2
2
3
Topology
3
0.1
2
Graph
4
nvGRAPHでなにができるの?
主要なAPIは３つ
• Single Source Shortest Path 単一始点から各点への最短路長
• Single Source Widest Path 単一始点から各点への最長路長
• Page Rank
ページランク
※ 最短/最長経路ではあ・り・ま・せ・ん
5
Graphのテーブル(表)による表現
0
0.3
0.1
0.4
4
0.1
1
0.2
0.2
0.2
3
0.1
2
 Edgeは重複してはならない
 重みは0より大きい
#
source
_indices[E]
destination weights[E]
_indices[E]
0
3
0
0.4
1
4
0
0.1
2
0
1
0.2
3
2
1
0.4
4
4
1
0.2
5
1
2
0.3
6
3
2
0.1
7
4
3
0.1
8
3
4
0.2
※ destination, source で昇順にソート
Edge数
6
GraphをSQL スキーマで書くと:
CREATE TABLE graph (
source
INTEGER,
← 入口
destination INTEGER
← 出口
weight
← 重み
REAL,
…
UNIQUE ( source, destination ),
← Edgeは重複しない
CHECK ( weight > 0.0 )
← 重み > 0.0
)
7
source, destination, weight を手に入れて…
SELECT
source, destination, weight
FROM
graph
ORDER BY
destination, source ASC
#
source
_indices[E]
destination weights[E]
_indices[E]
0
3
0
0.4
1
4
0
0.1
2
0
1
0.2
3
2
1
0.4
4
4
1
0.2
5
1
2
0.3
6
3
2
0.1
7
4
3
0.1
8
3
4
0.2
Edge数
9
destination を圧縮する
#
destination_indices[E]
#
destination_offsets[V+1]
0
0
0
0
1
0
1
2
2
1
2
5
3
1
3
7
4
1
4
8
5
2
5
9
6
2
7
3
8
4
Edge数
Vertex数+1
※ cuSPARSE : cusparseXcoo2csr で圧縮できます!
※ nvGRAPH : nvgraphConvertTopology,
nvgraphConvertGraph も用意されています!
ソートもついでにやってくれますよ♪
10
つまるところnvGRAPHに食わすdataは:
疎行列(sparse matrix)ではCSC-formatと称されます
Topology
重み
source_indices[E]
destination_offsets[V+1]
weights[E]
3
0
0.4
4
2
0.1
0
5
0.2
2
7
0.4
4
8
0.2
1
9
0.3
3
0.1
4
0.1
3
0.2
11
nvGRAPH Cheat Sheet(1)
1
nvgraphHandle_t
2
nvgraphGraphDescr_t
4
float EdgeData[E]
Topology
6
float [E]
weight列
5
float VertexData[V]
8
float[V]
3
nvgraphCSCTopolugy32I_st
int
int
int*
int*
nvertices;
V: Vertex数
nedges;
E: Edge数
destination_offsets;
source_indices;
計算結果
7
function
device領域でもOK
float[V+1]
float[E]
(圧縮された) destination列
source列
12
nvGRAPH Cheat Sheet(2)
つくる
こわす
書く
読む
nvgraphCreate [1]
nvgraphDestroy
nvgraphCreateGraphDescr [2]
nvgraphDestroyGraphDescr
nvgraphSetGraphStructure [3]
nvgraphGetGraphStructure
nvgraphAllocateEdgeData [4]
nvgraphSetEdgeData [6]
nvgraphGetEdgeData
nvgraphAllocateVertexData [5]
nvgraphSetVertexData
nvgraphGetVertexData [8]
Function [7]
nvgraphSssp
単一始点から各点への最短路長
nvgraphWidestPath 単一始点から各点への最長路長
nvgraphPagerank
ページランク
13
Demo : 「世間は(意外と)狭い」
14
Thank you!
επιστημη
BLOG:
http://blog.zaq.ne.jp/fareastprogramming/
FACEBOOK: https://www.facebook.com/cppepisteme
TWITTER: @epitwit

Download Report