指導 : 深澤良彰教授

(1)

プログラムの実行挙動変化を考慮した部分的パスプロファイリングに関する研究

2005 年 2 月 2 日（水曜日）提出

指導 : 深澤良彰教授

早稲田大学理工学部情報学科学籍番号 : 1G01P073-0

永松高明

(2)

1 はじめに 1

2 本研究の背景 3

2.1 動的コンパイラ . . . . 3

2.1.1 JAVAにおける動的コンパイル利用の例 . . . . 3

2.2 動的最適化 . . . . 4

2.2.1 実行頻度の情報 . . . . 5

2.3 プロファイリング . . . . 5

2.3.1 制御フロープロファイリング . . . . 5

2.3.2 ノードプロファイリング . . . . 6

2.3.3 エッジプロファイリング . . . . 6

2.3.4 パスプロファイリング . . . . 7

2.3.5 低コストな二段階パスプロファイリング . . . . 8

2.3.6 従来手法の利点と欠点 . . . . 10

3 解決すべき課題 11 4 本手法で用いる方法 13 4.1 概要 . . . . 13

4.2 本手法の詳細 . . . . 14

4.2.1 エッジプロファイリングの適用と低実行頻度エッジの除去 . 14 4.2.2 再構築CFGに対するパスプロファイリング . . . . 15

4.2.3 プログラム実行挙動変化の判断 . . . . 17

4.2.4 プログラム実行挙動変化時のCFGの変形 . . . . 18

4.2.5 除去Edge及びNodeの追加 . . . . 18

4.2.6 追加Edge及びNodeの削除 . . . . 22

4.2.7 レジスタ増分操作の最適化 . . . . 25

4.2.8 パスの再生成方法 . . . . 26

4.3 本手法の利点 . . . . 27

4.4 本手法の問題点 . . . . 28

5 実験 29 5.1 実験方法 . . . . 29

5.2 プロファイリングの精度の比較 . . . . 29

(3)

6 おわりに 34

7 謝辞 35

(4)

1 はじめに

Java言語の普及を背景に、近年動的コンパイラについての研究が多く行われて

いる[1][2]。動的コンパイラはプログラム実行中にプログラムのコンパイルを行う

ので、プログラム実行時間にコンパイル時間が含まれてしまうという問題点を持つが、プログラムの実行挙動の情報を利用することにより、静的コンパイラよりも高速な実行コードを生成することができる。

この動的コンパイラは、プログラム実行時の実行挙動を収集（プロファイリング）し、その情報を利用してコンパイル時の最適化を行う。そのため最適化に必要十分なプログラムの実行挙動を低コストで収集することが必要不可欠となる。

一般に精度の高いプログラムのプロファイルはコストが高くなり、逆にコストの低いプロファイリングは精度が低くなる。コストと精度とはトレードオフの関係にあり、課題は、いかして低コストで最適化に必要十分なプロファイリングを行うかという点である。

プロファイリングの手法として、ノードプロファイリング（vertex profiling）[3]、

エッジプロファイリング（edge profiling）[4]、パスプロファイリング（path profiling）

[5]など様々なプロファイリング手法が提案されている。最近では、従来十分とされていたエッジプロファイルではなく、パスプロファイリングによる、より詳細なプロファイリングが必要とされている。実行頻度の高い実行パスの分離処理のような高度な最適化のためには、より正確な実行経路の情報が必要となるためである。しかし、このパスプロファイリングは一般的にオーバーヘッドが大きいという問題がある。

この問題に取り組んだ手法として、BallのEfficient Path Profiling [5]がある。この手法では、コントロールフローグラフ(Control Flow Graph:以降 CFG)中の基本ブロックを走査し、適当なエッジにレジスタ増分操作を設置することによってパスプロファイリングの収集コストを大きく減らした。また、この手法の改良版として、最初にエッジプロファイリングを行い。実行頻度の少なかったエッジをCFG から除去することによって、パスプロファイリングの収集コストをさらに削減する手法として2段階パスプロファイリング[6]が提案されている。

Ballの手法[5]では、正確に実行パスを収集することができるが、すべてのパスについて収集するため、増分操作とカウンタによるパスの収集コストが高いこと、

また、プロファイリングに多くのバッファが必要であるという問題点がある。

一方、2段階パスプロファイリングでは、最初に実行頻度の少ないエッジを除去するので、パスプロファイリングにかかる収集コスト、およびバッファは飛躍的に削減させることが可能だが、一度除去したエッジを通るパスの実行頻度を計測して

(5)

いないため、プログラムを実行させている途中でプログラムの実行挙動が変化し、

除去エッジを通るパスの実行頻度が増加した場合に正確に高頻度実行パス(ホットパス)を発見することができない。

そこで、本稿では2段階パスプロファイリングにおいて、プログラムの実行挙動が変化した場合においても、その変化に対応し、継続的にホットパスを検出することが可能なプロファイリング手法を提案する。

本手法では、従来手法の2段階パスプロファイリングと同様、最初にエッジプロファイリングを行い、実行頻度の低いエッジを除去した後、BallのEfficient Path

Profilingを行うが、エッジを除去する際に、そのエッジにカウンタを設置し、除去

エッジの実行頻度を計測する。そして除去エッジの実行頻度の高低に応じて、適宜CFGへエッジの追加および削除を行い、継続的にCFGを再構築することによって、一度除去したエッジ（及びノード）を含むパスについても、レジスタの増分操作による計算だけで、継続して低コストに精度の高いパスプロファイリングを行うことを可能にした。

本手法の特徴は次のようになる。

• パスプロファイリングに用いるCFGのエッジ及びノードの追加および削除を適宜行い、ユーザーからの入力等によりプログラムの実行挙動が変化した際にも高い精度でホットパスを検出することができる点。

また、従来の手法[6]どおり、以下の利点をもつ

• エッジプロファイリングなどのプロファイリングと比較すると、精度の高いプロファイリングを行うことができる点。

• エッジプロファイリングを最初に行い、実行頻度の低いエッジを除去することにより、パスプロファイリングを行う際のオーバーヘッドを低減することが可能な点。

以下の構成は次の通りである。

まず、第2章で本研究の背景について紹介する。第3章では解決すべき課題について言及し、第4章で本手法の説明、第5章で本手法の実験、考察を行い、最後に第6章でまとめを述べる。

(6)

2 本研究の背景

本章では、本研究の背景について述べる。2.1節では、動的コンパイラの説明を行い、2.2節では動的最適化について、2.3節ではプロファイリングの説明、従来手法の例を挙げ、それぞれの利点と欠点について説明する。

2.1 動的コンパイラ

動的コンパイラは、JIT（Just In Time）コンパイラとも言われ、プログラム実行時に実行コードにコンパイルし実行する。

プログラム実行中にプログラムのコンパイルを行うので、プログラム実行時間にコンパイル時間が含まれてしまうという問題点を持つが、プログラムの実行挙動の情報を利用することにより、静的コンパイラよりも高速な実行コードを生成することができる。

近年では、JAVAプログラムなどの実行速度向上のために使用されている。

