依存関係の局所性を利用した

依存関係の局所性を利用した
プログラム依存グラフの
効率的な構築法
大畑文明
西松顯
井上克郎
大阪大学大学院基礎工学研究科
発表内容






プログラムスライス
既存の手法の問題点
提案する手法
評価実験
まとめ
今後の課題
99/03/18
第122回ソフトウェア工学研究会
2
研究の背景

ソフトウェアの大規模化・複雑化に伴い、ソフト
ウェア開発コストの50～80%をテスト工程に費や
すという報告がある(Robson, D.J et al., “Approaches to Program
Comprehension”, J.System Software, Vol.14, No.1, 1991.)

テスト工程の中で最も時間のかかる作業が
フォールト位置特定である

フォールト位置の特定を効率よく行う手法として、
プログラムスライスが提案されている
99/03/18
第122回ソフトウェア工学研究会
3
プログラムスライス

プログラム中のある文sのある変数v (スライス基
準)の値に影響を与えうる文の集合
1: b = 5;
2: a = b + b;
スライス基準(5, b)
3: if(a > 0) { のスライス
4: c = a:
5: d = b;
}

1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a:
5: d = b;
}
スライスの他の用途
– プログラム再利用・プログラム理解
99/03/18
第122回ソフトウェア工学研究会
4
スライスの計算過程
スライス計算問題
99/03/18
グラフ到達問題
第122回ソフトウェア工学研究会
5
Phase 1: 定義・参照変数抽出

各文の定義・参照変数を抽出
1: b = 5;
2: a = b + b;
文定義参照
3: if(a > 0) {
1 b
2 a
b 4: c = a:
3
a
5: d = b;
4 c
a
}
5 d
b
99/03/18
第122回ソフトウェア工学研究会
6
Phase 2-1: (データ)依存関係解析

文間に存在するデータ依存関係を抽出
– ある変数wが存在して、文sにおける変数wの定義
が、変数wを参照している文tに到達
– データ依存関係DD(s, w, t)が存在
– DD(1, b, 2), DD(2, a, 3)
– DD(1, b, 5), DD(2, a, 4)
99/03/18
第122回ソフトウェア工学研究会
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a:
5: d = b;
}
7
Phase 2-2: (制御)依存関係解析

文間に存在する制御依存関係を抽出
– 文sが分岐(繰り返し)命令であり、その分岐(繰り
返し)節が文tを直接含む
– 制御依存関係CD(s, t)が存在
– CD(3, 4), CD(3, 5)
99/03/18
第122回ソフトウェア工学研究会
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a:
5: d = b;
}
8
Phase 3: プログラム依存グラフ構築

プログラムに存在する文・依存関係を有向グラフ
で表現した(節点  文, 辺  依存関係)、プロ
グラム依存グラフ(PDG)を作成
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a:
5: d = b;
}
99/03/18
第122回ソフトウェア工学研究会
9
Phase 4: スライス抽出

スライス基準に対応した節点からPDG辺を逆に
たどる
– 到達可能節点  スライス基準に対するスライス
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a:
5: d = b;
}
99/03/18
1: b = 5;
2: a = b + b;
3: if(a > 0) {
4: c = a;
5: d = b;
}
第122回ソフトウェア工学研究会
10
既存の手法の問題点

「よりきめ細かい依存関係解析を行い、スライス
の大きさを小さくする」ことを目標としてきた
– ポインタ解析、構造体・配列の要素を区別
– 関数間の依存解析

大規模プログラムに対する同様の要求は困難
– 28,000行のプログラムに対し、620MBのメモリ空間・2
時間の解析時間(The Wisconsin Program-Slicing Tool 1.0,
Reference Manual. Computer Science Department, University of WinconsionMadison, August 1997.)
99/03/18
第122回ソフトウェア工学研究会
11
既存の手法の問題点続き

