DOI: https://doi.org/10.26089/NumMet.v20r104

The use of MPI and OpenMP technologies for subsequence similarity search in very long time series on a computer cluster system with nodes based on the Intel Xeon Phi Knights Landing many-core processor

Authors

  • Ya.A. Kraeva
  • M.L. Zymbler

Keywords:

time series
similarity search
parallel algorithm
OpenMP
Intel Xeon Phi
Knights Landing
data layout
vectorization

Abstract

Nowadays, the subsequence similarity search is required in a wide range of time series mining applications: climate modeling, financial forecasts, medical research, etc. In most of these applications, the Dynamic Time Warping (DTW) similarity measure is used, since DTW is empirically confirmed as one of the best similarity measures for the majority of subject domains. Since the DTW measure has a quadratic computational complexity with respect to the length of query subsequence, a number of parallel algorithms for various many-core architectures are developed, namely FPGA, GPU, and Intel MIC. In this paper we propose a new parallel algorithm for subsequence similarity search in very large time series on computer cluster systems with nodes based on Intel Xeon Phi Knights Landing (KNL) many-core processors. Computations are parallelized on two levels as follows: by MPI at the level of all cluster nodes and by OpenMP within a single cluster node. The algorithm involves additional data structures and redundant computations, which make it possible to efficiently use the capabilities of vector computations on Phi KNL. Experimental evaluation of the algorithm on real-world and synthetic datasets shows that the proposed algorithm is highly scalable.

New computational technologies

Downloads

Published

2019-02-10

Issue

Vol. 20 (2019): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biographies

Ya.A. Kraeva

South Ural State University,
School of Electronic Engineering and Computer Science
• Programmer

M.L. Zymbler

South Ural State University,
School of Electronic Engineering and Computer Science
• Head of Department

