ハードウェア化に適した文字列処理アルゴリズムの開発

点击翻译按钮获取中文摘要

ソフトウェアアルコリスムの分野で研究されている文字列処理の高速化手法を専用ハードウェアとして実装することを目標とし,ハードウェア化に適したアルゴリズムの開発を行った.具体的には,近似文字列照合アルゴリズムの高速化について,ハードウェアの実現可能性を考慮した手法の開発を行った.単位計算で処理できるデータサイズを「ワード長」,単位計算を同時に実行できる数を「コア数」とすると,近似文字列照合の単純な解法では,計算の並列化の困難さから,ワード長やコア数が大きくなっても計算時間を短縮できない.これに対し,本研究では以下の3つの高速化手法を提案した.まず,近似文字列照合のための計算のうち,ワード長増大による高速化が可能なものを事前に計算する手法を提案した.近似文字列照合で用いる「編集距離」は,文字の挿入,削除,および置換によって定義され,このうち挿入と削除を考慮することが計算の並列化を困難にしている.置換のみを考えた場合の距離は,2つの文字列の文字一致の数える「マッチカウント問題」の解であり,ワード長の増大による高速化が可能である.本研究では,マッチカウント問題の解と近似文字列照合問題の解関係を明らかにし,マッチカウント問題の解により近似文字列照合問題の解の探索範囲の削減する手法を提案した.次に,マッチカウント問題を解くアルゴリズムとして,コア数増大により高速化を提案した.ワード長の増大による高速化の適用が可能なアルゴリズムは既存手法として既に提案されている.本研究では,文字列をアルファベットについてビット列に変換することで計算の並列化を実現し,既存手法をコア数についての高速化も適用可能になるよう拡張した.最後に,近似文字列照合問題を解くアルゴリズムとして,ワード長の増大による高速化を提案した.コア数の増大による高速化の適用が可能なアルゴリズム既存手法として既に手案されている.本研究では,既存手法で並列に行われる計算の入出力の関係を明らかにし,複数の計算を一度の計算で行う手法を提案した.一度に行うことのできる計算の数はワード長に依存する.