本論文は、プログラム言語処理系における自動記憶管理(ごみ集め)において、ハードウェア支援を行なう際に問題となる「ルート検査のコスト」を低減するために、オブジェクトの配置を工夫することにより性能の向上をはかれることを提案、実証したものである。

　古くから用いられていたマークスイープ方式やコピー方式などの従来型ごみ集めを利用した場合には、長時間にわたって通常処理が停止するという問題が発生していた。現在ではこの問題を解決するための方法として、世代別ごみ集めを利用することが多い。世代別ごみ集めは、誕生してからの年齢によってオブジェクトを分類し、若いオブジェクトだけを通常のごみ集めの対象とすることによって、ごみ集めがひき起こす通常処理の停止時間を短縮する。しかし、世代別ごみ集めでは、古いオブジェクトに対する書き換えによって発生する世代間参照を検出する必婁がある。これを行うための方法として、ソフトウェアだけによる方法と、ハードウェアを利用する方法の二通りの方法がある。一般的なマシンでハードウェアを利用する方法を用いる場合には、ページングハードウェアを利用することができる。従来のOSでは、ページングハードウェアで管理している情報に直接アクセスできなかったために、ページトラップ機構を利用して必要な情報を得ていた。しかし、最近では、ページングハードウェアが管理する必要な情報を呼び出すためのシステムコールを提供するOSが登場しているため、これを世代間参照の検出のために利用することが可能になっている。

　以上のような背景から、本研究では、ハードウェア支援による世代別ごみ集めの性能向上が重要であると考え、ページングハードウェアを利用して世代間参照を行う世代別ごみ集めをGNU Emacsに実装した。そして性能計測を行い、ページングハードウェアを利用した世代別ごみ集めでは、ルート検査の際の局所性が重要であることを発見した。

　ここで言語処理系の協力によって、その局所性を向上することができるとの仮説をたてた。その方法として、書き換えの頻度によって、配置領域を分割する手法を提案した。

　そしてその仮説を実証するために、提案した手法についてダイナミックバインド言語のシンボルオブジェクトに対して実験とシミュレーションを行い、ルート検査の際の局所性を向上でき、世代別ごみ集めの性能を向上できることを示した。

　このことから、他のデータタイプに付いても、書き換えの頻度によって配置領域を分割する手法が有効であると推定できる。

　以下で、本論文の内容を具体的な結果を交えて説明する。

　本研究では、ページングハードウェアの機能を利用して世代間参照の検出を行う世代別ごみ集めをGNU Emacsに実装した。GNU Emacsは、Emacs LispというLisp処理系が組み込まれたテキストエディタである。Emacs Lispは、GNU Emacsの基本的な機能を定義するのに用いられるだけでなく、機能の拡張のためにも用いられ、多くのアプリケーションがEmacs Lispで作成されている。本研究では、実装した世代別ごみ集めの性能を評価するために、実際の利用時の状況を疑似的に作り出すことにした。こうすることで、実使用環境に近い状況での性能評価を行った。その結果、世代別ごみ集めを実装することによってごみ集めに必要な時間を短縮することができ、200msec以下におさえることが可能であると分かった。

　ページングハードウェアを利用して世代間参照を検出する場合、世代間参照を直接検出するのではなく、間接的に検出する。つまり、前回のごみ集め終了時から今回のごみ集めの開始時までにページの内容が書き換えられたページに世代間参照が含まれる可能性があるので、これらのページをページングハードウェアを利用して検出する。そしてこれらをすべて走査し、実際の世代間参照を検出する。このような処理は、ごみ集めの処理を行う場合の起点となるルートを求める処理であるので、ルート検査と呼ぶ。一般的なハードウェアでは検出の単位となるページのサイズが4096バイトとなり、一般的なオブジェクトの大きさに比べ大きい。計測の結果、1ページ内に存在する世代間参照の数が最大でも10個であり、1ページに存在可能な世代間参照の数(1024個)に比べ少ないことが分かった。つまり、ページあたりの世代間参照の密度を上げることにより、書き換えが行われるページ数を減らすことができると考えられ、これによりページの走査に必要な時間の短縮が行える。つまり、ルート検査のコストが少なくなると考えられる。

　このように、ページングハードウェアを世代間参照の検出に利用する場合には、従来は指摘されていなかったルート検査の際のオブジェクトの配置の局所性が問題となることが分かった。

　ここで、言語処理系の協力によって書き換えの局所性を向上することができるという仮説をたてる。そして、局所性を向上するための手法として、書き換えの頻度によってオブジェクトを違う領域に分けて配置するという方法を提案する。この方法によって書き換えの局所性が向上すれば、世代別ごみ集めを行なう場合のルート検査のコストを削減できる。

　この仮説を実証するために実際の言語処理系において実験を行った。実験は、Emacs Lispのシンボルオブジェクトに対し、バイトコードコンパイラを用いた静的解析の結果、書き換えが行われると分かったシンボルオブジェクトを他のシンボルオブジェクトとは別のページに配置するという手法を用いた。このときの世代別ごみ集めの性能を計測し、この手法の効果を判定した。

