可変長文字列をソートする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ワードのオンチップメモリから構成される．文字列の入出力は文字単位の逐次転送により行われる．ソート処理は転送と同時に行われ，転送以外の特別な処理時間を必要としない．オンチップメモリと外部メモリのアクセス時間をそれぞれTI，TEとする．一つのデータを転送するのに要する最小時間はmax（2TI，TE）である．総文字数がN 個の文字列の集合をソートするには2N max（2TI，TE）時間が必要である．