DocumentCode :
592036
Title :
Efficient Implementations of the Approximate String Matching on the Memory Machine Models
Author :
Nakano, Kaoru
Author_Institution :
Dept. of Inf. Eng., Hiroshima Univ., Higashi Hiroshima, Japan
fYear :
2012
fDate :
5-7 Dec. 2012
Firstpage :
233
Lastpage :
239
Abstract :
The Discrete Memory Machine (DMM) and the Unified Memory Machine (UMM) are theoretical parallel computing models that capture the essence of the shared memory access and the global memory access of GPUs. The approximate string matching for two strings X and Y is a task to find a sub string of Y most similar to X. The main contribution of this paper is to show efficient implementations of approximate string matching on the memory machine models. Our best implementation for strings X and Y with length m and n (m≤n), respectively, runs in O(mn/w + ml) time units using n threads both on the DMM on the UMM with width w and latency l.
Keywords :
computational complexity; graphics processing units; parallel architectures; shared memory systems; string matching; CUDA; DMM; GPU; UMM; approximate string matching; discrete memory machine; global memory access; graphical processing unit; memory machine models; shared memory access; theoretical parallel computing models; unified memory machine; Approximation algorithms; Computer architecture; Graphics processing units; Instruction sets; Parallel algorithms; Random access memory; CUDA; GPU; approximate string matching; edit distance; memory machine models;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Networking and Computing (ICNC), 2012 Third International Conference on
Conference_Location :
Okinawa
Print_ISBN :
978-1-4673-4624-5
Type :
conf
DOI :
10.1109/ICNC.2012.43
Filename :
6424569
Link To Document :
بازگشت