A High-Throughput String Search Using AVX for Partially Matching Data

  • Ko Kusudo
    Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
  • Fumihiko Ino
    Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
  • Kenichi Hagihara
    Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Bibliographic Information

Other Title
  • 部分一致を含む文字列に対する探索のAVXによる高スループット化

Search this article

Description

In this paper, we present an AVX (Advanced Vector Extensions) based high-throughput method for a bit-parallel algorithm, aiming at realizing fast string search for partially matching data. An advantage of the bit-parallel algorithm is that, its execution time does not depend on the number and length of partially matching strings. Our method realizes high-throughput string search by extending the bit-parallel algorithm so that it can simultaneously search multiple patterns of different lengths. We use AVX instructions to increase the search throughput per CPU core and employ OpenMP directives to realize data-parallel processing of string search. Furthermore, we improve the data structure so that multiple patterns of different lengths can be efficiently processed at the same time. As a result, we find that our data structure doubles the search throughput. We also find that our method is useful for partially matching large texts such as genomic data.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 2014 (14), 1-7, 2014-02-24

    Information Processing Society of Japan (IPSJ)

Keywords

Details 詳細情報について

  • CRID
    1573387452649257728
  • NII Article ID
    110009675728
  • NII Book ID
    AN10463942
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top