ВВЕДЕНИЕ 5
1. СОВРЕМЕННЫЕ МЕТОДЫ ПОИСКА ПОХОЖИХ
ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ ВО ВРЕМЕННЫХ РЯДАХ 8
1.1. Формальные определения и постановка задачи 8
1.2. Подходы к поиску похожих подпоследовательностей 9
1.3. Тенденции развития аппаратного обеспечения 13
1.4. Обзор работ по тематике исследования 15
1.5. Выводы по главе 1 17
2. ПРОЕКТИРОВАНИЕ 19
2.1. Базовые принципы 19
2.2. Алгоритмы поиска самой похожей подпоследовательности
временного ряда 23
2.3. Алгоритмы поиска локально похожих подпоследовательностей
временного ряда 28
2.4. Выводы по главе 2 34
3. РЕАЛИЗАЦИЯ 35
3.1. Модульная структура программного комплекса 35
3.2. Аспекты реализации 37
3.3. Выводы по главе 3 39
4. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 40
4.1. Аппаратная платформа 40
4.2. План экспериментов 41
4.3. Влияние параметров алгоритма на производительность 41
4.4. Векторизация DTW 44
4.5. Утилизация сопроцессора 44
4.6. Исследование ускорения 45
4.7. Исследование расширяемости 48
4.8. Сравнение с аналогами 50
4.9. Выводы по главе 4 54
ЗАКЛЮЧЕНИЕ 56
ЛИТЕРАТУРА 59
Поиск похожих подпоследовательностей временного ряда представляет собой одну из основных задач интеллектуального анализа временных рядов, возникающую в широком спектре предметных областей: мониторинг показателей функциональной диагностики организма человека [3], моделирование климата [1], финансовое прогнозирование [2] и др.
В поиске похожих подпоследовательностей можно выделить две следующие задачи: задачу поиска самой похожей подпоследовательности и задачу поиска локально похожих подпоследовательностей.
Задача поиска самой похожей подпоследовательности (best-match search) предполагает нахождение подпоследовательности в исходном временном ряде, максимально похожей на заданный ряд меньшей длины (поисковый запрос) в смысле некоторой меры схожести.
Поиск локально похожих подпоследовательностей предполагает (local-best-match search), что имеется временной ряд, в котором необходимо осуществить поиск заданного ряда меньшей длины (поискового запроса), и задано пороговое значение расстояния (меры схожести подпоследовательностей). Решением задачи является множество подпоследовательностей исходного ряда, каждая из которых удовлетворяет следующему условию: расстояние от подпоследовательности до запроса минимально среди соседних с ней подпоследовательностей, отстоящих от запроса не более чем на пороговое значение.
На сегодня динамическая трансформация времени (Dynamic Time Warping, DTW) [8] является одной из наиболее популярных мер во многих приложениях интеллектуального анализа временных рядов [11]. Однако по сравнению с евклидовым расстоянием DTW вычислительно более сложна. На сегодня предложено большое количество подходов для решения данной задачи: отбрасывание заведомо непохожих подпоследовательностей на основе оценки нижней границы расстояния [11], повторное использование вычислений [35], индексирование [23], раннее прекращение заведомо нерезультативных вычислений [32] и др. Тем не менее, вычисление DTW по-прежнему занимает существенную часть времени работы алгоритмов. В силу этого актуальными являются исследования, посвященные использованию параллельных вычислений для решения данной задачи на кластерных системах [36,39], многоядерных процессорах [38], FPGA и GPU [35,44, 45].
В настоящее время вычислительные системы с кластерной архитектурой занимают 85 % списка TOP500 самых мощных суперкомпьютеров мира. Около 20 % систем первой сотни данного списка оснащены многоядерными ускорителями. Вычислительный кластер Tianhe-2, занимающий первую строку списка, оснащен ускорителями на базе архитектуры Intel MIC [12]. На сегодня наиболее часто используемым представителем семейства Intel MIC (Intel Many Integrated Core) является ускоритель (сопроцессор) Intel Xeon Phi.
В этой связи представляется недооцененным потенциал многоядерных ускорителей на базе архитектуры Intel Many Integrated Core [12] для решения задач поиска похожих подпоследовательностей временных рядов.
В соответствии с этим актуальной является задача разработки новых эффективных алгоритмов параллельного поиска похожих подпоследовательностей на кластерных вычислительных системах, оснащенных многоядерными ускорителями.
Цель и задачи исследования
Цель данной работы состояла в разработке и исследовании эффек-алгоритмов поиска похожих подпоследовательностей временных рядов, ориентированных на кластерные вычислительные системы, оснащенные многоядерными ускорителями архитектуры Intel MIC. Для достижения этой цели необходимо было решить следующие задачи:
1) провести обзор последовательных и параллельных алгоритмов поиска похожих подпоследовательностей временных рядов;
2) разработать параллельные алгоритмы поиска похожих подпоследовательностей временного ряда для кластерных вычислительных систем на базе многоядерных ускорителей архитектуры Intel MIC;
3) реализовать разработанные алгоритмы в виде программного комплекса;
4) провести вычислительные эксперименты по исследованию производительности разработанных алгоритмов.
Структура и объем работы
Работа состоит из введения, 4 глав, заключения и библиографии.
Объем работы составляет 64 страницы, объем библиографии - 45 наименований.
Содержание работы
Первая глава, «Современные методы поиска похожих подпоследовательностей во временных рядах», посвящена формальному описанию задач поиска похожих подпоследовательностей. Также в данной главе рассматриваются тенденции развития аппаратного обеспечения и дается обзор научных исследований в области поиска похожих подпоследовательностей. Особое внимание уделяется параллельным алгоритмам поиска похожих подпоследовательностей для вычислительных систем с общей па-мятью, вычислительных систем с многоядерными ускорителями, а также кластерных вычислительных систем.
Вторая глава, «Проектирование», содержит описание базовых принципов проектирования алгоритмов поиска похожих подпоследовательностей и описание данных алгоритмов для различных вычислительных платформ.
Третья глава, «Реализация», содержит описание модульной структуры программного комплекса поиска похожих подпоследовательностей, интерфейсов классов. Также в данной главе рассмотрены основные аспекты, использованные в реализации.
В четвертой главе, «Вычислительные эксперименты», приведены результаты вычислительных экспериментов по исследованию производительности разработанных алгоритмов.
В заключении в краткой форме излагаются итоги выполненного исследования и рассматриваются перспективы дальнейшего развития темы.
Цель данной работы состояла в разработке и исследовании эффективных алгоритмов поиска похожих подпоследовательностей временных рядов, ориентированных на кластерные вычислительные системы, оснащенные многоядерными ускорителями архитектуры Intel MIC.
В данной работе были рассмотрены тенденции развития аппаратного обеспечения и научные исследования в области поиска похожих подпоследовательностей. Особое внимание уделялось параллельным алгоритмам поиска похожих подпоследовательностей для вычислительных систем с общей памятью, вычислительных систем с многоядерными ускорителями, а также кластерных вычислительных систем.
Предложены новые принципы проектирования алгоритмов поиска похожих подпоследовательностей для вычислительных систем с многоядерными ускорителями архитектуры Intel MIC и для кластерных вычислительных систем: трехуровневое распараллеливание, динамическое распределение сегментов, обмен оценками схожести между узлами. Основываясь на данных принципах, были спроектированы параллельные алгоритмы для задач поиска самой похожей подпоследовательности и поиска локально похожих подпоследовательностей. Все разработанные алгоритмы, а также вспомогательные утилиты были реализованы в программном комплексе. Репозиторий с исходными текстами программного комплекса опубликован в сети Интернет по адресу:https://bitbucket.org/movchan74/susu-dtw (общий объем исходных кодов составляет 8800 строк).
Проведены вычислительные эксперименты по исследованию производительности разработанных алгоритмов. В экспериментах использовалось до 128 вычислительных узлов суперкомпьютера «Торнадо ЮУрГУ». В экспериментах использовались 3 набора данных: 2 синтетических и 1 реальный. Эксперименты по исследованию влияния длины запроса показали, что разработанные параллельные алгоритмы имеют значительно большую производительность, чем последовательные. Однако алгоритмы для сопроцессора превосходят алгоритмы, использующие процессор, только на больших длинах запроса. Эксперименты по исследованию влияния раз-личных параметров алгоритмов позволили выявить параметры, при которых достигается наибольшая производительность. Исследование ускорения показало, что разработанные параллельные алгоритмы для кластерной вычислительной системы имеют нелинейное ускорение. На наборе данных Random Walk параллельные алгоритмы поиска локально похожих подпоследовательностей показали в два раза большее ускорение, чем алгоритмы поиска самой похожей подпоследовательности. В экспериментах по исследованию ускорения на наборе данных Pure Random было получено большее ускорение, чем на наборе данных Random Walk. Исследование расширяемости кластерных алгоритмов показало, что разработанные алгоритмы имеют расширяемость, близкую к единице. Сравнительные эксперименты показали превосходство разработанных алгоритмов как над аналогичными алгоритмами поиска самой похожей подпоследовательности для GPU и FPGA, так и над аналогичным алгоритмом для кластерной вычислительной системы.
Получены следующие новые научные результаты.
1. Предложены новые принципы проектирования алгоритмов поиска похожих подпоследовательностей для вычислительных систем с много-ядерными ускорителями архитектуры Intel MIC и для кластерных вычислительных систем.
2. Разработаны параллельные алгоритмы поиска похожих подпоследовательностей временного ряда для кластерных вычислительных систем на базе многоядерных ускорителей архитектуры Intel MIC.
3. Выполнена реализация предложенных алгоритмов в виде программного комплекса.
4. Проведены вычислительные эксперименты по исследованию производительности, показавшие эффективность разработанных алгоритмов.
Апробация результатов исследования
Основные положения выпускной квалификационной работы, разработанные методы, алгоритмы и результаты вычислительных экспериментов докладывались автором на следующих международных научных конференциях:
1) 38-я международная научная конференция по информационно-коммуникационным технологиям, электронике и микроэлектронике MIPRO’2015, 25-29 мая 2015 г, Хорватия, г Опатия;
2) 8-я международная конференция Similarity Search and Applications SISAP’2015, 12-14 октября 2015 г, Шотландия, г Глазго;
3) Международная научная конференция «Суперкомпьютерные дни в России», 28-29 сентября 2015 г., г Москва.
Публикации по теме исследования
Основные результаты опубликованы в 6 научных статьях: в статье [5], опубликованной в журнале из перечня ВАК, статьях [24, 27, 28], опубликованных в изданиях, индексируемых в SCOPUS, и статьях [6, 7], опубликованных в изданиях, индексируемых в РИНЦ.
Направления дальнейших исследований
В качестве возможного направления дальнейших исследований интересными представляются следующие задачи:
• модернизировать разработанные алгоритмы с помощью частичной репликации для обеспечения лучшей балансировки нагрузки между узлами кластерной вычислительной системы;
• создание фреймворка для поиска похожих подпоследовательностей, который позволит использовать разработанные алгоритмы для мер схожести, отличных от динамической трансформации шкалы времени.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
