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   

696

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...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: