Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора

Михаил Леонидович Цымблер, Яна Александровна Краева

Аннотация


Лейтмотив представляет собой пару подпоследовательностей временного ряда, наиболее похожих друг на друга. Задача поиска лейтмотивов встречается в широком спектре предметных областей: медицина, биология, предсказание погоды и др. В работе предложен новый параллельный алгоритм поиска лейтмотива во временном ряде на платформе графического процессора для случая, когда входные данные могут быть размещены в оперативной памяти. Предлагаемый алгоритм использует в качестве основы алгоритм MK, в котором применяется евклидово расстояние и неравенство треугольника для отбрасывания бесперспективных лейтмотивов без вычисления расстояния. MK позволяет сократить время поиска в разы по сравнению с другими последовательными алгоритмами, однако его производительность значительно снижается на временных рядах, имеющих длину от сотен тысяч элементов. Распараллеливание выполнено с помощью технологии программирования OpenACC. Разработаны матричные структуры данных, позволяющие эффективно распараллелить вычисления на графическом процессоре. Представлены результаты вычислительных экспериментов на реальных и синтетических наборах данных, подтверждающих высокую масштабируемость разработанного алгоритма.


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


временной ряд; поиск лейтмотивов; параллельный алгоритм; NVIDIA GPU; OpenACC

Полный текст:

PDF

Литература


Zymbler M.L. A Parallel Discord Discovery Algorithm for Time Series on Many-core Accelerators. Numerical methods and programming. 2019. Vol. 20, no. 3. P. 211–223. DOI: 10.26089/NumMet.v20r320

Balasubramanian A., Wang J., Prabhakaran B. Discovering Multidimensional Motifs in Physiological Signals for Personalized Healthcare. J. Sel. Topics Signal Processing. 2016. Vol. 10, no. 5. P. 832–841. DOI: 10.1109/JSTSP.2016.2543679.

Brown A., Yemini E., Grundy L., Jucikas T., Schafer W. A Dictionary of Behavioral Motifs Reveals Clusters of Genes Affecting Caenorhabditis Elegans Locomotion. Proceedings of the National Academy of Sciences of the United States of America. 2012. Vol. 110, no. 2. P. 791–796. DOI: 10.1073/pnas.1211447110.

Cheng J., Grossman M., McKercher T. Professional CUDA C Programming. 1st Edition. Wrox, 2014. 528 p.

Chiu B.Y., Keogh E.J., Lonardi S. Probabilistic Discovery of Time Series Motifs. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03 (Washington, D.C., USA, August, 24–27, 2003). ACM, 2003. P. 493–498. DOI: 10.1145/956750.956808.

Duran A., Klemm M. The Intel Many Integrated Core Architecture. Proceedings of the 2012 International Conference on High Performance Computing and Simulation, HPCS 2012 (Madrid, Spain, July, 2–6, 2012). 2012. P. 365–366. DOI: 10.1109/HPCSim.2012.6266938.

Fang J., Varbanescu A.L., Sips H.J. Sesame: A User-Transparent Optimizing Framework for Many-Core Processors. Proceedings of the 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGrid 2013 (Delft, Netherlands, May, 13–16, 2013). 2013. P. 70–73. DOI: 10.1109/CCGrid.2013.79.

Farber R. Parallel Programming with OpenACC. 1st Edition. Morgan Kaufmann, 2016. 326 p.

Goldberger A., Amaral L., Glass L., Hausdorff J., Ivanov P., Mark R., Mietus J., Moody G., Peng C., Stanley H. PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals. Circulation. 2000. Vol. 101, no. 23. P. 215–220. DOI: 10.1161/01.CIR.101.23.e215.

Kraeva Ya., Zymbler M. Scalable Algorithm for Subsequence Similarity Search in Very Large Time Series Data on Cluster of Phi KNL. 20th International Conference on Data Analytics and Management in Data Intensive Domains, DAMDID/RCDL 2018 (Moscow, Russia, October, 9–12, 2018), Revised Selected Papers. Communications in Computer and Information Science. 2019. Vol. 1003. P. 149–164. DOI: 10.1007/978-3-030-23584-0_9

Mattson T. S08 - Introduction to OpenMP. Proceedings of the ACM/IEEE SC2006 Conference on High Performance Networking and Computing (Tampa, FL, USA, November, 11–17, 2006). 2006. P. 209. DOI: 10.1145/1188455.1188673.

