Optimal implementations of the approximate string matching and the approximate discrete signal matching on the memory machine models

摘要

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 graphics processing units. The approximate string matching (ASM) for two strings X and Y is a task to find a substring of Y most similar to X. The main contribution of this paper is to show efficient implementations of ASM on the memory machine models. Our best implementation for strings X and Y with length m and n(m ≤ n), respectively, runs in 0((mn/w) ＋ ml) time units using n threads both on the DMM and on the UMM with width w and latency l. We also show that any implementation of the ASM on the DMM and the UMM needs O((mn/w) ＋ ml) time units. Thus, our implementations for the DMM and the UMM are optimal. Finally, we show that the approximate discrete signal matching of two signals can be computed in the same time complexity.