Header menu link for other important links
X
eMDPM: Efficient Multidimensional Pattern Matching Algorithm for GPU
Raj S, Chodnekar S.P, ,
Published in Springer Singapore
2019
Volume: 851
   
Pages: 97 - 104
Abstract

Parallelizing pattern matching in multidimensional images is very vital in many applications to improve the performance. With SIMT architectures, the performance can be greatly enhanced if the hardware threads are utilized to the maximum. In the case of pattern matching algorithms, the main bottleneck arises due to the reduction operation that needs to be performed on the multiple parallel search operations. This can be solved by using Shift-Or operations. The recent trend has shown the improvement in pattern matching using Shift-Or operations for bit pattern matching. This has to be extended for multiple dimensional images like hyper-cubes. In this paper, we have extended the Shift-Or pattern matching for multidimensional images. The algorithm is implemented for GPU architectures. The complexity of the proposed algorithm is @ where m is the number of dimensions, n is the size of the array if the multidimensional matrix values are placed in a single dimensional array, k is the size of the pattern and w is the size of the tile. From the result analysis it is found that the performance is maximum, when the pattern size matches the tile size and it is less than 64. This restriction is due to the size of the warp considered. © 2019, Springer Nature Singapore Pte Ltd.

About the journal
JournalData powered by TypesetSmart Innovations in Communication and Computational Sciences Advances in Intelligent Systems and Computing
PublisherData powered by TypesetSpringer Singapore
ISSN2194-5357
Open Access0