Ceriumによる
正規表現マッチャの実装

Masataka Kohagura
14th May , 2013

研究目的

本研究室では、Cell用に作られたCeriumにて並列プログラミングを行なっている。様々な例題を実装することにより、どのような問題でも並列処理ができることを証明する。

現在は正規表現を実装している段階であるが、「動的なコード生成を用いた正規表現マッチャの実装」で示されたオートマトンを並列実装する。これを実装することによって、Ceriumがオートマトンで表される問題に対して並列実装できることを証明する。

word_countのi_data o_data

word_count

o_dataは1つのタスク当たり4つの要素が吐き出される。
それらの配列をひとまとめにした配列をPrint.ccが読み込み、word_num、line_numの合計数、フラグ管理で正確にカウントできるようにされている。

regexのi_data o_data(予定)

regex

問題点

i_dataはword_countと同様にメモリに割り当てられた文字列である。それの先頭に検索したい文字列を入れて、プログラムが検索できるようにしたい。
問題点として、o_dataがそのtask内でマッチしたラインの先頭アドレスを格納したいので、1task当たりのo_dataが可変長となる。 o_dataのメモリをどう確保するべきなのか。 行の途中で分割されてしまった場合、flagをどう持たせたらいいのだろうか。

word_count/main.cc run_start() 

/* out用のdivision_size. statusが2つなので、あわせて16byteになるように、
long long(4byte)を使用 */

w->division_out_size = sizeof(unsigned long long)*4;
int out_size = w->division_out_size*out_task_num;
w->o_data = (unsigned long long *)manager->allocate(out_size);
w->out_size = 4;