=Paper=
{{Paper
|id=Vol-1482/332
|storemode=property
|title=Параллельный алгоритм поиска локально похожих подпоследовательностей временного ряда для ускорителей на базе архитектуры Intel MIC
(Parallel algorithm for local-best-match time series subsequence similarity search on the Intel MIC architecture)
|pdfUrl=https://ceur-ws.org/Vol-1482/332.pdf
|volume=Vol-1482
}}
==Параллельный алгоритм поиска локально похожих подпоследовательностей временного ряда для ускорителей на базе архитектуры Intel MIC
(Parallel algorithm for local-best-match time series subsequence similarity search on the Intel MIC architecture)==
https://ceur-ws.org/Vol-1482/332.pdf
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Параллельный алгоритм поиска локально похожих
подпоследовательностей временного ряда
для ускорителей на базе архитектуры Intel MIC\ast
А.В. Мовчан, М.Л. Цымблер
Южно-Уральский государственный университет (НИУ)
В работе рассматривается задача поиска локально похожих подпоследовательно-
стей временного ряда. Необходимо найти все подпоследовательности ряда, рас-
стояние от которых до заданного поискового запроса минимально среди всех со-
седних подпоследовательностей, отстоящих от запроса не более чем на заданное
пороговое значение. В качестве расстояния (меры схожести) используется дина-
мическая трансформация шкалы времени (Dynamic Time Warping, DTW), кото-
рая на сегодня признается лучшей мерой для большинства приложений времен-
ных рядов. Вычисление DTW, однако, является затратной операцией, несмотря
на существующие алгоритмические техники сокращения вычислений. Имеющи-
еся подходы к вычислению DTW с помощью многоядерных ускорителей задей-
ствуют архитектуры GPU и FPGA, оставляя без внимания потенциал архитек-
туры Intel Many Integrated Core. В работе предлагается параллельный алгоритм
решения указанной задачи, использующий как центральный процессор, так и
многоядерный сопроцессор Intel Xeon Phi. Реализация основана на технологии
параллельного программирования OpenMP и режиме выполнения приложения,
при котором часть кода и данных выгружается на сопроцессор. Алгоритм пред-
полагает использование на стороне процессора очереди подпоследовательностей,
данные о которых выгружаются на сопроцессор для вычисления DTW, что обес-
печивает высокую интенсивность вычислений, выполняемых на сопроцессоре.
Приведены результаты экспериментов, подтверждающих эффективность разра-
ботанного алгоритма.
1. Введение
Временной ряд представляет собой совокупность вещественных значений, каждое из ко-
торых ассоциировано с последовательными отметками времени. Поиск похожих подпосле-
довательностей временного ряда представляет собой одну из основных проблем интеллекту-
ального анализа временных рядов, возникающую в широком спектре предметных областей:
мониторинг показателей функциональной диагностики организма человека [3], моделиро-
вание климата [1], финансовое прогнозирование [2] и др.
Поиск локально похожих подпоследовательностей предполагает, что имеется временной
ряд, в котором необходимо осуществить поиск заданного ряда меньшей длины (поискового
запроса), и задано пороговое значение расстояния (меры схожести подпоследовательно-
стей). Решением задачи является множество подпоследовательностей исходного ряда, каж-
дая из которых удовлетворяет следующему условию: расстояние от подпоследовательности
до запроса минимально среди соседних с ней подпоследовательностей, отстоящих от запро-
са не более чем на пороговое значение.
На сегодня динамическая трансформация времени (Dynamic Time Warping, DTW) [5]
является наиболее популярной мерой во многих приложениях интеллектуального анализа
временных рядов [6]. Однако по сравнению с Евклидовым расстоянием DTW вычислитель-
но более сложна. На сегодня предложено большое количество подходов для решения данной
задачи: отбрасывание заведомо непохожих подпоследовательностей на основе оценки ниж-
\ast
Работа выполнена при финансовой поддержке Минобрнауки России в рамках ФЦП «Исследования и
разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014–
2020 годы» (Соглашение № 14.574.21.0035 от 17.06.2014, идентификатор RFMEFI57414X0035).
332
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
ней границы расстояния [6], повторное использование вычислений [16], индексирование [11],
раннее прекращение заведомо нерезультативных вычислений [14] и др. Тем не менее, вы-
числение DTW по-прежнему занимает существенную часть времени работы алгоритмов. В
силу этого актуальными являются исследования, посвященные использованию параллель-
ных вычислений для решения данной задачи на кластерных системах [18], многоядерных
процессорах [17], FPGA и GPU [16, 19, 20]. В этой связи представлется недооцененным по-
тенциал многоядерных ускорителей на базе архитектуры Intel Many Integrated Core [7] для
решения задач поиска похожих подпоследовательностей временных рядов.
В данной статье предлагается параллельный алгоритм поиска локально похожих под-
последовательностей временного ряда для узла, оснащенного многоядерным сопроцесором
Intel Xeon Phi. Статья организована следующим образом. Раздел 2 содержит формаль-
ное определение задачи и краткое описание архитектуры и модели программирования Intel
Xeon Phi, а также обзор работ по теме исследования. В разделе 3 описан предложенный ал-
горитм. Результаты экспериментов представлены в разделе 4. В заключении суммируются
полученные результаты и указываются направления будущих исследований.
2. Контекст исследования и обзор работ
2.1. Формальная постановка задачи
Временной ряд (time series) T — упорядоченная последовательность t1 , t2 , ..., tN (где
N — длина последовательности) вещественных значений, каждое из которых ассоциировано
с отметкой времени.
Подпоследовательность (subsequence) Tim временного ряда T представляет собой непре-
рывное подмножество T , начинающееся с позиции i, и имеющее длину m,
т.е. Tim = ti , ti+1 , . . . , ti+m - 1 , где 1 \leq i \leq N и i + m \leq N .
Запрос (query) Q — временной ряд, поиск которого необходимо осуществить во времен-
ном ряде T . Пусть n — длина запроса, n \ll N .
Задача поиска локально похожих подпоследовательностей (local-best-match subsequence
search) [19] определяется следующим образом. Пусть D является мерой схожести, \scrE > 0 —
пороговое значение меры и L означает результирующее множество подпоследовательностей.
Тогда Tim \in L \leftrightarrow Tim удовлетворяет следующим условиям:
1. m = n;
2. D(Tim , Q) < \scrE ;
3. i = argmin D(Tjm , Q).
j\in \{ i - 1,i,i+1\}
Динамическая трансформация шкалы времени (Dynamic Time Warping, DTW) пред-
ставляет собой меру схожести двух временных рядов. Расстояние на основе DTW между
двумя временными рядами X и Y , где X = x1 , x2 , ..., xN и Y = y1 , y2 , ..., yN , обозначается
как D(X, Y ) и определяется следующим образом.
D(X, Y ) = d(N, N ),
\left\{
d(i - 1, j)
d(i, j) = | xi - yj | + min d(i, j - 1)
d(i - 1, j - 1),
d(0, 0) = 0; d(i, 0) = d(0, j) = \infty ; i = 1, 2, . . . , N ; j = 1, 2, . . . , N .
333
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
2.2. Архитектура и модель программирования сопроцессора Intel Xeon Phi
Многоядерный сопроцессор Intel Xeon Phi состоит из 61 ядра на базе архитектуры
x86, соединенных высокоскоростной двунаправленной шиной, где каждое ядро поддержи-
вает 4\times гипертрединг и содержит 512-битный векторный процессор. Каждое ядро имеет
собственный кэш 1 и 2 уровня, при этом обеспечивается когерентность кэшей всех ядер.
Сопроцессор соединяется с хост-компьютером посредством интерфейса PCI Express. По-
скольку сопроцессор Intel Xeon Phi основан на архитектуре Intel x86, он поддерживает те
же программные инструменты и модели программирования, что и ординарный процессор
Intel Xeon.
Сопроцессор поддерживает следующие режимы запуска приложений: native, offload и
symmetric. В режиме native приложение выполняется независимо исключительно на сопро-
цессоре. В режиме offload приложение запускается на процессоре и выгружает вычисли-
тельно интенсивную часть работы (код и данные) на сопроцессор. Режим symmetric позво-
ляет сопроцессору и процессору взаимодействовать в рамках модели обмена сообщениями
(Message Passing Interface).
2.3. Работы по тематике исследования
В настоящее время DTW рассматривается научным сообществом как наилучшая мера
схожести для большинства приложений интеллектуального анализа временных рядов [6],
несмотря на большие временны́е затраты, связанные с ее вычислением [9,18]. Исследования,
посвященные ускорению вычисления DTW, представлены следующими работами.
Алгоритм SPRING [15] использует технику повторного использования вычислений. Од-
нако, данная техника ограничивает приложение алгоритма, поскольку повторное использо-
вание данных предполагает использование последовательностей, не подвергаемых норма-
лизации. В работе [11] для ускорения вычислений используется техника индексирования,
которая требует заранее задавать длину поискового запроса, что не всегда приемлемо. Ав-
торами работы [10] предложен многомерный индекс для поисковых запросов с различными
длинами. Техника отбрасывания заведомо непохожих подпоследовательностей на основе
оценки нижней границы расстояния предложена в работе [8]. Алгоритм UCR-DTW [14] ин-
тегрирует большое количество существующих техник ускорения вычислений DTW и явля-
ется на сегодня, вероятно, самым быстрым последовательным алгоритмом поиска похожих
подпоследовательностей.
Вышеперечисленные алгоритмы направлены на сокращение количества вызовов проце-
дуры вычисления DTW, но не ускорения процедуры вычисления DTW как таковой. Однако,
в силу своей вычислительной сложности, вычисление DTW по-прежнему занимает суще-
ственную часть времени выполнения поиска подпоследовательностей. Данное обстоятель-
ство стимулировало исследования, направленные на использование параллельного аппарат-
ного обеспечения для распределения вычислений DTW для разных подпоследовательностей
на разные вычислительные устройства.
В работе [17] подпоследовательности, начинающиеся с разных позиций временного ря-
да, направляются для вычисления DTW на различные процессоры Intel Xeon. В работе [18]
разные поисковые запросы распределяются на разные ядра процессора, и каждая подпосле-
довательность пересылается на различные ядра для сравнения с запросами. Реализация на
GPU [20] распараллеливает создание матрицы трансформации шкалы времени, однако путь
трансформации вычисляется последовательно. В работе [16] предложена GPU-реализация,
использующая те же идеи, что и в работе [17]. Реализация для FPGA, описанная в ра-
боте [16], предлагает наивный поиск похожих подпоследовательностей, не использующий
предварительную обработку данных. Приложение, осуществляющее поиск, генерируется
с помощью инструмента C-to-VHDL и ввиду отсутствия знания внутреннего устройства
FPGA не может быть применено к задачам большой размерности. Для преодоления ука-
334
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
занных проблем в работе [19] предложен потоково-ориентированнный фреймворк, в кото-
ром реализован крупнозернистый параллелизм путем повторного использования данных
различных вычислений DTW.
В данной работе на базе последовательного алгоритма поиска наиболее похожей подпо-
следовательности временного ряда [14] нами разработан алгоритм поиска локально похожих
подпоследовательностей, который затем распараллелен с помощью технологии OpenMP и
адаптирован для многоядерного сопроцессора Intel Xeon Phi на основе идей, предложенных
нами ранее в работах [4, 12].
3. Параллельный алгоритм для сопроцессора Intel Xeon Phi
В данном разделе описаны этапы разработки параллельного алгоритма поиска локаль-
но похожих подпоследовательностей для многоядерного сопроцессора Intel Xeon Phi. В
разделе 3.1 описан последовательный алгоритм решения данной задачи, построенный на
основе алгоритма UCR-DTW [14]. Раздел 3.2 содержит описание распараллеливания после-
довательного алгоритма с помощью технологии OpenMP. В разделе 3.3 описана адаптация
алгоритма, полученного на предыдущем шаге, для исполнения на сопроцессоре Intel Xeon
Phi.
3.1. Последовательный алгоритм
Разработанный нами последовательный алгоритм поиска локально похожих подпосле-
довательностей представлен на рис. 1. Алгоритм получил название lbm-UCR-DTW, по-
скольку базируется на алгоритме UCR-DTW [14]. Оригинальный алгоритм использует кас-
кад оценок динамической трансформации шкалы времени для отбрасывания заведомо непо-
хожих подпоследовательностей (составная деятельность Lower Bounding на рис. 1).
Мы полагаем, что | L| \leq K, т.е. результирующее множество содержит не более K подпо-
следовательностей, где K является параметром алгоритма. Данное ограничение является
практически полезным ввиду возможного лимита оперативной памяти для хранения най-
денных подпоследовательностей и не ограничивает общность, поскольку мы можем рас-
смотреть случай K = \infty .
Переменная алгоритма bsf (best-so-far) используется для хранения текущей лучшей
оценки расстояния от подпоследовательностей до запроса и вычисляется следующим обра-
зом:
\left\{
\scrE , | L| < K
bsf =
min(\scrE , max DT W (Tmn , Q)) , else
Tmn \in L
Для поиска локально похожих подпоследовательностей алгоритм осуществляет после-
довательный просмотр каждых трех соседних подпоследовательностей. Текущую обрабаты-
ваемую подпоследовательность Tin мы обозначаем как CR , а две предшествующие ей и уже
обработанные подпоследовательности Ti - 1n и Ti - 2n как CM и CL соответственно. Расстоя-
ние от данных подпоследовательностей до запроса обозначаются как distR , distM и distL
соответственно. Вспомогательный алгоритм Sliding осуществляет обновление указанных
переменных во время работы алгоритма.
В случае, если подпоследовательность CM является локальным минимумом, то вспо-
могательный алгоритм Update Result включает подпоследовательность CM в результиру-
ющее множество L. Если после этого мощность множества L превышает K, то из данного
множества исключается подпоследовательность, расстояние от которой до запроса макси-
мально среди всех подпоследовательностей, входящих в L, и далее обновляется значение
переменной bsf в соответствии с вышеуказанной формулой.
335
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
lbm-UCR-DTW Update result
[no Tin]
Init Read Next
𝕃 := 𝕃 ∪ CM
else
Lower Bounding else
[ |𝕃| > K ]
Local Min else
Condition dist := DTW(Tin, Q)
𝕃 := 𝕃 \ argmax DTW(Tmn, Q)
Tmn ∈ 𝕃
CL ≠ EMPTY ∧ [pruned]
CM ≠ EMPTY ∧
CR ≠ EMPTY ∧ bsf := min(bsf, max DTW(Tmn, Q))
Tmn ∈ 𝕃
distM < ε ∧
distM < distL ∧
distM < distR
Sliding
[Local Min
Condition] else
Update Result
Init Sliding Read Next
i := 0
dist := ∞ CL := CM
CL := EMPTY CM := CR CR := Tin i := i + 1
Get Tin
CM := EMPTY distL := distM distR := dist dist := ∞
CR := EMPTY distM := distR
bsf := ε
Lower Bounding
non-pruned
else else else
LB_Kim(Tin, Q) LB_Keogh(Tin, Q) LB_KeoghEC(Tin, Q)
[lb_kim ≥ bsf] [lb_keogh ≥ bsf] [lb_keogh_ec ≥ bsf]
pruned
Рис. 1. Последовательный алгоритм lbm-UCR-DTW
Таким образом, схема работы алгоритма кратко может быть представлена следующим
образом. Считанная подпоследовательность проверяется с помощью каскада оценок вспомо-
гательного алгоритма Lower Bounding. Если подпоследовательность не отбрасывается как
заведомо непохожая, то вычисляется DTW до запроса. Затем вспомогательный алгоритм
Sliding выполняет обновление переменных CL , CM , CR и соответсвующих им расстояний
distL , distM , distR . Если выполнено условие локального минимума, то вспомогательный
алгоритм Update Result обновляет результирующее множество L. Алгоритм заканчивает
работу, когда исчерпаны все подпоследовательности исходного временного ряда.
3.2. Параллельный алгоритм для процессора
На основе последовательного алгоритма, предложенного в предыдущем разделе, нами
разработан параллельный алгоритм для процессора, представленный на рис. 2.
Для распараллеливания используется технология программирования OpenMP. Времен-
ной ряд разбивается на промежутки равной длины, каждый из которых обрабатывается
отдельной OpenMP-нитью. Для того, чтобы избежать потери результирующих подпоследо-
вательностей, находящихся на стыке промежутков, разбиение на промежутки осуществля-
ется с перекрытием, равным длине запроса. Это означает, что начало каждого промежутка,
336
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Read data Swap Buf_1
Open file
in Buf_1 and Buf_2
else [EOF]
Read data
lbm-UCR-DTW lbm-UCR-DTW ... lbm-UCR-DTW
in Buf_2
result = min_dist(result, res1, ..., resCPU_THREADS)
[Buf_2 is empty]
Output else
Close file
result
Рис. 2. Параллельный алгоритм для процессора
за исключением первого, пересекается с концом предыдущего промежутка в n точках.
Данный принцип разбиения формально может быть описан следующим образом.
Пусть P – количество OpenMP-нитей, тогда промежуток, назначаемый k-й нити, есть
последовательностью Tsl , где
\left\{
1 ,k = 0
s=
k \cdot \lfloor N
P \rfloor - n + 2 , else
\left\{
\lfloor N
P \rfloor + 1 ,k = 0
l= \lfloor N
P \rfloor + n - 1 + (N mod P ) , k = P - 1
\lfloor N
P \rfloor + n , else
Здесь lbm-UCR-DTW представляет собой подпрограмму, реализующую последовательный
алгоритм, представленный в предыдущем разделе. Этот алгоритм использует разделяемую
переменную bsf, что позволяет каждой нити отбросить заведомо непохожую подпоследо-
вательность, если расстояние до нее больше значения указанной переменной. Главная нить
считывает данные из файла одновременно с обработкой остальными нитями уже прочитан-
ных данных.
3.3. Параллельный алгоритм для сопроцессора
Параллельный алгоритм для процессора и сопроцессора Intel Xeon Phi представлен на
рис. 3.
Основная идея данного параллельного алгоритма заключается в том, что сопроцессор
используется только для вычислений DTW, а процессор выполняет вычисление каскада
оценок, подготавливая подпоследовательности для сопроцессора, и вычисление DTW, если
сопроцессор полностью занят. Процессор поддерживает очередь кандидатов (т.е. подпосле-
довательностей, для каждой из которых сопроцессор должен вычислить DTW).
Элементами очереди являются кортежи вида (i, A), соответствующие подпоследователь-
ности-кандидату Tin . Здесь A представляет собой массив длины n, содержащий оценки
337
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Process Candidate
CPU Intel Xeon Phi
Swap Buf_1 Read data
Open file
and Buf_2 in Buf_1
Send Buf_1 Receive Buf Get Candidate
else [EOF]
dist := DTW(candidate)
Read data Wait for Receive
lbm-UCR-DTW* lbm-UCR-DTW* ... lbm-UCR-DTW* candidates candidates
in Buf_2 phi_result := phi_result ∪ (candidate, dist)
Send candidates
else
Process ... Process
Receive Candidate Candidate [no candidates]
phi_result
else Update
Send phi_result Update Distances
Distances
[no candidates and
all threads are finished]
result = min_dist(result, 𝕃1, ..., 𝕃CPU_THREADS)
Get (subsequence, dist) from phi_result
result = find_local_min(result, DTW_distances)
DTW_distances[subsequence] := dist
[Buf_2 is
else empty] Output
Close file result else
[phi_result is empty]
Рис. 3. Параллельный алгоритм для процессора и сопроцессора Intel Xeon Phi
LBKeogh для каждой позиции подпоследовательности, который используется для заблаго-
временной отмены вычисления DTW [14].
При заполнении очереди она выгружается на сопроцессор для выполнения вычислений
DTW. Максимальное количество элементов в очереди является параметром алгоритма и
вычисляется как C \cdot h \cdot W , где C — количество ядер сопроцессора, доступных для вычисле-
ний (например, для Intel Xeon Phi SE10X C = 60), h — фактор гипертрединга сопроцессора
(h = 4 для ранее упомянутой модели сопроцессора), W — количество кандидатов, обраба-
тываемых одной нитью сопроцессора, которое является параметром алгоритма.
Работа алгоритма может быть описана следующим образом. Одна из нитей процессора
объявляется мастером, остальные — рабочими. Сначала мастер отправляет буфер с теку-
щим фрагментом временного ряда на сопроцессор. Как только очередь заполняется, мастер
выгружает ее на сопроцессор, а сопроцессор выполняет вычисление DTW для соответству-
ющих подпоследовательностей.
Вспомогательный алгоритм lbm-UCR-DTW*, изображенный на рис. 4, реализует поведе-
ние рабочего. Рабочий выполняет вычисление каскадных оценок для подпоследовательно-
сти. Если подпоследовательность не похожа на запрос, то рабочий отбрасывает ее, иначе
подпоследовательность добавляется в очередь. Если очередь заполнена, и данные, загру-
женные ранее на сопроцессор, еще не обработаны, то рабочий вычисляет DTW самостоя-
тельно. При этом реализация поиска локально похожих подпоследовательностей идеологи-
чески близка последовательному алгоритму, описанному в разделе 3.1. Результаты вычис-
лений DTW рабочий сохраняет в разделяемом массиве для последующего поиска локально
похожих подпоследовательностей.
После выгрузки кандидатов на сопроцессор для каждого кандидата выполняется вы-
числение DTW, и пары «индекс-расстояние» выгружаются обратно на процессор.
После того, как вычисления на процессоре и сопроцессоре завершены, выполняется
поиск локально похожих подпоследовательностей в разделяемом массиве, заполненном ра-
нее.
338
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Push to Queue
[no Tin]
Init Read Next
Queue.Push (Tin)
else
Lower Bounding Sliding
Push else else
CR := EMPTY
to Queue
[Queue.IsFull] [pruned]
dist := DTW(Tin, Q)
Sliding
DTW_distances[i] := dist
[Local Min
Condition] else
Update Result
Рис. 4. Вспомогательный алгоритм lbm-UCR-DTW*
4. Вычислительные эксперименты
Для оценки разработанного алгоритма мы выполнили эксперименты на узле суперком-
пьютера «Торнадо ЮУрГУ»1 , спецификации которого представлены в табл. 1.
Таблица 1. Спецификация узла суперкомпьютера «Торнадо ЮУрГУ»
Спецификации Процессор Сопроцессор
Модель Intel Xeon X5680 Intel Xeon Phi SE10X
Количество ядер 6 61
Тактовая частота, ГГц 3.33 1.1
Количество нитей на ядро 2 4
Пиковая производительность, TFLOPS 0.371 1.076
В качестве временного ряда фигурировали как синтетические, так и реальные данные.
В экспериментах измерялось время поиска похожих подпоследовательностей для запросов
различной длины. Мы также исследовали влияние порогового значения \scrE на время работы
алгоритма.
В экспериментах использовалось пороговое значение \scrE = 2 + Dmin , где Dmin представ-
ляет расстояние до самой похожей подпоследовательности, предварительно вычисленное с
помощью алгоритма, предложенного в работах [4, 12]. Мощность результирующего множе-
ства ограничивалась сверху значением K = 10000.
В первой серии экспериментов мы использовали синтетический временной ряд, состоя-
щий из 100 млн. точек, сгенерированный на основе модели случайных блужданий [13].
Результаты экспериментов на синтетических данных, представленные на рис. 5, показы-
вают, что разработанный алгоритм более эффективен для запросов большей длины. В слу-
1
supercomputer.susu.ru/en/computers/tornado/
339
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
2500
2000
Время выполнения, с
1500
1000
500
Serial
Parallel, CPU
Parallel, CPU+Xeon Phi
0
500 2000 4000 6000
Длина запроса
Рис. 5. Производительность на синтетических данных
чае, когда запросы имеют меньшую длину, наш алгоритм показывает производительность,
сходную с параллельным алгоритмом для процессора (не использующим сопроцессор).
Вторая серия экспериментов исследует производительность разработанного алгорит-
ма на реальных данных ЭКГ, состоящих из 20 млн. точек (около 22 час. ЭКГ, снятой с
дискретизацией 250 Гц).
Serial
Parallel, CPU
5000 Parallel, CPU+Xeon Phi
Время выполнения, с
4000
3000
2000
1000
0
1000 1500 2000
Длина запроса
Рис. 6. Производительность на реальных данных
Результаты экспериментов на реальных данных показаны на рис. 6. Разработанный
алгоритм показывает в почти три раза бо́льшую производительность, чем параллельный
алгоритм, не использующий сопроцессор.
Влияние порогового значения \scrE на время работы алгоритма показано на рис. 7. Данный
эксперимент производился с использованием параллельного алгоритма поиска локально по-
хожих подпоследовательностей для процессора и сопроцессора Intel Xeon Phi. В качестве
данных эксперимента использовались синтетический и реальный временные ряды, рассмот-
ренные в предыдущих экспериментах. Как и ожидалось, с увеличением порогового значения
\scrE время выполнения увеличивается.
340
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
3000
Random Walk, ✁✂✄☎✆ ✝✆✞✟✠✡✆: 2000
Random Walk, ✁✂✄☎✆ ✝✆✞✟✠✡✆: 4000
ECG, ✁✂✄☎✆ ✝✆✞✟✠✡✆: 1000
2500 ECG, ✁✂✄☎✆ ✝✆✞✟✠✡✆: 1500
Время выполнения, с
2000
1500
1000
500
0
0 1 5 10 15
Рис. 7. Влияние порогового значения \scrE на время выполнения
5. Заключение
В данной статье описаны проектирование и реализация параллельного алгоритма по-
иска локально похожих подпоследовательностей временного ряда, использующего в каче-
стве мероы схожести динамическую трансформацию шкалы времени, для архитектуры Intel
Many Integrated Core.
На основе последовательного алгоритма поиска самой похожей подпоследовательности
временного ряда, комбинирующего известные на сегодня техники редукции вычислений,
разработан последовательный алгоритм решения указанной задачи.
На следующем шаге разработки выполнено распараллеливание полученного алгоритма
на основе технологии OpenMP. Временной ряд разбивается на промежутки равной длины,
обрабатываемые отдельными OpenMP-нитями. Для исключения потерь результирующих
подпоследовательностей, находящихся на стыке промежутков, разбиение осуществляется с
частичным нахлестом соседних промежутков.
Наконец, алгоритм, полученный на предыдущем шаге, адаптирован для выполнения
вычислений как на центральном процессоре, так и на многоядерном сопроцессоре Intel
Xeon Phi. Сопроцессор используется только для вычисления расстояний между подпосле-
довательностями и запросом. Процессор выполняет отбрасывание заведомо непохожих под-
последовательностей и подготовку подпоследовательностей для обработки сопроцессором,
вычисляя расстояния лишь при отсуствии другой работы. Взаимодействие процессора и
сопроцессора реализовано с помощью режима offload, когда часть кода и данных выгружа-
ется на сопроцессор. Высокая интенсивность вычислений, выполняемых на сопроцессоре,
достигается за счет использования на стороне процессора очереди подпоследовательностей,
данные о которых выгружаются на сопроцессор для вычисления динамической трансфор-
мации шкалы времени.
Эксперименты, проведенные на синтетических и реальных данных, показали эффектив-
ность разработанного алгоритма и его превосходство над последовательным алгоритмом и
параллельным алгоритмом, использующим только процессор.
В качестве возможного направления дальнейших исследований интересными представ-
ляются следующие задачи: модернизация разработанного алгоритма для случая, когда про-
цессор оснащен несколькими сопроцессорами Intel Xeon Phi, и расширение разработанного
алгоритма для кластерной системы, каждый вычислительный узел которой оснащен сопро-
цессором Intel Xeon Phi.
341
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Литература
1. Абдуллаев С.М., Ленская О.Ю., Гаязова А.О., Иванова О.Н., Носков А.А.,
Соболев Д.Н., Радченко Г.И. Алгоритмы краткосрочного прогноза с использованием
радиолокационных данных: оценка трасляции и композиционный дисплей жизненного
цикла // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2014.
Т. 3, № 1. С. 17–32.
2. Дышаев М.М., Соколинская И.М. Представление торговых сигналов на основе
адаптивной скользящей средней Кауфмана в виде системы линейных неравенств //
Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2013. Т. 2, № 4.
C. 103–108.
3. Епишев В.В., Исаев А.П., Миниахметов Р.М., Мовчан А.В., Смирнов А.С.,
Соколинский Л.Б., Цымблер М.Л., Эрлих В.В. Система интеллектуального анализа
данных физиологических исследований в спорте высших достижений // Вестник
ЮУрГУ. Серия: Вычислительная математика и информатика. 2013. Т. 2, № 1.
С. 44–54.
4. Мовчан А.В., Цымблер М.Л. Нахождение похожих подпоследовательностей
временного ряда с помощью многоядерного сопроцессора Intel Xeon Phi //
Параллельные вычислительные технологии (ПаВТ’2015): труды международной
научной конференции (Екатеринбург, 31 марта – 2 апреля 2015 г.). Челябинск:
Издательский центр ЮУрГУ, 2015. С. 212–224.
5. Berndt D.J., Clifford J. Using Dynamic Time Warping to Find Patterns in Time Series //
Knowledge Discovery in Databases: Papers from the 1994 AAAI Workshop, Seattle,
Washington, July 1994. AAAI Press, 1994. P. 359–370.
6. Ding H., Trajcevski G., Scheuermann P., Wang X., Keogh E. Querying and Mining of Time
Series Data: Experimental Comparison of Representations and Distance Measures //
Proceedings of the VLDB Endowment, 2008. Vol. 1, No. 2. P. 1542–1552.
7. Duran A., Klemm M. The Intel Many Integrated Core Architecture // 2012 International
Conference on High Performance Computing and Simulation, HPCS 2012, Madrid, Spain,
July 2–6, 2012. IEEE, 2012. P. 365–366.
8. Fu A.W-C., Keogh E.J., Lau L.Y.H., Ratanamahatana C., Wong R.C.-W. Scaling and Time
Warping in Time Series Querying // Proceedings of the 31st International Conference on
Very Large Data Bases, Trondheim, Norway, August 30 – September 2, 2005. P. 649–660.
9. Fu A.W-C., Keogh E.J., Lau L.Y.H., Ratanamahatana C., Wong R.C.-W. Scaling and
Time Warping in Time Series Querying // VLDB Journal. 2008. Vol. 17, No. 4. P. 899–921.
10. Keogh E.J., Wei L., Xi X., Vlachos M., Lee S.H., Protopapas P. Supporting Exact Indexing
of Arbitrarily Rotated Shapes and Periodic Time Series under Euclidean and Warping
Distance Measures // VLDB Journal. 2009. Vol. 18, No. 3. P. 611–630.
11. Lim S.-H., Park H., Kim S.-W. Using Multiple Indexes for Efficient Subsequence Matching
in Time-series Databases // Database Systems for Advanced Applications, 11th
International Conference, DASFAA 2006, Singapore, April 12–15, 2006, Proceedings.
Lecture Notes in Computer Science. Vol. 3882. Springer, 2006. P. 65–79.
12. Miniakhmetov R.M., Movchan A.V., Zymbler M.L. Accelerating Time Series Subsequence
Matching on the Intel Xeon Phi Many-core Coprocessor // Proceedings of the 38th
International Convention on Information and Communication Technology, Electronics and
342
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Microelectronics, MIPRO’2015, Opatija, Croatia, May 25–29, 2015. IEEE, 2015.
P. 1675–1680.
13. Pearson K. The Problem of the Random Walk // Nature. 1905. Vol. 72, No. 1865. P. 294.
14. Rakthanmanon T., Campana B., Mueen A., Batista G., Westover B., Zhu Q., Zakaria J.,
Keogh E. Searching and Mining Trillions of Time Series Subsequences under Dynamic
Time Warping // The 18th ACM SIGKDD Conference on Knowledge Discovery and Data
Mining, Beijing, China, 12–16 August, 2012. ACM, 2012. P. 262–270.
15. Sakurai Y., Faloutsos C., Yamamuro M. Stream Monitoring under the Time Warping
Distance // Proceedings of the 23rd International Conference on Data Engineering, ICDE
2007, The Marmara Hotel, Istanbul, Turkey, April 15–20, 2007. P. 1046–1055.
16. Sart D., Mueen A., Najjar W., Keogh E., Niennattrakul V. Accelerating Dynamic Time
Warping Subsequence Search with GPUs and FPGAs // The 10th IEEE International
Conference on Data Mining, Sydney, NSW, Australia, 13–17 December, 2010. IEEE, 2010.
P. 1001–1006.
17. Srikanthan S., Kumar A., Gupta R. Implementing the Dynamic Time Warping Algorithm
in Multithreaded Environments for Real Time and Unsupervised Pattern Discovery //
Computer and Communication Technology (ICCCT), Allahabad, India, 15–17 September,
2011. IEEE Computer Society, 2011. P. 394–398.
18. Takahashi N., Yoshihisa T., Sakurai Y., Kanazawa M. A Parallelized Data Stream
Processing System Using Dynamic Time Warping Distance // 2009 International
Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2009, Fukuoka,
Japan, March 16–19, 2009. IEEE Computer Society, 2009. P. 1100–1105.
19. Wang Z., Huang S., Wang L., Li H., Wang Y., Yang H. Accelerating Subsequence
Similarity Search Based on Dynamic Time Warping Distance with FPGA // Proceedings
of the 2013 ACM/SIGDA International Symposium on Field Programmable Gate Arrays,
FPGA ’13, Monterey, CA, USA, February 11–13, 2013. ACM, 2013. P. 53–62.
20. Zhang Y., Adl K., Glass J.R. Fast Spoken Query Detection Using Lower-bound Dynamic
Time Warping on Graphical Processing Units // Proceedings of the 2012 IEEE
International Conference on Acoustics, Speech and Signal Processing, ICASSP 2012,
Kyoto, Japan, March 25–30, 2012. IEEE, 2012. P. 5173–5176.
343
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Parallel algorithm for local-best-match time series subsequence
similarity search on the Intel MIC architecture
Aleksander Movchan and Mikhail Zymbler
Keywords: time series data mining, subsequences similarity search, parallel algorithm,
OpenMP, Intel Xeon Phi
The paper touches upon the problem of local-best-match time series subsequence similarity
search that assumes that a query sequence and a longer time series are given, and the task is to
find all the subsequences whose distance from the query is the minimal among their
neighboring subsequences whose distance from the query is under specified threshold. The
Dynamic Time Warping (DTW) is used as a distance metric, which currently is recognized as
the best similarity measure for most time series applications. However, computation of DTW
is an expensive operation, in spite of the existing sophisticated software approaches. Existing
hardware approaches to DTW computation involve GPU and FPGA architectures and ignore
the potential of Intel Many Integrated Core architecture. The paper proposes a parallel
algorithm for solving this problem using both the CPU and Intel Xeon Phi many-core
coprocessor. The implementation is based on the OpenMP parallel programming technology
and offload execution mode, where part of the code and data is transmitted to the coprocessor.
The algorithm utilizes a queue of subsequences on the processor side, which are uploaded to
the coprocessor for the DTW computations. The results of experiments confirms the
effectiveness of the algorithm.