Parallelization of Dynamic Time Warping on a Heterogeneous Platform

Yao ZHENG; Limin XIAO; Wenqi TANG; Lihong SHANG; Guangchao YAO; Li RUAN

doi:10.1587/transfun.E97.A.2258

Regular Section

Parallelization of Dynamic Time Warping on a Heterogeneous Platform

Yao ZHENG, Limin XIAO, Wenqi TANG, Lihong SHANG, Guangchao YAO, Li RUAN

Author information

Keywords: dynamic time warping (DTW), parallel algorithm, graphics processing unit (GPU), compute unified device architecture (CUDA)

JOURNAL RESTRICTED ACCESS

2014 Volume E97.A Issue 11 Pages 2258-2262

DOI https://doi.org/10.1587/transfun.E97.A.2258

Details

Abstract

The dynamic time warping (DTW) algorithm is widely used to determine time series similarity search. As DTW has quadratic time complexity, the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms. In this paper, we present a parallel approach for DTW on a heterogeneous platform with a graphics processing unit (GPU). In order to exploit fine-grained data-level parallelism, we propose a specific parallel decomposition in DTW. Furthermore, we introduce an optimization technique called diamond tiling to improve the utilization of threads. Results show that our approach substantially reduces computational time.

Corresponding author

Register with J-STAGE for free!