LRCによる多重参照管理方式  [in Japanese] Multiple Reference Management by LRC  [in Japanese]

KL1はフラットGHCに基づく並列論理型言語であり,並列処理システムの実現にとって不可欠である同期や通信等の基本概念が自然に記述できる。ただし,KL1のようなメモリセルの破壊的書き換えを許さない並列論理型言語を単純に実装すると,メモリ領域を単調かつ急速に消費してしまう。この結果,メモリ参照の局所性が悪い一括型GCを頻発してしまい,キャッシュのミスヒットやページフォールトが多くなる。一方,ICOTにおいて開発を進めている並列推論マシンPIMのように,並列マシンによってKL1を並列処理する場合,プログラムの実行を並列に行なうだけでなく,GCも並列に実行する必要がある。このため,KL1の並列処理には,インクリメンタルGCのように,不要になったメモリ領域を各要素プロセッサが実行時に回収し再利用する機構が重要となる。実行時のGC方式としては,各データオブジェクトにそこへの参照数を示すカウンタを設ける参照カウンタ方式が一般的である。しかし,この方式では,原理的にポインタの一語長分の参照カウンタ領域が必要であり,参照カウンタ更新のためのオーバヘッドも大きい。これに対し,実際のプログラムの実行では,データオブジェクトへの参照数が1または2の場合が多いことを利用した方式が幾つか提案されている。多重参照ビット(MRB:Multiple Reference Bit)方式では,データオブジェクトではなく,ポインタ上の1ビットのフラグ(MRB)を用いて参照カウンタに相当する情報を表現する。これによって,メモリ資源を節約し,操作を簡素化している。ただし,1ビット分のMRBでは一度多重参照になったデータオブジェクトは参照数が0となっても回収できないため,メモリの再利用という点では完全ではない。このため,MRB方式は一括型のGCと併用する必要がある。本稿では,遅延参照カウント(LRC:Lazy Reference Count)と呼ぶGC方式を提案する。LRC方式は,2ワードからなる参照カウント付き間接参照セルを用いて参照数を表現し,多重参照か単一参照かはMRBと同様のポインタタグによって識別する。これにより,MRB方式の長所を活かしたまま,MRB方式における回収の不完全さを補うことができる。