Тема: РАЗРАБОТКА ПАРАЛЛЕЛЬНОГО АЛГОРИТМА ПОИСКА САМОЙ ПОХОЖЕЙ ПОДПОСЛЕДОВАТЕЛЬНОСТИ ВРЕМЕННОГО РЯДА ДЛЯ МНОГОЯДЕРНЫХ ПРОЦЕССОРОВ INTEL XEON PHI (KNIGHTS LANDING)

Актуальность темы
В интеллектуальном анализе данных (Data Mining) большой интерес вызывают временные ряды. Данные, представленные в виде временных рядов, широко распространены во многих предметных областях: в науке (температура, влажность воздуха), экономике (ежедневные цены на акций, курсы валют), медицине (электрокардиограммы), биологии (ДНК), астрономии.
Поиск похожих подпоследовательностей во временном ряде часто используется как подпрограмма во многих задачах интеллектуального анализа временных рядов: обнаружении мотивов [12], классификации [1, 23], кластеризации [7]. Основной идеей задачи является нахождение к подпоследовательностей в заданном временном ряде, наиболее похожих на образец поиска.
Существуют области, в которых поиск похожих подпоследовательностей очень необходим, например, в мониторинге температуры, в медицине [13], в энтомологии [19], распознавании жестов и слов в рукописном тексте и др. Например, каждый день астрономы получают большое количество данных, измеренных с помощью антенной решетки. Поиск определенной последовательности в большой базе данных может помочь астрономам обнаружить типичные астрономические явления [4].
Схожесть двух подпоследовательностей определяет мера схожести. Среди десятков различных мер схожести, наилучшей мерой признана динамическая трансформация временной шкалы (Dynamic Time Warping, DTW) [5]. Однако классический расчет DTW трудоемок и сложен, из-за чего снижается эффективность алгоритмов, которые используют данную меру. Чтобы улучшить производительность алгоритмов на основе DTW, исследователями были предложены техники [3,5, 9, 13,15], которые ускоряют поиск самой похожей подпоследовательности. Однако вычисление расстояния DTW по-прежнему занимает слишком много времени, до 80 % всего времени поиска подобия [24]. Поэтому есть необходимость в распараллеливании DTW меры.
В связи с этим были предложены исследователями различные параллельные реализации данного алгоритма на таких вычислительных системах, как кластерах [16, 20], многоядерных процессорах [18], GPU [24], FPGA [15, 22]. Однако перечисленные реализации не могут быть перенесены на Intel Xeon Phi. Поэтому объектом исследования данной работы является процессор Intel Xeon Phi.
Использование процессоров Intel Xeon Phi - новая тенденция в разработке аппаратных средств для суперкомпьютеров. Intel Xeon Phi основан на архитектуре Intel Many Integrated Core (MIC), которая выполняет более одного триллиона операций в секунду (TFLOPS) с плавающей запятой. Процессор Intel Xeon Phi включает до 61 процессорных ядер, основанных на архитектуре x86 и соединенных высокопроизводительной встроенной кольцевой шиной. Каждое ядро содержит 512-битный блок векторных вычислений (vector processor unit, VPU), так что может обрабатывать 16 32битных целых чисел на каждом такте. Также Intel Xeon Phi поддерживает параллелизм уровня потоков для ускорения сложных вычислительных задач с использованием таких технологий параллельного программирования, как OpenMP, MPI.
Существует два поколения Intel Xeon Phi. Второе поколение Phi, Knights Landing (KNL) [17], отличается от первого поколения Phi, Knights Corner (KNC) [2], тем, что может выступать в качестве автономного процессора без центрального процессора. Данная работа является продолжением работ [11, 25], в которых представлена разработка поиска похожих подпоследовательностей в режиме offload, когда приложение запускается на хост-системе и некоторые вычислительно сложные участки программы выгружаются на сопроцессор Intel Xeon Phi (Knights Corner). Однако данная схема работы алгоритма слабо использует возможности векторизации Intel Xeon Phi и не применима для процессоров второго поколения Knights Landing, которые могут запускать программы только в native режиме.
В данной работе рассматривается случай, когда все данные размещаются в оперативой памяти Intel Xeon Phi. Данный случай является практически значимым во многих предметных областях, например, в энтомологии, распознавании речи и др.
Цель и задачи исследования
Целью данной выпускной квалификационной работы является разработка параллельного алгоритма поиска самой похожей подпоследовательности временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing).
Для достижения поставленной цели необходимо было решить следующие задачи:
1) провести обзор параллельных алгоритмов поиска похожих подпоследовательностей временных рядов;
2) изучить аппаратную архитектуру и программную модель процессора Intel Xeon Phi (Knights Landing);
3) спроектировать и реализовать параллельный алгоритм поиска самой похожей подпоследовательности временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing);
4) провести вычислительные эксперименты по анализу эффективности разработанного алгоритма.
Структура и объем работы
Работа состоит из введения, 4 глав, заключения и списка используемой литературы.
Объем работы составляет 31 страница, объем библиографии - 25 наименований.
Содержание работы
Первая глава, «Обзор работ по тематике исследования», содержит обзоры существующих параллельных алгоритмов поиска похожих подпоследовательностей во временном ряде для различных вычислительных систем. В каждом алгоритме выявлены плюсы и минусы.
Вторая глава, «Формальные обозначения и постановка задачи», содержит формальные определения и обозначения, описание задачи поиска самой похожей подпоследовательности во временном ряде. Приведены техники ускорения поиска самой похожей подпоследовательности, и описан последовательный алгоритм UCR-DTW, на основе которого разработан параллельный алгоритм.
Третья глава, «Параллельный алгоритм phiBestMatch», содержит детальное описание разработанного параллельного алгоритма для многоядерного процессора Intel Xeon Phi.
В четвертой главе, «Вычислительные эксперименты», приведены результаты вычислительных экспериментов по исследованию предложенного алгоритма.
В заключении приведены основные итоги проделанной работы.
Купить

Данная выпускная квалификационная работа была посвящена разработке параллельного алгоритма поиска самой похожей подпоследовательности временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing).
В ходе выполнения работы были получены следующие основные результаты:
1) проведен обзор параллельных алгоритмов поиска похожих подпоследовательностей временных рядов на различных вычислительных системах;
2) изучена аппаратная архитектура и программная модель процессора Intel Xeon Phi (Knights Landing);
3) спроектирован и реализован параллельный алгоритм поиска самой похожей подпоследовательности временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing);
4) проведены вычислительные эксперименты на реальных и синтетических данных, показавшие хорошую масштабируемость разработанного алгоритма.
В ходе выпускной квалификационной работы были сделаны доклады на 71-ой студенческой научной конференции ЮУрГУ и XIII Уральской выставке НТТМ «Евразийские ворота России - Шаг в будущее».
В рамках выпускной работы была подана статья на XX международную конференцию «Data Analytics and Management in Data Intensive Domains 2018».

Купить