計算機のメモリ資源は有限である.そのため,計算機上で実行されるユーザプログラムは,動的に不要となったメモリ領域を解放し,再利用しなくては,メモリ不足によって途中で停止してしまうおそれがある.この再利用処理はプログラマが手動で行う場合と,言語処理系が自動的に行ってくれる場合とがある.C, C++などの言語処理系の多くは前者であり,Scheme, Java, KLICなどの処理系は後者である.前者では,プログラム中でメモリ領域を確保したら,使用後に必ず解放せねばならないため,プログラマの負担が大きい.一方後者は言語処理系が自動的に解放するのでその負担は小さい.

　この不要になった領域を自動的に解放,再利用する機構はガーベジコレクタ(GC)と呼ばれている.GCはプログラマにとって非常に有用であるが,言語処理系には非常に重い処理でもある.そのため,これまでに多くの効率的なGC手法が提案されてきた.世代方式GCもその一つである.世代方式GCでは,メモリ領域を新世代領域・旧世代領域の2つに分割する.そして,新たに生成されたオブジェクトは,まず新世代領域に割り付けられ,何回かのGCを経た後,旧世代領域に移される(殿堂入り).もし,適切な寿命予測に基づくGC回収効率の予測が的確に行われれば,適切な世代分割を行うことによってGCの手間を削減でき,実行効率の向上が見込まれる.また,GCコストの見積もりが容易になり,プログラマは,より効率の良いプログラムを作成できるようになる.さらに,キャッシュ,メモリ階層を意識した世代の分割やオブジェクト配置も実現できれば,局所性を向上させることが出来る.これまで,寿命予測に基づくオブジェクト寿命分布モデル・GC回収効率モデルとそれに基づく世代分割手法,及び局所性を向上させるオブジェクトの配置を実現する手法がいくつも提案されてきた.しかし,世代GCをより効率よく行うためには双方を同時に考慮する必要があると考えられる.

　そこで本研究では,まず以下の3つを行ない,効率の良い世代方式GCの提案を行った.

　1)　データ寿命分布モデルとGC効率モデルの提案.

　まず,いくつかのKL1プログラムで寿命分布を測定した結果,短寿命オブジェクトの寿命に対する確率密度分布はGamma分布,

に非常に近いことが分かった.そこで,短寿命オブジェクトと長寿命オブジェクトの比をα:(1-α),長寿命オブジェクトの寿命をL(但し,Lは十分大きな値とする.)として,全オブジェクトの寿命に対する確率密度分布を

とした.(αは短寿命オブジェクト比率,kは短寿命オブジェクト寿命の広がりの指標.)この確率密度分布と生存曲線のグラフを図1,2に示す.

　次に,世代方式GCの回収効率を示す指標であるMark/Cons比(新世代GC時に回収されたオブジェクト量と,前回GC直後からのメモリ割付量の比)と新世代サイズとの関係のモデルを,上の寿命分布モデルから導き出した(図3,4).

　その結果,新世代GCの回収効率は新世代サイズが大きくなればなるほど改善されるが収束する値は2(1-α)である.またkの値が大きい(短寿命オブジェクトの平均寿命が長い)ほどM/C比の収束は速いということが導かれた.

　そして,このモデルは,実際のKL1プログラムの振る舞いとほぼ一致した.

　2)　局所性を考慮した殿堂入り時期調節手法の提案.

　次に,新世代サイズの違いによるキャッシュミス数と実行時間の関係を,いくつかのKL1プログラムについて測定した.その結果,多くのプログラムでは,新世代サイズが大きくなるとキャッシュミスやTLBミスなどの増加により,実行時間の低下が見られることが分かった.

　一方,(1)のGC回収効率のモデルから,新世代サイズを大きくすると,M/C比の値が減少(=GC効率は改善)し,やがて2(1-α)に収束する.そのため,世代方式GCでは,新世代サイズを,M/C比がほぼ2(1-α)で,局所性が悪くない値,すなわち,M/C比と新世代サイズのグラフの傾きがある閾値よりも小さくなった値にするのが最も良いと考えられる.

　3)新世代サイズを自動調節する世代GC方式の提案.

