パイプラインマージソータに於ける可変長レコードソート用String Length Tuningアルゴリズムとその評価

概要

論文の詳細を見る
VLSI技術によって汎用性のあるアルゴリズムを専用ハードウェアで実現する場合,そのハードウェア化による高速性を追求するのと同様に,実用時のパラメータの変動に対応すべく,柔軟性を持たせることも重要である.我々はこうした目的を目指してパイプラインマージソータの([1][2])研究開発を続いてきた.ハードウェアソータに於て重要なパラメータの一つはレコード長である.そのレコード長の変化には,ファイル内では固定長レコード(ファイル内では固定でファイル間では可変),及び可変長レコード(ファイル内でも可変),という二つの状況が考えられる.前者に対しては,我々はすでにString Length Tuningアルゴリズムを開発し([6]),ハードウェアで実装した.更に,後者についてはソータの記憶管理方式について詳しく考察し,ブロック分割記憶管理方式によって,可変長レコードソートをサポート出来ることを示した.本稿では,可変長レコードソートに於て,ソータのメモリを効率的に管理できるString Length Tuningアルゴリズムを紹介し,その性能を評価する.
一般社団法人情報処理学会の論文
1986-10-01