本論文は共有メモリ並列計算機のためのメモリ管理モジュールの実装について述べる。このモジュールはメモリ確保ルーチンとガーベージコレクタ(GC)のそれぞれを並列化したものであり、スケーラビリティに焦点をおく。メモリ管理モジュールのスケーラビリティは、特にメモリ確保を頻繁に行なうプログラムにおいて重要である。本論文はメモリ管理モジュールをスケーラブルにする技法を提案し、実験により効果を評価する。実験には対象型共有メモリ並列計算機(SMP) Sun Ultra Enterprise 10000と、分散共有メモリ並列計算機(DSM) SGI Origin 2000を用いる。スケーラビリティを達成するためには、排他制御によるボトルネックを削減するだけでなく、計算機のメモリアーキテクチャの差異を考慮することが必要不可欠である。アーキテクチャに適応した技法を採用することにより、それぞれのマシン上で最適な性能を得ることを目的とする。GCの最適化技法の効果を実験により評価するだけでなく、並列GCの性能予測モデルを提案し、そのモデルを通した議論も行なう。メモリ確保ルーチンの最適化技法の効果について、確保ルーチン自身の速度、メモリ利用効率、ユーザプログラム性能への影響の観点から議論する。

　メモリ確保ルーチンの効率には時間的効率と空間的効率があり、これらはトレードオフになりやすい。メモリ確保の高速化のみを追求するのであれば、プロセッサ毎にヒープを分離させるのが良い。この場合確保時の排他制御は必要なく、完全に並列にメモリ確保することができる一方、メモリ使用量が増大してしまう。メモリ確保時の並列性と、メモリ利用効率の両方を満たす方式を提案する。また、メモリ確保ルーチンの設計はそれ自身だけでなくユーザプログラムの性能にも大きく影響する。例えば空間的効率を追求した結果としてユーザプログラムの局所性が低下したり、false sharingが増大してしまう場合が考えられる。このため、ユーザプログラムの性能も考慮に入れ、トレードオフについて議論する。両方の効率が良好なメモリ確保ルーチンを実装し、実験により性能評価を行なう。

　実装したGCは並列マークスイープGCであり、全スレッドが協調して処理を行なう。この並列GCの最適化の一つとして、DSM上のマークビットのメモリノード間平均化を提案した。DSMにおいては多数のプロセッサから特定メモリノードヘアクセスが集中するとアクセスコストが非常に高くなる。アクセス集中を低減するためにこの最適化を提案し、実計算機上の実験により効果があることを確認した。しかし、提案した最適化が特定の計算機で効果があったとしても、レイテンシやメモリ占有時間の異なる別の計算機で効果があることは保証されない。この問題を解決するには、並列GCの性能とメモリアーキテクチャの関係を定量的に理解することが必要である。このために、GC性能の予測モデルを構築した。このモデルはヒープ状態とアーキテクチャパラメータを入力とし、予測GC時間を出力する。ヒープ状態から、生きたオブジェクトの総量、オブジェクトグラフの並列度、キャッシュミス数を得る。一方、アーキテクチャの性質を捉えるために、メモリアクセスのレイテンシだけでなくアクセス要求の衝突も考慮する。本モデルの正当性を、予測結果と並列計算機上の実験による実測結果を比較することにより示す。衝突コストを入れないモデルによる結果との比較により、正確な予測を行なうには衝突コストを考慮することが必須であることが分かった。この手法の応用には、GCの並列度の調整や仕事移動アルゴリズムの変更などの適応的アルゴリズムが考えられる。

　本論文は6つの章からなる。第1章は序論であり、本論文の研究にあたって動機となった背景について論じている。動的なメモリ確保を頻繁に行なう並列プログラムにおいて、メモリ確保処理の性能はプログラム性能に重大な影響を与えうる。また、自動的に不要なデータ構造を回収するガーベージコレクション(GC)は、プログラマの手間を軽減する一方で、プログラム実行中の無視できない時間を消費する。このため、共有メモリ並列計算機上でプログラムを効率的に実行するにはメモリ管理モジュールが充分に高速化されている必要がある。本論文では(1)メモリアロケータと(2)GCのそれぞれの効率化技法を提案、実装することにより、スケーラブルなメモリ管理モジュールを構築することに主題をおいている。この主題の設定は、学位論文の主題として十分、かつ妥当であると認められる。

　第2章は、上記(1)で述べられているメモリアロケータについて、並列化技法を提案している。アロケータが満たすべき性質として、スケーラビリティに加え、局所性とメモリ利用効率に注目する。局所性の向上により、間接的にプログラム性能を向上させることができる。局所性とメモリ利用効率の間にはトレードオフがあり、利用者(プログラマ)はそのトレードオフを連続的に調節することができる。分散共有メモリ計算機(DSM)での実験を通して、アロケータの効率化によりプログラム性能が向上することが述べられている。

　第3章から第5章までは、上記(2)で述べられているGCについて議論している。議論されているのは、マークスイープ方式と呼ばれるGC方式を並列化したものである。第3章は、GCの際にユーザプログラムを全て停止させてから、複数スレッドが協調的にGCを行なう、ストップ並列GCについて述べている。GC時間を短縮するためには負荷分散が必須であり、そのアルゴリズムが示されている。最大64プロセッサによる実験を通して、特に対象型共有メモリ計算機(SMP)で良好な性能を達成することが示されている。

　第4章は、第3章で示した並列GC方式の性能モデルを提案している。この章は、第3章で示された、GC性能のアーキテクチャごとの性能差の原因を解析するものである。GCの並列化に伴ういくつかのオーバヘッドを考慮してGC時間の予測を行なう。具体的には、キャッシュミスコストの増加と、キャッシュミス数の増加などである。実測値と予測値の比較を通して、提案したモデルがアーキテクチャ間の性能の差異を捉えることが可能であることが示されている。

　第5章は、GCとユーザプログラムが同時に動作し、かつGC自身が並列化されている、並行並列GCについて述べている。並行性を持ったGCは特にリアルタイム性を必要とするプログラムに対して有用である。このGCとストップ並列GCとの比較実験を通して、停止時間の向上が見られる一方、プログラムのスケーラビリティを低下させることが示されている。この低下の最大要因はマーク処理の一貫性を保つための処理であることが述べられている。

　第6章は、論文全体の内容をまとめ、今後の研究課題について論じている。特に、本論文の方式によりスケーラブルなメモリ管理モジュールの構築が可能であり、それにより並列プログラムの性能を向上させることができることが主張されている。

　本学位論文は、動的に多くのメモリ確保を行なうプログラムの実行の際にボトルネックとなるメモリ管理モジュールについて、アロケータとGCのそれぞれについて有効な効率化方式を示している。それらを利用すれば、メモリ管理処理自身の効率化と局所性の向上により、プログラムの速度性能が向上することを、数多くの実験結果とともに示している。これらの方式の特徴は、既存のメモリ管理の研究であまり重視されていない、計算機アーキテクチャの差異を考慮することである。2種類の大規模共有メモリ並列計算機上での実験に加え、性能モデルによる性能解析が数多くなされており、それらを通して提案方式の有用性を示している。以上のように、本論文は並列メモリ管理の研究において優れた研究であり、極めて有意義な成果を得ている。この点で本論文は高く評価され、審査委員全員で、博士(理学)の学位を授与するにふさわしいと判断した。

　なお本論文の内容の一部は、共著論文として印刷公表済みであるが、論文提出者が主体となって研究および開発を行なったもので、論文提出者の寄与は十分であると判断する。