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

Совместное использование технологий MPI и OpenMP для параллельного поиска похожих подпоследовательностей в сверхбольших временных рядах на вычислительном кластере с узлами на базе многоядерных процессоров Intel Xeon Phi Knights Landing

Авторы

  • Я.А. Краева
  • М.Л. Цымблер

Ключевые слова:

временной ряд
поиск похожих подпоследовательностей
параллельный алгоритм
OpenMP
Intel Xeon Phi
Knights Landing
представление данных в памяти
векторизация вычислений

Аннотация

В настоящее время поиск похожих подпоследовательностей требуется в широком спектре приложений интеллектуального анализа временных рядов: моделирование климата, финансовые прогнозы, медицинские исследования и др. В большинстве указанных приложений при поиске используется мера схожести Dynamic Time Warping (DTW), поскольку на сегодняшний день научное сообщество признает меру DTW одной из лучших для большинства предметных областей. Мера DTW имеет квадратичную вычислительную сложность относительно длины искомой подпоследовательности, в силу чего разработан ряд параллельных алгоритмов ее вычисления на устройствах FPGA и многоядерных ускорителях с архитектурами GPU и Intel MIC. В настоящей статье предлагается новый параллельный алгоритм для поиска похожих подпоследовательностей в сверхбольших временных рядах на кластерных системах с узлами на базе многоядерных процессоров Intel Xeon Phi поколения Knights Landing (KNL). Вычисления распараллеливаются на двух уровнях: на уровне всех узлов кластера — с помощью технологии MPI и в рамках одного узла кластера — с помощью технологии OpenMP. Алгоритм предполагает использование дополнительных структур данных и избыточных вычислений, позволяющих эффективно задействовать возможности векторизации вычислений на процессорных системах Phi KNL. Эксперименты, проведенные на синтетических и реальных наборах данных, показали хорошую масштабируемость алгоритма.

Новые вычислительные технологии

Загрузки

Опубликован

2019-02-10

Выпуск

Том 20 (2019): Выпуск 1.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

Я.А. Краева

Южно-Уральский государственный университет,
Высшая школа электроники и компьютерных наук
просп. Ленина, 76, 454080, Челябинск
• программист

М.Л. Цымблер

Южно-Уральский государственный университет,
Высшая школа электроники и компьютерных наук
просп. Ленина, 76, 454080, Челябинск
• начальник отдела

Библиографические ссылки

  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.