References

  1. V. V. Voevodin and Vl. V. Voevodin, The Parallel Computing (BHV-Petersburg, St. Petersburg, 2002).
  2. V. Athitsos, P. Papapetrou, M. Potamias, et al., “Approximate Embedding-Based Subsequence Matching of Time Series,” in Proc. ACM SIGMOD Int. Conf. on Management of Data. Vancouver, Canada, June 10-12, 2008 (ACM Press, New York, 2008), pp. 365-378.
  3. D. F. Bacon, S. L. Graham, and O. J. Sharp, “Compiler Transformations for High-Performance Computing,” ACM Comput. Surv. 26 (4), 345-420 (1994).
  4. D. J. Berndt and J. Clifford, “Using Dynamic Time Warping to Find Patterns in Time Series,” in Proc. 3rd Int. Conf. Knowledge Discovery and Data Mining, Seattle, USA. July 31-August 1, 1994 (AAAI Press, Palo Alto, 1994), pp. 359-370.
  5. G. Chrysos, “Intel Xeon Phi Coprocessor (Codename Knights Corner),” in Proc. 2012 IEEE Hot Chips 24th Symposium (HCS), Cupertino, USA, August 27-29, 2012 (IEEE Press, New York, 2012),
    doi 10.1109/HOTCHIPS.2012.7476487
  6. H. Ding, G. Trajcevski, P. Scheuermann, et al., “Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures,” J. Proc. VLDB Endowment 1 (2), 1542-1552 (2008).
  7. A. W. Fu, E. Keogh, L. Y. H. Lau, et al., “Scaling and Time Warping in Time Series Querying,” VLDB J. 17 (4), 899-921 (2008).
  8. W. Gropp, “MPI 3 and Beyond: Why MPI is Successful and What Challenges It Faces,” in Lecture Notes in Computer Science (Springer, Berlin, 2012), Vol. 7490, pp. 1-9.
  9. E. J. Keogh and C. A. Ratanamahatana, “Exact Indexing of Dynamic Time Warping,” Knowl. Inf. Syst. 7 (3), 358-386 (2005).
  10. P. S. Kostenetskiy and A. Y. Safonov, “SUSU Supercomputer Resources,” in Proc. 10th Annual Int. Scientific Conf. on Parallel Computing Technologies (PCT 2016), Arkhangelsk, Russia, March 29-31, 2016 CEUR Workshop Proc. 1576, 561-573 (2016).
  11. Ya. Kraeva and M. Zymbler, “An Efficient Subsequence Similarity Search on Modern Intel Many-Core Processors for Data Intensive Applications,” in Selected Papers of XX Int. Conf. on Data Analytics and Management in Data Intensive Domains (DAMDID/RCDL 2018), Moscow, Russia, October 9-12, 2018. CEUR Workshop Proc. Vol. 2277, 143-151 (2018).
  12. V. Kumar, A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing (Benjamin/Cummings, Redwood City, 1994).
  13. S. Lim, H. Park, and S. Kim, “Using Multiple Indexes for Efficient Subsequence Matching in Time-Series Databases,” in Lecture Notes in Computer Science (Springer, Berlin, 2006), Vol. 3882, pp. 65-79.
  14. T. Mattson, “Introduction to OpenMP,” in Proc. 2006 ACM/IEEE Conf. on Supercomputing, Tampa, USA, November 11-17, 2006 (ACM Press, New York, 2006),
    doi 10.1145/1188455.1188673
  15. F. N. Mazandarani and M. Mohebbi, “Wide Complex Tachycardia Discrimination Using Dynamic Time Warping of ECG Beats,” Comput. Meth. Prog. Biomed. 164, 238-249 (2018).
  16. A. V. Movchan and M. L. Zymbler, “Parallel Implementation of Searching the Most Similar Subsequence in Time Series for Computer Systems with Distributed Memory,” in Proc. 10th Annual Int. Scientific Conf. on Parallel Computing Technologies (PCT 2016), Arkhangelsk, Russia, March 29-31, 2016. CEUR Workshop Proc. Vol. 1576, 615-628 (2016).
  17. K. Pearson, “The Problem of the Random Walk,” Nature 72 (1), 342 (1905).
  18. T. Rakthanmanon, B. Campana, A. Mueen, et al., “Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping,” in Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Beijing, China, August 12-16, 2012 (ACM Press, New York, 2012), pp. 262-270.
  19. U. Rebbapragada, P. Protopapas, C. E. Brodley, and C. Alcock, “Finding Anomalous Periodic Time Series,” Mach. Learn. 74 (3), 281-313 (2009).
  20. H. Sakoe and S. Chiba, Readings in Speech Recognition (Morgan Kaufmann, San Francisco, 1990), pp. 159-165.
  21. Y. Sakurai, C. Faloutsos, and M. Yamamuro, “Stream Monitoring under the Time Warping Distance,” in Proc. 23rd Int. Conf. on Data Engineering, Istanbul, Turkey, April 15-20, 2007 (IEEE Press, Washington, DC, 2007), pp. 1046-1055.
  22. D. Sart, A. Mueen, W. A. Najjar, et al., “Accelerating Dynamic Time Warping Subsequence Search with GPUs and FPGAs,” in Proc. 2010 IEEE Int. Conf. on Data Mining, Sydney, Australia, December 14-17, 2010} (IEEE Press, Washington, DC, 2010), pp. 1001-1006.
  23. A. Sodani, “Knights Landing (KNL): 2nd Generation Intel Xeon Phi Processor,” in 2015 IEEE Hot Chips 27th Symposium (HCS), Cupertino, CA, August 22-25, 2015 (IEEE Press, New York, 2015), pp. 1-24.
  24. I. Sokolinskaya and L. Sokolinsky, “Revised Pursuit Algorithm for Solving Non-Stationary Linear Programming Problems on Modern Computing Clusters with Manycore Accelerators,” in Communications in Computer and Information Science (Springer, Cham, 2016), Vol. 687, pp. 212-223.
  25. A. Shabib, A. Narang, C. P. Niddodi, et al., “Parallelization of Searching and Mining Time Series Data using Dynamic Time Warping,” in Proc. 2015 Int. Conf. on Advances in Computing, Communications and Informatics, Kochi, India, August 10-13, 2015 (IEEE Press, New York, 2015), pp. 343-348.
  26. S. Srikanthan, A. Kumar, and R. Gupta, “Implementing the Dynamic Time Warping Algorithm in Multithreaded Environments for Real Time and Unsupervised Pattern Discovery,” in Proc. 2011 2nd Int. Conf. on Computer and Communication Technology, Allahabad, India, September 15-17, 2011 (IEEE Press, New York, 2011), pp. 394-398.
  27. N. Takahashi, T. Yoshihisa, Y. Sakurai, and M. Kanazawa, “A Parallelized Data Stream Processing System Using Dynamic Time Warping Distance,” in Proc. 2009 Int. Conf. on Complex, Intelligent and Software Intensive Systems, Fukuoka, Japan, March 16-19, 2009 (IEEE Press, New York, 2009), pp. 1100-1105.
  28. J. Tarango, E. Keogh, and P. Brisk, “Instruction Set Extensions for Dynamic Time Warping,” in Proc. Int. Conf. on Hardware/Software Codesign and System Synthesis, Montreal, Canada, September 29-October 4, 2013 (IEEE Press, Piscataway, 2013),
    doi 10.1109/CODES-ISSS.2013.6659005
  29. Z. Wang, S. Huang, L. Wang, et al., “Accelerating Subsequence Similarity Search Based on Dynamic Time Warping Distance with FPGA,” in Proc. ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays, Monterey, USA, February 11-13, 2013 (ACM Press, New York, 2013), pp. 53-62.
  30. Y. Zhang, K. Adl, and J. R. Glass, “Fast Spoken Query Detection Using Lower-Bound Dynamic Time Warping on Graphical Processing Units,” in Proc. 2012 IEEE Int. Conf. on Acoustics, Speech and Signal Proc., Kyoto, Japan, March 25-30, 2012 (IEEE Press, New York, 2012), pp. 5173-5176.
  31. M. Zymbler, “Best-Match Time Series Subsequence Search on the Intel Many Integrated Core Architecture,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2015), Vol. 9282, pp. 275-286.