Dynamic Time Warping DTW [] DTW DTW DTW Lower Bound LB [3] DTW [4] SPRING DTW [5] DTW 80% [6] FPGA [7] FPGA Field Programmable Gate Array DTW GPU DTW

Size: px

Start display at page:

Download "Dynamic Time Warping DTW [] DTW DTW DTW Lower Bound LB [3] DTW [4] SPRING DTW [5] DTW 80% [6] FPGA [7] FPGA Field Programmable Gate Array DTW GPU DTW"

はすなうえや
5 years ago
Views:

1 ,a),b),c),d),e) Dynamic Time Warping DTW DTW DTW Xilinx SoC Zynq DTW 04 FPGA Design and Implementation of Real-Time time series classification for Embedded Device Sonoda Yusuke,a) Kuga Morihiro,b) Amagasaki Motoki,c) Iida Masahiro,d) Sueyoshi Toshinori,e) Abstract: It is predicted that tremendous amount of sensor-based devices will be connected to the Internet and there is an increasing demand for time series data analysis method with high processing capability. Dynamic Time Warping (DTW) is one of the most popular similarity measure method and it is an important subroutine in time series data classification. Related works have been proposed to speed up DTW, but there is few case of realizing real-time time series classification using DTW on the relay node. In this paper, We propose a real-time time series classification architecture on Xilinx programmable SoC Zynq. Proposed architecture show that the execution time was reduced by up to /04 times compared to software. Keywords: Time series, Classification, Accelerator, FPGA. Internet of Things IoT -39- Kurokami, Chuo, Kumamoto , Japan -39- Kurokami, Chuo, Kumamoto , Japan a) sonoda@arch.cs.kumamoto-u.ac.jp b) kuga@cs.kumamoto-u.ac.jp c) amagasaki@cs.kumamoto-u.ac.jp d) iida@cs.kumamoto-u.ac.jp e) sueyoshi@cs.kumamoto-u.ac.jp [] c 07 Information Processing Society of Japan

2 Dynamic Time Warping DTW [] DTW DTW DTW Lower Bound LB [3] DTW [4] SPRING DTW [5] DTW 80% [6] FPGA [7] FPGA Field Programmable Gate Array DTW GPU DTW [8][9] Xilinx SoC Zynq Processing System PS Programmable Logic PL DTW PL PS PL PL BRAM Block RAM (a) t (b) DTW :. Dynamic Time Warping DTW K-Nearest Neighbor KNN. DTW C = c, c,..., c n, T = t, t,..., t m () n m C T DTW () DTW [0] n S = (s, s,..., s n ) µ = k= s k () n σ = n n n s k µ (3) k= s k = s k µ σ t (4) s k s k DTW () DTW D(C, T ) D(C, T ) = f(n, m) c 07 Information Processing Society of Japan

3 C U U T T L T L R (a) (b) 3: Lower Bound(LB) : C f(i, j ) f(i, j) = c i t j + min f(i, j) f(i, j ) f(0, 0) = 0, f(i, 0) = f(0, j) = inf (i =,..., n; j =,..., m) (5) DTW DTW O(mn) [] Sakoe-Chiba band R 0 00% R Sakoe-Chiba band R Lower Bounds LB [3] DTW LB DTW LB DTW LB DTW DTW () LB LB Keogh (C, T ) U i = max(t i R : t i+r ), L i = min(t i R : t i+r )? K 3 K 5 4: k-nearest Neighbor m c i U i if c i > U i LB Keogh (C, T ) = L i c i if L i > c i (6) i= 0 otherwise R 3(a) T U L C 3(b) U L LB O(n) DTW. K-Nearest Neighbor KNN 4 KNN KNN K K K.3 Anytime Classification KNN [5] KNN 5 c 07 Information Processing Society of Japan 3