　並行並列論理型言語処理系KLIC-3.003版を,プログラム実行中に,

　・　新世代サイズとM/C比の関係を測定可能,

　・　新世代サイズを変更可能,

に出来るようにし,実行時に動的に(2)の方針に従って新世代サイズを「M/C比の変化が閾値以下になる値」とすることによって,非常に効率の良い実行が行えるようにした.

　実行時のサイズ変更は,以下のように行うようにした.

　まず,新世代サイズの初期値は一次データキャッシュサイズの半分とし,二回目のGC時に新世代サイズを二倍にする.そして,新世代サイズを変更する毎にM/C比と新世代サイズを記録し,前回新世代サイズ変更時のM/C比,新世代サイズと比較した結果:

　今回の新世代サイズ変更では,M/C比が閾値以上改善しているので,次のGC時には,同じ方向同じ変化幅で新世代サイズを変更する(図5).

　このとき,新世代サイズ変更では,M/C比が閾値以上悪化しているので,次のGC時には,反対方向,半分の変化幅で新世代サイズを変更する(図6).

なお,変化幅を半分にするのは,新世代サイズが過度の振動をしないためと,最適値に収束しやすくするためである.

(C)M/C比の変化が閾値以下の場合

　このとき,新世代サイズが十分大きく,M/C比の値はほぼ2(1-α)に収束してきていると考えられる.そのため,次のGC時に新世代サイズをより大きく変更しても,M/C比はあまり変化しないと考えられるので,新世代サイズを元に戻して新世代サイズ変更を一旦止める(図7).

　このルールで新世代サイズを目標値に調節することが出来ると考えられる.しかし,最適な新世代サイズはプログラムの実行フェーズによって変わる事がある.そこで,新世代GC10回毎に新世代サイズを2倍,50回毎に新世代サイズを1/2倍することにした.

　サイズ変更の閾値は,小さすぎると新世代サイズが過度に変動してしまい,実行速度が低下してしまう.逆に大きくし過ぎると適切なサイズに変更される前にサイズ変更を止めてしまうため,GC回収効率や局所性が悪化し,実行速度が低下してしまう.そこで,いくつかのKL1プログラムにおいて,様々な閾値を設定して実行時間を比較し,その結果が最も良かった0.45を閾値とすることにした.

　そして,並列論理型言語処理系KLICで,以下の3つのGC手法での性能比較を行った.

　・　2面のStop-and-Copy GC (SC).

　・　従来の世代GC方式(GGC).

　・　新世代サイズを調節するGC方式(AGC).

　実行環境はIntel Celeron 333MHz(1st D-Cache 16KB, 2nd cache 128KB), Linux 2.2.5. GGCとAGCの初期新世代サイズは8KB(1次データキャッシュサイズの半分),旧世代サイズは88KBとし,SCの初期ヒープサイズは片面96KBとした.実行時間のグラフを図8に示す.

　その結果,多くのKL1プログラムにおいて,本手法が有効であることが示された.ただ,kkqueenでのみAGCがGGCよりも遅くなってしまっている.このプログラムには,2つの実行フェーズがあり,実行初期の短いフェーズでは大きなサイズが,そしてそれに続く長いフェーズでは小さなサイズが新世代サイズ調節の目標値となっている.AGCは,実行初期の段階で新世代サイズを拡大し,その後のフェーズで縮小を始めたのだが,GC回数が全体で298回しか無かったため,最適な新世代サイズ(約30KB)までの縮小が間に合わなかった.一方,GGCでは,最初からあまり新世代サイズを拡大しなかったため,後半のフェーズでAGCよりも効率のよいGCが出来,実行速度もAGCを上回った.

まとめると,本研究では,

(1)　データ寿命,GCコスト予測のためのモデルを作成.

　単純なデータ寿命分布モデルからM/C比(GC回収効率)と新世代サイズの関係を導いた.これにより,実行時にデータ寿命分布を予測し,新世代GC回収効率を改善可能にした.

(2)　局所性を考慮した殿堂入り時期調節法の提案.

　キャッシュ新世代サイズを大きくし過ぎるとキャッシュミスやTLBミスなどにより実行速度が低下する.そこで,新世代サイズをM/C比の変化が,ちょうど閾値以下になる値に設定することとした.