　Emacs Lispにおけるオブジェクトの書き換えのトレースの結果では、シンボルオブジェクトはconsオブジェクトに比べて書き換えの頻度の差が大きい。これは、Emacs Lispではダイナミックバインドであるので、書き換えが何度も行われるシンボルオブジェクトが存在するためである。実験の結果、書き換えのあるシンボルを他のシンボルオブジェクトとは別のページに配置することで、プログラムの実行時間およびごみ集めの実行時間を短縮することができることが分かった。ごみ集めの実行時間は、本方法を利用することによりCPUのユーザ時間で約10%短縮できた。ここで、短縮できたごみ集めの実行時間が、書き換えの局所性が向上したことによって、ルート検査に必要な時間が短縮されたことによるものであることを確かめるためにシミュレーションを行った。その結果、短縮された時間の50%はルート検査の時間の短縮によるものであることを確認した。プログラムの実行時間の短縮は、書き換えの多いオブジェクトが同じページに配置されることになったことによるキャッシュのヒット率向上によるものであると推察される。

　さらに、ハードウェアによるライトバリアとソフトウェアを用いたライトバリアの性能の比較をシミュレーションによって行った。この結果、ハードウェアによるライトバリアがソフトウェアを用いたライトバリアに対して同程度の性能であると分かった。

　これらの結果から、他のデータタイプにおいても書き換えの頻度の推定の方法があれば、言語処理系の協力によって書き換えの局所性を向上することができることが分かった。この方法を利用して、ページングハードウェアをライトバリアとして利用した世代別ごみ集めにおいて、ルート検査に必要な時間を短縮することができ、ごみ集めの高速化が可能である。

　本研究の寄与として以下の点があげられる。

1.ページングハードウェアを用いた世代別ごみ集めにおいて、従来指摘されなかったルート検査の際の局所性の問題が存在することを発見し、これがごみ集めの性能向上の鍵となっていることを指摘したこと。

2.書き換えの局所性が通常実行だけでなくごみ集めの性能にも大きく影響を与えるという仮説を提示したこと。

3.具体的な局所性の向上法として、オブジェクトの書き換えの頻度によって配置する領域を分割する手法を提案したこと。

4.テストケースとしてEmacs Lispのシンボルオブジェクトに対して実験を行い、この手法が効果的であることを明らかにしたこと。

5.書き換えの頻度推定ができる場合は、それがごみ集めの性能向上に利用できることが明らかになったこと。

　本論文は「世代別ごみ集めのためのオブジェクトの配置法」と題し、記憶領域の自動管理システムであるごみ集めにおいて、広く用いられている世代別ごみ集め方式を対象としてハードウェアによる支援を有効に用いるための研究をまとめたもので、以下の6章からなる。

　第1章「序論」では、研究の背景、研究全体の概要と論文の構成について述べている。

　第2章「ごみ集めの基本的アルゴリズムとその問題点」では、ごみ集めに関する各種の方式を概観し、従来の研究成果をまとめている。

　第3章「ページングハードウェアを用いた世代別ごみ集めの実装」では、ページングハードウェアを利用する世代別ごみ集めを現実的な言語処理系へ実装して得られた知見について述べている。世代別ごみ集めは通常処理の停止時間を短縮できるという利点があり、近年広く利用されているが、その実装のためには世代間参照の検出の必要があり、通常処理に対するオーバヘッドの面からも、既存の処理系への導入の面からも問題となってきた。本章ではこの問題点について先行研究を紹介しつつ論じ、ページングハードウェアを利用する方式を有望な選択肢として位置付ける。そのうえで、広く使われているEmacsテキストエディタの記述言語であるEmacs Lispに実装されている従来型のごみ集めを、提案方式に変更する実験を計画・実施し、性能計測を通じてその有効性と問題点を明らかにする。この実験により、世代別ごみ集めの有効性を示す一方で、世代間参照の検出にページングハードウェアを利用する際に従来は注目されてこなかった、オブジェクトの書き換えの散在が性能に影響を及ぼす問題であることを指摘した。

　第4章「ページングハードウェアを生かすオブジェクト配置法の提案」では、前章で明らかになった書き換えの散在の問題について、それを軽減するための手法を提案する。書き換えの発生しやすいオブジェクトを検出し、それらをできるだけ同一ページに配置するという配置法であり、検出と配置のそれぞれについて複数の実現法を考察している。

　第5章「ページングハードウェアを生かすオブジェクト配置法の実験」では、前章で提案した配置法の有効性を実験を通して評価・検証している。具体的には、第3章で実装したEmacs Lisp上のごみ集めをベースとして、シンボルというデータ型を対象として提案した配置法を実施し、性能計測を行なうものである。まず予備実験として、シンボルとコンスの二種のデータ型を対象として、プログラム実行時の書き換えの頻度の分布を測定し、頻繁に書き換えられるオブジェクトが全体の一部に集中するという前提を確認している。つぎに、Emacs Lisp処理系の一部であるバイトコンパイラを書き換えて、プログラム中で変数として扱われるシンボルを静的に発見し、それらを別領域に割り当てるという方法により前章の提案を実現する。その実験の結果、通常の世代別ごみ集めと比較して約10%のユーザ時間の短縮が達成されている。さらに、達成された高速化の主要な部分が提案手法に由来することを実験により確認している。

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

　以上これを要するに、本論文では複雑なソフトウェアを構成するために重要となるプログラムの記憶領域自動管理システムであるごみ集めについて、世代別方式をハードウェア支援によって効率化できることを示し、さらにその過程で発生する書き換えの散在という問題点を軽減するためのオブジェクトの配置法を提案し、現実的な処理系上での実験を通してその有効性を実証しており、その成果は情報工学上貢献するところが少なくない。

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