コスト軽減のため多くの依存関係解析アルゴリ
ズムが提案され、スライスの正確性(スライスの大
きさ)とのトレード・オフが考えられてきた(Atkison, D. C.
and Griswold, W. G. “The Design of Whole-Program Analysis Tools”. In
Proceedings of the 18th International Conference on Software Engineering, Berlin,
Germany, pages 16--27, 1996.)

異なる依存関係解析アルゴリズムで構築された
PDGは相互利用が困難
99/03/18
第122回ソフトウェア工学研究会
12
提案する手法

依存関係解析アルゴリズム(Phase 2:)と独立した、
コスト削減

従来PDG節点と文は1対1対応であったものを、
1節点で複数文を処理(節点集約)
– 情報共有による、情報量(空間コスト)削減
– 計算対象の削減による、計算量(時間コスト)削減
99/03/18
第122回ソフトウェア工学研究会
13
節点集約

位置付け
– 「Phase 2: 依存関係解析」と独立
– 依存関係解析前に集約を実行(Phase 1.5: 集約)

対象
– 集約の時間コストを最小限に抑える
– 制限された依存関係情報
– PDG構築後の、正確性の変更コストを抑える
– 文・プログラム構造のまとまりに限定
第122回ソフトウェア工学研究会
99/03/18
14
集約の問題

単純に連続した文を集約する
と、スライスが著しく不正確にな
る可能性がある
(7)
99/03/18
(9)
第122回ソフトウェア工学研究会
1:
2:
3:
4:
5:
6:
7:
8:
a = 1;
b = 1;
c = 1;
d = 1;
if(a > 0) {
e = b;
f = c * d;
g = f + c + d + a;
}
9: h = g;
10: i = e;
15
集約の方針

同じ文に依存する(依存関係の 1:
局所性を有する)文の集約では、2:
正確性の低下を抑えることがで 3:
4:
きる
a = 1;
b = 1;
c = 1;
d = 1;
5: if(a > 0) {
6: e = b;
7: f = c * d;
8: g = f + c + d + a;
}
9: h = g;
10: i = e;
(7)
99/03/18
(7)
第122回ソフトウェア工学研究会
16
依存関係の局所性

隣接する2文に関して、それらが依存している文
が一致していること

依存関係の局所性を把握するため、局所デー
タ依存関係LD(s, w, t)を定義
99/03/18
第122回ソフトウェア工学研究会
17
局所データ依存関係

直接のデータ依存関係に加え、間接的なデータ
依存関係を含んでいる

集約対象文s1・s2の全参照変数集合Aに対し、
"a$t[aA LD(t, a, s )&LD(t, a, s )]を満たす場
1
2
合、集約を行う
99/03/18
第122回ソフトウェア工学研究会
18
依存関係の局所性(例1)

(直接の)参照変数の一致
1: a = 1;
2: b = 1;
3: c = a + b;
4: d = a + b;
99/03/18
第122回ソフトウェア工学研究会
19
依存関係の局所性(例2)

(DD+DD間接を含む)参照変数の一致
1: a = 1;
2: b = 1;
3: c = a + b;
4: d = c;
99/03/18
第122回ソフトウェア工学研究会
20
依存関係の局所性(例3)

(DD+CD間接を含む)参照変数の一致
1: a = 1;
2: b = 1;
3: if(a > 0) {
4: c = b;
5: d = a + b;
}
99/03/18
第122回ソフトウェア工学研究会
21
集約の判定(例)

文7・文8の集約
1:
2:
3:
4:
5:
6:
7:
8:
a = 1;
b = 1;
c = 1;
d = 1;
if(a > 0) {
e = b;
f = c * d;
g = f + c + d + a;
}
9: h = g;
10: i = e;
99/03/18
第122回ソフトウェア工学研究会
22
集約アルゴリズム



判定に必要な局所データ依存関係LDは、
「Phase 1: 定義・参照変数抽出」で取得可能
DD集合  LD集合であるため、集約によりスライ
スに含まれるべき文が含まれなくなることはない
プログラム構造ごとの判定および集約
99/03/18
第122回ソフトウェア工学研究会
23
集約アルゴリズム続き

