https://link.springer.com/chapter/10.1007/978-3-030-57675-2_37
Abstract
DTW는 타임시리즈 데이터 분야에서 많이 쓰이는 거리 측정방식이다. 그러나 DTW 스코어를 계산하는 것은 시간이 많이드는 작업이다. 기존의 GPU 기반 고속 DTW 기법들은 부족한 메모리 접근 방식 때문에 퍼포먼스를 최대로 이용하지 못했다. 이 논문에서 우리는 CUDA 를 지원하는 GPU 상에서 고속화된 DTW를 수행할 수 있는 병렬화 방식을 제안한다. 이 방식은 빠른 스레드간 커뮤니케이션을 위한 저지연 warp intrinsic에 기반한다. 우리는 우리의 기법인 cuDTW++가 현재의 Volta 기반의 GPU들이 낼 수 있는 이론적 피크 퍼포먼스의 90% 수준에 달하는 것을 검증한다. 이는 기존의 STOA를 뛰어넘는 성능이다.
Dynamic Time Warping (DTW) is a widely used distance measure in the field of time series data mining. However, calculation of DTW scores is compute-intensive since the complexity is quadratic in terms of time series lengths. This renders important data mining tasks computationally expensive even for moderate query lengths and database sizes. Previous solutions to accelerate DTW on GPUs are not able to fully exploit their compute performance due to inefficient memory access schemes. In this paper, we introduce a novel parallelization strategy to drastically speed-up DTW on CUDA-enabled GPUs based on using low latency warp intrinsics for fast inter-thread communication. We show that our CUDA parallelization (cuDTW++) is able to achieve over 90% of the theoretical peak performance of modern Volta-based GPUs, thereby clearly outperforming the previously fastest CUDA implementation (cudaDTW) by over one order-of-magnitude. Furthermore, cuDTW++ achieves two-to-three orders-of-magnitude speedup over the state-of-the-art CPU program UCR-Suite for subsequence search of ECG signals.