1. No category

平成 25 年度創成シミュレーション工学専攻修士論文梗概集
計算システム工学分野
オブジェクト探索のハードウェア支援による GC の高速化
学籍番号 24413537 氏名
里見 優樹
指導教員名
津邑 公暁
1 はじめに
スマートフォンに代表されるモバイル機器の普及
に伴い，これらの機器への性能要求が高まりを見せ
ている．モバイル機器では一般に，搭載されるメモ
リ量が汎用計算機と比較して少ないため，ガベー
ジ・コレクション（GC: Garbage Collection）のよ
うなメモリ管理機能の性能が非常に重要となる．し
かしGCには，GC実行時のアプリケーションプロセス
図 1: 子オブジェクトへの参照
停止により，システムのレスポンスが低下してしま
うという問題が存在する．そこで本研究では，ハー
DalivikVMはMark & Sweep[1]というオブジェクト
ドウェア支援によって，より高速かつ効率的なGCを
にマークを付けて，そのオブジェクトがゴミかを判
実現することで，こうした問題の解決を目指す．
別するGCアルゴリズムを採用している．単純なMark
2 ガベージ・コレクション
& Sweepではオブジェクトのヘッダ内にマーク用の
GC とは,プログラムが動的に確保したメモリ領域
ビットを確保するのが一般的であり,オブジェクト
のうち,不要となった領域を自動的に解放する機能
にマークする際はオブジェクトへの書き込みが発生
である．しかし GC には，先に述べたように GC 実行
することになる．
しかし,これはコピーオンライトと
に伴うシステムのレスポンス低下という問題が存在
の相性が悪い．
そこでDalvikVMでは,ビットマップマ
する．
この問題を解決するため,これまで主にアルゴ
ーキング[2]というビットマップと呼ばれるビット
リズムの改良という観点から多くの研究がなされて
列でオブジェクトへのマークを管理する手法でこの
きたが，それらはスループットを犠牲にして停止時
問題に対処している．ここでDalvikVMにおいて，あ
間の短縮を図るものであったり，システムに合わせ
るオブジェクト（obj）が子オブジェクトを参照する
た煩雑なチューニングが必要であったりと，根本的
様子を図1に示す．obj内でマークが必要なブジェク
な問題解決には至っていない．
これに対し,本研究で
トへのポインタは,クラスメソッド等のクラス情報
は多くの実行環境で用いられる代表的な GC アルゴ
を持つクラスオブジェクトへのポインタ(clazz)，
及
リズムに共通して存在する構成処理要素に着目し,
び子オブジェクトへのポインタを格納する配列
これを高速化するハードウェア支援手法を提案する．
(instance Data)に存在する．なお，instance Data
3 GC の動作解析
には数値等，ポインタ以外のデータも区別なく格納
ハードウェア支援による GC 高速化手法の提案
されているため，refOffsetsというビットマップか
にあたり，モバイル機器の実行環境として代表的な
らポインタが格納されている位置（オフセット）を
AndroidのDalvikVMに実行されたGCを対象に，
実行時
計算する必要がある．
間の内訳を評価した．その結果，オブジェクトか
しかし，こうしたビットマップマーキングや
ら参照されるオブジェクトの探索処理が多くのプロ
refOffsetsを使用したポインタの取得など，ビット
グラムで GC の動作のボトルネックとなっているこ
マップを用いた処理では，実際のメモリアドレスと
とが分かった．
そこで本論文では,このオブジェクト
そのアドレスに対応するビットの位置を変換するた
探索を高速化するハードウェア支援手法を提案
めの計算が必要となる．そのため，例えばビットマ
し,GC 処理の高速化を図る．
ップマーキングでは，オブジェクトのヘッダへのマ
平成 25 年度創成シミュレーション工学専攻修士論文梗概集
計算システム工学分野
ーキングと比較してマーク処理が非常に遅くなって
しまうという問題が存在する．
4 ハードウェア支援による探索の高速化
そこで本論文では，先に述べたようなビットマッ
プ表現に対する処理の結果得られた値のうちオブジ
ェクトのクラスごとに固有なものを専用の表で記憶
しておく手法を提案する．これによって，オブジェ
クトを探索する時に，記憶した値を用いてクラスオ
ブジェクトへの重複したマークやオフセット計算処
理の実行自体を省略し，オブジェクト探索の高速化
を実現する．
5 評価
提案手法をgem5シミュレータに実装し，シミュレ
ーションによる評価を行った．評価にはGCBench，
AOBench，SPECjvm2008から5種類の，計7種類のプロ
グラムを用いた．
GCの実行サイクル数比を図2に示す．
図 2: GC 実行サイクル数
図2中の凡例はサイクル数の内訳を示しており，
MarkRoot はルート集合からのマーク，MarkObject
必要となる表のサイズは合計で約8Kbytes と，少量
は子オブジェクトのマーク，
Sweepは不要なオブジェ
のハードウェアで実現できることが分かった．加え
クトの回収，misc はスレッド同期などMark & Sweep
て，表へのアクセスによるオーバヘッドを概算した
以外の処理に要したサイクル数をそれぞれ示してい
ところ，それらはGC 実行サイクル数に対して，平均
る．また，3 本のグラフは左から順に，（MS）既存
1.7%と十分に小さいものであることが確認できた．
のMark & Sweep，（S1）クラスオブジェクトへのポ
6 おわりに
インタを表に登録する提案モデル，（S2）加えてオ
本論文では，GCの代表的アルゴリズムに共通して
フセットを登録する提案モデル，の結果を示してお
存在するオブジェクト探索処理をハードウェア支援
り，(MS)のサイクル数を1として正規化している．
によって高速化する手法を提案した．提案手法の有
結果を見るとほぼ全てのプログラムで（S1），
（S2）
効性をシミュレーションにより評価した結果，既存
が（MS）と比較して，GC の実行サイクル数を削減で
のMark & Sweepと比較して，最大32%のGC 実行サイ
きていることが分かる．これは，提案手法によって
クル数が削減できることを確認した．またGCに要す
MarkObjectが削減されたためである．特に，GCBench
るサイクル数の削減によって，多くのプログラムで
とcrypto.signverifyの2 つのプログラムに関して
GC 実行時の停止時間を短縮できたことが分かった．
は，
既存モデル(MS) においてMarkObjectが占める割
本研究の今後の課題として，スイープ処理のような
合が大きく，提案手法が特に有効に働いたため，提
代表的GCアルゴリズムを構成する処理の高速化手法
案モデル(S2) で最大32.1%のGC実行サイクル数が削
の検討が挙げられる．
減できている．
6 参考文献
また，プログラムの総実行時間とGCによる平均停
[1] McCarthy, J.: Recursive Functions of Symbolic
止時間を計測したところ，既存手法と比較して，実
Expressions and Their Computation by Machine, Part I,
行時間と停止時間がともに改善されたことが分かっ
Communications of the ACM, Vol. 3, pp. 184–195 (1960).
た．このことから，提案手法によるGC高速化によっ
[2] Wilson, P. R., Johnstone, M. S., Neely, M. and Boles,
て，システムの高いスループットと短い停止時間の
D.: Dynamic Storage Allocation:A Survey and Critical
両立が実現できていることが確認できた．更に，提
Review, Springer-Verlag, pp. 1–116 (1995).
案手法のハードウェアコストを見積もったところ，