Ceriumによる
正規表現の実装

Masataka Kohagura
8th October , 2013

研究目的

本研究室では、Cell用に作られたCeriumにて並列プログラミングを行なっている。Ceriumにて正規表現を実装し、既存の正規表現との処理速度、処理効率がどれだけ良くなるのかを測定する。

現在は文字列サーチ(Boyer-Moore String Search Algorithm)を実装している。セミグループという、分割したファイルに対して並列処理をさせるような手法によって、効率化を測る。

今週のしたこと

mmapからfreadに変更していたものを、readに変更。

・シンヤさんのRegenを動かしてみた

・シンヤさんの論文「並列化と実行時コード生成を用いた正規表現マッチングの高速化」読み

mmapからfreadへの書き換え(1)

変更前

static st_mmap_t
my_mmap(char *filename)
{
    int fd = -1; 
    int map = MAP_PRIVATE;
    st_mmap_t st_mmap;
    struct stat sb; 

    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);
    }   

    st_mmap.size = fix_byte(sb.st_size,4096);

    st_mmap.file_mmap = (char*)mmap(NULL,st_mmap.size,PROT_READ,map,fd,(off_t)0);    if (st_mmap.file_mmap == (caddr_t)-1) {
        fprintf(stderr,"Can't mmap file\n");
        perror(NULL);
        exit(0);
    }       
    return st_mmap;
}

mmapからfreadへの書き換え(2)

変更後

my_read(TaskManager *manager,char *filename)
{
    int fd = -1;
    st_mmap_t st_mmap;
    struct stat sb;

    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);
    }

    st_mmap.size = fix_byte(sb.st_size,4096);
    st_mmap.file_mmap = (char*)manager->allocate(st_mmap.size);

    sread(fd,st_mmap.file_mmap,st_mmap.size);

    if (st_mmap.file_mmap == (caddr_t)-1) {
        fprintf(stderr,"Can't mmap file\n");
        perror(NULL);
        exit(0);
    }
    return st_mmap;
}

mmapからreadへの書き換え(2)

変更後

my_read(TaskManager *manager,char *filename)
{
    int fd = -1;
    st_mmap_t st_mmap;
    struct stat sb;

    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);
    }

    st_mmap.size = fix_byte(sb.st_size,4096);
    st_mmap.file_mmap = (char*)manager->allocate(st_mmap.size);

    read(fd,st_mmap.file_mmap,st_mmap.size);

    if (st_mmap.file_mmap == (caddr_t)-1) {
        fprintf(stderr,"Can't mmap file\n");
        perror(NULL);
        exit(0);
    }
    return st_mmap;
}

並列化と実行時コード生成を用いた正規表現マッチングの高速化について

・NFA/DFAから同時初期状態有限オートマトン(SSFA)を構成

・Simultaneous Start-state Finite Automata

・「NFAの全状態について、それぞれを初期状態とした場合の状態遷移」を　同時初期状態遷移(SST)と呼んでいる。