Виявлення підпослідовностей у часових рядах, Відкриті системи

Повсякденне життя людини нерозривно пов'язане з тимчасовими рядами: курси валют, електрокардіограми та інші показники надають сировину, інтелектуальний аналіз якої приносить сьогодні чималу користь, зокрема, дозволяючи автоматично виявляти аномальні явища. Однак вирішення даних завдань для великих часових рядів потребує особливих алгоритмів, які максимально використовують потенціал сучасних багатоядерних прискорювачів.

Завдання пошуку схожих підпослідовностей тимчасових рядів — ділянок тимчасового ряду, аналогічних ряду меншої довжини, виникає в широкому спектрі предметних областей, серед яких моделювання клімату (тимчасові ряди температури та вологості повітря), фінанси (тимчасові ряди курсів акцій та валют), медицина ( тимчасові ряди ЕКГ та будь-які інші показники функціональної діагностики організму людини) та ін. Наприклад, пошук у ЕКГ підпослідовностей, схожих на ділянки, типові для серцевих захворювань, дозволить вже на ранній стадії виявити схильність пацієнта до відповідних захворювань.

Тимчасовий ряд є сукупністю речових значень, кожне з яких асоційовано з послідовними відмітками часу. Завдання пошуку схожих підпослідовностей передбачає знаходження ділянок тимчасового ряду, що включають значення, що містяться в заданому ряду меншої довжини (запит). Виявлення схожих підпослідовностей часових рядів часто потрібне на вирішення різних завдань інтелектуального аналізу даних: пошуку шаблонів, виявлення аномалій, класифікації тощо.

Існуючі послідовні алгоритми виявлення схожих підпослідовностей, незважаючи на використання витончених технік оптимізації пошуку(індексування, відкидання свідомо несхожих підпослідовностей та ін.), не можуть забезпечити належну ефективність у разі великих часових рядів, що виникають при високій частоті зняття показань (наприклад, 250 вимірювань за секунду для ЕКГ) та перманентному накопиченні знятих показань (за одну добу показання , зняті по 12 каналах, являють собою тимчасовий ряд з 260 млн крапок). Одним із рішень може бути використання потенціалу багатоядерних прискорювачів, проте для роботи з ними потрібен паралельний алгоритм, який оптимізує спільну роботу процесора та прискорювача.

Для визначення схожості часових рядів використовуються різні заходи схожості, і одним з найпопулярніших є динамічна трансформація шкали часу (Dynamic Time Warping, DTW), яка дозволяє порівнювати часові ряди, отримані при різній швидкості зміни даних, проте за це доводиться платити ускладненням обчислень. У ранніх роботах на цю тему для визначення схожості використовується дискретне перетворення Фур'є, тимчасовий ряд сприймається як набір точок у багатовимірному просторі, якими будується просторовий індекс, а пошук підпослідовностей полягає у виконанні просторових запитів до цього індексу. В інших алгоритмах використовуються суфіксні дерева для побудови індексу, індекси на основі префіксу запитів, оптимізації послідовного порівняння всіх можливих підпослідовностей та ін.

Алгоритм UCR-DTW [1] є, мабуть, найбільш швидким і полягає у застосуванні каскаду попередніх оцінок, що дозволяють відкинути несхожу підпослідовність до виконання обчислювально складної динамічної трансформації шкали часу. Існують реалізації даного алгоритму для GPU та FPGA [2], проте йогоможна адаптувати і для багатоядерних співпроцесорів на базі архітектури Intel Many-Integrated Core, які за порівнянної вартості потенційно здатні забезпечити більш високу продуктивність.

Багатоядерний співпроцесор Intel Xeon Phi SE10X містить 61 ядро, кожне з яких має чотири потоки та 512-розрядні векторні пристрої, що забезпечують виконання до 16 операцій у форматі з плаваючою точкою або до восьми операцій над числами з подвійною точністю. Підтримуються такі режими запуску програм: 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). Після закінчення вивантаження на процесор передається інформація про знайдені на співпроцесор найбільш схожі підпослідовності. У результаті обчислюється подібна підпослідовність серед знайдених напроцесор і співпроцесор.

Мал. 1. Паралельний алгоритм для співпроцесора

Ефективність алгоритму перевірялася на вузлі суперкомп'ютера "РСК Торнадо ЮУрГУ" з процесором Intel Xeon X5680 та співпроцесором Intel Xeon Phi SE10X. В експериментах були використані синтетичний часовий ряд довжиною 109 точок і реальні дані ЕКГ з 2 на 107 точок (приблизно 22 години при частоті зняття показань ЕКГ 250 Гц). Результати експериментів (рис. 2) показали перевагу запропонованої версії алгоритму.

Мал. 2. Продуктивність алгоритму

Запропонований паралельний алгоритм ефективно працює при вирішенні задач інтелектуального аналізу даних у різних предметних галузях, зокрема для оперативного виявлення аномальних показників функціональної діагностики пацієнта. Таке виявлення можливе, наприклад, у ході неінвазивного моніторингу життєдіяльності організму. При цьому від часу обробки показань датчиків, що сигналізують про позаштатну ситуацію в роботі серця хворого, нерідко залежить його життя.

Література

Rakthanmanon T. та ін. Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping // The 18th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (Бейдж, China, 12–16 August, 2012). - ACM, 2012. - P. 262-270.
Sart D. та ін. 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.

Михайло Цимблер ([email protected]) - зав. кафедрою,Олександр Мовчан ([email protected]) - магістрант, Південно-Уральський державний університет (Челябінськ). Статтю підготовлено на основі матеріалів доповіді, представленої на конференції «Великі Дані в національній економіці» (грант РФФД 14-07-20305-г). Роботу виконано за підтримки Мінобрнауки України (ФЦП «Дослідження та розробки за пріоритетними напрямками розвитку науково-технологічного комплексу України на 2014–2020 роки», держконтракт № 14.574.21.0035).

Поділіться матеріалом з колегами та друзями