Cerium Task Manager
による正規表現の実装

Masataka Kohagura
10th December , 2013

研究目的

マルチコア CPU を最大限に活かすためには、並列プログラミングによる並列度を向上させなければならないが、実装が難しい。当研究室では Cerium Libraryを提供することによって並列プログラミングを容易にしているが、ファイル読み込み等のI/O部分に関してはまだ実装されていない。

本研究ではその例題として正規表現を実装し、I/Oの並列化の設計・実装によって既存の正規表現の処理速度、処理効率を上げる。

今週のしたこと

read関数によるfileの順次読み込み
(読み込み部分をread()からpread()へ変更)
Read Taskのブロック化 (1つずつ起動していたものを、ブロック単位で起動するようにした)
MapReduce関数の整理

readからpreadへ

変更前

int *fd = (int *)s->get_input(rbuf,0);  ///ファイルディスクリプタの受取
long readsize = (long)s->get_param(0);
long task_number = (long)s->get_param(1);

char text[(long)readsize];

read(*fd,text,(long)readsize);

s->printf("[start task No. %d]\n",task_number);
s->printf("%s\n",text);

変更後

pread(*fd, text, (long)read_size , division_size*task_number);

pread

read(int fd, void *buf, size_t count);

pread(int fd, void *buf, size_t count, off_t offset);

fd:ファイルディスクリプタ
buf:readするDataの格納領域
count:どれだけの量(byte)を読み込むか
offset:ファイルの先頭からどれだけの量(byte)を飛ばして読み込むのか

read関数だと、Taskの起動する順番やタイミングによって同じ場所を読み込んだりしてしまう。read関数は読み込んだ後にファイルディスクリプタをずらしてしまうので、そのような現象が起こると考えられる。

pread関数だと、ファイルディスクリプタを動かさずにoffsetを取ることで読み込む場所が替えることができる。これだと、上記の現象が起こらずにすむ。

readでの読み込みの失敗例

% ./fileread -file d.txt
filesize     : 16398
one_task_size: 16384
task_num     : 2
[start task No. 0]
firstaaaaaaaaaaaaaaaaaaaaaa...16380
doin
[start task No. 1]
firstaaaaaaaaa

[start task No. 0]
gxbaaabaaabab
[start task No. 1]
gxbaaabaaabab

Read Taskのblock化

変更前

run_start(TaskManager *manager,char *filename)
{
    HTask *read;
    int *fd = (int*)manager->allocate(sizeof(int));

    if ((*fd=open(filename,O_RDONLY,0666))==0) {
        fprintf(stderr,"can't open %s\n",filename); 
    }
        ...

    for(int task_number = 0; task_number < task_num; task_number++){
        read = manager->create_task(READ_TASK);
        read->set_cpu(spe_cpu);

        [task settings(省略)]

    }
}

変更後

run_start(TaskManager *manager,char *filename)
{
    int *fd = (int*)manager->allocate(sizeof(int));

    if ((*fd=open(filename,O_RDONLY,0666))==0) {
        fprintf(stderr,"can't open %s\n",filename);
    }

    if (fstat(*fd,sb)) {
        fprintf(stderr,"can't fstat %s\n",filename);
    }
        ...

    FilereadPtr fr = (FilereadPtr)manager->allocate(sizeof(Fileread));

    HTaskPtr run = manager->create_task(RUN_BLOCKS, (memaddr)&fr->self, sizeof(memaddr),0,0);
    run->spawn();
}

RUN_BLOCKS

SchedDefineTask1(RUN_BLOCKS,run16);

run16(SchedTask *manager, void *in, void *out) {

    FilereadPtr fr = (FilereadPtr)in;
    HTaskPtr wait;

    for (int i = 0; (fr->left_size > 0) && (i < fr->task_blocks); i++) {
        HTaskPtr read = manager->create_task(Read_task);
        read->set_cpu(fr->cpu);

        if (i == fr->task_blocks / 2) wait = read;

        [task settings(省略)]

    }
    return 0;
}

Taskを1個1個起動ではなくブロック単位で起動している理由は、メモリの再利用のためである。 1個1個起動すると、その分のメモリが必要となり、Task数が多くなると肥大化する。ブロック単位で起動することでメモリを節約するとともに、メモリの書き換えが少なくて済むので高速化につながる。

Taskのブロック化の図(1)

word countでの実装

run16がブロック単位でTaskを起動する。word countでは48 Task/1block。
ブロック内の処理が全て終わらないと、新しいブロックを生成することができない。
すべてのTaskが終わるまで待つので、オーバヘッドが起こる。

Taskのブロック化の図(2)

filereadでの実装

Cerium Task Manager による正規表現の実装