Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/HPCC.and.EUC.2013.50 | HPCC/EUC |
Keywords | Field | DocType |
data dependence,parallel processing,nvidia gtx480,time complexity,gpu,gpu based dtw algorithms,graphics processing units,parallel dtw algorithms,cuda,parallelizing dynamic time warping algorithm,prefix computations,multiprocessing systems,dynamic time warping,gpu multiprocessor,serial algorithm,parallel algorithm,time series,instruction sets,time series analysis,parallel algorithms | Graphics,Dynamic time warping,Cache,Instruction set,Computer science,Parallel algorithm,Parallel computing,Algorithm,Multiprocessing,Real-time computing,Time complexity,Computation | Conference |
Citations | PageRank | References |
2 | 0.39 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Limin Xiao | 1 | 107 | 28.51 |
| Yao Zheng | 2 | 3 | 2.10 |
| Wenqi Tang | 3 | 3 | 1.42 |
| Guangchao Yao | 4 | 4 | 2.13 |
| Li Ruan | 5 | 123 | 25.10 |