Суперкомпьютерные дни в России 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.