=Paper=
{{Paper
|id=Vol-1576/196
|storemode=property
|title=Parallel implementation of searching the most similar subsequence in time series for computer systems with distributed memory
|pdfUrl=https://ceur-ws.org/Vol-1576/196.pdf
|volume=Vol-1576
|authors=Aleksandr Movchan,Mikhail Zymbler
}}
==Parallel implementation of searching the most similar subsequence in time series for computer systems with distributed memory==
https://ceur-ws.org/Vol-1576/196.pdf
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
Параллельная реализация поиска самой похожей
подпоследовательности временного ряда
для систем с распределенной памятью\ast
А.В. Мовчан, М.Л. Цымблер
Южно-Уральский государственный университет (НИУ)
В работе представлена параллельная реализация поиска самой похожей подпо-
следовательности временного ряда для вычислительного кластера c узлами на
базе многоядерных ускорителей Intel MIC. Алгоритм предполагает три уровня
параллелизма по данным. На первом уровне временной ряд разбивается на фраг-
менты равной длины, каждый из которых обрабатывается отдельным узлом вы-
числительного кластера; взаимодействие узлов реализуется на основе технологии
MPI. Второй уровень параллелизма предполагает разбиение фрагмента на сег-
менты равной длины, обрабатываемые нитями на основе технологии OpenMP.
Третий уровень параллелизма заключается в балансировке вычислительной на-
грузки между процессором и ускорителем. Процессор выполняет отбрасывание
заведомо непохожих подпоследовательностей. Ускоритель выполняет наиболее
трудоемкие вычисления меры схожести. Результаты вычислительных экспери-
ментов показывают эффективность разработанного алгоритма.
Ключевые слова: интеллектуальный анализ временных рядов, вычислительный
кластер, сопроцессор Intel Xeon Phi, OpenMP, MPI, динамическая трансформа-
ция шкалы времени.
1. Введение
Временной ряд представляет собой хронологически упорядоченную последовательность
вещественных значений, ассоциированных с отметками времени. Поиск похожих подпосле-
довательностей временного ряда предполагает нахождение участков данного ряда, которые
являются похожими на заданный ряд существенно меньшей длины. Данная задача возни-
кает в широком спектре предметных областей: мониторинг показателей физиологической
активности человека, моделирование климата и предсказание погоды, финансовое прогно-
зирование и др.
В качестве меры схожести временных рядов в настоящее время наиболее часто исполь-
зуется динамическая трансформация шкалы времени (Dynamic Time Warping, DTW) [1].
Мера DTW признается наилучшей для большинства приложений временных рядов [2],
несмотря на то, что она является вычислительно более сложной по сравнению с Евклидовым
расстоянием и ее вычисление занимает существенную часть времени работы алгоритмов
поиска похожих подпоследовательностей [4,14]. Для современных приложений, продуциру-
ющих временные ряды из триллионов элементов, требуются эффективные параллельные
алгоритмы поиска для многопроцессорных многоядерных аппаратных платформ.
Существующие на сегодня параллельные реализации алгоритмов поиска похожих под-
последовательностей временного ряда ориентированы в основном на ускорители GPU [6,10,
13, 17, 18] и FPGA [10, 16]. Исследования, посвященные использованию для решения данной
задачи кластерных вычислительных систем с узлами на базе многоядерных ускорителей,
отсутствуют.
Данная работа продолжает исследование [7], в рамках которого разработан параллель-
ный алгоритм поиска самой похожей подпоследовательности временного ряда для ускори-
Работа выполнена при финансовой поддержке Минобрнауки России в рамках ФЦП «Исследования и
\ast
разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014–
2020 годы» (Госконтракт № 14.574.21.0035).
615
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
теля с архитектурой Intel Many Integrated Core (MIC) [3]. Разработанный ранее алгоритм
переносится на платформу вычислительного кластера, узлы которого оснащены ускорите-
лями на базе архитектуры Intel MIC. Статья организована следующим образом. В разделе 2
приведена формальная постановка задачи и кратко описано аппаратно-программное окру-
жение исследования. Раздел 3 содержит описание принципов проектирования и реализации
алгоритма. Результаты вычислительных экспериментов по исследованию эффективности
предложенного алгоритма представлены в разделе 4. В заключении суммируются получен-
ные результаты.
2. Формальные определения и контекст исследования
2.1. Постановка задачи
Временной ряд (time series) T представляет собой хронологически упорядоченную по-
следовательность вещественных значений t1 , t2 , ..., tN , ассоциированных с отметками вре-
мени, где N — длина последовательности.
Подпоследовательность (subsequence) Ti m временного ряда T представляет собой непре-
рывное подмножество T из m элементов, начиная с позиции i, т.е. Ti m = ti , ti+1 , . . . , ti+m - 1 ,
где 1 \leq i \leq N и i + m \leq N .
Запрос (query) Q — подпоследовательность, поиск которой будет осуществляться в T .
Пусть n — длина запроса, n \ll N .
Задача поиска самой похожей подпоследовательности (best-match-search) предполага-
ет нахождение подпоследовательности Tj n (где 1 \leq j \leq N - n), максимально похожей на
запрос Q в смысле некоторой меры D, т.е. Tj n = argmin D(Ti n , Q).
динами-
1\leq i\leq N - n
В данной работе в качестве меры схожести D временных рядов используется
ческая трансформация шкалы времени (Dynamic Time Warping, DTW) , определяемая сле-
дующим образом. Пусть имеются два временных ряда X = x1 , x2 , ..., xN и Y = y1 , y2 , ..., yN ,
тогда
DT W (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 = j = 1, 2, . . . , N .
2.2. Аппаратно-программное окружение
В настоящее время вычислительные системы с кластерной архитектурой занимают 85%
списка TOP500 самых мощных суперкомпьютеров мира1 . Около 20% систем первой сотни
данного списка оснащены многоядерными ускорителями. Вычислительный кластер Tianhe-
2, занимающий первую строку списка, оснащен ускорителями на базе архитектуры Intel
MIC [3]. На сегодня наиболее часто используемым представителем семейства Intel MIC
является ускоритель (сопроцессор) Intel Xeon Phi.
Cопроцессор Intel Xeon Phi состоит из 61 ядра на базе архитектуры x86, соединенных
высокоскоростной двунаправленной шиной, где каждое ядро поддерживает 4-кратную ги-
перпоточность и содержит 512-битный векторный процессор. Каждое ядро имеет собствен-
ный кэш 1 и 2 уровня, при этом обеспечивается когерентность кэшей всех ядер. Сопроцессор
1
http://top500.org (ноябрь 2015 г.)
616
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
соединяется с хост-компьютером посредством интерфейса PCI Express. Поскольку сопро-
цессор Intel Xeon Phi основан на архитектуре x86, он поддерживает те же инструменты и
модели программирования, что и процессор Intel Xeon (OpenMP, Intel Cilk и др.).
Сопроцессор поддерживает следующие режимы запуска приложений: , native offload
и
symmetric . В режиме native
приложение выполняется независимо на сопроцессоре. В режи-
ме offloadприложение запускается на процессоре и выгружает вычислительно интенсивную
часть работы (код и данные) на сопроцессор. Режим symmetric
поддерживает взаимодей-
ствие сопроцессора и процессора в рамках модели обмена сообщениями.
2.3. Результаты предыдущих исследований
Данная статья является продолжением исследования, начатого в работе [7], где авто-
рами разработан параллельный алгоритм поиска самой похожей подпоследовательности
временного ряда для сопроцессора Intel Xeon Phi. Данный алгоритм основан на последо-
вательном алгоритме UCR-DTW [9], который в настоящее время является одним из самых
быстрых последовательных алгоритмов решения данной задачи [16]. Алгоритм UCR-DTW
выполняет последовательно вычисление динамической трансформации шкалы времени для
каждой подпоследовательности исходного временного ряда и запроса, используя при этом
каскад оценок значения меры DTW для отбрасывания заведомо непохожих подпоследова-
тельностей.
Параллельный алгоритм, разработанный на предыдущем этапе исследования, кратко
может быть описан следующим образом. Алгоритм задействует как процессор, так и сопро-
цессор. Сопроцессор используется исключительно для выполнения вычислительно затрат-
ной операции нахождения меры DTW для подпоследовательностей. Процессор выполняет
вычисление каскада оценок меры DTW для отбрасывания непохожих подпоследовательно-
стей и подготовку данных для выгрузки на сопроцессор. Процессор поддерживает очередь
подпоследовательностей-кандидатов, выгружаемых на сопроцессор для вычисления меры
DTW. Распараллеливание осуществляется на основе технологии OpenMP, для чего времен-
ной ряд разбивается на сегменты равной длины. Эксперименты на реальных и синтетиче-
ских данных показали преимущество разработанного алгоритма над аналогами для GPU,
особенно в случае поиска запросов длины более 103 .
Новый алгоритм должен распараллеливать вычисления между процессорами узлов
кластерной системы и использовать алгоритм, разработанный ранее.
3. Принципы проектирования и реализации алгоритма
3.1. Уровни параллелизма алгоритма
Алгоритм предполагает три уровня распараллеливания по данным, представленные на
рис. 1.
Первый уровень параллелизма представляет распределение нагрузки между вычисли-
тельными узлами кластерной системы. На этом уровне временной ряд разбивается на фраг-
менты равной длины, каждый из которых обрабатывается отдельным узлом вычислитель-
ного кластера. В процессе вычислений узлы обмениваются информацией о найденном зна-
чении меры DTW для подпоследовательности, которая на текущий момент является самой
похожей на запрос. Для реализации данного вида параллелизма используется технология
MPI.
Второй и третий уровни распараллеливания осуществляются в рамках одного вычис-
лительного узла, процессор и сопроцессор которого совместно исполняют разработанный
ранее алгоритм [7].
Второй уровень параллелизма реализуется посредством разбиения фрагмента на сег-
менты для того, чтобы каждый сегмент обрабатывался отдельной нитью процессора или
617
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
... Временной ряд
1 уровень
... Фрагменты
(узлы кластера)
2 уровень
... ... Сегменты
(нити процессора)
3 уровень
... ... ... ... ... ... ... ... ... ... Кандидаты
(нити сопроцессора)
Рис. 1: Уровни параллелизма алгоритма
сопроцессора. Данный вид параллелизма реализуется с помощью технологии программи-
рования OpenMP.
Третий уровень параллелизма заключается в распределении вычислительной нагрузки
между процессором и многоядерным сопроцессором таким образом, чтобы выполнять слож-
ные вычисления только на сопроцессоре. Процессор выполняет вычисление каскада оценок
меры DTW (LBKim [9], LBKeogh [4], LBKeoghEC [9]) для отбрасывания заведомо непохо-
жих подпоследовательностей. Сопроцессор используется для вычисления меры DTW. На
стороне процессора организуется очередь обрабатываемых подпоследовательностей. После
заполнения данные, имеющиеся в очереди, и код для их обработки посредством использо-
вания режима offload
выгружаются на ускоритель, где осуществляется вычисление меры
DTW.
3.2. Фрагментация и сегментация временного ряда
Для реализации описанных уровней параллелизма необходимо обеспечить разбиение
временного ряда на порции между вычислителями: распределение фрагментов по узлам
кластерной системы и разделение каждого фрагмента на сегменты.
Для того, чтобы избежать потери результирующих подпоследовательностей, находя-
щихся на стыке порций, нами используется техника , которая разбиения с перекрытием
заключается в следующем. В конец каждой порции временного ряда, за исключением по-
следней по порядку, добавляется n - 1 точек, взятых с начала следующей порции, где n —
длина запроса. Формальное определение разбиения с перекрытием выглядит следующим
образом.
Пусть P — количество порций, F k — k -я порция временного ряда T = t1 , t2 , . . . , tN ,
где 0 \leq k \leq P - 1. Обозначим за M общее количество подпоследовательностей, которые
необходимо обработать, M = N - n + 1. Тогда F k определяется как подпоследовательность
Tstart len , где
M
start = k \cdot \lfloor \rfloor + 1
P
\left\{
\lfloor M
P \rfloor + (M mod P ) + n - 1 , k = P - 1
len =
\lfloor M
P \rfloor + n - 1 , else
Фрагментация предполагает, что временной ряд разделяется на фрагменты равной
длины с помощью описанной выше техники, которые распределяются по узлам вычисли-
тельного кластера (один фрагмент на один узел). Количество порций-фрагментов P совпа-
618
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
дает с количеством узлов вычислительного кластера. В качестве длины запроса при разде-
лении без ограничения общности берется nmax — максимальная из всех возможных длин
запроса, nmax \ll N .
Для распределения вычислительной нагрузки между нитями процессора каждый фраг-
мент подвергается сегментациис помощью описанной выше техники. Длина сегмента яв-
ляется параметром алгоритма. Количество порций-сегментов определяется следующим об-
разом.
Пусть H — количество сегментов в фрагменте F k (где F k \equiv Tstart len определено выше),
S — количество нитей, выделяемых для параллельной обработки сегментов, L — длина
сегмента. Тогда
len
H = \lceil
\rceil \cdot S.
S \cdot L
Количество сегментов является кратным количеству нитей, выделяемых для их обра-
ботки, для обеспечения лучшей балансировки вычислительной нагрузки между нитями.
Сегмент должен целиком помещаться в оперативную память как процессора, так и сопро-
цессора.
Параметр L (длина сегмента) подбирается эмпирическим путем исходя из следующих
соображений. Слишком малая длина сегмента приведет к его быстрой обработке, но при
этом возрастут накладные расходы на динамическое выделение сегментов нитям процес-
сора. Слишком большая длина сегмента увеличивает вероятность наличия в нем заранее
неизвестного количества непохожих (отбрасываемых) подпоследовательностей, что приве-
дет к плохой балансировке вычислительной нагрузки.
3.3. Обновление оценки схожести запроса и самой похожей
подпоследовательности
Исходный последовательный алгоритм [9] использует переменную bsf (best-so-far) для
хранения оценки схожести запроса и подпоследовательности, наиболее похожей на него
на текущий момент. Для подпоследовательностей, имеющих схожесть с запросом меньше,
чем bsf, вычисление меры DTW не производится (они отбрасываются как заведомо непо-
хожие), что позволяет существенно сократить количество вычислений. В параллельном
алгоритме [9] стандартными средствами технологии OpenMP переменная bsf объявляется
разделяемой (shared) для нитей процессора, обрабатывающих сегменты ряда.
BSF Exchange BSF Recv
BSF Recv
new_bsf = last_bsf
BSF Send
Probe(bsf_buf)
[bsf_buf is empty]
BSF Send else
Recv(bsf)
[last_bsf - total_bsf > eps]
new_bsf = min(new_bsf, bsf)
else
last_bsf = total_bsf
ISend(i, total_bsf) ∀ i, i ≠ rank last_bsf = new_bsf
total_bsf = min(total_bsf, new_bsf)
Рис. 2: Обновление оценки схожести
619
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
В случае платформы вычислительного кластера необходима альтернатива общей пе-
ременной, которая хранит наилучшую текущую оценку и обновляется всеми процессами,
обрабатывающими фрагменты ряда. Данная реализация использует следующий подход к
обновлению оценки схожести, представленный на рис. 2. Каждый процесс поддерживает
локальную оценку схожести, которая обновляется перед началом обработки очередного сег-
мента. Обновление выполняется в два шага: сначала осуществляется изменение локальной
оценки на наилучшую оценку, полученную от других процессов, затем запускается широко-
вещательная рассылка обновленной оценки другим процессам. При этом для сокращения
количества обменов между процессами отправка обновленной оценки производится лишь
в том случае, когда новая оценка улучшила текущую более чем на некоторое пороговое
значение \scrE > 0, являющееся параметром алгоритма. Коммуникации между процессами
реализуются посредством технологии MPI.
3.4. Реализация
Параллельный алгоритм поиска самой похожей подпоследовательности временного ря-
да для вычислительного кластера с сопроцессорами Intel Xeon Phi представлен на рис. 3.
Node's CPU Node's Intel Xeon Phi
Swap Buf_1 Read data
Open file
and Buf_2 in Buf_1
k := 0
Send Buf_1 Receive Buf
Read data
in Buf_2
Process Process Process Wait for Receive
Segments Segments ... Segments candidates candidates
by UCR-DTW* by UCR-DTW* by UCR-DTW*
Send candidates
else ...
Receive DTW DTW
phi_result
[no candidates and
all threads are finished]
phi_result = min_dist
(res1, ..., resPHI_THREADS)
result = min_dist(result, res1, ..., resCPU_THREADS)
[Buf_2 is
else empty] Output
Send phi_result
Close file result
Process Segments by UCR-DTW*
[k > H]
BSF Exchange segment := segments[k] k := k + 1 UCR-DTW*(segment)
else
Рис. 3: Поиск самой похожей подпоследовательности на кластере с сопроцессорами
Процесс, запускаемый на узле вычислительного кластера, реализует данный алгоритм
для обработки соответствующего фрагмента временного ряда. Процессор выполняет обра-
ботку сегментов фрагмента, реализуя модификацию разработанного ранее алгоритма [7].
Процессор поддерживает очередь подпоследовательностей-кандидатов, выгружаемых на
сопроцессор, который выполняет для них вычисление меры DTW (деятельность DTW). Про-
620
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
цессор выполняет вычисление каскада оценок меры DTW для отбрасывания непохожих
подпоследовательностей и подготовку данных для выгрузки на сопроцессор (деятельность
UCR-DTW*). Распараллеливание осуществляется на основе технологии OpenMP, для чего вре-
менной ряд разбивается на сегменты равной длины. Для увеличения эффективности отбра-
сывания непохожих подпоследовательностей перед обработкой сегмента осуществляется об-
новление оценки схожести на основе алгоритма, описанного в разделе 3.3 (деятельность BSF
Exchange). Обновление оценки схожести реализуется с помощью технологии MPI.
Результирующая подпоследовательность заданного временного ряда находится следу-
ющим образом. Один из процессов (например, с номером 0) объявляется мастером, осталь-
ные — рабочими. Рабочие отправляют мастеру результат вычислений соответствующего
фрагмента, после чего мастер находит среди полученных результатов наилучший и выдает
его пользователю.
4. Эксперименты
Для оценки эффективности разработанного алгоритма нами выполнены эксперименты
на суперкомпьютере «Торнадо ЮУрГУ», спецификации вычислительного узла которого
представлены в табл. 1.
Таблица 1: Спецификация вычислительного узла суперкомпьютера «Торнадо ЮУрГУ»
Спецификации Процессор Сопроцессор
Модель Intel Xeon X5680 Intel Xeon Phi SE10X
Количество ядер 6 61
Тактовая частота, ГГц 3.33 1.1
Количество нитей на ядро 2 4
Пиковая производительность, TFLOPS 0.371 1.076
В экспериментах было задействовано от 1 до 64 вычислительных узлов кластера. В ка-
честве данных в экспериментах использовался синтетический временной ряд, полученный
на основе модели случайных блужданий [8]. В экспериментах исследовались ускорение и
расширяемость предложенного алгоритма и его версии, которая не задействует сопроцес-
сор (т.е. выполняет вычисления меры DTW полностью на центральном процессоре). Также
выполнено сравнение ускорения данного алгоритма и его версии с аналогичными разработ-
ками.
4.1. Ускорение и расширяемость алгоритма
В первой серии экспериментов исследовалось ускорениеалгоритма, т.е. значение t1 /tP ,
где t1 и tP — время работы алгоритма на одном и P узлах вычислительного кластера со-
ответственно при одной и той же длине временного ряда, подвергаемого фрагментации и
распределяемого по узлам. Использовались следующие значения параметров эксперимента:
длина временного ряда N = 8\cdot 108 (размер данных 6 Гб), длина запроса n = 4000, длина сег-
мента L = 106 , пороговое значение улучшения оценки \scrE = 0.01. Результаты экспериментов
представлены на рис. 4.
Во второй серии экспериментов исследовалась расширяемость алгоритма, т.е. значение
t1 T1 /tP TP , где t1 T1 и tP TP — время обработки алгоритмом временного ряда T1 на одном уз-
ле и временного ряда TP на P узлах вычислительного кластера соответственно, где длина
621
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
30 1000
Intel Xeon Phi Intel Xeon Phi
25 Intel Xeon Phi 0.44% Intel Xeon Phi
800
20
,
600
15 0.44% 0.45%
400
10 0.54%
0.45%
200 0.53% 0.63%
5
0.62% 0.74%
0.74% 0.87%
0.90% 0.92% 0.86%
0 0
1 4 16 32 64 1 2 4 8 16 32 64
(a) Ускорение (b) Время выполнения
Рис. 4: Исследование ускорения алгоритма
TP превосходит длину ряда T1 в P раз. Использовались следующие значения параметров
эксперимента: длина ряда T1 — 108 (размер данных — от 0.7 Гб до 47.7 Гб), длина запро-
са n = 4000, длина сегмента L = 106 , пороговое значение улучшения оценки \scrE = 0.01.
Результаты экспериментов представлены на рис. 5.
1.4 Intel Xeon Phi 200 Intel Xeon Phi 0.60%
Intel Xeon Phi Intel Xeon Phi
1.2
0.56% 0.59%
150 0.59%
1.0 0.58% 0.58%
,
0.42%
0.8
100 0.60%
0.6 0.62% 0.60% 0.60% 0.57% 0.59%
0.43%
0.4 50
0.2
0.0 0
1 4 16 32 64 1 2 4 8 16 32 64
(a) Расширяемость (b) Время выполнения
Рис. 5: Исследование расширяемости алгоритма
Проценты над столбцами графиков указывают долю подпоследовательностей соответ-
ствующего временного ряда, для которых осуществлялось вычисление меры DTW (т.е. под-
последовательности, которые не были отброшены как заведомо непохожие). Как можно
заметить, в экспериментах по исследованию ускорения доля подпоследовательностей, ко-
торые не были отброшены как заведомо непохожие, возрастает с увеличением количества
узлов, что снижает ускорение. Это можно объяснить следующим образом. Поскольку узлы
кластера обрабатывают фрагменты временного ряда одновременно и независимо друг от
друга, то количество подпоследовательностей, для которых производится вычисление ме-
ры DTW, до обнаружения значительного улучшения оценки bsf возрастает. В результате
при увеличении количества узлов возрастает общее количество подпоследовательностей,
которые не были отброшены как заведомо непохожие.
Во второй серии экспериментов расширяемость остается примерно на уровне единицы,
однако на 64 узлах наблюдается расширяемость больше единицы. Это объясняется умень-
622
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
шением доли подпоследовательностей, для которых производится вычисление меры DTW.
Данное уменьшение связано с тем, что для исследования расширяемости на 64 узлах был
задействован синтетический ряд в 2 раза большей длины, чем в экспериментах на 32 узлах,
который содержал большее количество подпоследовательностей, позволивших улучшить
оценку bsf раньше.
4.2. Сравнение с аналогами
Имеющиеся на сегодня параллельные реализации алгоритма UCR-DTW ориентированы
на многоядерные ускорители GPU [10,13,17,18] (с возможным совместным использованием
в вычислениях центрального процессора и графического ускорителя [6]) и FPGA [10, 16].
Эксперименты, проведенные на предыдущем этапе исследования показали [7], что разра-
ботанный авторами параллельный алгоритм для процессора и сопроцессора Intel Xeon Phi
способен дать большую эффективность, чем аналоги для GPU.
Работы, в которых предлагаются параллельные реализации рассматриваемой задачи на
платформе вычислительного кластера с узлами на базе многоядерных ускорителей, в насто-
ящее время, по-видимому, отсутствуют. Относительно релевантной работой является ста-
тья [11], в которой описано распараллеливание алгоритма UCR-DTW для вычислительного
кластера с узлами без ускорителей. Распараллеливание выполнено на основе использования
фреймворка Apache Spark [12]. В рамках данного фреймворка приложение запускается как
процесс, координируемый мастер-узлом вычислительного кластера, на котором установлен
соответствующий драйвер. Алгоритм предполагает фрагментацию временного ряда с пе-
рекрытием (как и алгоритм, описанный в данной работе), однако количество фрагментов
не совпадает с количеством узлов вычислительного кластера. Фрагменты сохраняются в
виде отдельных файлов, доступных всем узлам в силу использования распределенной фай-
ловой системы HDFS (Hadoop Distributed File System). Каждый фрагмент обрабатывается
отдельным процессом, реализующим последовательный алгоритм UCR-DTW. Количество
процессов, запускаемых на узле кластера, равно количеству ядер процессора на данном
узле. Алгоритм использует обновление оценки bsf, которое выполняется следующим об-
разом. Один из процессов объявляется мастером, остальные — рабочими. Мастер хранит
наилучшую из локальных оценок рабочих. По завершении обработки фрагментов рабочие
пересылают локальные оценки мастеру, который выбирает из этих оценок наилучшую и
рассылает ее рабочим.
2 4 6
20
Intel Xeon Phi
Intel Xeon Phi
15 Shabib et al
10
5
0 220 400 520 660 220 400 520 660 220 400 520 660
, . , . , .
Рис. 6: Сравнение алгоритма с аналогом
В статье [11] приведены результаты экспериментов по исследованию ускорения разрабо-
танного авторами статьи алгоритма на 2, 4 и 6 узлах. Эксперименты проводились на узлах с
4-ядерными процессорами, на каждом узле выполнялось по 4 процесса, реализующих алго-
ритм UCR-DTW, длина запроса n = 128, в качестве данных использовался синтетический
623
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
временной ряд, полученный на основе модели случайных блужданий. Ускорение считалось
по отношению к последовательному алгоритму UCR-DTW.
Нами были проведены эксперименты по сравнению разработанных нами алгоритмов
с алгоритмом из статьи [11]. Для создания честных условий сравнения на нашей вычис-
лительной системе использовались 4 нити на узел, каждая из которых выполняла поиск
похожих подпоследовательностей, и сравнивалось ускорение алгоритмов. Результаты экс-
периментов представлены на рис. 6.
Разработанные нами алгоритмы показали большее ускорение по сравнению с алгорит-
мом из статьи [11] во всех случаях. Однако алгоритм, использующий сопроцессор, показал
меньшее ускорение, чем его версия, не использующая сопроцессор. Это объясняется тем, что
алгоритм, использующий сопроцессор, показывает наибольшую эффективность при длине
запроса больше 103 [7].
5. Заключение
В данной статье описаны проектирование и реализация параллельного алгоритма по-
иска самой похожей подпоследовательности временного ряда для вычислительной системы
с кластерной архитектурой, узлы которой оснащены многоядерными ускорителями Intel
Xeon Phi.
Алгоритм предполагает три уровня параллелизма по данным. На первом уровне вре-
менной ряд разбивается на фрагменты равной длины, распределяемые по узлам вычисли-
тельного кластера. В ходе обработки вычислительные узлы обмениваются информацией о
найденном значении меры DTW для подпоследовательности, которая на текущий момент
является самой похожей на запрос. Для реализации данного вида параллелизма исполь-
зуется технология MPI. Второй уровень параллелизма предполагает разбиение фрагмента
на сегменты равной длины, обрабатываемые нитями на основе технологии OpenMP. Тре-
тий уровень параллелизма заключается в балансировке вычислительной нагрузки между
процессором и ускорителем. Процессор выполняет вычисление каскада оценок меры DTW
для отбрасывания заведомо непохожих подпоследовательностей. Сопроцессор используется
для вычисления меры DTW. Разбиение данных на порции (фрагменты и сегменты) выпол-
няется с использованием техники перекрытия, предотвращающей потерю результирующих
подпоследовательностей, которые могут находиться на стыке порций.
Представлены результаты вычислительных экспериментов, показывающих эффектив-
ность разработанного алгоритма и его превосходство над известными аналогами.
Литература
1. Berndt D.J., Clifford J. Using Dynamic Time Warping to Find Patterns in Time Series //
Proceedings of the 1994 AAAI Workshop on Knowledge Discovery in Databases, Seattle,
Washington, July 1994. AAAI Press, 1994. P. 359–370.
2. 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.
3. Duran A., Klemm M. The Intel Many Integrated Core Architecture // Proceedings of the
2012 International Conference on High Performance Computing and Simulation, HPCS
2012, Madrid, Spain, July 2–6, 2012. IEEE, 2012. P. 365–366.
4. Fu A.W.-C., Keogh E.J., Lau L.Y.H., Ratanamahatana C. Scaling and Time Warping in
Time Series Querying // Proceedings of the 31st International Conference on Very Large
DataBases, Trondheim, Norway, August 30 – September 2, 2005. P. 649–660.
624
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
5. Heinecke A., Klemm M., Pfluger D., Bode A., Bungartz H.-J. Extending a Highly Parallel
Data Mining Algorithm to the Intel Many Integrated Сore Architecture // Proceedings of
the Euro-Par 2011 Workshops, Bordeaux, France, August 29 – September 2, 2011. Lecture
Notes in Computer Science. 2012. Vol. 7156. Springer, 2011. P. 375–384.
6. Huang S., Dai G., Sun Y., Wang Z., Wang Y., Yang H. DTW-Based Subsequence
Similarity Search on AMD Heterogeneous Computing Platform // Proceedings of the 10th
IEEE International Conference on High Performance Computing and Communications &
2013 IEEE International Conference on Embedded and Ubiquitous Computing,
HPCC/EUC 2013, Zhangjiajie, China, November 13–15, 2013. IEEE Computer Society,
2013. P. 1054–1063.
7. 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
Microelectronics, MIPRO 2015, Opatija, Croatia, May 25–29, 2015. IEEE Computer
Society, 2015. P. 1399–1404.
8. Pearson K. The Problem of the Random Walk // Nature. 1905. Vol. 72, No. 1865. P. 294.
9. 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 // Proceedings of the 18th ACM SIGKDD Conference on Knowledge
Discovery and Data Mining, Beijing, China, August 12–16, 2012. ACM, 2012. P. 262–270.
10. Sart D., Mueen A., Najjar W., Keogh E., Niennattrakul V. Accelerating Dynamic Time
Warping Subsequence Search with GPUs and FPGAs // Proceedings of the 10th IEEE
International Conference on Data Mining, Sydney, NSW, Australia, December 13–17, 2010.
IEEE Computer Society, 2010. P. 1001–1006.
11. Shabib A., Narang A., Niddodi C.P., Das M., Pradeep R., Shenoy V., Auradkar P., Vignesh
T.S., Sitaram D. Parallelization of Searching and Mining Time Series Data Using Dynamic
Time Warping // Proceedings of the International Conference on Advances in Computing,
Communications and Informatics, ICACCI 2015, Kochi, India, August 10–13, 2015. IEEE
Computer Society, 2015. P. 343–348.
12. Shanahan J.G., Dai L. Large Scale Distributed Data Science using Apache Spark //
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining, Sydney, NSW, Australia, August 10–13, 2015. ACM, 2015. P. 2323–2324.
13. Srikanthan S., Kumar A., Gupta R. Implementing the Dynamic Time Warping Algorithm
in Multithreaded Environments for Real Time and Unsupervised Pattern Discovery //
Proceedings of the Computer and Communication Technology (ICCCT) conference,
Allahabad, India, September 15–17, 2011. IEEE Computer Society, 2011. P. 394–398.
14. Takahashi N., Yoshihisa T., Sakurai Y., Kanazawa M. A Parallelized Data Stream
Processing System Using Dynamic Time Warping Distance // Proceedings of the 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.
15. Tarango J., Keogh E.J., Brisk P. Instruction set extensions for Dynamic Time Warping //
Proceedings of the International Conference on Hardware/Software Codesign and System
Synthesis, CODES+ISSS 2013, Montreal, QC, Canada, September 29 – October 4, 2013.
IEEE Computer Society, 2013. P 18:1–18:10.
625
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
16. 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.
17. Xiao L., Zheng Y., Tang W., Yao G., Ruan L. Parallelizing Dynamic Time Warping
Algorithm Using Prefix Computations on GPU // Proceedings of the 10th IEEE
International Conference on High Performance Computing and Communications & 2013
IEEE International Conference on Embedded and Ubiquitous Computing, HPCC/EUC
2013, Zhangjiajie, China, November 13–15, 2013. IEEE Computer Society, 2013.
P. 294–299.
18. 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 Computer Society, 2012. P. 5173–5176.
626
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
Parallel implementation
of searching the most similar subsequence in time series
for computer systems with distributed memory
A.V. Movchan, M.L. Zymbler
South Ural State University (Chelyabinsk, Russia)
The paper presents parallel implementation of searching the most similar subsequence
in time series for computer cluster system with nodes based on Intel MIC accelerators.
The algorithm involves three levels of data parallelism. The first level provides partitio-
ning of time series into equal-length fragments, each of which is processed on a separate
node of the computer cluster; nodes interact using MPI technology. The second
level of parallelism supposes division of the fragment into equal-length segments and
processing of each segment by a separate thread by means of OpenMP technology.
The third level provides load balancing between CPU and accelerator. CPU performs
pruning of dissimilar subsequences. Accelerator performs heavy-weighted calculations
of similarity measure. The results of experiments confirm the efficiency of algorithm.
Keywords:time series data mining, computer cluster, Intel Xeon Phi coprocessor,
OpenMP, MPI, dynamic time warping.
References
1. Berndt D.J., Clifford J. Using Dynamic Time Warping to Find Patterns in Time Series //
Proceedings of the 1994 AAAI Workshop on Knowledge Discovery in Databases, Seattle,
Washington, July 1994. AAAI Press, 1994. P. 359–370.
2. 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.
3. Duran A., Klemm M. The Intel Many Integrated Core Architecture // Proceedings of the
2012 International Conference on High Performance Computing and Simulation, HPCS
2012, Madrid, Spain, July 2–6, 2012. IEEE, 2012. P. 365–366.
4. Fu A.W.-C., Keogh E.J., Lau L.Y.H., Ratanamahatana C. Scaling and Time Warping in
Time Series Querying // Proceedings of the 31st International Conference on Very Large
DataBases, Trondheim, Norway, August 30 – September 2, 2005. P. 649–660.
5. Heinecke A., Klemm M., Pfluger D., Bode A., Bungartz H.-J. Extending a Highly Parallel
Data Mining Algorithm to the Intel Many Integrated Сore Architecture // Proceedings of
the Euro-Par 2011 Workshops, Bordeaux, France, August 29 – September 2, 2011. Lecture
Notes in Computer Science. 2012. Vol. 7156. Springer, 2011. P. 375–384.
6. Huang S., Dai G., Sun Y., Wang Z., Wang Y., Yang H. DTW-Based Subsequence
Similarity Search on AMD Heterogeneous Computing Platform // Proceedings of the 10th
IEEE International Conference on High Performance Computing and Communications &
2013 IEEE International Conference on Embedded and Ubiquitous Computing,
HPCC/EUC 2013, Zhangjiajie, China, November 13–15, 2013. IEEE Computer Society,
2013. P. 1054–1063.
7. 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
627
Параллельные вычислительные технологии (ПаВТ’2016) || Parallel computational technologies (PCT’2016)
agora.guru.ru/pavt
Microelectronics, MIPRO 2015, Opatija, Croatia, May 25–29, 2015. IEEE Computer
Society, 2015. P. 1399–1404.
8. Pearson K. The Problem of the Random Walk // Nature. 1905. Vol. 72, No. 1865. P. 294.
9. 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 // Proceedings of the 18th ACM SIGKDD Conference on Knowledge
Discovery and Data Mining, Beijing, China, August 12–16, 2012. ACM, 2012. P. 262–270.
10. Sart D., Mueen A., Najjar W., Keogh E., Niennattrakul V. Accelerating Dynamic Time
Warping Subsequence Search with GPUs and FPGAs // Proceedings of the 10th IEEE
International Conference on Data Mining, Sydney, NSW, Australia, December 13–17, 2010.
IEEE Computer Society, 2010. P. 1001–1006.
11. Shabib A., Narang A., Niddodi C.P., Das M., Pradeep R., Shenoy V., Auradkar P., Vignesh
T.S., Sitaram D. Parallelization of Searching and Mining Time Series Data Using Dynamic
Time Warping // Proceedings of the International Conference on Advances in Computing,
Communications and Informatics, ICACCI 2015, Kochi, India, August 10–13, 2015. IEEE
Computer Society, 2015. P. 343–348.
12. Shanahan J.G., Dai L. Large Scale Distributed Data Science using Apache Spark //
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining, Sydney, NSW, Australia, August 10–13, 2015. ACM, 2015. P. 2323–2324.
13. Srikanthan S., Kumar A., Gupta R. Implementing the Dynamic Time Warping Algorithm
in Multithreaded Environments for Real Time and Unsupervised Pattern Discovery //
Proceedings of the Computer and Communication Technology (ICCCT) conference,
Allahabad, India, September 15–17, 2011. IEEE Computer Society, 2011. P. 394–398.
14. Takahashi N., Yoshihisa T., Sakurai Y., Kanazawa M. A Parallelized Data Stream
Processing System Using Dynamic Time Warping Distance // Proceedings of the 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.
15. Tarango J., Keogh E.J., Brisk P. Instruction set extensions for Dynamic Time Warping //
Proceedings of the International Conference on Hardware/Software Codesign and System
Synthesis, CODES+ISSS 2013, Montreal, QC, Canada, September 29 – October 4, 2013.
IEEE Computer Society, 2013. P 18:1–18:10.
16. 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.
17. Xiao L., Zheng Y., Tang W., Yao G., Ruan L. Parallelizing Dynamic Time Warping
Algorithm Using Prefix Computations on GPU // Proceedings of the 10th IEEE
International Conference on High Performance Computing and Communications & 2013
IEEE International Conference on Embedded and Ubiquitous Computing, HPCC/EUC
2013, Zhangjiajie, China, November 13–15, 2013. IEEE Computer Society, 2013.
P. 294–299.
18. 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 Computer Society, 2012. P. 5173–5176.
628