(3)新世代サイズを調節する世代GC方式の提案.

　M/C比と新世代サイズを観測しながら,(2)で定めた値に新世代サイズを自動調節する世代GC方式を提案した.

　そして,このGC方式を並列論理型言語処理系KLICに実装し,いくつかのテストプログラムにおいて,他のGC手法との比較を行った.その結果,本手法では多くのプログラムにおいて,新世代GCの回収効率と局所性のバランスが取れ,世代GCの効率化が実現された.

図1.寿命の確率密度分布

図2.生存曲線

図3.GC回収効率のモデル(α固定)

図4.GC回収効率モデル(k固定)

図5サイズ変更ルール(Case A)

図6サイズ変更ルール(Case B)

図7サイズ変更ルール(Case C)

図8実行時間の比較

　本論文は、「世代方式ガーベジコレクタの効率化に関する研究」と題し、動的に生成・消滅するオブジェクトを扱うソフトウェアに不可欠なメモリ領域自動管理機構であるガーベジコレクション(GC)について、その効率化のために提案されている世代方式GCをさらに効率化する技術の研究をまとめたもので、以下の9章よりなる。

　第1章「序論」では、研究の背景、目的、方針について述べている。

　第2章「ガーベジコレクション」では、本研究が基礎とする世代方式のGCを概説し、プログラム実行効率上で重要な意味を持ち、研究の主要な着眼点のひとつであるキャッシュメモリの利用効率との関係について述べている。

　第3章「関連研究」では、本研究と同様の目的をもって行われてきた、オブジェクト寿命分布モデル、世代分割手法、局所性向上のためのオブジェクト配置法について、既存の研究を概観している。

　第4章「並列論理型言語処理系KLIC」では、本研究の実証のテストベッドとして用いた並列論理型言語KL1と、その処理系KLIC、わけてもそのメモリ利用の特性とメモリ管理方式、および論文提出者自身が以前に行い本研究でもベースとした世代方式ガーベジコレクタの実装方式について述べている。

　第5章「寿命モデルと回収効率モデル」では、KLIC処理系上での実際のプログラム実行履歴の解析を通じて、実際のプログラムに適合したオブジェクト寿命モデルを明らかにしている。また、GCの効率を表す回収効率モデルを提案し、プログラム実行時の計測結果からモデルの妥当性を検証している。

　第6章「局所性を考慮した世代分割手法」では、世代方式GCの重要なパラメタである新世代サイズと性能との関係を、実際のプログラム実行において計測し、その結果を参照局所性の観点から説明する理論を与えている。これに基づき、世代方式GCの主要なパラメタのひとつである新世代サイズについて、参照局所性と回収効率のトレードオフを考慮した上で、どのような値に設定するのが最適であるかを明らかにしている。

　第7章「新世代サイズを自動調節する世代方式GC」では、新世代サイズを前章までに明らかになった最適な値に向けて自動的に調節する方式を提案している。提案する方式は、新世代領域のGC時に生存しているオブジェクトの比率を計測、新世代サイズの変化に伴ってその比率がどのように変化するかに基づいてオブジェクト寿命分布のパラメタを推定、それに合わせて新世代サイズを調整するもので、人手の介在なしに、プログラムごと、同一プログラムでもその実行フェーズごとの寿命分布の動的変化に自動追随できるという特徴を有している。

　第8章「実装と評価」では、前章に提案した方式を実際にKLICに対して実装、キャッシュメモリ容量などの異なるさまざまな機種の計算機上で種々のサンプルプログラムの実行性能を計測した結果、提案方式が多くの場合に有効であったことを示している。

　第9章「結論」では本研究の成果をまとめている。

　以上これを要するに、本論文では複雑なソフトウェアの記述にあたってプログラマの大きな負担となるメモリ管理を自動化するガーベジコレクションについて、世代方式と呼ばれる効率化手法にさらに改良を加え、プログラムの実行状況の計測を通じてその主要なパラメタを自動調節して性能向上を図る方式を提案、効果を処理系への実装と計測を通じて実証しており、その成果は情報工学上貢献するところが少なくない。

　よって本論文は博士(工学)の論文として合格と認められる。