Linked Data Structures のための記憶構成 : MOLDS

概要

論文の詳細を見る
ポインタでリンクされた構造を持つデータ(Linked Data Structures,図2,以下リストデータ)は,記号処理の分野などで重要で不可欠である。リストデータは、ポインタの付け換えによる構造の柔軟性をもち、データ構造の変化しやすい問題の記述や処理に向いている、しかし、リストデータをページング方式のような仮想記憶方式によって管理したとき(図1)、そのデータ構造の柔軟性ゆえ,仮想化の処理と仮想空間上でのガーベージコレクション(GC)において、主記憶・二次記憶間のデータ転送が多くなり、全体の処理効率の低下する傾向がある。記憶空間におけるデータセル間の参照の局所性を大きくすれば、無駄なデータ転送は少なくなる。そのための種々の手法が報告されているが、リストデータの性質を活かした本質的な解決策にはなっていない。この参照の局所性の問題は,構造的に柔軟なデータを一次元的にアドレス付けされた空間で管理することによって生じる。我々は,リストデータをその構造に基づいて記憶空間上に表現し効率の良い記憶管理を実現する記憶構成方式MOLDS(Memory Organization for Linked Data Structures)を提案している。
一般社団法人情報処理学会の論文
1991-02-25