В работе рассматривается задача поиска локально похожих подпоследовательностей временного ряда. Необходимо найти все подпоследовательности ряда, расстояние от которых до заданного поискового запроса минимально среди всех соседних подпоследовательностей, отстоящих от запроса не более чем на заданное пороговое значение. В качестве расстояния (меры схожести) используется динамическая трансформация шкалы времени (Dynamic Time Warping, DTW), которая на сегодня признается лучшей мерой для большинства приложений временных рядов. Вычисление DTW, однако, является затратной операцией, несмотря на существующие алгоритмические техники сокращения вычислений. Имеющиеся подходы к вычислению DTW с помощью многоядерных ускорителей задействуют архитектуры GPU и FPGA, оставляя без внимания потенциал архитектуры Intel Many Integrated Core. В работе предлагается параллельный алгоритм решения указанной задачи, использующий как центральный процессор, так и многоядерный сопроцессор Intel Xeon Phi. Реализация основана на технологии параллельного программирования OpenMP и режиме выполнения приложения, при котором часть кода и данных выгружается на сопроцессор. Алгоритм предполагает использование на стороне процессора очереди подпоследовательностей, данные о которых выгружаются на сопроцессор для вычисления DTW, что обеспечивает высокую интенсивность вычислений, выполняемых на сопроцессоре. Приведены результаты экспериментов, подтверждающих эффективность разработанного алгоритма.
ней границы расстояния [
В данной статье предлагается параллельный алгоритм поиска локально похожих подпоследовательностей временного ряда для узла, оснащенного многоядерным сопроцесором 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 l\eq
N и i + m \leq
N .
Запрос (query) Q — временной ряд, поиск которого необходимо осуществить во временном ряде T . Пусть n — длина запроса, n \l
N .
Задача поиска локально похожих подпоследовательностей (local-best-match subsequence
search) [
Tim удовлетворяет следующим условиям: Тогда Tim \in L \leftrighaow 1. m = n; 2. D(Tim, Q) < \scrE ; 3. i =
argmin j\in \{i- 1,i,i+1\}
D(Tjm, Q).
Динамическая трансформация шкалы времени (Dynamic Time Warping, DTW) представляет собой меру схожести двух временных рядов. Расстояние на основе DTW между 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, ofload и symmetric. В режиме native приложение выполняется независимо исключительно на сопроцессоре. В режиме ofload приложение запускается на процессоре и выгружает вычислительно интенсивную часть работы (код и данные) на сопроцессор. Режим symmetric позволяет сопроцессору и процессору взаимодействовать в рамках модели обмена сообщениями (Message Passing Interface). 2.3. Работы по тематике исследования
В настоящее время DTW рассматривается научным сообществом как наилучшая мера
схожести для большинства приложений интеллектуального анализа временных рядов [
Алгоритм SPRING [
Вышеперечисленные алгоритмы направлены на сокращение количества вызовов процедуры вычисления DTW, но не ускорения процедуры вычисления DTW как таковой. Однако, в силу своей вычислительной сложности, вычисление DTW по-прежнему занимает существенную часть времени выполнения поиска подпоследовательностей. Данное обстоятельство стимулировало исследования, направленные на использование параллельного аппаратного обеспечения для распределения вычислений DTW для разных подпоследовательностей на разные вычислительные устройства.
В работе [
В данной работе на базе последовательного алгоритма поиска наиболее похожей
подпоследовательности временного ряда [
Разработанный нами последовательный алгоритм поиска локально похожих
подпоследовательностей представлен на рис. 1. Алгоритм получил название lbm-UCR-DTW,
поскольку базируется на алгоритме UCR-DTW [
K, т.е. результирующее множество содержит не более K подпоследовательностей, где K является параметром алгоритма. Данное ограничение является практически полезным ввиду возможного лимита оперативной памяти для хранения найденных подпоследовательностей и не ограничивает общность, поскольку мы можем рассмотреть случай K = \infty .
Переменная алгоритма bsf (best-so-far) используется для хранения текущей лучшей оценки расстояния от подпоследовательностей до запроса и вычисляется следующим обраbsf =
else
else
else Local Min Condition CL ≠ EMPTY ∧ CM ≠ EMPTY ∧ CR ≠ EMPTY ∧ distM < ε ∧ distM < distL ∧ distM < distR i := 0 dist := ∞ CL := EMPTY CM := EMPTY CR := EMPTY bsf := ε
LB_Kim(Tin, Q) Таким образом, схема работы алгоритма кратко может быть представлена следующим образом. Считанная подпоследовательность проверяется с помощью каскада оценок вспомогательного алгоритма Lower Bounding. Если подпоследовательность не отбрасывается как заведомо непохожая, то вычисляется DTW до запроса. Затем вспомогательный алгоритм Sliding выполняет обновление переменных CL, CM , CR и соответсвующих им расстояний distL, distM , distR. Если выполнено условие локального минимума, то вспомогательный алгоритм Update Result обновляет результирующее множество L. Алгоритм заканчивает работу, когда исчерпаны все подпоследовательности исходного временного ряда. 3.2. Параллельный алгоритм для процессора
На основе последовательного алгоритма, предложенного в предыдущем разделе, нами разработан параллельный алгоритм для процессора, представленный на рис. 2.
Для распараллеливания используется технология программирования OpenMP. Временной ряд разбивается на промежутки равной длины, каждый из которых обрабатывается отдельной OpenMP-нитью. Для того, чтобы избежать потери результирующих подпоследовательностей, находящихся на стыке промежутков, разбиение на промежутки осуществляется с перекрытием, равным длине запроса. Это означает, что начало каждого промежутка, lbm-UCR-DTW lbm-UCR-DTW ... lbm-UCR-DTW result = min_dist(result, res1, ..., resCPU_THREADS) Output result 3.3. Параллельный алгоритм для сопроцессора Параллельный алгоритм для процессора и сопроцессора Intel Xeon Phi представлен на Основная идея данного параллельного алгоритма заключается в том, что сопроцессор используется только для вычислений DTW, а процессор выполняет вычисление каскада оценок, подготавливая подпоследовательности для сопроцессора, и вычисление DTW, если сопроцессор полностью занят. Процессор поддерживает очередь кандидатов (т.е. подпоследовательностей, для каждой из которых сопроцессор должен вычислить DTW).
Элементами очереди являются кортежи вида (i, A), соответствующие подпоследовательности-кандидату Tin. Здесь A представляет собой массив длины n, содержащий оценки
CPU Swap Buf_1 and Buf_2
Read data in Buf_1 else Get (subsequence, dist) from phi_result DTW_distances[subsequence] := dist result = min_dist(result, 1, ..., CPU_THREADS) result = find_local_min(result, DTW_distances) else [eBmupf_ty2]isClose file
Output
result
Рис. 3. Параллельный алгоритм для процессора и сопроцессора Intel Xeon Phi
LBKeogh для каждой позиции подпоследовательности, который используется для
заблаговременной отмены вычисления DTW [
При заполнении очереди она выгружается на сопроцессор для выполнения вычислений DTW. Максимальное количество элементов в очереди является параметром алгоритма и вычисляется как C \cdot h c\dot W , где C — количество ядер сопроцессора, доступных для вычислений (например, для Intel Xeon Phi SE10X C = 60), h — фактор гипертрединга сопроцессора (h = 4 для ранее упомянутой модели сопроцессора), W — количество кандидатов, обрабатываемых одной нитью сопроцессора, которое является параметром алгоритма.
Работа алгоритма может быть описана следующим образом. Одна из нитей процессора объявляется мастером, остальные — рабочими. Сначала мастер отправляет буфер с текущим фрагментом временного ряда на сопроцессор. Как только очередь заполняется, мастер выгружает ее на сопроцессор, а сопроцессор выполняет вычисление DTW для соответствующих подпоследовательностей.
Вспомогательный алгоритм lbm-UCR-DTW*, изображенный на рис. 4, реализует поведение рабочего. Рабочий выполняет вычисление каскадных оценок для подпоследовательности. Если подпоследовательность не похожа на запрос, то рабочий отбрасывает ее, иначе подпоследовательность добавляется в очередь. Если очередь заполнена, и данные, загруженные ранее на сопроцессор, еще не обработаны, то рабочий вычисляет DTW самостоятельно. При этом реализация поиска локально похожих подпоследовательностей идеологически близка последовательному алгоритму, описанному в разделе 3.1. Результаты вычислений DTW рабочий сохраняет в разделяемом массиве для последующего поиска локально похожих подпоследовательностей.
После выгрузки кандидатов на сопроцессор для каждого кандидата выполняется вычисление DTW, и пары «индекс-расстояние» выгружаются обратно на процессор.
После того, как вычисления на процессоре и сопроцессоре завершены, выполняется поиск локально похожих подпоследовательностей в разделяемом массиве, заполненном ранее. Init else else
else [Queue.IsFull] dist := DTW(Tin, Q)
[pruned]
Sliding DTW_distances[i] := dist
else 4. Вычислительные эксперименты
Для оценки разработанного алгоритма мы выполнили эксперименты на узле суперкомпьютера «Торнадо ЮУрГУ»1, спецификации которого представлены в табл. 1.
Таблица 1. Спецификация узла суперкомпьютера «Торнадо ЮУрГУ» Спецификации Модель Количество ядер Тактовая частота, ГГц Количество нитей на ядро Пиковая производительность, TFLOPS Процессор
Сопроцессор Intel Xeon X5680 Intel Xeon Phi SE10X 6 2 3.33
Serial
Parallel, CPU Parallel, CPU+Xeon Phi
6000 Рис. 5. Производительность на синтетических данных чае, когда запросы имеют меньшую длину, наш алгоритм показывает производительность, сходную с параллельным алгоритмом для процессора (не использующим сопроцессор).
Вторая серия экспериментов исследует производительность разработанного алгоритма на реальных данных ЭКГ, состоящих из 20 млн. точек (около 22 час. ЭКГ, снятой с дискретизацией 250 Гц).
Serial
Parallel, CPU
Parallel, CPU+Xeon Phi 1000
1500 Длина запроса
2000 Рис. 6. Производительность на реальных данных Результаты экспериментов на реальных данных показаны на рис. 6. Разработанный алгоритм показывает в почти три раза б´ольшую производительность, чем параллельный алгоритм, не использующий сопроцессор.
Влияние порогового значения \scrE на время работы алгоритма показано на рис. 7. Данный эксперимент производился с использованием параллельного алгоритма поиска локально похожих подпоследовательностей для процессора и сопроцессора Intel Xeon Phi. В качестве данных эксперимента использовались синтетический и реальный временные ряды, рассмотренные в предыдущих экспериментах. Как и ожидалось, с увеличением порогового значения \scrE время выполнения увеличивается. с я, 2000 и н е н ол 1500 п ы в я ем 1000 р В 500 0
В данной статье описаны проектирование и реализация параллельного алгоритма поиска локально похожих подпоследовательностей временного ряда, использующего в качестве мероы схожести динамическую трансформацию шкалы времени, для архитектуры Intel Many Integrated Core.
На основе последовательного алгоритма поиска самой похожей подпоследовательности временного ряда, комбинирующего известные на сегодня техники редукции вычислений, разработан последовательный алгоритм решения указанной задачи.
На следующем шаге разработки выполнено распараллеливание полученного алгоритма на основе технологии OpenMP. Временной ряд разбивается на промежутки равной длины, обрабатываемые отдельными OpenMP-нитями. Для исключения потерь результирующих подпоследовательностей, находящихся на стыке промежутков, разбиение осуществляется с частичным нахлестом соседних промежутков.
Наконец, алгоритм, полученный на предыдущем шаге, адаптирован для выполнения вычислений как на центральном процессоре, так и на многоядерном сопроцессоре Intel Xeon Phi. Сопроцессор используется только для вычисления расстояний между подпоследовательностями и запросом. Процессор выполняет отбрасывание заведомо непохожих подпоследовательностей и подготовку подпоследовательностей для обработки сопроцессором, вычисляя расстояния лишь при отсуствии другой работы. Взаимодействие процессора и сопроцессора реализовано с помощью режима ofload , когда часть кода и данных выгружается на сопроцессор. Высокая интенсивность вычислений, выполняемых на сопроцессоре, достигается за счет использования на стороне процессора очереди подпоследовательностей, данные о которых выгружаются на сопроцессор для вычисления динамической трансформации шкалы времени.
Эксперименты, проведенные на синтетических и реальных данных, показали эффективность разработанного алгоритма и его превосходство над последовательным алгоритмом и параллельным алгоритмом, использующим только процессор.
В качестве возможного направления дальнейших исследований интересными представляются следующие задачи: модернизация разработанного алгоритма для случая, когда процессор оснащен несколькими сопроцессорами Intel Xeon Phi, и расширение разработанного алгоритма для кластерной системы, каждый вычислительный узел которой оснащен сопроцессором Intel Xeon Phi. Литература 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.