6229

Bit-Parallel Multiple Pattern Matching

Tuan Tu Tran, Mathieu Giraud, Jean-Stephane Varre
LIFL, UMR 8022 CNRS, Universite Lille 1, France
Parallel Processing and Applied Mathematics / Parallel Biocomputing Conference (PPAM / PBC 11), 2011

@inproceedings{TRAN:2011:INRIA-00637227:1,

   hal_id={inria-00637227},

   url={http://hal.inria.fr/inria-00637227/en/},

   title={Bit-Parallel Multiple Pattern Matching},

   author={Tran, Tuan Tu and Giraud, Mathieu and Varr{‘e}, Jean-St{‘e}phane},

   keywords={bit parallelism; pattern matching; sequence comparison; neighborhood indexing; GPU; OpenCL},

   language={English},

   affiliation={Laboratoire d’Informatique Fondamentale de Lille – LIFL – CNRS : UMR8022 – INRIA – IRCICA – Universit{‘e} des Sciences et Technologies de Lille – Lille I – BONSAI – INRIA Lille – Nord Europe – CNRS : UMR8022 – Universit{‘e} des Sciences et Technologies de Lille – Lille I – INRIA},

   booktitle={Parallel Processing and Applied Mathematics / Parallel Biocomputing Conference (PPAM / PBC 11)},

   address={Torun, Poland},

   audience={international },

   year={2011},

   pdf={http://hal.inria.fr/inria-00637227/PDF/pbc11-tran.pdf}

}

Download Download (PDF)   View View   Source Source   

1916

views

Text matching with errors is a regular task in computational biology. We present an extension of the bit-parallel Wu-Manber algorithm to combine several searches for a pattern into a collection of fixed-length words. We further present an OpenCL parallelization of a redundant index on massively parallel multicore processors, within a framework of searching for similarities with seed-based heuristics. We successfully implemented and ran our algorithms on GPU and multicore CPU. Some speedups obtained are more than 60x.
No votes yet.
Please wait...

You must be logged in to post a comment.

* * *

* * *

HGPU group © 2010-2025 hgpu.org

All rights belong to the respective authors

Contact us: