download0 view158
twitter facebook

공공누리This item is licensed Korea Open Government License

Title
High performance parallelization of Boyer–Moore algorithm on many-core accelerators
Author(s)
정요상이명호김직수남덕윤황순욱
Publication Year
2015-06-18
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. Using the two shift rules, pattern matching operations are performed against the target input string in the second phase. The string shift rules calculated in the first phase let parts of the target input string be skipped where there are no matches to be found in the second phase. The second phase is a time consuming process and needs to be parallelized in order to realize
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 microprocessors. For the parallel string matching, the target input data is partitioned amongst multiple threads. Data lying on the threads’ boundaries is searched redundantly so that the pattern string lying on the boundary between two neighboring threads cannot be missed. The redundant data search overheads increases significantly for a large number of threads. For a fixed target input length, the number of possible matches decreases as the pattern length increases. Furthermore, the positions
of the pattern string are spread all over the target data randomly.
This leads to the unbalanced workload distribution among threads. We employ the dynamic scheduling and the multithreading techniques to deal with the load balancing issue. We also use the algorithmic cascading technique to maximize the benefit of the multithreading and to reduce the overheads associated with the redundant data search between neighboring threads. Our parallel implementation leads to ∼17-times speedup on the Xeon Phi and ∼47-times speedup
on the Nvidia Tesla K20 GPU compared with a serial implementation on the host Intel Xeon processor.
Keyword
  Boyer–Moore algorithm; Many-core accelerator; Parallelization; Dynamic scheduling; Multithreading; Algorithmic cascading
Journal Title
Cluster Computing
ISSN
1386-7857
Files in This Item:
There are no files associated with this item.
Appears in Collections:
7. KISTI 연구성과 > 학술지 발표논문
URI
https://repository.kisti.re.kr/handle/10580/14445
Export
RIS (EndNote)
XLS (Excel)
XML

Browse