Задача поиска похожих подпоследовательностей временных рядов — участков временного ряда, аналогичных ряду меньшей длины, — возникает в широком спектре предметных областей, в числе которых моделирование климата (временные ряды температуры и влажности воздуха), финансы (временные ряды курсов акций и валют), медицина (временные ряды ЭКГ и любые другие показатели функциональной диагностики организма человека) и др. Например, поиск в ЭКГ подпоследовательностей, похожих на участки, типичные для сердечных заболеваний, позволит уже на ранней стадии выявить предрасположенность пациента к соответствующим заболеваниям.
Временной ряд представляет собой совокупность вещественных значений, каждое из которых ассоциировано с последовательными отметками времени. Задача поиска похожих подпоследовательностей предполагает нахождение участков временного ряда, включающих значения, которые содержатся в заданном ряду меньшей длины (запрос). Выявление похожих подпоследовательностей временных рядов часто требуется для решения различных задач интеллектуального анализа данных: поиска шаблонов, обнаружения аномалий, классификации и т. п.
Существующие последовательные алгоритмы выявления похожих подпоследовательностей, несмотря на использование изощренных техник оптимизации поиска (индексирование, отбрасывание заведомо непохожих подпоследовательностей и др.), не могут обеспечить надлежащую эффективность в случае больших временных рядов, возникающих при высокой частоте снятия показаний (например, 250 измерений в секунду для ЭКГ) и перманентном накоплении снятых показаний (за одни сутки показания ЭКГ, снятые по 12 каналам, представляют собой временной ряд из 260 млн точек). Одним из решений может быть использование потенциала многоядерных ускорителей, однако для работы с ними требуется параллельный алгоритм, оптимизирующий совместную работу процессора и ускорителя.
Для определения похожести временных рядов используются различные меры схожести, и одной из наиболее популярных является динамическая трансформация шкалы времени (Dynamic Time Warping, DTW), которая позволяет сравнивать временные ряды, полученные при различной скорости изменения данных, однако за это приходится платить усложнением вычислений. В ранних работах на данную тему для определения схожести используется дискретное преобразование Фурье, временной ряд рассматривается как набор точек в многомерном пространстве, по которым строится пространственный индекс, а поиск подпоследовательностей заключается в выполнении пространственных запросов к этому индексу. В других алгоритмах используются суффиксные деревья для построения индекса, индексы на основе префикса запросов, оптимизации последовательного сравнения всех возможных подпоследовательностей и др.
Алгоритм UCR-DTW [1] является, по-видимому, наиболее быстрым и заключается в применении каскада предварительных оценок, позволяющих отбросить непохожую подпоследовательность еще до выполнения вычислительно сложной динамической трансформации шкалы времени. Существуют реализации данного алгоритма для GPU и FPGA [2], однако его можно адаптировать и для многоядерных сопроцессоров на базе архитектуры Intel Many-Integrated Core, которые при сравнимой стоимости потенциально способны обеспечить более высокую производительность.
Многоядерный сопроцессор Intel Xeon Phi SE10X содержит 61 ядро, каждое из которых имеет четыре потока и 512-разрядные векторные устройства, обеспечивающие выполнение до 16 операций в формате с плавающей точкой или до восьми операций над числами c двойной точностью. Поддерживаются следующие режимы запуска программ: native — приложение запускается независимо только на сопроцессоре; offload — приложение запускается на центральном процессоре, а интенсивные вычисления — на сопроцессоре; symmetric — программа запускается как MPI-приложение. Основной особенностью вычислений на Intel Xeon Phi является совместимость сопроцессора с архитектурой x86, в силу чего при разработке параллельного приложения имеется возможность использовать стандартные технологии параллельного программирования и известные инструменты, такие как OpenMP, MPI, Intel MKL и Intel TBB. Однако разработка эффективного параллельного приложения для Intel Xeon Phi не может быть сведена к тривиальной расстановке в исходном коде директив компилятора, обеспечивающих запуск программы на сопроцессоре, — если не обеспечить достаточно высокую интенсивность вычислений, выносимых на сопроцессор (то есть достаточно большое количество операций с плавающей точкой на байт данных), то узким местом окажется передача данных с процессора на сопроцессор, что приведет к деградации производительности.
Предлагаемый параллельный алгоритм поиска похожих подпоследовательностей для сопроцессора Intel Xeon Phi основан на параллельной версии алгоритма UCR-DTW, реализованного на технологии OpenMP, — приложение исполняется как набор одинаковых нитей, обрабатывающих равные отрезки временного ряда с помощью алгоритма UCR-DTW. В алгоритме используется общая переменная, хранящая расстояние до наиболее похожей подпоследовательности, что позволяет отбрасывать большее количество непохожих подпоследовательностей. Результаты экспериментов показали, что параллельный алгоритм превосходит последовательный на порядок при большой длине запроса, однако при запуске на сопроцессоре в режиме native его эффективность ниже, чем у параллельного алгоритма, запущенного на процессоре. Это обусловлено тем, что вычисления, выполнявшиеся на сопроцессоре, имели малую интенсивность. Кроме того, на загрузку данных с диска в память сопроцессора Intel Xeon Phi уходит на порядок больше времени, чем на загрузку временного ряда с диска в оперативную память процессора.
Для решения данной проблемы было предложено следующее (рис. 1). На стороне процессора организуется очередь подпоследовательностей (Queue), которые выгружаются на сопроцессор для вычисления динамической трансформации шкалы времени (DTW). Одна из нитей, выполняемых на ядрах процессора, объявляется мастером (Master), остальные — рабочими (Worker). Мастер осуществляет выгрузку очереди на сопроцессор при ее заполнении (символ «письмо» на рис. 1). Рабочий вычисляет каскадные оценки и отбрасывает заведомо непохожую подпоследовательность (символ «корзина» на рис. 1) либо добавляет эту подпоследовательность в очередь. Если очередь заполнена, то рабочий вычисляет динамическую трансформацию шкалы времени самостоятельно (на рис. 1 данная деятельность обозначена как UCR-DTW). По окончании выгрузки на процессор передается информация о найденных на сопроцессоре наиболее похожих подпоследовательностях. В итоге вычисляется самая похожая подпоследовательность среди найденных на процессоре и сопроцессоре.
.png "Рис. 1. Параллельный алгоритм для сопроцессора") |
| Рис. 1. Параллельный алгоритм для сопроцессора |
Эффективность алгоритма проверялась на узле суперкомпьютера «РСК Торнадо ЮУрГУ» с процессором Intel Xeon X5680 и сопроцессором Intel Xeon Phi SE10X. В экспериментах были использованы синтетический временной ряд длиной 109 точек и реальные данные ЭКГ из 2 на 107 точек (примерно 22 часа при частоте снятия показаний ЭКГ 250 Гц). Результаты экспериментов (рис. 2) показали преимущество предлагаемой версии алгоритма.
.png "Рис. 2. Производительность алгоритма") |
| Рис. 2. Производительность алгоритма |
***
Предложенный параллельный алгоритм эффективно работает при решении задач интеллектуального анализа данных в различных предметных областях, в частности для оперативного обнаружения аномальных показателей функциональной диагностики пациента. Такое обнаружение возможно, например, в ходе неинвазивного мониторинга жизнедеятельности организма. При этом от времени обработки показаний датчиков, сигнализирующих о нештатной ситуации в работе сердца больного, нередко зависит его жизнь.
Литература
- Rakthanmanon T. et al. 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.
- Sart D. et al. 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.
Михаил Цымблер (mzym@susu.ru) — зав. кафедрой, Александр Мовчан (movchanav@susu.ru) — магистрант, Южно-Уральский государственный университет (Челябинск). Статья подготовлена на основе материалов доклада, представленного на конференции «Большие Данные в национальной экономике» (грант РФФИ 14-07-20305-г). Работа выполнена при поддержке Минобрнауки РФ (ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014–2020 годы», госконтракт № 14.574.21.0035).
