|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора
М. Л. Цымблер, Я. А. Краева Южно-Уральский государственный университет (454080 Челябинск, пр. им. В.И. Ленина, д. 76)
Аннотация:
Лейтмотив представляет собой пару подпоследовательностей временного ряда, наиболее похожих друг на друга. Задача поиска лейтмотивов встречается в широком спектре предметных областей: медицина, биология, предсказание погоды и др. В работе предложен новый параллельный алгоритм поиска лейтмотива во временном ряде на платформе графического процессора для случая, когда входные данные могут быть размещены в оперативной памяти. Предлагаемый алгоритм использует в качестве основы алгоритм MK, в котором применяется евклидово расстояние и неравенство треугольника для отбрасывания бесперспективных лейтмотивов без вычисления расстояния. MK позволяет сократить время поиска в разы по сравнению с другими последовательными алгоритмами, однако его производительность значительно снижается на временных рядах, имеющих длину от сотен тысяч элементов. Распараллеливание выполнено с помощью технологии программирования OpenACC. Разработаны матричные структуры данных, позволяющие эффективно распараллелить вычисления на графическом процессоре. Представлены результаты вычислительных экспериментов на реальных и синтетических наборах данных, подтверждающих высокую масштабируемость разработанного алгоритма.
Ключевые слова:
временной ряд, поиск лейтмотивов, параллельный алгоритм, NVIDIA GPU, OpenACC.
Поступила в редакцию: 26.07.2020
Образец цитирования:
М. Л. Цымблер, Я. А. Краева, “Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора”, Вестн. ЮУрГУ. Сер. Выч. матем. информ., 9:3 (2020), 17–34
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vyurv239 https://www.mathnet.ru/rus/vyurv/v9/i3/p17
|
Статистика просмотров: |
Страница аннотации: | 113 | PDF полного текста: | 33 |
|