2.1.1 JAVAにおける動的コンパイル利用の例

Javaで書かれたプログラムは、JavaコンパイラでJava VM上で実行されるバイトコードと呼ばれる中間言語にコンパイルされるため、プロセッサやOSに依存せず、Javaの実行環境さえあればどのような計算機上においても実行できるという長所がある。しかし、一方でJava VMは、バイトコードインタプリンタでバイトコードを実行するため実行速度が非常に遅いという問題がある。

最初は非常に遅かったJava VMだが、その後、高速化のため動的コンパイルを導入した。現在では、Sun Microsystems社のHotSpot VMをはじめ、多くのJava VMがバイトコードインタプリタと動的コンパイラを併用している。

図1は、動的コンパイルを利用したJava VMの処理の流れの例を示した図である。多く実行されると判断したメソッドはネイティブコード（マシン実行コード）

にコンパイルされメモリに格納される。次回以降そのメソッドが呼び出された際にはインタプリンタではなく、直接ネイティブコードを実行することで実行速度の高速化を図っている。

(7)

[ Y @ P H ? N = V R 5 U S ] Z = V R ; : 6

@PH?LAODF9 G?E>I@4F<@PH?N

XW78G?E>I@4F

=Q\ ?PC4JMPC9US

T=KBDF

G?E>I@4F=US G?E>I@4F=_^

203, -+.1,

203,

203, /0 -+.1,

図 1: 動的コンパイルを利用したJava VMの処理の流れの例

2.2 動的最適化

動的最適化とは、プログラムの実行挙動情報を利用して行う最適化のことである。動的コンパイラは動的最適化を行うことにより、静的コンパイラよりも高速な実行コードを生成することができる。

動的コンパイラでは、実際にプログラムを実行させて、実行情報を収集することによりプログラム中の頻繁に実行される部分を特定することができる。その情報を利用して行う最適化が動的最適化である。高実行頻度の部分やパスに対して、

基本ブロックの並び替えや高実行頻度パスの分離処理等、高速化を図る工夫をすることで、より高速な実行コードを生成することができる。

一方、静的コンパイラでもレジスタの有効活用やコードの冗長性の除去などを行い、何も行わない場合より高速な実行コードを生成することが可能であるが、全体的に万遍なく高速化を試みるほかなく、動的最適化と比較すると大きな効果は期待できない。

(8)

2.2.1 実行頻度の情報

実行頻度の情報を収集することによって、プログラム中の頻繁に実行される部

分(ホットスポット)や経路(ホットパス)を特定することができる。プログラム実

行時間の大半がホットスポットやホットパスである場合、その部分を重点的に最適化することが効果的である。例えば、ほかの大部分が大幅に低速化しても、ホットスポットが少し高速化されれば、プログラム全体としてのパフォーマンスは向上する可能性がある。

2.3 プロファイリング

プロファイリングとは、プログラム内の関数や区間ごとにその実行回数や時間などを計測し、実行時の情報を取得することをいう。これによって、プログラム内のどの関数が多く呼ばれ、どの区間にかかる時間が多いかといったプログラムの実行挙動を得ることができる。プログラム中で多く実行され多くの時間を要している箇所を中心に最適化を施すことによって、プログラム全体を満遍なく最適化した場合よりも、プログラム全体の実行時間は短い、より高速な実行コードを生成することができると期待できる。なお、本稿では命令がどのような順番で何回実行されたかという情報に着目する。

2.3.1 制御フロープロファイリング

制御フロープロファイリングは、どのような順番で命令が実行されたかというプログラムの流れの情報を収集するプロファイリングである。制御フロープロファイリングでは、コントロールフローグラフ(CFG)を用いてプロファイリングを行う。このCFGとは、基本ブロックを論理的構成に基づき有向グラフ化したものである。CFGを構成するノードは基本ブロック、エッジは基本ブロック間の遷移である。

基本ブロックは、命令文シーケンスである。順番どおりに並んだ命令の集合で、

最後は分岐かあるいはJUMP命令である。つまり基本ブロックはプログラムを分岐あるいはJUMP命令で区切った命令の集合ということができる。

この制御フローグラフを用いた制御フロープロファイリングには以下の3種類の方法がある。

• ノードプロファイリング

(9)

• エッジプロファイリング

• パスプロファイリング

次節より、それぞれのプロファイリングについて説明する。

2.3.2 ノードプロファイリング

ノードプロファイリングとは、基本ブロックの実行回数を計測することにより、

プログラム中のどの部分が多く実行されているのかを計測する。これにより主に分岐の偏りの情報を取得することを目的としている。分岐の偏りの情報を得ることで、例えば高頻度の分岐の方を近くに配置することでキャッシュヒット率を高めるといった最適化を行うことができる。このノードプロファイリングは、実装が容易であり低コストにプロファイルを行うことができる。しかし、ノードプロファイリングでは分岐の偏りを正しく得ることができるとは限らない。例えば、図2のような場合、A →CとA →Dのどちらの実行回数が多いのかをノードプロファイリングで得た各ノードの実行回数の情報だけで正確に得ることはできない。

/ 0 1 2

+* .*

,* -*

図 2: ノードプロファイリングで分岐の偏りを正しく得ることができない例

2.3.3 エッジプロファイリング

エッジプロファイリングは基本ブロック間のエッジの通過回数を計測する。エッジの通過頻度を計測するため、ノードプロファイリングで取得することができない分岐の偏りの情報を正しく収集することができる。ノードプロファイルよりオーバーヘッドは大きくなるが、比較的容易に実装することができ、一般的に用いられることが多い。分岐ごとに実行頻度の高いエッジを選択していくことによって、

(10)

エッジプロファイリングの結果から、ホットパスを導くことを目的とした手法[7]

を用いることによって、ホットパスを予測することはできるが、正確なホットパスを必ずしも発見することはできない。

図3 は、エッジプロファイルが最頻の実行パスを取得することができない例である。図3 右側の表は2つの異なるパスプロファイリングの結果である。どちらのパスプロファイリングの場合でも、左側のCFGに示されているようようなエッジプロファイリングの結果に帰結する。Prof1のパスプロファイリングにおいては

ABCDEF が最頻である。しかし、エッジプロファイリングによるホットパスの

発見手法[7]では、ACDEF を最頻としてしまう。

2 3 4

5 6 7

+.*

+,*

+**

,.*

,*

