NDLI: High Performance Parallelization of Boyer-Moore Algorithm on Many-Core Accelerators

Content Provider	IEEE Xplore Digital Library
Author	Jeong, Yosang Lee, Myungho Nam, Dukyun Kim, Jik-Soo Hwang, Soonwook
Copyright Year	2014
Abstract	Boyer-Moore (BM) algorithm is a single pattern string matching algorithm. It is considered as the most efficient string matching algorithm and used in many applications. The algorithm first calculates two string shift rules based on the given pattern string in the preprocessing phase. These rules help skip parts of the target input string where there is no match to be found. Using the two shift rules, pattern matching operations are performed against the target input sting in the second phase. The second phase is a time consuming process and needs to be parallelized to achieve the high performance string matching. In this paper, we parallelize the BM algorithm on the latest many core accelerators such as the Intel Xeon Phi and the Nvidia Tesla K20 GPU, along with the general-purpose multi-core processors. We partition the target input data amongst multiple threads for parallel execution. Data lying on the threads' boundaries need to be copied redundantly so that the pattern string lying on the boundary can be found. As the target length increases, the algorithm incurs increased matching operations. Also, as the pattern length increases, the number of possible matches decreases. This can potentially lead to the unbalanced workload distribution among threads. Furthermore, the redundant data copy significantly overloads the on-chip shared memories of the GPU for a large number of threads. We use the dynamic scheduling and the multithreading techniques to solve the load balancing problem. We also use the algorithmic cascading technique to reduce the burden on the shared memories of the GPU. Our parallel implementation leads to ~ 17-times speedup on the Xeon Phi and ~ 45-times speedup on the Nvidia Tesla K20GPU compared with a serial implementation on the host Intel Xeon processor.
Starting Page	265
Ending Page	272
File Size	880482
Page Count	8
File Format	PDF
ISBN	9781479958412
DOI	10.1109/ICCAC.2014.20
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-09-08
Publisher Place	United Kingdom
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Algorithmic cascading Many-core accelerator Multicore processing Instruction sets Heuristic algorithms Graphics processing units Dynamic scheduling Partitioning algorithms Boyer-Moore algorithm Multithreading Pattern matching Parallelization
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

High performance parallelization of Boyer–Moore algorithm on many-core accelerators

Novel Multi-Layer Network Decomposition boosting acceleration of multi-core algorithms

A trade-off between complexity and performance over multi-core systems

High performance string matching for security applications

Efficient homology computations on multicore and manycore systems

Dynamic thread mapping for high-performance, power-efficient heterogeneous many-core systems

Parallelization methods of the template matching method on graphics accelerators

Performance Optimization of Aho-Corasick Algorithm on a GPU

Efficient multicore scheduling of dataflow process networks

High Performance Parallelization of Boyer-Moore Algorithm on Many-Core Accelerators

Similar Documents

High performance parallelization of Boyer–Moore algorithm on many-core accelerators

Novel Multi-Layer Network Decomposition boosting acceleration of multi-core algorithms

A trade-off between complexity and performance over multi-core systems

High performance string matching for security applications

Efficient homology computations on multicore and manycore systems

Dynamic thread mapping for high-performance, power-efficient heterogeneous many-core systems

Parallelization methods of the template matching method on graphics accelerators

Performance Optimization of Aho-Corasick Algorithm on a GPU

Efficient multicore scheduling of dataflow process networks

High Performance Parallelization of Boyer-Moore Algorithm on Many-Core Accelerators