Efficient Implementations of the Approximate String Matching on the Memory Machine Models
Efficient Implementations of the Approximate String Matching on the Memory Machine Models
复制标题
记忆机模型上近似字符串匹配的高效实现
DOI：
10.1109/icnc.2012.43
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
K. Nakano
中科院分区：
文献类型：
--
作者：
K. Nakano
DMM （Discrete Memory Machine）和UMM （Unified Memory Machine）是理论上的并行计算模型，它们捕捉了gpu的共享内存访问和全局内存访问的本质。两个字符串X和Y的近似字符串匹配任务是找到Y中与X最相似的子字符串。本文的主要贡献是展示了在内存机模型上近似字符串匹配的有效实现。对于长度分别为m和n （m≤n）的字符串X和Y，我们的最佳实现是在宽度为w、延迟为1的UMM的DMM上使用n个线程，以O（mn/w + ml）时间单位运行。
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.