RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Вестн. ЮУрГУ. Сер. Выч. матем. информ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Вестн. ЮУрГУ. Сер. Выч. матем. информ., 2020, том 9, выпуск 3, страницы 17–34 (Mi vyurv239)  

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

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

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

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

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 20-07-00140
Министерство науки и высшего образования Российской Федерации FENU-2020-0022
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант № 20-07-00140) и Министерства образования и науки РФ (государственное задание FENU-2020-0022)


DOI: https://doi.org/10.14529/cmse200302

Полный текст: PDF файл (676 kB)

Тип публикации: Статья
УДК: 004.272.25, 004.421, 004.032.24
Поступила в редакцию: 26.07.2020

Образец цитирования: М. Л. Цымблер, Я. А. Краева, “Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора”, Вестн. ЮУрГУ. Сер. Выч. матем. информ., 9:3 (2020), 17–34

Цитирование в формате AMSBIB
\RBibitem{TsyKra20}
\by М.~Л.~Цымблер, Я.~А.~Краева
\paper Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора
\jour Вестн. ЮУрГУ. Сер. Выч. матем. информ.
\yr 2020
\vol 9
\issue 3
\pages 17--34
\mathnet{http://mi.mathnet.ru/vyurv239}
\crossref{https://doi.org/10.14529/cmse200302}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vyurv239
  • http://mi.mathnet.ru/rus/vyurv/v9/i3/p17

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Вестник Южно-Уральского государственного университета. Серия «Вычислительная математика и информатика»
    Просмотров:
    Эта страница:20
    Полный текст:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021