Cache-conscious階層的グループ化データ配置法：Cache-oblivious配置法との実験的比較

IPSJ Web Site

Bibliographic Information

Other Title
  • Cache-conscious カイソウテキ グループカ データ ハイチホウ : Cache-oblivious ハイチホウ ト ノ ジッケンテキ ヒカク
  • A Cache-conscious Hierarchical-clustering Data Placement Technique: An Experimental Comparison with a Cache-oblivious Technique

Search this article

Abstract

プロセッサとメモリの性能差は拡大していることから，仮想記憶の局所性とともにキャッシュの局所性の改善は重要な課題である．ポインタベースの大規模データ構造上の探索などでは，データオブジェクトの配置が悪いと，キャッシュミス，TLB ミス（場合によっては，ページフォールト）が多発する．このため，コピー型ごみ集めアルゴリズムにおいては，幅優先順，深さ優先順以外に，グループ化された配置を実現するアルゴリズムも提案されてきた．本研究では「階層的グループ化」を提案している．これは，データオブジェクトを複数の階層レベルにおいてグループ化するものであり，メモリ階層上のキャッシュレベル，仮想記憶レベルの双方において局所性を改善する．たとえば，2 分探索木上の探索，および連想リストの配列上の探索において，従来よく用いられてきた幅優先のコピーアルゴリズムと比較して，約 2～5 倍の性能向上が得られた．本論文では以前提案した複数のスタックを用いた cache-oblivious 配置アルゴリズムを発展させた，階層レベルごとのスキャンポインタを使うcache-conscious 配置アルゴリズムを提案し，両者の実験的比較について報告する．

The increasing processor-memory performance gap makes improving the cache locality as important as the virtual memory locality. In some applications, such as search algorithms on pointer-based large data structures, locality-poor data-object placement significantly increases cache misses and TLB misses (and page faults in some cases). Thus, for garbage collection, several clustering copying algorithms have been proposed instead of breadth-first copying and depth-first copying. In this research, we have proposed "hierarchical clustering"which groups data objects at multiple hierarchical levels and provides better locality at both the cache and virtual memory levels of the memory hierarchy. For example, when employing a binary search tree and an array of associative lists, our algorithms achieved approximately two (sometimes five) times speedups compared to the conventional breadth-first copying algorithms. In this paper, we propose a new copying algorithm that achieves cache-conscious data placement with multiple scan pointers for their own levels of memory hierarchy, developed from our previously proposed algorithm that achieves cache-oblivious data placement with multiple stacks; we report an experimental comparison of these two algorithms.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top