新アルゴリズム1

分岐の相関関係を用いた
効率的なパスプロファイリングに
関する研究
深沢研究室
野崎晋也
概要
• 既存のパスプロファイリングでは調べる
パスの総本数が多かった為、
一度エッジプロファイリングを行ってから
調べる本数を減らす事を目的とする
• 参考：既存研究のTargeted Path Profiling
Targeted Path Profilingの特徴（1）
A
AI
AIJ
CE ABCEHJ
DE ABDEHJ
FH ABDFHJ
FG ABDFGHJ
B
赤い辺を
通ると
必ず
パスが
決まる
C
D
F
E
I
G
H
J
Defining Obvious
edge
path
Obvious pathの実行頻度=
Defining edgeの実行頻度
Targeted Path Profilingの特徴（2）
A
120
150
100
B
Path
C
20
250
D
160
E
110
160
F
Prof1 Prof2
ACDF
90 110
ACDEF
60
40
ABCDF
0
0
ABCDEF 100 100
ABDF
20
0
ABDEF
0
20
実行頻度の低い辺の除去
Cold Path Elimination
今回着目した問題点：
0であるはずのものが消えない
EdgeをBasic Blockに
開始
A
AB:120
120
AC:150
150
100
BC:100
B
C
20
250
BD:20
CD:250
D
DE:160
160
E
DF:110
110
160
EF:160
F
これだけでは意味がない
Path
Prof1
ACDF
90
ACDEF
60
ABCDF
0
ABCDEF 100
ABDF
20
ABDEF
0
終了
Edge Profilingの結果
開始
AB:120
INもOUTも2つ以上の
部分に注目
AC:150
100
150
BC:100
20
100
BD:20
0
CD:250
20
160 90
DE:160
DF:110
160
90
EF:160
160
Path
Prof1
ACDF
90
ACDEF
60
ABCDF
0
ABCDEF 100
ABDF
20
ABDEF
0
終了
ノードに何らかの処理
開始
AB:120
AC:150
100
150
BC:100
20
100
BD:20
0
20
ここの２＊２を
4本ばらばらに
160 90
DE:160
DF:110
160
90
Path
Prof1
ACDF
90
ACDEF
60
ABCDF
0
ABCDEF 100
ABDF
20
ABDEF
0
EF:160
160
終了
結果
開始
AB:120
AC:150
100
20
BC:100
90
100
BD:20
60
0
20
DE:160
0
DF:110
これなら
Path Pathの
Prof1
Obvious
ACDF
90
概念が使える
ACDEF
60
ABCDF
0
その中で０のものを
ABCDEF 100
消してしまえば
ABDF
20
ABDEF
0
Cold Path Elimination
これで0だった
ABCDFを除去出来た
終了
現在検討中の部分
開始
A
60
AB:60
150
B
60
C
BD:60
CD:120
CE:30
120 30
D
E
40 140 30
F
40
AC:150
• グラフを見ると、INもOUTも2つ以上
あるのは、DとGのノード
G
90 80
H
I
130
80
J
• しかしながら、BDFを通るパスは
DF:40
DG:140
EG:30
1つしかない事がわかる
※CDF.EGH,EGIも同様
FH:40
GH:90
GI:80
• この図の辺をノードとして
IJ:80
HJ:130
グラフを再構築
終了
現段階でのDefining
Edge
開始
A
60
AB:60
150
B
60
AC:150
C
BD:60
CD:120
CE:30
120 30
D
E
DF:40
DG:140
EG:30
40 140 30
F
40
G
FH:40
90 80
H
GH:90
GI:80
I
130
80
HJ:130
IJ:80
J
やはり注目すべきは
IN/OUTが2箇所以上のところ
終了
分岐の場合分け
開始
左から入り左へ出るものを1
左から入り右へ出るものを2
AB:60
右から入り左へ出るものを3
AC:150
右から入り右へ出るものを4
BD:60
CD:120
CE:30
とすると
ABDFHJ
DF:40
EG:30
ABD1GHJ
ABD2GIJ
FH:40
GH:90
GI:80
ACDFHJ
ACD3GHJ
HJ:130
IJ:80
ACD4GIJ
ACEGHJ
終了
ACEGIJ

Download Report