可変長文字列をソートするVLSIのレジスタ転送レベルにおける設計

林 世紀  田中 譲  

誌名
電子情報通信学会論文誌 A   Vol.J73-A   No.4   pp.829-838
発行日: 1990/04/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: アルゴリズムとデータ構造,計算複雑度
キーワード: 


本文: PDF(783.6KB)>>
論文を購入




あらまし: 
可変長文字列を直接ソートすることが可能なVLSIアルゴリズムが田中により提案されている.本論文では,そのアルゴリズムに基づいたハードウェアソータのレジスタ転送レベルにおける設計を示す.ソータは一つの専用チップと一つの外部メモリから構成される.この専用チップはVソートエンジンコアと呼ばれる.外部メモリの全ワード数をNとする.このVソートエンジンにより,総文字数がN 個以下の文字列の集合をソートすることができる.Vソートエンジンコアのレベル数をLとすると,2L個の文字列をソートできる.Vソートエンジンコアの中のレベルlは,一つの論理セルと2lワードのオンチップメモリから構成される.文字列の入出力は文字単位の逐次転送により行われる.ソート処理は転送と同時に行われ,転送以外の特別な処理時間を必要としない.オンチップメモリと外部メモリのアクセス時間をそれぞれTITEとする.一つのデータを転送するのに要する最小時間はmax(2TITE)である.総文字数がN 個の文字列の集合をソートするには2N max(2TITE)時間が必要である.