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

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

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 3 т.9, 2020 года.

Бесплатный доступ

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

Еще

Временной ряд, поиск лейтмотивов, параллельный алгоритм

Короткий адрес: https://sciup.org/147234275

IDR: 147234275 | DOI: 10.14529/cmse200302

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

Цымблер М.Л. Параллельный алгоритм поиска диссонансов временного ряда для многоядерных ускорителей // Вычислительные методы и программирование: Новые вычислительные технологии. 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.

Еще

Статья научная