Anomaly detection in long time series on high-performance cluster with GPUs
Authors: Краева Я.А. , Цымблер М.Л. 
Published: August 2023

В настоящее время обнаружение аномалий в длинных временных рядах возникает в широком спектре предметных областей: цифровая индустрия, здравоохранение, моделирование климата, финансовая аналитика и др. Диссонанс формализует понятие аномалии и определяется как подпоследовательность ряда, которая имеет расстояние до своего ближайшего соседа, не превышающее наперед заданного аналитиком порога. Ближайшим соседом подпоследовательности является та подпоследовательность ряда, которая не пересекается с данной и имеет минимальное расстояние до нее. В статье представлен новый алгоритм поиска диссонансов временн´ого ряда на вычислительном кластере, каждый узел которого оснащен графическим процессором. Алгоритм применяет параллелизм по данным: временн´ой ряд разбивается на непересекающиеся фрагменты, обрабатываемые графическими процессорами узлов вычислительного кластера. С помощью ранее разработанного авторами параллельного алгоритма на каждом узле выполняется отбор локальных кандидатов в диссонансы. Далее с помощью обменов на каждом узле формируется множество глобальных кандидатов как объединение всех локальных кандидатов. Затем каждый узел выполняет глобальную очистку, удаляя из множества глобальных кандидатов ложноположительные диссонансы. Глобальная очистка распараллеливается на основе блочного умножения матрицы кандидатов и матрицы подпоследовательностей фрагмента. Результирующее множество диссонансов формируется как пересечение множеств, полученных узлами по итогу глобальной очистки. Вычислительные эксперименты с синтетическими и реальными временными рядами, проведенные на платформе суперкомпьютеров Ломоносов-2 и Лобачевский, оснащенных 48–64 графическими процессорами, показывают высокую масштабируемость разработанного алгоритма.

Currently, the discovery of anomalies in long time series occurs in a wide range of subject areas: digital industry, healthcare, climate modeling, financial analytics, etc. Discord formalizes the anomaly concept being defined as a time series subsequence that has a distance of at least r to its non-overlapping nearest neighbor, where r is a prespecified threshold. This article presents a new algorithm for discord discovery on a high-performance computing cluster, where each cluster node is equipped with a GPU. The algorithm employs the data parallelism concept: the time series is divided into disjoint fragments that are processed separetely by GPUs of the cluster nodes. Using a parallel algorithm previously developed by the authors, local candidates for discords are selected at each node. Further, through the data exchanges, a set of global candidates is formed at each node as a union of all local candidates. Then each node performs a global refinement, removing false-positive discords from the global candi date set. Global refinement is parallelized based on block multiplication of the candidate matrix and the subsequence matrix of the fragment. The resulting set of discords is formed as the intersection of the sets obtained by the nodes as a result of global refinement. Computational experiments with synthetic and real time series, carried out on the Lomonosov-2 and Lobachevsky supercomputers equipped with 48–64 GPUs, show the high scalability of the developed algorithm.