+/* ++*

+/*

,0*

89>; 8=<:+ 8=<:, 2457 24567

23457 234567 23567 2357

1* /*

* +**

,* *

++* -*

* +**

* ,*

図 3: エッジプロファイリングで最頻実行パスを取得することができない例

2.3.4 パスプロファイリング

パスプロファイリングはCFG中に存在する各パス(経路)の実行回数を計測する。パスプロファイリングを行うことにより、どのパスの実行頻度が高いかという情報を取得することができる。これにより実行頻度の高いパスの分離処理[8]などの最適化が可能となる。パスプロファイリングの情報量が、ノードプロファイリングやエッジプロファイリングよりも多いことは、パスプロファイリングの情報からノードプロファイリングやエッジプロファイリングの情報を導き出すことはできるが、その逆はできないことから明らかであろう。

(11)

このパスプロファイリングの問題点は、オーバーヘッドが高い点である。特に大きなプログラムでは潜在するパス数は膨大になり、それに伴ってパスプロファイリングのオーバーヘッドも膨大になってしまう。

図4は、Ballの手法(Efficient Path Profiling[5])を施したCFGである。この手法はCFG中の基本ブロックを走査し、適当なエッジにレジスタの増分操作を設置することによって、パスプロファイリングの収集コストを減らしている。図中の小さな四角付きの矢印は、レジスタrを更新する操作を含む。これらのエッジを通過する際に、図に示すようなレジスタrの更新作業を行うことによって、ループの最後の基本ブロック(図中のF)に達した時のrの値から、通過パスを得ることができるように工夫している。この手法を用いることでパスプロファイリングの収集コストは削減される。しかし、すべてのパスを計測するため潜在するパス数が多い場合、この手法のオーバーヘッドは増大してしまう。

3 4 5

6 7 8

D 2 ,

9<E@ 7B=C>AB?

3568 35678 34568 345678 3468 34678

, - . / 0 1

D 2 . D 2 0

D +2 -

5CFBE:D;++

図 4: Efficient Path Profiling[4]の例

2.3.5 低コストな二段階パスプロファイリング

プログラムが大きくなると潜在するパスの総数は莫大になり、オーバーヘッドが増大してしまうというパスプロファイリングの欠点を補うために提案されたのが2段階パスプロファイリング手法[6]である。通過頻度の低いエッジを含むパスは実行頻度が低いはずであるという考えの下、まず最初にエッジプロファイリングを行い通過頻度の低いエッジを除去し、CFGの再構築を行う。その後で、再構

(12)

築したCFGに対してパスプロファイリングを行うことによってパスプロファイリングのオーバーヘッドを抑えることを可能にした手法である。

図6は、Efficient Path Profilingと2段階パスプロファイリングのパスプロファイリングの結果の比較を示している。図6(a)がEfficient Path ProfilingのCFG、

図6(b)が2段階パスプロファイリングのCFGである。２段階パスプロファイリングのCFGは、図6(b)の示すとおり、低実行頻度エッジのD→F とF →Gを除去している。CFGを簡略化しプロファイリングを行うことにより、上側のEfficient Path Profilingよりも低コストにパスの収集を行っているのである。また、図6(c) の表は、両手法のパス収集結果Prof1,Prof2を示しているが、この結果を見るとより2段階パスプロファイリング手法の結果Prof2がホットパスを正しく検出していることがわかる。

6 7 8

9 : ;

F 5 -

=@GC

^:DA.

689;<

689:<

6789;<

6789:<

679;<

679:<

- . / 0 1 2

F 5 / F 5 1

F +5 .

8EHDG>F?++

<

6 7 8

9 :

F 5 -

F 5 . F 5 /

8EHDG>F?++

<

:DA/

- . /

=FEB. =FEB/

/ .4 0 /3 -

/- 0- 2- 2-

JPK L `^ NO[U NZYSVWVXT JOK MSSVQVRX[ NO[U NZYSVWVXT

, , ,

JQK NZYSVWVXT \_]

図 5: Efficient Path Profiling[4]と手法[6]の比較

しかし、２段階パスプロファイリングでは除去エッジを含むパスの計測をまったく行っていないため、プログラムの実行中に実行挙動が変化した場合、正しくパスを計測することがでないという問題点がある。例えば、図6においてD →F と F →Gを含むパスACDF Gの実行頻度が増えた場合、2段階パスプロファイリン

グではACDF GをACDEGとして計測してしまい、その結果、ホットパスを検出

することができなくなってしまう。

(13)

2.3.6 従来手法の利点と欠点

以上のように、従来手法のノードプロファイリング、エッジプロファイリングでは、必ずしもホットパスを発見することができないといった問題がある。一方、従来手法のEfficient Path Profilingは、継続して正確にパスを計測しホットパスを発見することができるが特に大きなプログラムに対してコストがかかりすぎるという問題点がある。これはノードとエッジの数はプログラムに対し線形であるのに対して、パスの数はループを含めると果てしなく巨大な数になることに起因する。

また、非環式なパスに限定した場合でもその数は膨大である。

また、エッジプロファイリングを行った後にCFGの再構築を行い、パスプロファイリングを行うことで、低コストにパスプロファイリングを行うことを可能とした 2段階パスプロファイリング手法[6]では、オーバーヘッドを抑えてパスプロファイリングを行うことができるが、プログラム実行挙動が変化した場合、正確にパスホットパスを発見することができないという問題がある。

表 1: 各Profiling手法の性能の比較

Profiling コスト精度実行挙動変化への対応

Vertex Profiling ° × ×

Edge Profiling 4 4 4

Efficient Path Profiling[5] × ° °

2段階Path Profiling[6] 4 ° ×

(14)

3 解決すべき課題

動的コンパイラにおけるパスプロファイリング手法で満たすべき要件は、少ないコストで必要十分な精度のプロファイルを継続的に収集することである。最適化による高速化を上回るようなオーバーヘッドは許されず、また、精度の低いプロファイルでは効果的な最適化を行うことができない。

従来手法のエッジプロファイリング、ノードプロファイリングでは、ホットパスの検出には不十分であり、また、すべてのパスについて計測を行うBallのEfficient

Path Profilingでは、プログラムが大きい場合、パス数の増加に伴いコストが莫大

になってしまうため許容されるオーバーヘッドを超えてしまう。ホットパスを検出するためにすべてのパスを調べる必要はない。

より低コストな2段階パスプロファイリング手法では、エッジ除去の閾値を低く設定した場合、多くのエッジが除去されるためパス収集コストは低くなるが、実行挙動が変化した場合に正しいホットパスを発見することができなくなってしまう。また、閾値を高く設定した場合には、Efficient Path Profilingと同様の理由で収集コストが高くなってしまう。

図6は、図6のCFGについてのプログラム実行挙動が変化した際の2段階パスプロファイリングを用いたプロファイリング結果である。図6(b)の実行Pathを見て分かるように、この例におけるホットパスはP ath2及びP ath5である。しかし、２段階パスプロファイリングでは、プロファイリング結果Profの示す通り本来ホットパスとして検出されるべきP ath5を全く検出することができず、実行回

数の低いABDEGをホットパスとして検出してしまう。

(15)

7 8 9

:

; <

G 6 -

>AHD . 79:<=

/ 79:;=

0 789:<=

1 789:;=

2 78:<=

3 78:;=

G 6 . G 6 /

9FIEH?G@++

=

;EB

- . /

KJ >AHD >GFC

2 /5 4 - 2-

00 4 .- 3-

MTNO hb ST^X S]\VYZY[W _ PQR

, , ,

MUN gfcij`e_ S]\VYZY[W _da

図 6: 手法[6]で正確にプロファイリングが行えない例の図

(16)

4 本手法で用いる方法

本章では、前章の問題を解決する新しいパスプロファイリング手法を提案する。

最初に本手法の概要を述べ、続く節で本手法の詳細について説明する。

4.1 概要

本手法は、非環式有効グラフ(Directed Acyclic Graph：以降 DAG)において、2 段階パスプロファイリング同様、実行頻度の低いエッジを含むパスは実行頻度が低いという考えの下、最初にエッジプロファイリングを行い、低実行頻度エッジを除去した後に再構築したCFGに対しパスプロファイリングを行うことで、パスプロファイリングのオーバーヘッドを抑える。

また、2段階パスプロファイリングではプログラムの実行挙動変化時に正確なホットパスを検出できないといった問題(図6)があったが、本手法では除去エッジの実行頻度を逐一計測し、実行挙動変化が認められた際に適宜除去エッジ及びノー

ドをCFGに追加(あるいは削除)することで、ホットパスを含む最小の範囲に対し

て継続的にパスプロファイリングを行ことによって、ユーザーの入力などによってプログラムの実行挙動が変化した際においても正確にホットパスを検出することができる。本手法を導入したプロファイリングの流れは次の通りである。

1. エッジプロファイリングを行う

2. 通過頻度の低いエッジを除去し、除去エッジにカウンタを設置し、CFGを再構築する

3. Efficient Path Profilingに基づいて、CFGに適当なエッジにレジスタの増分操作を設置する

4. パスプロファイリングを行う

5. 除去エッジのカウンタから、プログラムの実行挙動の変化が認められた場合、

エッジの追加および削除を行いCFGを再構築する 6. ４.に戻る。

1.で行うエッジプロファイリングは、各エッジにカウンタを設置することで実現する。また、3.及び4.のパスプロファイリングはEfficient Path Profilingのアルゴリズムに従う。このアルゴリズムを用いることで各パスにユニークな値を割り当て、

効率的にパス情報を収集することが可能となる。

(17)

4.2 本手法の詳細

本節では、本手法の詳細について述べる。

4.2.1 エッジプロファイリングの適用と低実行頻度エッジの除去

最初のステップは、エッジプロファイリングを行って低実行頻度エッジをCFG から除去することである。CFG内に潜在するパス数を削減させることで、後に行うパスプロファイリングのオーバーヘッドの削減を狙う。

エッジプロファイリングは、CFGの各エッジにカウンタを設置し通過回数を計測することで実現する。そして、エッジプロファイリングの結果を元に低実行頻度のエッジの除去を行うが、除去するか否かの判断はある閾値T を上回っているか否かで行う。

なお、除去した際、そのエッジeにはカウンタedgeCount(e)を設置する。このカウンタは、プログラムの実行挙動が変化したか否かの情報を得るために使用する。この除去エッジにカウンタを設置することによって、プロファイリング時に一定のコストを伴うが、そもそも除去エッジは通過頻度が低いのでカウンタの実行頻度も低く収集コストに対する影響は少ないと考える。

図7(a)は、元のCFGを100回実行した時のエッジプロファイリングの結果である。図7では、閾値を10とし実行回数が10以下のエッジを除去している。また、

低実行回数エッジ除去後、再構築を行ったCFGを図7(b)に示す。

3 4 5 6

7 8

9 :

1* ,/ /

- 2

/ / /* .*

0*

-/

,*

+**

3 4 5

8 9 :

1* ,/

.*

/*

0*

-/

,*

+**

,

<C=?EHF BMLGIJIKH NPO <D= SRTQQN >@A

図 7: 低実行頻度エッジの除去とCFG再構築の例

(18)

4.2.2 再構築CFGに対するパスプロファイリング

低通過頻度のエッジ除去後のCFGに対して、パスプロファイリングを行う。パスプロファイリングは、BallのEfficient Path Profilingのアルゴリズムを利用する。本手法のパスプロファイリングは、次の手順で行われる。

エッジへの非負数の割り当て

パスプロファイリングの最初の手順は、CFGの各辺eに正の整数値V al(e)を、

EN T RY からEXIT へのどのパスを通っても通過辺に割り当てられた値の合計値

（以降パス合計値）が異なるように割り当てることである。各パスに対して、ユニークな値を割り当てることが目的である。また、エンコードのオーバーヘッドを最小にするため、パス合計値は0からn−1(nはCFG内に潜在するパスの総数) になるようにする。

基本的な考えは、CFG内のノードをEXIT からENT RY まで逆順に追っていき、各ノードからEXIT まで何通りのパスがあるかを調べながら、必要なエッジ

に非負数V al(e)を割り当てていく。アルゴリズムは以下の通りである。

foreach vertex v in reverse topological order { if v is a leaf vertex {

NumPaths(v) = 1;

} else {

NumPaths(v) = 0;

for each edge e = v->w { Val(e) = NumPaths(v);

NumPaths(v) = NumPaths(v) + NumPaths(w);

} } }

このアルゴリズムはDAG内のノードをEXIT から逆向きに訪問してV al(e)の計算を行う。逆向きに訪問することにより、ノードvの全ての後続のノードwは、

vより前に訪問されることを保証する。各ノードvにはNumP aths(v)という値が割り当てられる。これはvからEXIT へのパスの数を記録するものである。ノードvでは、vから外向きに出る全ての辺v→w_i,1≦i≦n を逆順に訪れ、k番目の外向きの辺に次のような値を割り当てる。

V al(v→w_k) =

k−1X

NumP aths(w_i)

(19)

また、続く定理がこのアルゴリズムを正しく証明する。

定理1

DAGを与えられたとき、このアルゴリズムがノードvを訪れた後、NumP aths(v) がvからEXIT までのパスの数であり、各vからEXIT へのパスは異なる合計値を0...NumP aths(v)-1の範囲内で生成する[5]。

図8は、このアルゴリズム適用後のCFGと、V al(e)及びNumP ath(v)の結果である。図8(a)は、各エッジeに保存されたV al(e)の値を示している。また、図 8(b)は、各ノードvに保存されたNumP ath(v)の値を示している。ここで保存

されたV al(e)の値は、各辺のレジスタ更新操作の増分として用いられる。また、

NumP ath(v)は、CFGの再構築を行う際に用いられる。

2 3 4

5 6 7

DIEH /

.

:<?@<C B 8A>9;@=+B,

2 4 3 5 6 7

1 0 / / . .

- - - -

/ - DFHDG

KPL OPTKRL YZ KQL MWUNPVSKXL YZ

図 8: アルゴリズム適用後のCFG

このアルゴリズムの適用によって求めたV al(e)の値を元に、レジスタ増分操作の設置を各エッジに対して行ったCFGを図9(a)に示す。CFG中のENT RY(図中のA)を訪れた際にレジスタrの初期化を行い、レジスタ増分操作が設置されているエッジを通過する度に図中に定められた計算をレジスタrに施す。そうすることで、EXIT(図中のH)に到着した時にレジスタrは、通過したエッジに応じ

て値(パス合計値)を持つ。このCFGにおける各パスに割り当てられるパス合計

値は、図9(b)の通りである。CFG中に潜在する全てのパスに対してユニークな値

(20)

(Encoding)が0からn−1(nは潜在するパス数)の範囲で割り当てられていることが確認できる。

そして、それらの情報を効率よく保存するため、EXIT(図中のH)に、count[r]+

+という式を置く。こうすることで、パス合計値rが配列count[ ]のインデックスの役割を果たし、配列count[r]に各パスの実行回数が効率よく保存される。

4 5 6

8 9 :

F 3,

?EHDG<F=++2 F +3.

F +3.

F +3-

;>GB 7D?E@CDA 468: 4689:

458: 4589:

4568:

45689:

, - . / 0 1

JOK [^ZXY]VQ LMN JPK TSRQSRWU\

_ac_b

_d`c

図 9: アルゴリズム適用後のCFG

レジスタ増分操作の最適化レジスタrに施す計算量を削減するためにCFGの最適化を行う。詳細は、4.2.7にて説明する。

以上の様にCFGに対して、操作を加えることで、効率的にパスを収集することが可能である。また、count[r]に保存した値からパスを再生成する方法については、

4.2.8にて説明する。

4.2.3 プログラム実行挙動変化の判断

本手法では、プログラムの実行挙動の変化を各除去エッジeに設置したカウンタ edgeCount(e)の値を見ることで判断する。除去エッジeは、4.2.1にて、実行頻度

(21)

が低かったためCFGから除去されたエッジである。すなわち、このedgeCount(e) の値が閾値T₁以上であった場合に、プログラム実行挙動が変化したと判断する。

また、追加したエッジに関しては、追加後もedgeCount(e)を設置し続け、今度は異なる閾値T2を下回ったときにそのエッジeをCFGから除去する。

エッジのCFGからの追加及び削除には、一定のコストが生じるため閾値T₁及びT₂は適切に設定する必要がある。

4.2.4 プログラム実行挙動変化時のCFGの変形

本手法では、実行頻度の高いエッジを含むパスは実行頻度が高く、実行頻度の低いエッジを含むパスは実行頻度が低いという考えの下、パスプロファイリングを行う範囲であるCFGにエッジの追加及び削除の操作を適宜行う。ホットパスが存在しうる範囲を動的に限定してパスプロファイリングを行うことによって、低いオーバーヘッドでホットパスを検出することを可能とする。そのためCFGの変形操作が本手法の最も肝となる部分となる。CFG変形後のオーバーヘッドはもちろんのこと、CFG変形自体にかかるオーバーヘッドも最小限に抑えなければならない。

CFGの変形操作は、4.2.1にて除去したエッジを追加、或いは削除することで実現する。具体的なエッジの追加及び削除の方法については、次の4.2.5及び4.2.6にて説明する。

4.2.5 除去Edge及びNodeの追加

本節では、4.2.3よりエッジの実行頻度の増加が認められた際に、除去エッジを CFGに追加し、CFGの再構築を行う方法について説明する。エッジ及びノードを追加しても、4.2.2と同様に効果的にパスプロファイルを行うことができるように、既存のレジスタ増分操作の増分を変更する。低コストにCFGの再構築を行うためレジスタ増分操作の場所は変更はせず、さらに各パスのパス合計値が0から n−1(nはCFG中のパス数)になるようにする。

そのとき隣接するノードがCFG内に無い場合は、そのノードをCFGに追加する。ノードを追加した場合、そのノードから逆順にたどっていき、アルゴリズムに従って適切なNumP ath(v)、及びV al(e)を割り当てていく。

エッジの追加は次の2つの工程によって実現する。

(22)

工程1 CFGへのEdge及びNodeの追加

edgeCount(e₁)の値が閾値T₁を越え、追加すべきと判断されたエッジe₁(v₁→v₂) をCFGに追加する。この時、e₁(v₁→v₂)に隣接するノードv₁,v₂がCFG内に無い場合はCFGに追加する。また、この時追加されたノードvのNumP ath(v)は、初

期値(= 0)とする。以下に、CFGへの追加のアルゴリズムを示す。

if(edgeCount(e1) > T1){

contain_CFG(e1) = true ;

if(v1 or v2 is not contained CFG) contain_CFG(v1 or v2) = true ; NumPath(v1 or v2) = 0 ;

}

工程2 CFGの再構築

CFG内の各エッジのレジスタ増分操作は、後続のノードに依存する。つまり、

エッジe₁(v₁ → v₂)が追加された場合、ノードv₁の先行ノードを逆順に訪れ、各ノードv のNumP ath(v)及び各ノードvを始点とするエッジeのV al(e)を更新していく必要がある。逆にv₁より後続のノードについては更新作業をする必要はない。

まず最初に行う作業は、追加すべきエッジe1(v1 →v2)自身のV al(e1)の決定である。V al(e₁)には、NumP ath(v₁)を代入する。そして、次にNumP ath(v₁)に NumP ath(v₁)の値を加える。各ノードvの持つNumP ath(v)は、各ノードv からEXIT までの間の総パス数を保存する変数である。そのため、それまでのv1からEXIT の間の総パス数NumP ath(v₁)に、エッジの追加によって新たに増加したにv₂からEXIT までの総パス数NumP ath(v₂)の値を加えるのである。

アルゴリズムは次の通りである。

Val(e1) = NumPath(v1) ;

NumPaths(v1) += NumPath(v2) ;

次に、v1の各先行ノードvを逆順に訪問して、NumP ath(v)及びvを始点とするエッジeのV al(e)の更新作業を行う。各ノードvのNumP ath(v)には、最初に0が代入され、その後にvを始点とする各エッジe(v →w)を訪問して、NumP ath(v)

(23)

及びV al(e)を更新する。ただし、各ノードvはvより後続のノードviが先に訪問されることを保障する。また、エッジe(v →w)を訪問する際、wより後続ノードのw_iは、wよりも先に訪問されることを保障する。

このように各先行ノードvに対して行うNumP ath(v)とV al(e)の更新のアルゴリズムは次の通りである。

for each vertex v in reverse topological order { NumPaths(v) = 0);

NumPaths(v) += NumPaths(w);

} }

このアルゴリズムを用いることによって、NumP ath(v)には各ノードvからの総パス数が保存され、各エッジeにはレジスタ増分操作であるV al(e)が適切に保存される。これによって、CFG再構築前と同様の方法で実行パスの情報を低コストに収集することが可能となる。

図10は、CFGにエッジ(D→E)とエッジ(E→F)の追加を順に行った例である。

図10(a)は、エッジ(D→E)の追加を行っている。エッジ(D→E)の両端のノード D及びEはCFG中に無かったため、エッジの追加と同時にCFGに加える。この際、NumP ath(D)及びNumP ath(E)の値は、0に初期化される。次に、CFGを上のアルゴリズムを使用して再構築する。V al(D→E)には、NumP ath(D)の値が代入されるので、V al(D →E) = 0となる。V al(e) = 0は、レジスタrの増分操作をそのエッジで行わないことを意味する。よって、エッジ(D→E)にはレジスタ増分操作は設置しない。Dの各先行ノードは存在しないため(先行エッジが無く訪問不可能である)、V al(e)及びNumP ath(v)の更新作業はこれで完了である。

このように追加ノードから先行ノードにたどり着けない場合はパスの増加は起こらないので、他のV al(e)やNumP ath(v)に影響を及ぼすことは無い。

図10(b)は、CFGにさらにエッジ(E→F)を追加した例である。この場合、V al(E → F)にNumP ath(E)が代入されるので、V al(E →F) = 0となる。また、NumP ath(E) にはNumP ath(F)の値が加算され、NumP ath(E) = 2となる。次にEの先行ノードを訪問する。CFG中の先行ノードはDのみである。Dにて上のアルゴリズムを

(24)

用いて、NumP ath(D)及び、Dを始点とするエッジ(D→E)のV al(D → E)を更新すると図10(b)に示すようにNumP ath(D) = 2およびV al(D→E) = 0に更新される。

+0, .243+- 5 ., 687 +1, .243+. 5 /, 687

C D

@

A B

E

F G

M ?;

JLOKNHMI::>

M :?=

M :?<

WY\W[

W]X\

C D

@

A B

E

F G

M ?;

JLOKNHMI::>

M :?=

M :?<

WY\W[

W]X\

Yb`Z^a_QVR U S

Yb`Z^a_QWR U S

Yb`Z^a_QVR U T

Yb`Z^a_QWR U T

; ;

;

図 10: Edgeの追加

図11(a)は、図10(b)のCFGにエッジ(C→D)の追加し、再構築したCFGである。まず、CFGにエッジ(C→D)を追加し、その後V al(C →D)にNumP ath(C) の値を代入する。これは、エッジ(C→D)にレジスタ増分操作r+ = 2を設置することを意味する。

次に、ノードCからCFG内の各先行ノードを逆順に訪問する。この例では、まず最初にノードBを訪れる。そしてBを始点とするエッジ(B→F)とエッジ(B→ C)のレジスタ増分操作を更新し、それに伴ってNumP ath(B)の更新も行う。具体的には、最初にNumP ath(B)を0に初期化し、次にV al(B →F)をNumP aht(B) に代入する。そして、NumP ath(B)+ = NumP ath(F)を計算する。この計算により、NumP ath(B) = 2及びV al(B →F) = 0が導かれる。

続いて、エッジ(B→C)を訪問し、V al(B→C)にNumP ath(B)を代入する。

さらにNumP ath(B)+ =NumP ath(C)を計算する。

この結果、NumP ath(B) = 6及びV al(B → C) = 2が導かれる。この時、

V al(B → C) = 2のため、エッジ(B→C)にレジスタ増分操作r+ = 2 が設置さ

(25)

れる。

同様の更新作業をノードAにも施すことによって、NumP ath(A)の値とV al(A→ B)及びV al(A→C)が求まり、CFGの再構築が終了する。

また、図11(b)は、再構築されたCFGの各パスとパス合計値との対応を示して

いる。CFG内に潜在する全てのパスにユニークな値が割り当てられていて、なおかつパス合計値が0からn−1(nはCFG内のパスの総数)となっていることが確認できる。

+2, /465+- 7 ., 8B; +3, ?=A -01 8:9><@

T U Q

R S

V

W X

d PE

]cfbeZd[DDO d DPj

d DPG

d DPF suxsw

sytx uvmpn o hg d DPi uvmrn o j

uvmqn o k

Y\e` Ub]c^ab_

E F G H I J K L M N QSVX QSVWX

QSTUVX QSTUVWX QRVX QRVWX QRSVX QRSVWX QRSTUVW QRSUUVWX

図 11: Edge(C→D)の追加と再構築CFGのパス合計値

4.2.6 追加Edge及びNodeの削除

本節では、4.2.3よりエッジの実行頻度の減少が認められた際に、追加エッジを CFGから再度除去し、CFGの再構築を行う方法について説明する。エッジ及びノードの削除を行っても、4.2.2と同様に効果的にパスプロファイルを行うことができるように、既存のレジスタ増分操作の増分を変更する。低コストにCFGの再構築を行うためレジスタ増分操作の場所は変更はせず、さらに各パスのパス合計値が0からn−1(nはCFG中のパス数)になるようにする。

そのとき、削除すべきエッジe₁に隣接するノードv₁,v₂にとって、e₁が唯一の隣接エッジである場合、e のCFGからの除去と同時にv ,v もCFGから削除する。

(26)

エッジの追加は次の2つの工程によって実現する。

工程1 CFGからのEdge及びNodeの削除

ある期間における実行回数が閾値T2を下回り、削除すべきと判断されたエッジ e₁(v₁ → v₂)をCFGから削除する。この時、e₁(v₁ → v₂)に隣接するノードv₁,v₂ について、それぞれの隣接エッジを調べ、e1(v1→v2)をCFGから削除することで、隣接エッジが一つも無い状態になってしまう場合、そのノードv1あるいはv2

をCFGから削除する。

以下に、CFGから削除を行うアルゴリズムを示す。

if(edgeCount(e1) < T2){

contain_CFG(e1) = False ;

if(v1 or v2 do not have any edges) contain_CFG(v1 or v2) = False ; }

工程2 CFGの再構築

CFG内の各エッジのレジスタ増分操作は、後続のノードに依存する。つまり、

エッジe₁(v₁ → v₂)が削除された場合、ノードv₁の先行ノードを逆順に訪れ、各ノードvのNumP ath(v)及び各ノードvを始点とするエッジe(v →w)のV al(e) を更新していく必要がある。逆にv₁より後続のノードについては更新作業をする必要はない。

エッジ削除の際のCFG再構築のアルゴリズムは、エッジ除去後のCFGに対して、v1から各先行ノードvを逆順に訪問して、NumP ath(v)及びvを始点とする

エッジeのV al(e)の更新作業を行う。削除の際は、追加の際と異なり、v₁自身に

ついても訪問することに注意する。

各エッジvのNumP ath(v)には、最初に0が代入され、その後にvを始点とする各エッジe(v →w)を訪問して、NumP ath(v)及びV al(e)を更新する。ただし、

各ノードvはvより後続のノードv_iが先に訪問されることを保障する。また、エッジe(v → w)を訪問する際、wより後続ノードのwiは、wよりも先に訪問されることを保障する。

v₁及び各先行ノードvに対して行うNumP ath(v)とV al(e)の更新のアルゴリズムは次の通りである。

(27)

for each vertex v in reverse topological order { NumPaths(v) = 0;

NumPaths(v) += NumPaths(w);

} }

このアルゴリズムを用いることによって、NumP ath(v)には各ノードvからの総パス数が保存され、各エッジeにはレジスタ増分操作であるV al(e)が適切に保存される。これによって、CFG再構築前と同様の方法で実行パスの情報を低コストに収集することが可能となる。

図12(a)は、図11(a)のCFGからエッジ(E→F)の削除を行い、再構築を行ったCFGである。エッジ(E→F)を削除する際の最初の手順は、エッジ(E→F)を CFGから削除することである。そして、次にノードEから各先行ノードvを訪れ、

NumP ath(v)及びV al(v →w)の更新作業を行う。この先行ノードの更新作業は、

基本的にはエッジを追加した際と同様のアルゴリズムである。そのようにして、再構築が完成する。また、この再構築したCFGの各パスのパス合計値を示したものが、図12(b)である。各パスにユニークなパス合計値が0からn−1(nはパスの総数)の範囲で割り当てられていることが確認できる。

+2, /465+- 7 ., 8B; +3, ?=A -01 8:9><@

P Q M

N O

R

S T

` LE

Y_b^aV`WDDK

` DLd

` DLG

` DLF npsnr

ntos pqhki j f

` DLc pqhmi j d

pqhli j e

UXa\ Q^Y_Z]^[

E F G H I J MORT MORST

MNRT MNRST MNORT MNORST

pqhni j c pqhni j c

図 12: Edge(E→F)の削除と再構築CFGのパス合計値

(28)

以上の4.2.5及び4.2.6の方法によって追加後及び削除を行い再構築したCFGにおいても、4.3.2と同じ仕組みでパスを収集するすることが可能となる。

4.2.7 レジスタ増分操作の最適化

本手法を用いて構築したCFGは、最適化を施すことで、さらにオーバーヘッドを削減することができる。

本手法がパスを収集するために行う処理は次の3つであるが、特に1. パスレジスタrの更新作業の計算回数を減らすことにより最適化を施す。

1. パスレジスタrの更新作業(r+≡inc(e))

2. パスレジスタrのENT RY ノードでの初期化(r= 0)

3. EXIT ノードでのcount配列のインクメント(count[r] + +)

まず、1. パスレジスタrの更新作業(r+ = inc(e))についてであるが、この操作をなるべくCFG中の後ろに移動することにって、パスレジスタrの更新作業の回数を減らすことが可能である。たとえば、図13(a)のようなCFGでは、エッジ(A

→B)のレジスタ増分操作をエッジ(B→F)及びエッジ(B→C)に上乗せすることによって、パスを収集する際のパスレジスタrの更新作業の実行回数を減らすことが可能である。なお、その際のエッジ(B→F)の増分操作はr+ = 2となり、エッジ(B→C)のレジスタ増分操作はr+ = 4となる。このように増分操作を移動することによって、例えばパスABCF Hのパス合計値を収集するにあたっての場合のレジスタ増分操作を1回削減することが可能となる。

次に、2. レジスタの初期化について注目する。考えてみると、必ずしもENT RY ノードでr= 0の初期化する必要はなく、パスレジスタrの初期化は最初のレジスタ増分操作が行われる所で、その増分に応じて初期化を行えばよい。パスレジスタrの初期化を最初のレジスタ増分操作のところに持ってくることによって、各パスのレジスタrの更新作業の回数を削減することができる。

もちろん、このように初期化の位置を最初のレジスタ増分操作のところへ持ってきても、生成結果に変化を及ぼすことはない。

最後に、3. EXIT ノードでのcount配列のインクメント作業(count[r] + +)であるが、この作業はなるべく前に持ってくることにってレジスタrの更新作業の実行回数を削減する。例えば、図13(a)のエッジ(F→G)では、最後のレジスタ更新作業r+ = 1を行っているが、このような最後のレジスタ更新作業をcount[r+ 1] + +

(29)

のようにインデックス(メモリアドレス)を直接変えることによって、レジスタ更新作業の実行回数を削減することができる。

このようにして最適化を施した例を図13に示す。図13(a)が最適化を施す前の CFGであり、図13(b)が最適化を施した後のCFGである。パスレジスタrの更新作業の実行回数が削減されていることが確認できる。

2 3 4

5 6 7

= 1,

:<?;>8=9++0

= +1.

= +1-

AFB KMILH CDE AGB KMIJH CDE

NPRNQ

NSOR

2 3 4

5 6 7

= 1,

:<?;>8=9++0

= 1 .

= 1 / NPRNQ

NSOR :<?;>8=+-9++

図 13: レジスタ増分操作の最適化

4.2.8 パスの再生成方法

本節では、以上のパスプロファイリングで構築したCFG、あるいはエッジの追加や除去を行って再構築した後のCFGについて、パス合計値Rからパスを再生成する方法について説明する。CFG中のEN T RY からEXIT まで、各エッジを辿っていくだけの非常に単純なアルゴリズムでパスを再生成することが可能となる。

各ノードでは、そのノードから出てるエッジeの中から、R ≤ V al(e)を満たすエッジの中で、最大のV al(e)を持つエッジeへと進む。そして進むときには、

R−=V al(e)を計算しレジスタRの更新を行う。

これをEXITノードまで繰り返すことで、パス合計値からパスを再生成することが可能となる。

(30)

図14は、図9(a)のCFGについてパス合計値R=3のパスを再生成する場合の例である。まず、最初はENTRYノードAである。このときはもちろんR = 3である。次にノードBあるいはノードCに進む。BとCの両方ともR ≤ V al(e)を満たしており、V al(A → B)> V al(A →C)のため、ノードBに進む。次の分岐では、エッジ(B→F)のみR ≤V al(e)を満たすので、Ｆに進む。そして最後の分岐においては、エッジ(F→G)とエッジ(F→H)が両方ともR ≤ V al(e)を満たすが、V al(F →G) > V al(G→ H)のため、ノードGに進みEXIT ノードHに到達する。このようにしてパス合計値R = 3からパスABF GHを再生成することができる。また、この結果は図9(b)の各パスのパス合計値の結果と比較し、正しくパスが再生成されていることが確認できる。

3 4 5

6 7 8

0 0

?FEIHFD @DFJ AHBGC SUWSV

SXTW .

.

/ . .

.

9 2 1

9 2 /

9 2 9 - :;<+3 = 4,

9 2 9 - :;<+4 = 6,

9 2 9 - :;<+6 = 7,

34

346 3467

34678 9 2 .

9 2 9 - :;<+7 = 8,

OPMR NQLK

図 14: R=3の場合のパス再生性方法

4.3 本手法の利点

本手法の利点は、ユーザーからの入力などによってプログラムの実行挙動がどのように変化しても、その変化に応じてパスプロファイリングを行う範囲を修正し、継続して低コストにホットパスを検出することができる点である。

(31)

本手法は、２段階パスプロファイリングと同様、低実行頻度エッジを含むパスの計測を行わないことで、低コストにパスプロファイリングを行いホットパスを検出する。そのため、本手法はよりエッジの密度の高いCFGに対して効果的であるといえる。それは、従来手法のEfficient Path Profiling の収集コストは、主にエッジの密度に依存するため、複雑なCFGの場合にコストが増大してしまうのに対して、本手法ではエッジプロファイリングを行い低実行頻度パスを最初に除去することによって変密度を低下させるためである。除去されるエッジ数は、エッジの密度に依存するため、多くのパスを最初の段階で除外することで、コスト削減を図ることができる。

また、複雑なプログラムは実行挙動変化の可能性が高い。そのため、従来手法の2段階パスプロファイリング手法では正確かつ継続的にホットパスを検出することは難しくなる。これに対し、本手法では、プログラムの実行挙動変化に応じて、

CFGに必要なエッジを追加(あるいは削除)しパスプロファイリングを行う範囲を動的に変化させることが可能なためで、継続的に正確なホットパスを検出することができる。

もう一つの利点として、本手法では、閾値を決定することによってプロファイリングの精度及びオーバーヘッドを自由に変える事が可能な点が挙げられる。それぞれの実行環境やプログラムの挙動変化の度合に応じて、エッジ除去の閾値T、エッジ追加の閾値T₁及びエッジ削除の閾値T₂を設定することにより、目的や用途に応じたプロファイリングを行うことが可能である。

4.4 本手法の問題点

本手法は、プログラムの実行挙動の変化に応じてCFGの再構築を行うため、プログラムの実行挙動変化が激しい場合、再構築が頻繁に行われ、それに伴ってオーバーヘッド高くなってしまう恐れがある点である。本手法のCFGの再構築に用いるアルゴリズムは、ノード数とエッジの密度に依存する。低実行頻度エッジの除去後なのでエッジの密度、及びノード数はある程度少ないと思われるが、それでも頻繁に再構築が行われる際には、そのオーバーヘッドは無視することはできないであろう。この再構築を過剰に行ってしまうという問題は、適切にエッジの追加(あるいは削除)を発動させる閾値を設けることで、回避できる。だが許容されるオーバーヘッドは、環境によって異るためチューニングを行うなどして、適切な閾値を見つけるほかない。

(32)

5 実験

本章では、本手法の性能について実験を行う。実験は、実行挙動変化のあるプログラムに対して、本手法、低コストな2段階プロファイリング手法[6]、Efficient Path Profiling[5]の3つの手法を用いてそれぞれパスプロファルを収集し、ホットパスの検出率及びオーバーヘッドについて比較を行う。

5.1 実験方法

図15のノード数8総パス数15の非環式のCFGについて、実行挙動に変化をつけて1000回実行させて実験を行う。

1000回実行する際、200回ごとに5回に区切って計測し、各時点においてプロファイリングがどの程度の精度で行われているか、また、その時点でのオーバーヘッドはどの程度なのかを計測する。なお、2段階パスプロファイリング及び本手法の最初のエッジプロファイリングの結果を基にしたCFGの構築は、テスト実行 50回を事前に行うことで済ませておくものとし、その際の除去エッジの閾値T は T = 5とする。

また、本手法におけるエッジの追加を行う閾値T1は過去50回の計測中T1 > 5 を満たすものとし、エッジの削除を行う閾値T₂は過去50回の計測中T₂ ≤3を満たすものに設定した。

プロファイリングの精度に関しては、実際に実行された実行経路中の実行回数が200回中20回を超えるパスをホットパスとし、それぞれの手法でどのくらいの確率でこのホットパスを検出することができたかをもって精度の比較とする。

また、オーバーヘッドに関しては、各プロファイリング手法の収集を行うパス数での比較を行う。これは、収集する経路数が少なければ、パスレジスタrの計算回数が削減され、さらにはパスの記憶領域も削減されるので、よりオーバーヘッドが少ないと考えられるためである。

5.2 プロファイリングの精度の比較

表2は、3つの手法についてホットパスの検出率の結果をまとめた表である。このホットパス検出率は、実際のホットパスの集合に含まれる各プロファイリング手法から導かれたホットパスの割合で求める。

本手法と2段階パスプロファイリングを比較してみると、2段階パスプロファイリングのホットパス検出率の平均が51.67%であるのに対し、本手法のホットパス

(33)

,

- . /

0 1

2 3

+***

図 15: 実験に用いるCFG

検出率の平均は82.50%という結果が得られた。これは、本手法が2段階パスプロファイリングに比べ高い精度でプロファイリングを行っている事を示している。

また、このような結果の理由としては従来手法の2段階パスプロファイリングが実行挙動の変化時においても簡略化したCFGでプロファイリングを行うのに対して、本手法でのプロファイリングは実行挙動の変化に応じてプロファイリングを行っているため、この様な精度の差が生まれたのだろうと考えられる。また、

Efficient Path Profilingは、全てのパスについて継続的にプロファイリングを行うので、プロファイリング精度は常に100%であることが表から確認できる。

表 2: 各パスプロファイリングにおけるホットパス検出率

実行回数 1〜200 201〜400 401〜600 601〜800 801〜1000 平均

EPP 100% 100% 100% 100% 100% 100%

本手法 100% 83.33% 87.50% 83.33% 58.33% 82.50%

2段階PP 100% 66.67% 25.00% 33.33% 33.33% 51.67%

一方、表3は、3つの手法について誤ったホットパスの検出率の比較の表である。

この数値は、各プロファイリング手法で得たホットパスの中の実際にはホットパスでないパスの割合である。例え実際のホットパスを全て検出できたとしても、誤ったパスも同時にホットパスとして認識してしまっては、最適化に生かすことはできない。そういった意味で、この誤った検出率の比較は重要となる。このホットパスの誤検出率は、本手法が平均 12.67%であるのに対して、2段階パスプロファイ

(34)

リングが平均35.00%であった。

本手法の方がホットパスを誤って検出する確率が低く、この結果からも本手法が 2段階パスプロファイリングに比べより精度の高いプロファイリングを行っているといえる。

これらの結果から、実行挙動が変化するプログラムにおいて本手法は2段階パスプロファイリングよりも精度の高いプロファイリングを行うことができるといえる。これは本手法がプログラムの実行挙動に応じてプロファイリングをとる範囲を動的に変化させることが効果的に働いていることを示唆している。

表 3: 誤ったホットパスの検出率の比較

実行回数 1〜200 201〜400 401〜600 601〜800 801〜1000 平均

EPP 0% 0% 0% 0% 0% 0%

本手法 0% 33.33% 0% 0% 30.00% 12.67%

2段階PP 0% 0% 50.00% 75.00% 50.00% 35.00%

5.3 プロファイリングのオーバーヘッドの比較

今回はオーバーヘッドの比較のため、各プロファイリング手法の収集を行うパス数を比較する。収集する経路数が少なければ、パスレジスタrの計算回数が削減されパスの記憶領域も削減されるので、よりオーバーヘッドが少ないと考えられるためである。

表4は、各時点でのそれぞれのプロファイリング手法のパスプロファイリングを行う潜在パスについて比較した表である。本手法は、動的にパスの潜在数が変化するため本手法のパス潜在数は各区間での平均のパス潜在数を値とした。Efficient

Path Profilingは、すべてのパスを常に調べているので、潜在するパス数は最大パ

ス数の15である。これに対し、実行頻度の低いエッジを除去する本手法及び2段階パスプロファイリングは、それぞれ平均10.08及び平均6と、オーバーヘッドを抑えてプロファイリングを行っていることが確認できる。

指導 : 深澤良彰教授

プログラムの実行挙動変化を考慮した 部分的パスプロファイリングに関する研究

2005 年 2 月 2 日（水曜日）提出