원문: https://ieeexplore.ieee.org/document/6831932
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 algori
ieeexplore.ieee.org
Abstract
DTW알고리즘은 O(n^2)의 시간복잡도를 가진다. 최근 많은 연구자들이 GPU를 이용하여 DTW를 가속화하고 있다. 하지만 DTW의 데이터 의존성으로 인해 대부분의 GPU 기반 DTW 알고리즘은 단순히 순차적 알고리즘을 GPU의 여러 멀티프로세서로 변환하는 테스크 레벨의 병렬화를 수행한다. 이러한 coarse-grained 병렬화의 중요한 이슈는 수행할 수 있는 대상의 크기가 공유 메모리와 GPU의 캐시에 제한된다는 부분이다. 우리는 본 연구를 통해서 prefix computation을 통한 데이터 의존성의 변환방식을 도입했다. 덧붙여 우리는 효율적인 GPU 병렬 DTW알고리즘을 사용하여 사이즈 제한의 문제를 해결했다. 우리 알고리즘의 정확도는 실험을 통해서 검증되었고, 그 속도는 GTX 480 을 이용했을 시, CPU 구현방식에 비해 99배 빨랐다.
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.