McGovern A., Rosendahl D.H., Brown R.A., Droegemeier K. Identifying Predictive Multi-dimensional Time Series Motifs: an Application to Severe Weather Prediction. Data Min. Knowl. Discov. 2011. Vol. 22, no. 1–2. P. 232–258. DOI: 10.1007/s10618-010-0193-7.

Meng J., Yuan J., Hans M., Wu Y. Mining Motifs from Human Motion. Proceedings of the Eurographics 2008 - Short Papers (Crete, Greece, April, 14–18, 2008). Eurographics Association, 2008. P. 71–74. DOI: 10.2312/egs.20081024.

Minnen D., Isbell C.L., Essa I.A., Starner T. Discovering Multivariate Motifs using Subsequence Density Estimation and Greedy Mixture Learning. Proceedings of the 22nd AAAI Conference on Artificial Intelligence (Vancouver, British Columbia, Canada, July, 22–26, 2007). AAAI Press, 2007. P. 615–620.

Mueen A., Keogh E.J., Zhu Q., Cash S., Westover M.B. Exact Discovery of Time Series Motifs. Proceedings of the SIAM International Conference on Data Mining, SDM 2009 (Sparks, Nevada, USA, April, 30 – May, 2, 2009). SIAM, 2009. P. 473–484. DOI: 10.1137/1.9781611972795.41.

Munshi A., Gaster B.R., Mattson T.G., Fung J., Ginsburg D. OpenCL Programming Guide. 1st Edition. Addison-Wesley, 2011. p. 646.

Narang A., Bhattacherjee S. Parallel Exact Time Series Motif Discovery. Proceedings of the 16th International Euro-Par Conference, (Ischia, Italy, August, 31 – September, 3, 2010). Part II. Lecture Notes in Computer Science. Vol. 6272. Springer, 2010. P. 304–315. DOI: 10.1007/978-3-642-15291-7_28.

Owens J. GPU Architecture Overview. Proceedings of the International Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’07 (San Diego, California, USA, August, 5–9, 2007). ACM, New York, NY, USA. DOI: 10.1145/1281500.1281643.

Padua D.A. POSIX Threads (Pthreads). Encyclopedia of Parallel Computing. Springer, 2011. P. 1592–1593. DOI: 10.1007/978-0-387-09766-4_447.

Patel P., Keogh E.J., Lin J., Lonardi S. Mining Motifs in Massive Time Series Databases. Proceedings of the 2002 IEEE International Conference on Data Mining, ICDM 2002 (Maebashi City, Japan, December, 9–12, 2002). IEEE Computer Society, 2002. P. 370–377. DOI: 10.1109/ICDM.2002.1183925.

Pearson K. The Problem of the Random Walk. Nature. 1905. Vol. 72, no. 294. DOI: 10.1038/072342a0.

Shieh J., Keogh E.J. iSAX: Indexing and Mining Terabyte Sized Time Series. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Las Vegas, Nevada, USA, August, 24–27, 2008). ACM, 2008. P. 623–631. DOI: 10.1145/1401890.1401966.

Tanaka Y., Iwamoto K., Uehara K. Discovery of Time-Series Motif from Multi-Dimensional Data Based on MDL Principle. Machine Learning. 2005. Vol. 58, no. 2-3. P. 269–300. DOI: 10.1007/s10994-005-5829-2.

Wilson D.R., Martinez T.R. Reduction Techniques for Instance-based Learning Algorithms. Machine Learning. 2000. Vol. 38, no. 3. P. 257–286. DOI: 10.1023/A:1007626913721.

Yoon C.E., O’Reilly O., Bergen K.J., Beroza G.C. Earthquake Detection through Computationally Efficient Similarity Search. Science Advances. 2015. Vol. 1, no. 11. P. 1–13. DOI: 10.1126/sciadv.1501057.

Zymbler M.L., Kraeva Ya.A. Discovery of Time Series Motifs on Intel Many-Core Systems. Lobachevskii Journal of Mathematics. 2019. Vol. 40, no. 12. P. 2124–2132. DOI: 10.1134/S199508021912014X.

Zymbler M., Polyakov A., Kipnis M. Time Series Discord Discovery on Intel Many-Core Systems. 13th International Conference, PCT 2019 (Kaliningrad, Russia, April, 2–4, 2019). Revised Selected Papers. Communications in Computer and Information Science. Springer, 2019. Vol. 1063. P. 168–182. DOI: 10.1007/978-3-030-28163-2_12.




DOI: http://dx.doi.org/10.14529/cmse200302