NDLI: Bit-Parallel Approximate Pattern Matching on the Xeon Phi Coprocessor

Content Provider	IEEE Xplore Digital Library
Author	Tran, T.T. Schindel, S. Yongchao Liu Schmidt, B.
Copyright Year	2014
Description	Author affiliation: Inst. fur Inf., Johannes Gutenberg-Univ. Mainz, Mainz, Germany (Tran, T.T.; Schindel, S.; Yongchao Liu; Schmidt, B.)
Abstract	Bit-parallel pattern matching encodes calculated values in bit arrays. This approach gains its efficiency by performing multiple updates within a machine word. An important parameter is therefore the machine word size (e.g. 32 or 64 bits). With the increasing length of vector registers, the efficient mapping of bit-parallel pattern matching algorithms onto modern high performance computing architectures is becoming increasingly important. In this paper, we investigate an efficient implementation of the Wu-Manber approximate pattern matching algorithm on the Intel Xeon Phi coprocessor. This architecture features a 512-bit long vector processing unit (VPU) as well as a large number of processing cores. We present two mappings of the Wu-Manber algorithm based on auto-vectorization and intrinsics, respectively. Our evaluation shows that the intrinsic approach yields higher performance and gains a speedup of around two orders-of-magnitude compared to a serial CPU version. The source code is available at http://xbitpar.sourceforge.net/.
Starting Page	81
Ending Page	88
File Size	271730
Page Count	8
File Format	PDF
ISBN	9781479969050
ISSN	15506533
DOI	10.1109/SBAC-PAD.2014.37
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-10-22
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Pattern matching Vectors Instruction sets Approximation algorithms Coprocessors Computer architecture Graphics processing units bioinformatics. bit-parallelism approximate pattern matching Wu-Manber algorithm OpenMP Intel Xeon Phi
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient GCD Computation for Big Integers on Xeon Phi Coprocessor

Accelerating time series subsequence matching on the Intel Xeon Phi many-core coprocessor

Finite element numerical integration on Xeon Phi coprocessor

Investigating large-scale feature matching using the Intel® Xeon Phi™ coprocessor

Behavior of MDynaMix on Intel Xeon Phi Coprocessor

Optimizing the MapReduce framework on Intel Xeon Phi coprocessor

Efficient Implementation of Many-Body Quantum Chemical Methods on the Intel® Xeon Phi Coprocessor

Practical SIMD Vectorization Techniques for Intel® Xeon Phi Coprocessors

Hierarchical Parallelism of Bit-Parallel Algorithm for Approximate String Matching on GPUs

Bit-Parallel Approximate Pattern Matching on the Xeon Phi Coprocessor

Similar Documents

Efficient GCD Computation for Big Integers on Xeon Phi Coprocessor

Accelerating time series subsequence matching on the Intel Xeon Phi many-core coprocessor

Finite element numerical integration on Xeon Phi coprocessor

Investigating large-scale feature matching using the Intel® Xeon Phi™ coprocessor

Behavior of MDynaMix on Intel Xeon Phi Coprocessor

Optimizing the MapReduce framework on Intel Xeon Phi coprocessor

Efficient Implementation of Many-Body Quantum Chemical Methods on the Intel® Xeon Phi Coprocessor

Practical SIMD Vectorization Techniques for Intel® Xeon Phi Coprocessors

Hierarchical Parallelism of Bit-Parallel Algorithm for Approximate String Matching on GPUs

Bit-Parallel Approximate Pattern Matching on the Xeon Phi Coprocessor