Parallelizing Dynamic Time Warping Algorithm Using Prefix Computations on GPU

The dynamic time warping (DTW) algorithm has O(n2) time complexity, which indicates that it is hard to process large-scale time series within an acceptable time. Recently, many researchers have used graphics processing units (GPUs) to accelerate the algorithm. Owing to the data dependence of DTW, however, most of existing GPU-based DTW algorithms exploits task-level parallelism by simply replicating the serial algorithm on every multiprocessor of a GPU. The fundamental issue with such coarse-grained parallelism is that the solvable problem size is severely limited by the share memory and cache of a GPU multiprocessor. In this study, we introduce a specific transformation of data dependence by using prefix computations. Further, we propose an efficient GPU-parallel DTW algorithm to address the problem of instance sizes limitation. The efficiency of our algorithm is validated through experiments, which demonstrate improved performance over existing GPU-based task-level parallel DTW algorithms. Our experimental results indicate speedups up to 99 times faster on NVIDIA GTX480, compared to CPU implementations.