依存している文が一致する場合のみの集約は
厳密であるため、集約許容値limit(0)を定義
– limitを大きくすることで集約条件が緩和
– limit = 0のとき集約可能
– limit = 1のとき集約可能
99/03/18
第122回ソフトウェア工学研究会
24
評価実験

我々が試作したスライスツールへの機能追加
– サブセットPascalを対象(レコード型・ポインタなし)


テストプログラム
テスト項目
P1
P2
P3
P4
行手続き
内容
249
14 pの計算
449
30 小プログラムの集合
429
18 酒屋問題
434
18 酒屋問題
– 空間コスト(PDGの節点・辺数)
– 時間コスト(解析時間)
– 正確性(スライスサイズ)
99/03/18
第122回ソフトウェア工学研究会
25
実験結果(空間コスト) その1

PDG節点数[個]
集約
集約あり
なし limit:0 limit:1 limit:2
P1 128
104
96
86
(-18.8%) (-25.0%) (-32.8%)
P2
243
199
187
177
(-18.1%) (-23.0%) (-27.2%)
P3
211
166
153
136
(-21.3%) (-27.5%) (-35.5%)
P4
226
157
141
124
(-30.5%) (-37.6%) (-45.1%)
99/03/18
第122回ソフトウェア工学研究会
26
実験結果(空間コスト) その２

PDG辺数[本]
集約
集約あり
なし limit:0 limit:1 limit:2
P1 525
443
433
394
(-15.6%) (-21.2%) (-25.0%)
P2 1092
980
951
912
(-10.3%) (-12.9%) (-16.5%)
P3 1487
1387
1336
1290
(-6.7%) (-10.2%) (-13.2%)
P4 1823
1662
1590
1525
(-8.8%) (-12.8%) (-16.3%)
99/03/18
第122回ソフトウェア工学研究会
27
実験結果(時間コスト)

解析時間[ms]
–
–
–
–
Phase 1:
(Phase 1.5:)
Phase 2:
Phase 3:
集約
集約あり
なし limit:0 limit:1 limit:2
P1
50
40
30
30
(-20.0%) (-40.0%) (-40.0%)
P2
180
150
130
130
(-16.7%) (-27.8%) (-27.8%)
P3
200
180
170
170
(-10.0%) (-15.0%) (-15.0%)
P4
320
260
240
230
(-18.8%) (-25.0%) (-28.0%)
PentiumII-300MHz-128MB(Linux)
99/03/18
第122回ソフトウェア工学研究会
28
実験結果(スライスサイズ)

平均スライスサイズ[文]
P2
集約
なし
69.00
集約あり
limit:0 limit:1 limit:2
70.67 70.67 77.22
(+2.42%)
(+2.42%)
(+12.64%)
P3 143.22 145.00 147.44 148.28
(+1.24%)
(+2.95%)
(+3.53%)
P4 168.67 170.83 170.83 170.83
(+1.28%)
99/03/18
第122回ソフトウェア工学研究会
(+1.28%)
(+1.28%)
29
考察


約500行のプログラムに対し、PDGの空間コス
ト:6.7～45.1%・時間コスト:10.0～40.0%の削減
を行うことができた
より大きなプログラムに対して集約によるスライス
正確性低下が抑えられる傾向がある
99/03/18
第122回ソフトウェア工学研究会
30
まとめ


プログラムスライスの紹介を行った
節点集約によるPDG構築コストの削減手法を
提案し、その有効性を実験により評価した
99/03/18
第122回ソフトウェア工学研究会
31
今後の課題




ポインタ変数を持つ言語への本アルゴリズムの適
応
PDG構築後の節点分解
大規模プログラムに対する有効性の評価
プログラム理解に対する有効性の評価
99/03/18
第122回ソフトウェア工学研究会
32

Download Report