Эта публикация цитируется в 1 статье

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

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

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

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

Ключевые слова: временной ряд, поиск лейтмотивов, параллельный алгоритм, NVIDIA GPU, OpenACC.

УДК: 004.272.25, 004.421, 004.032.24

Поступила в редакцию: 26.07.2020

DOI: 10.14529/cmse200302