В работе представлена параллельная реализация поиска самой похожей подпоследовательности временного ряда для вычислительного кластера c узлами на базе многоядерных ускорителей Intel MIC. Алгоритм предполагает три уровня параллелизма по данным. На первом уровне временной ряд разбивается на фрагменты равной длины, каждый из которых обрабатывается отдельным узлом вычислительного кластера; взаимодействие узлов реализуется на основе технологии MPI. Второй уровень параллелизма предполагает разбиение фрагмента на сегменты равной длины, обрабатываемые нитями на основе технологии OpenMP. Третий уровень параллелизма заключается в балансировке вычислительной нагрузки между процессором и ускорителем. Процессор выполняет отбрасывание заведомо непохожих подпоследовательностей. Ускоритель выполняет наиболее трудоемкие вычисления меры схожести. Результаты вычислительных экспериментов показывают эффективность разработанного алгоритма.
Параллельная реализация поиска самой похожей подпоследовательности временного ряда для систем с распределенной памятью\ast agora.guru.ru/pavt теля с архитектурой Intel Many Integrated Core (MIC) [3]. Разработанный ранее алгоритм переносится на платформу вычислительного кластера, узлы которого оснащены ускорителями на базе архитектуры Intel MIC. Статья организована следующим образом. В разделе 2 приведена формальная постановка задачи и кратко описано аппаратно-программное окружение исследования. Раздел 3 содержит описание принципов проектирования и реализации алгоритма. Результаты вычислительных экспериментов по исследованию эффективности предложенного алгоритма представлены в разделе 4. В заключении суммируются полученные результаты. 2. Формальные определения и контекст исследования 2.1. Постановка задачи где 1 \leq i l\eq
N и i + m \leq
N . Пусть n — длина запроса, n \l
N .
Временной ряд (time series) T представляет собой хронологически упорядоченную последовательность вещественных значений t1, t2, ..., tN , ассоциированных с отметками времени, где N — длина последовательности.
Подпоследовательность (subsequence) Ti m временного ряда T представляет собой непрерывное подмножество T из m элементов, начиная с позиции i, т.е. Ti m = ti, ti+1, . . . , ti+m- 1, Запрос (query) Q — подпоследовательность, поиск которой будет осуществляться в T . Задача поиска самой похожей подпоследовательности (best-match-search) предполагает нахождение подпоследовательности Tj n (где 1 \leq запрос Q в смысле некоторой меры D, т.е. Tj n = argmin D(Ti n, Q). j \leq
N - n), максимально похожей на В данной работе в качестве меры схожести D временных рядов используется динамическая трансформация шкалы времени (Dynamic Time Warping, DTW) , определяемая следующим образом. Пусть имеются два временных ряда X = x1, x2, ..., xN и Y = y1, y2, ..., yN , 1l\eq i l\eq N- n тогда
DT W (X, Y ) = d(N, N ), где d(i, j) = | xi - yj| + min d(0, 0) = 0; d(i, 0) = d(0, j) = \infty ; i = j = 1, 2, . . . , N . 2.2. Аппаратно-программное окружение
В настоящее время вычислительные системы с кластерной архитектурой занимают 85% списка TOP500 самых мощных суперкомпьютеров мира 1. Около 20% систем первой сотни данного списка оснащены многоядерными ускорителями. Вычислительный кластер Tianhe2, занимающий первую строку списка, оснащен ускорителями на базе архитектуры Intel MIC [3]. На сегодня наиболее часто используемым представителем семейства Intel MIC является ускоритель (сопроцессор) Intel Xeon Phi.
Cопроцессор Intel Xeon Phi состоит из 61 ядра на базе архитектуры x86, соединенных высокоскоростной двунаправленной шиной, где каждое ядро поддерживает 4-кратную гиперпоточность и содержит 512-битный векторный процессор. Каждое ядро имеет собственный кэш 1 и 2 уровня, при этом обеспечивается когерентность кэшей всех ядер. Сопроцессор 1http://top500.org (ноябрь 2015 г.) соединяется с хост-компьютером посредством интерфейса PCI Express. Поскольку сопроцессор Intel Xeon Phi основан на архитектуре x86, он поддерживает те же инструменты и модели программирования, что и процессор Intel Xeon (OpenMP, Intel Cilk и др.).
Сопроцессор поддерживает следующие режимы запуска приложений: native, ofload и symmetric. В режиме native приложение выполняется независимо на сопроцессоре. В режиме ofload приложение запускается на процессоре и выгружает вычислительно интенсивную часть работы (код и данные) на сопроцессор. Режим symmetric поддерживает взаимодействие сопроцессора и процессора в рамках модели обмена сообщениями. 2.3. Результаты предыдущих исследований
Данная статья является продолжением исследования, начатого в работе [7], где
авторами разработан параллельный алгоритм поиска самой похожей подпоследовательности
временного ряда для сопроцессора Intel Xeon Phi. Данный алгоритм основан на
последовательном алгоритме UCR-DTW [
Параллельный алгоритм, разработанный на предыдущем этапе исследования, кратко может быть описан следующим образом. Алгоритм задействует как процессор, так и сопроцессор. Сопроцессор используется исключительно для выполнения вычислительно затратной операции нахождения меры DTW для подпоследовательностей. Процессор выполняет вычисление каскада оценок меры DTW для отбрасывания непохожих подпоследовательностей и подготовку данных для выгрузки на сопроцессор. Процессор поддерживает очередь подпоследовательностей-кандидатов, выгружаемых на сопроцессор для вычисления меры DTW. Распараллеливание осуществляется на основе технологии OpenMP, для чего временной ряд разбивается на сегменты равной длины. Эксперименты на реальных и синтетических данных показали преимущество разработанного алгоритма над аналогами для GPU, особенно в случае поиска запросов длины более 103.
Новый алгоритм должен распараллеливать вычисления между процессорами узлов кластерной системы и использовать алгоритм, разработанный ранее. 3. Принципы проектирования и реализации алгоритма 3.1. Уровни параллелизма алгоритма
Алгоритм предполагает три уровня распараллеливания по данным, представленные на рис. 1.
Первый уровень параллелизма представляет распределение нагрузки между вычислительными узлами кластерной системы. На этом уровне временной ряд разбивается на фрагменты равной длины, каждый из которых обрабатывается отдельным узлом вычислительного кластера. В процессе вычислений узлы обмениваются информацией о найденном значении меры DTW для подпоследовательности, которая на текущий момент является самой похожей на запрос. Для реализации данного вида параллелизма используется технология MPI.
Второй и третий уровни распараллеливания осуществляются в рамках одного вычислительного узла, процессор и сопроцессор которого совместно исполняют разработанный ранее алгоритм [7].
Второй уровень параллелизма реализуется посредством разбиения фрагмента на сегменты для того, чтобы каждый сегмент обрабатывался отдельной нитью процессора или agora.guru.ru/pavt ...
... ...
...
Временной ряд Фрагменты (узлы кластера) 1 уровень 2 уровень 3 уровень Сегменты (нити процессора) ... Кандидаты (нити сопроцессора) ...
...
...
...
...
...
...
...
...
Рис. 1: Уровни параллелизма алгоритма сопроцессора. Данный вид параллелизма реализуется с помощью технологии программирования OpenMP.
Третий уровень параллелизма заключается в распределении вычислительной нагрузки
между процессором и многоядерным сопроцессором таким образом, чтобы выполнять
сложные вычисления только на сопроцессоре. Процессор выполняет вычисление каскада оценок
меры DTW (LBKim [
выгружаются на ускоритель, где осуществляется вычисление меры DTW. 3.2. Фрагментация и сегментация временного ряда
Для реализации описанных уровней параллелизма необходимо обеспечить разбиение временного ряда на порции между вычислителями: распределение фрагментов по узлам кластерной системы и разделение каждого фрагмента на сегменты.
Для того, чтобы избежать потери результирующих подпоследовательностей, находящихся на стыке порций, нами используется техника разбиения с перекрытием , которая заключается в следующем. В конец каждой порции временного ряда, за исключением последней по порядку, добавляется n
- 1 точек, взятых с начала следующей порции, где n — длина запроса. Формальное определение разбиения с перекрытием выглядит следующим образом. где 0 \leq k \leq
P Tstart len, где Пусть P — количество порций, F k — k-я порция временного ряда T = t1, t2, . . . , tN , 1. Обозначим за M общее количество подпоследовательностей, которые необходимо обработать, M = N - n + 1. Тогда F k определяется как подпоследовательность start = k \cdot \lfor
M
P \rflo + 1 len = дает с количеством узлов вычислительного кластера. В качестве длины запроса при разделении без ограничения общности берется nmax — максимальная из всех возможных длин запроса, nmax \l N .
Для распределения вычислительной нагрузки между нитями процессора каждый фрагмент подвергается сегментации с помощью описанной выше техники. Длина сегмента является параметром алгоритма. Количество порций-сегментов определяется следующим образом.
Пусть H — количество сегментов в фрагменте F k (где F k \equiv Tstart len определено выше), S — количество нитей, выделяемых для параллельной обработки сегментов, L — длина сегмента. Тогда
len
H = \lcei S \cdot L r\ceil c\dot S.
Количество сегментов является кратным количеству нитей, выделяемых для их обработки, для обеспечения лучшей балансировки вычислительной нагрузки между нитями. Сегмент должен целиком помещаться в оперативную память как процессора, так и сопроцессора.
Параметр L (длина сегмента) подбирается эмпирическим путем исходя из следующих соображений. Слишком малая длина сегмента приведет к его быстрой обработке, но при этом возрастут накладные расходы на динамическое выделение сегментов нитям процессора. Слишком большая длина сегмента увеличивает вероятность наличия в нем заранее неизвестного количества непохожих (отбрасываемых) подпоследовательностей, что приведет к плохой балансировке вычислительной нагрузки. 3.3. Обновление оценки схожести запроса и самой похожей
подпоследовательности
Исходный последовательный алгоритм [
BSF Exchange
BSF Recv BSF Recv
BSF Send BSF Send
[last_bsf - total_bsf > eps] else last_bsf = total_bsf new_bsf = last_bsf
Probe(bsf_buf) [bsf_buf is empty]
else
Recv(bsf) new_bsf = min(new_bsf, bsf) total_bsf = min(total_bsf, new_bsf) ISend(i, total_bsf) ∀ i, i ≠ rank
last_bsf = new_bsf Рис. 2: Обновление оценки схожести В случае платформы вычислительного кластера необходима альтернатива общей переменной, которая хранит наилучшую текущую оценку и обновляется всеми процессами, обрабатывающими фрагменты ряда. Данная реализация использует следующий подход к обновлению оценки схожести, представленный на рис. 2. Каждый процесс поддерживает локальную оценку схожести, которая обновляется перед началом обработки очередного сегмента. Обновление выполняется в два шага: сначала осуществляется изменение локальной оценки на наилучшую оценку, полученную от других процессов, затем запускается широковещательная рассылка обновленной оценки другим процессам. При этом для сокращения количества обменов между процессами отправка обновленной оценки производится лишь в том случае, когда новая оценка улучшила текущую более чем на некоторое пороговое значение \scrE > 0, являющееся параметром алгоритма. Коммуникации между процессами реализуются посредством технологии MPI. 3.4. Реализация
Параллельный алгоритм поиска самой похожей подпоследовательности временного ряда для вычислительного кластера с сопроцессорами Intel Xeon Phi представлен на рис. 3.
and Buf_2 Read data in Buf_1
k := 0
Read data in Buf_2
by UCR-DTW* ...
Process Segments by UCR-DTW* result = min_dist(result, res1, ..., resCPU_THREADS) [Buf_2 is else empty]
Рис. 3: Поиск самой похожей подпоследовательности на кластере с сопроцессорами Процесс, запускаемый на узле вычислительного кластера, реализует данный алгоритм для обработки соответствующего фрагмента временного ряда. Процессор выполняет обработку сегментов фрагмента, реализуя модификацию разработанного ранее алгоритма [7]. Процессор поддерживает очередь подпоследовательностей-кандидатов, выгружаемых на сопроцессор, который выполняет для них вычисление меры DTW (деятельность DTW). Про
Receive Buf
Wait for candidates
Send candidates else
Receive phi_result [no candidates and all threads are finished]
Receive candidates DTW ...
DTW phi_result = min_dist (res1, ..., resPHI_THREADS)
Send phi_result цессор выполняет вычисление каскада оценок меры DTW для отбрасывания непохожих подпоследовательностей и подготовку данных для выгрузки на сопроцессор (деятельность UCR-DTW*). Распараллеливание осуществляется на основе технологии OpenMP, для чего временной ряд разбивается на сегменты равной длины. Для увеличения эффективности отбрасывания непохожих подпоследовательностей перед обработкой сегмента осуществляется обновление оценки схожести на основе алгоритма, описанного в разделе 3.3 (деятельность BSF Exchange). Обновление оценки схожести реализуется с помощью технологии MPI.
Результирующая подпоследовательность заданного временного ряда находится следующим образом. Один из процессов (например, с номером 0) объявляется мастером, остальные — рабочими. Рабочие отправляют мастеру результат вычислений соответствующего фрагмента, после чего мастер находит среди полученных результатов наилучший и выдает его пользователю. 4. Эксперименты
Для оценки эффективности разработанного алгоритма нами выполнены эксперименты на суперкомпьютере «Торнадо ЮУрГУ», спецификации вычислительного узла которого представлены в табл. 1.
Таблица 1: Спецификация вычислительного узла суперкомпьютера «Торнадо ЮУрГУ» Спецификации Модель Количество ядер Тактовая частота, ГГц Количество нитей на ядро Пиковая производительность, TFLOPS Процессор
Сопроцессор
Intel Xeon X5680 Intel Xeon Phi SE10X
6
2
3.33
В экспериментах было задействовано от 1 до 64 вычислительных узлов кластера. В
качестве данных в экспериментах использовался синтетический временной ряд, полученный
на основе модели случайных блужданий [
В первой серии экспериментов исследовалось ускорение алгоритма, т.е. значение 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 узлах вычислительного кластера соответственно, где длина 0 1 4 16 32 64 1 2 4 8 , шением доли подпоследовательностей, для которых производится вычисление меры DTW. Данное уменьшение связано с тем, что для исследования расширяемости на 64 узлах был задействован синтетический ряд в 2 раза большей длины, чем в экспериментах на 32 узлах, который содержал большее количество подпоследовательностей, позволивших улучшить оценку bsf раньше. 4.2. Сравнение с аналогами
Имеющиеся на сегодня параллельные реализации алгоритма UCR-DTW ориентированы
на многоядерные ускорители GPU [
Работы, в которых предлагаются параллельные реализации рассматриваемой задачи на
платформе вычислительного кластера с узлами на базе многоядерных ускорителей, в
настоящее время, по-видимому, отсутствуют. Относительно релевантной работой является
статья [
2 6 4 Shabib et al
Intel Xeon Phi
Intel Xeon Phi
20
15
10
5
0
220
400
520
660
220
400
520
660
220
400
520
660
В статье [
Нами были проведены эксперименты по сравнению разработанных нами алгоритмов
с алгоритмом из статьи [
Разработанные нами алгоритмы показали большее ускорение по сравнению с
алгоритмом из статьи [
В данной статье описаны проектирование и реализация параллельного алгоритма поиска самой похожей подпоследовательности временного ряда для вычислительной системы с кластерной архитектурой, узлы которой оснащены многоядерными ускорителями Intel Xeon Phi.
Алгоритм предполагает три уровня параллелизма по данным. На первом уровне временной ряд разбивается на фрагменты равной длины, распределяемые по узлам вычислительного кластера. В ходе обработки вычислительные узлы обмениваются информацией о найденном значении меры DTW для подпоследовательности, которая на текущий момент является самой похожей на запрос. Для реализации данного вида параллелизма используется технология MPI. Второй уровень параллелизма предполагает разбиение фрагмента на сегменты равной длины, обрабатываемые нитями на основе технологии OpenMP. Третий уровень параллелизма заключается в балансировке вычислительной нагрузки между процессором и ускорителем. Процессор выполняет вычисление каскада оценок меры DTW для отбрасывания заведомо непохожих подпоследовательностей. Сопроцессор используется для вычисления меры DTW. Разбиение данных на порции (фрагменты и сегменты) выполняется с использованием техники перекрытия, предотвращающей потерю результирующих подпоследовательностей, которые могут находиться на стыке порций.
Представлены результаты вычислительных экспериментов, показывающих эффективность разработанного алгоритма и его превосходство над известными аналогами. Литература 1. Berndt D.J., Cliford 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. 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.
Parallel implementation of searching the most similar subsequence in time series for computer systems with distributed memory
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 partitioning 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 eficiency of algorithm. 1. Berndt D.J., Cliford 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