4 Quality of Solution Setup Time Current Solution Time Interrupt 5: Anytime Classification PS Zynq Normalization Classification Normalized & Train Data Normalized Data Distance Lower bounds DTW Accelerator PL 7: i++ No START i= 0 正規化 Cand_seq = Normalized_data Train_seq = Train_db[i] 距離計算次のシーケンスが存在分類 Yes 6: START LB 距離計算 LB < 閾値 DTW 距離計算 [5] KNN rank(x) = { if class(x) = class(xj ) j /(num of class ) otherwise (7) x j x END 3. Xilinx SoC Zynq [] KNN K K LB DTW LB DTW Zynq PL 7 LB LB DTW DTW LB DTW LB 3. 8 PS PL AXI4 LB DTW BRAM LB U L C c 07 Information Processing Society of Japan 4

5 AXI4 AXI4 Lite AXI Reader FIFO Normalized Sequence Memory Controller Lower Bounds DTW 8: DTW distance Result Controller PL SoC N N FIFO FIFO DTW N W DTW N/W N 4. FIFO Train FIFO Candidate Memory 9: ring N- N 4. Xilinx Zynq-7000 XC7Z00- CLG400C Digilent ZYBO[3] Xilinx Vivado 06.4[4] ARM 650MHz FPGA 50MHz 48 FPGA 0 N- 0: LB LB DTW DTW AXI4-Lite PS DTW 9 [7] Processing Element 0 3 N : [ ] [ ] [%] LUT,56 7, LUTRAM 409 6, FF 9,93 35,00 6. BRAM ARM ARM+FPGA UCR time series classification archive[5] : Beef Synthetic Control CBF c 07 Information Processing Society of Japan 5

6 実行時間 [seconds] 高速化率 Beef synthetic_control CBF ARM ARM+FPGA 高速化率 : 3 Beef synthetic control CBF PL ARM N C T (N + N T ) C Beef,06,08 /s Synthetic control 6,936,485 /s CBF 3,084,99 /s 5. Xilinx SoC Zynq PL BRAM (008). [3] Keogh, E. J., Wei, L., Xi, X., Vlachos, M., Lee, S. H. and Protopapas, P. Supporting exact indexing of arbitrarily rotated shapes and periodic time series under Euclidean and warping distance measures, VLDB, Vol.8, No3, pp (009). [4] Sakurai, Y., Faloutsos, C. and Yamamoto, M. Stream monitoring under the time warping distance, Proc. ICDE, pp (007). [5] Ueno, K., Xi, X., Keogh, E. and Lee, D. Anytime classification using the nearest neighbor algorithm with applications to stream mining, Proc. ICDM, pp (006). [6] Zhang, Y., Adl, K. and Glass, J. Fast spoken query detection using lower-bound Dynamic Time Warping on Graphical Processing Units, Proc. ICASSP, pp (0). [7] Wang, Z., Huang, S., Wang, L., Li, H., Wang, Y. and Yang, H. Accelerating subsequence similarity search based on Dynamic time Warping distance with FPGA, Proc. FPGA, pp.53-6 (0). [8] Sart, D., Mueen, A., Najjar, W., Keogh, E. and Niennattrakul. Accelerating Dynamic Time Warping subsequence search with GPUs and FPGAs, Proc. ICDM, pp (00). [9] Hundt, C., Schmidt, B. and Schomer, E. Cudaaccelerated alignment of subsequences in streamed time series data, Proc. ICPP, pp.0-9 (04). [0] Rakthanmanon, T., Campana, B., Mueen, A., Batista, G., Westover, B., Zhu, Q., Zakaria, J. and Keogh, E. Searching and mining trillions of time series subsequences under Dynamic Time Warping, Proc. KDD, pp.6-70 (0). [] Keogh, E. Exact indexing of Dynamic Time Warping, Proc. VLDB, pp (00). [] Xilinx Inc. Zynq 7000 All Programmable SoC < com/support/documentation/data_sheets/j_ ds90-zynq-7000-overview.pdf>( 07--9) [3] Digilent Inc. ZYBO FPGA Board Reference Manual, available from< com/_media/zybo:zybo_rm.pdf>(accessed 07--9). [4] Xilinx Inc. Vivado Design Suite < documentation/sw_manuals_j/xilinx04_/ ug90-vivado-getting-started.pdf>( ) [5] Chen, Y., Keogh, E., Hu, B., Begum, N., Bagnall, A., Mueen, A. and Batista, G. UCR Time Series Classification Archive, available from< edu/~eamonn/time_series_data/>(accessed ). [] Dave Evans. The Internet of Thigs: How the Next Evolution of the Internet Is Changing Everything, CISCO white paper, 0. [] Ding, H., Trajcevski, G., Scheuermann, P., Wang, X. and Keogh, E. Querying and mining of time series data: experimental comparison of representations and distance measures, PVLDB Endowment, Vol., No., pp.54- c 07 Information Processing Society of Japan 6

IPSJ SIG Technical Report Vol.2012-DBS-154 No.9 Vol.2012-IFAT-107 No /8/ (DTW) CrossMatch An efficient method for pattern discovery in

IPSJ SIG Technical Report Vol.2012-DBS-154 No.9 Vol.2012-IFAT-107 No /8/ (DTW) CrossMatch An efficient method for pattern discovery in 1 1 2 2 (DTW) CrossMatch An efficient method for pattern discovery in data streams Machiko Toyoda 1 Yasushj Sakurai 1 Yoshiharu Ishikawa 2 Abstract: Subsequence matching is the problem of finding subsequences