Параллельный алгоритм поиска диссонансов временного ряда для многоядерных ускорителей
Цымблер М.Л.

Диссонанс является уточнением понятия аномальной подпоследовательности (существенно непохожей на остальные подпоследовательности) временного ряда. Задача поиска диссонанса встречается в широком спектре предметных областей, связанных с временными рядами: медицина, экономика, моделирование климата и др. В работе предложен новый параллельный алгоритм поиска диссонанса во временном ряде на платформе многоядерного ускорителя для случая, когда входные данные могут быть размещены в оперативной памяти. Алгоритм использует возможность независимого вычисления евклидовых расстояний между подпоследовательностями ряда. Алгоритм состоит из двух этапов: подготовка данных и поиск. На этапе подготовки выполняется построение вспомогательных матричных структур данных, обеспечивающих распараллеливание и векторизацию вычислений. На стадии поиска осуществляется нахождение диссонанса с помощью построенных структур данных. Выполнена реализация алгоритма для ускорителей архитектур Intel MIC (Many Integrated Core) и NVIDIA GPU, распараллеливание выполнено с помощью технологий программирования OpenMP и OpenAcc соответственно. Представлены результаты вычислительных экспериментов, подтверждающих масштабируемость разработанного алгоритма.

Ключевые слова: временной ряд, поиск диссонансов, параллельный алгоритм, векторизация вычислений, OpenMP, OpenAcc, Intel Xeon Phi, NVIDIA GPU.

Название статьи, аннотация и ключевые слова на английском языке

  • Цымблер М.Л. – Южно-Уральский государственный университет, Высшая школа электроники и компьютерных наук, просп. Ленина, 76, 454080, Челябинск; начальник отдела, e-mail: mzym@susu.ru