平成 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). 案手法のハードウェアコストを見積もったところ，