Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора
Автор: Цымблер Михаил Леонидович, Краева Яна Александровна
Статья в выпуске: 3 т.9, 2020 года.
Бесплатный доступ
Лейтмотив представляет собой пару подпоследовательностей временного ряда, наиболее похожих друг на друга. Задача поиска лейтмотивов встречается в широком спектре предметных областей: медицина, биология, предсказание погоды и др. В работе предложен новый параллельный алгоритм поиска лейтмотива во временном ряде на платформе графического процессора для случая, когда входные данные могут быть размещены в оперативной памяти. Предлагаемый алгоритм использует в качестве основы алгоритм MK, в котором применяется евклидово расстояние и неравенство треугольника для отбрасывания бесперспективных лейтмотивов без вычисления расстояния. MK позволяет сократить время поиска в разы по сравнению с другими последовательными алгоритмами, однако его производительность значительно снижается на временных рядах, имеющих длину от сотен тысяч элементов. Распараллеливание выполнено с помощью технологии программирования OpenACC. Разработаны матричные структуры данных, позволяющие эффективно распараллелить вычисления на графическом процессоре. Представлены результаты вычислительных экспериментов на реальных и синтетических наборах данных, подтверждающих высокую масштабируемость разработанного алгоритма.
Временной ряд, поиск лейтмотивов, параллельный алгоритм
Короткий адрес: https://sciup.org/147234275
IDR: 147234275 | УДК: 004.272.25, | DOI: 10.14529/cmse200302
Parallel algorithm for time series motif discovery on graphic processor
A time series motif is a pair of subsequences of the series that are most similar to each other. The problem of motif discovery occurs in a wide range of subject areas: medicine, biology, weather prediction, etc. The paper proposes a novel parallel algorithm for time series motif discovery on GPU for the case when the input data fit in the main memory. The proposed algorithm is based on the MK algorithm, which exploits the Euclidean distance and the triangle inequality to prune clearly unpromised pairs of subsequences without computation of the distance. MK decreases the running time up to several orders of magnitude in comparison to the most serial algorithms. However, the performance of MK decreases significantly when the time series length is greater then hundreds of thousands of elements. We designed matrix data structures that ensure the efficient parallel computations on GPU, and paralleled the calculations through the OpenACC programming technology. The results of experimental evaluation on synthetic and real-world datasets confirmed the high scalability of the developed algorithm.
Список литературы Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора
- Цымблер М.Л. Параллельный алгоритм поиска диссонансов временного ряда для многоядерных ускорителей // Вычислительные методы и программирование: Новые вычислительные технологии. 2019. Т. 20, № 3. С. 211-223. DOI: 10.26089/NumMet.v20r320
- Balasubramanian A., Wang J., Prabhakaran В. 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.l211447110.
- 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. URL: 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., et al. PhysioBank, Physio Toolkit, 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 Multidimensional 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/sl0618-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., Iwanroto 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/ sl0994-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.
- Zynrbler 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.
- Zynrbler 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.
