階層的グループ化に基づくコピー型ごみ集めによる局所性改善

IPSJ Web Site 8 References

Bibliographic Information

Other Title
  • カイソウテキ グループカ ニ モトヅク コピーカタゴミ アツメ ニ ヨル キョクショセイ カイゼン
  • Improving Locality by Copying Garbage Collection Based on Hierarchical Clustering

Search this article

Abstract

プロセッサとメモリの性能差は近年拡大しており，仮想記憶の局所性だけでなく，キャッシュの局所性を改善することも重要となっている．ごみ集め（GC）の1つであるコピーGCでは，2つの部分空間の片方から生きているオブジェクトのみを他方の部分空間にコピー（移動）する．Cheneyの非再帰的なコピーGCは，コピー先の部分空間の一部をスキャン待ちオブジェクトのキューとして利用するので追加の作業領域をほとんど必要としないが，オブジェクトが幅優先順にコピーされる．しかし幅優先順のコピーでは，多くの応用プログラムでメモリアクセスの空間的局所性が低下し，キャッシュミスや仮想記憶のミス（ページフォールトやTLBミス）が増加する．本研究では，できるだけ深さ優先順にコピーする方式を提案する．実際にはそれでも局所性の改善は限定的なため，さらに，オブジェクトを階層的にグループ化してコピーする方式を提案する．これらの再帰的なコピーGCではコピーの際に使用するスタックなどの作業領域のサイズが最悪の場合に生きているオブジェクトの個数に比例するという問題がある．そこで，限られた作業領域でできるだけ多くの部分に深さ優先コピーや階層的グループ化を高速に適用する方式を提案する．本論文では提案手法によるミス率低減効果の測定結果も示す．

The increasing processor-memory performance gap makes improving cache locality as important as virtual memory locality. Copying garbage collection moves all live objects from one semi-space to another semi-space. Cheney’s nonrecursive copying algorithm employs a section of the destination semi-space as a queue of unscanned objects and requires only a negligible working space, but objects are copied in breadth-first order. However, in many applications, the breadth-first copying makes the spatial memory access locality worse and increases cache misses, page faults and TLB misses. In this paper, we propose a mostly depth-first copying algorithm. Since depth-first copying only achieves limited locality improvement, we also propose a new “hierarchical clustering” copying algorithm. Since these recursive copying algorithms require a working space (e.g., a stack) for recording unscanned objects whose worst-case size is proportional to the number of live objects, we also propose an efficient technique which achieves depth-first copying or hierarchical clustering as approximately as possible using bounded workspace. This paper also shows the effect of our approach on miss-rate reduction.

Journal

References(8)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top