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.

This paper proposes methods for accelerating DPA by using the CPU and the GPU in a parallel manner. The overhead of naive DPA evaluation software increases excessively as the number of points in a trace or the number of traces is enlarged due to the rapid increase of file I/O overhead. This paper presents some techniques, with respect to DPA-arithmetic and file handling, which can make the overhead of DPA software become not extreme but gradual as the increase of the amount of trace data to be processed. Through generic experiments, we show that the software, equipped with the proposed methods, using both CPU and GPU can shorten the time for evaluating the DPA resistance of devices by almost half.