Помощь студентам в учебе
Разработка параллельного алгоритма поиска диссонансов временного ряда для многоядерного процессора Intel Xeon Phi
|
ВВЕДЕНИЕ 5
1. ОБЗОР РАБОТ ПО ТЕМАТИКЕ ИССЛЕДОВАНИЯ 9
1.1. Последовательные алгоритмы 9
1.2. Параллельные алгоритмы 11
1.3. Методы Machine Learning для поиска аномалий временного ряда.. 15
2. ФОРМАЛЬНЫЕ ОБОЗНАЧЕНИЯ И ПОСТАНОВКА ЗАДАЧИ 19
2.1. Формальные обозначения 19
2.2. Последовательный алгоритм HOTSAX 20
3. ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ PHIDD 22
3.1. Краткое описание параллельного алгоритма phiDD 22
3.2. Проектирование алгоритма 23
3.3. Реализация алгоритма 25
4. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 33
4.1. Цели, аппаратная платформа и наборы данных экспериментов .... 33
4.2. Результаты экспериментов 34
4.3. Анализ пространственной сложности алгоритма 36
ЗАКЛЮЧЕНИЕ 39
ЛИТЕРАТУРА 40
1. ОБЗОР РАБОТ ПО ТЕМАТИКЕ ИССЛЕДОВАНИЯ 9
1.1. Последовательные алгоритмы 9
1.2. Параллельные алгоритмы 11
1.3. Методы Machine Learning для поиска аномалий временного ряда.. 15
2. ФОРМАЛЬНЫЕ ОБОЗНАЧЕНИЯ И ПОСТАНОВКА ЗАДАЧИ 19
2.1. Формальные обозначения 19
2.2. Последовательный алгоритм HOTSAX 20
3. ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ PHIDD 22
3.1. Краткое описание параллельного алгоритма phiDD 22
3.2. Проектирование алгоритма 23
3.3. Реализация алгоритма 25
4. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 33
4.1. Цели, аппаратная платформа и наборы данных экспериментов .... 33
4.2. Результаты экспериментов 34
4.3. Анализ пространственной сложности алгоритма 36
ЗАКЛЮЧЕНИЕ 39
ЛИТЕРАТУРА 40
Актуальность темы
В интеллектуальном анализе данных (Data Mining) большой интерес вызывают временные ряды. Данные, представленные в виде временных рядов, широко распространены во многих предметных областях: в науке (температура, влажность воздуха), экономике (ежедневные цены на акций, курсы валют), медицине (электрокардиограммы), биологии (ДНК), астрономии.
Под временным рядом (time series) понимают последовательность хронологически упорядоченных вещественных значений. Наличие у каждого элемента ряда временной метки, неотделимой от значения, существенным образом влияет на по становку и решение задач интеллектуального анализа временных рядов [6,7].
Важной задачей интеллектуального анализа временных рядов является поиск диссонансов (discord) временного ряда. Диссонанс является уточнением понятия аномальной подпоследовательности временного ряда. Задача поиска диссонансов встречается в широком спектре предметных областей, связанных с временными рядами: медицина [10], экономика [28], моделирование климата [26] и др. Понятие диссонанса предложено Кеогом (Keogh) в 2005 г. в работе [10] и определяется как подпоследовательность ряда, которая имеет максимальное расстояние до ближайшего соседа. Ближайшим соседом подпоследовательности является та подпоследовательность ряда, которая не пересекается с данной и имеет минимальное расстояние до нее.
Как отмечается в работе Е. Кеога и др. [11], диссонансы временного ряда для интеллектуального анализа данных особенно привлекательны как детекторы аномалий, т.к. требуют только один интуитивный параметр (длина подпоследовательности), в отличие от большинства других алгоритмов поиска аномалий, требующих много параметров (от 3 до 7 неинтуитивных параметров).
Процесс выявления аномалий в важнейших системах настоятельно рекомендуется автоматизировать, чтобы в процессе мониторинга больших систем была возможность автоматически выполнять действия, корректирующие состояние системы при выявлении аномалий, предотвращая тем самым, например, аварийные ситуации в системе. Также поскольку реальные данные могут быть огромного объема, необходимо задействовать все ресурсы вычислительной системы, на которой они обрабатываются (параллельное выполнение обработки, использование общей и дисковой памяти и др.). Актуальными являются исследования, посвященные использованию параллельных вычислений для решения данной задачи на кластерных системах, многоядерных процессорах и GPU. Для параллельной реализации алгоритма поиска диссонансов ряда перспективным является использование сопроцессоров Intel Xeon Phi.
Нахождение диссонансов временного ряда находят свое применение в следующих областях:
1) медицина (электрокардиограммы, и др.) - отслеживание изменений состояния пациента и поиск патологий;
2) дата-центры и компьютеры - мониторинг состояния памяти, загрузки ресурсов ВС, отслеживание сбоев;
3) отслеживание изменений температуры и климата, погодных аномалий.
Для нахождения диссонанса необходимо находить евклидовы расстояния между подпоследовательностями временного ряда. Нахождение расстояний между подпоследовательностями независимы друг от друга, поэтому есть необходимость в распараллеливании. Поэтому объектом исследования данной работы является процессор 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) [18], отличается от первого поколения Phi, Knights Corner (KNC) [5], тем, что может выступать в качестве автономного процессора без центрального процессора.
В данной работе рассматривается случай, когда все данные размещаются в оперативой памяти Intel Xeon Phi. Данный случай является практически значимым во многих предметных областях, например, в медицине, металлургии и др.
Цель и задачи исследования
Целью данной выпускной квалификационной работы является разработка параллельного алгоритма поиска диссонансов временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing).
Для достижения поставленной цели необходимо было решить следующие задачи:
1) провести обзор последовательных и параллельных алгоритмов поиска диссонансов временных рядов;
2) изучить аппаратную архитектуру и программную модель процессора Intel Xeon Phi (Knights Landing);
3) спроектировать и реализовать параллельный алгоритм поиска диссонансов временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing);
4) провести вычислительные эксперименты по анализу эффективности разработанного алгоритма.
Структура и объем работы
Работа состоит из введения, 4 глав, заключения и списка используемой литературы. Объем работы составляет 43 страницы, объем библиографии - 30 наименований.
Содержание работы
Первая глава, «Обзор работ по тематике исследования», содержит обзоры существующих последовательных и параллельных алгоритмов поиска диссонансов во временном ряде для различных вычислительных систем. В каждом алгоритме выявлены плюсы и минусы.
Вторая глава, «Формальные обозначения и постановка задачи», содержит формальные определения и обозначения, описание задачи поиска диссонанса во временном ряде. Приведены техники ускорения поиска диссонанса, и описан последовательный алгоритм HOTSAX, на основе которого разработан параллельный алгоритм PhiDD.
Третья глава, «Параллельный алгоритм PhiDD», содержит детальное описание разработанного параллельного алгоритма PhiDD для многоядерного процессора Intel Xeon Phi.
В четвертой главе, «Вычислительные эксперименты», приведены результаты вычислительных экспериментов по исследованию предложенного алгоритма.
В заключении приведены основные итоги проделанной работы.
В интеллектуальном анализе данных (Data Mining) большой интерес вызывают временные ряды. Данные, представленные в виде временных рядов, широко распространены во многих предметных областях: в науке (температура, влажность воздуха), экономике (ежедневные цены на акций, курсы валют), медицине (электрокардиограммы), биологии (ДНК), астрономии.
Под временным рядом (time series) понимают последовательность хронологически упорядоченных вещественных значений. Наличие у каждого элемента ряда временной метки, неотделимой от значения, существенным образом влияет на по становку и решение задач интеллектуального анализа временных рядов [6,7].
Важной задачей интеллектуального анализа временных рядов является поиск диссонансов (discord) временного ряда. Диссонанс является уточнением понятия аномальной подпоследовательности временного ряда. Задача поиска диссонансов встречается в широком спектре предметных областей, связанных с временными рядами: медицина [10], экономика [28], моделирование климата [26] и др. Понятие диссонанса предложено Кеогом (Keogh) в 2005 г. в работе [10] и определяется как подпоследовательность ряда, которая имеет максимальное расстояние до ближайшего соседа. Ближайшим соседом подпоследовательности является та подпоследовательность ряда, которая не пересекается с данной и имеет минимальное расстояние до нее.
Как отмечается в работе Е. Кеога и др. [11], диссонансы временного ряда для интеллектуального анализа данных особенно привлекательны как детекторы аномалий, т.к. требуют только один интуитивный параметр (длина подпоследовательности), в отличие от большинства других алгоритмов поиска аномалий, требующих много параметров (от 3 до 7 неинтуитивных параметров).
Процесс выявления аномалий в важнейших системах настоятельно рекомендуется автоматизировать, чтобы в процессе мониторинга больших систем была возможность автоматически выполнять действия, корректирующие состояние системы при выявлении аномалий, предотвращая тем самым, например, аварийные ситуации в системе. Также поскольку реальные данные могут быть огромного объема, необходимо задействовать все ресурсы вычислительной системы, на которой они обрабатываются (параллельное выполнение обработки, использование общей и дисковой памяти и др.). Актуальными являются исследования, посвященные использованию параллельных вычислений для решения данной задачи на кластерных системах, многоядерных процессорах и GPU. Для параллельной реализации алгоритма поиска диссонансов ряда перспективным является использование сопроцессоров Intel Xeon Phi.
Нахождение диссонансов временного ряда находят свое применение в следующих областях:
1) медицина (электрокардиограммы, и др.) - отслеживание изменений состояния пациента и поиск патологий;
2) дата-центры и компьютеры - мониторинг состояния памяти, загрузки ресурсов ВС, отслеживание сбоев;
3) отслеживание изменений температуры и климата, погодных аномалий.
Для нахождения диссонанса необходимо находить евклидовы расстояния между подпоследовательностями временного ряда. Нахождение расстояний между подпоследовательностями независимы друг от друга, поэтому есть необходимость в распараллеливании. Поэтому объектом исследования данной работы является процессор 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) [18], отличается от первого поколения Phi, Knights Corner (KNC) [5], тем, что может выступать в качестве автономного процессора без центрального процессора.
В данной работе рассматривается случай, когда все данные размещаются в оперативой памяти Intel Xeon Phi. Данный случай является практически значимым во многих предметных областях, например, в медицине, металлургии и др.
Цель и задачи исследования
Целью данной выпускной квалификационной работы является разработка параллельного алгоритма поиска диссонансов временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing).
Для достижения поставленной цели необходимо было решить следующие задачи:
1) провести обзор последовательных и параллельных алгоритмов поиска диссонансов временных рядов;
2) изучить аппаратную архитектуру и программную модель процессора Intel Xeon Phi (Knights Landing);
3) спроектировать и реализовать параллельный алгоритм поиска диссонансов временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing);
4) провести вычислительные эксперименты по анализу эффективности разработанного алгоритма.
Структура и объем работы
Работа состоит из введения, 4 глав, заключения и списка используемой литературы. Объем работы составляет 43 страницы, объем библиографии - 30 наименований.
Содержание работы
Первая глава, «Обзор работ по тематике исследования», содержит обзоры существующих последовательных и параллельных алгоритмов поиска диссонансов во временном ряде для различных вычислительных систем. В каждом алгоритме выявлены плюсы и минусы.
Вторая глава, «Формальные обозначения и постановка задачи», содержит формальные определения и обозначения, описание задачи поиска диссонанса во временном ряде. Приведены техники ускорения поиска диссонанса, и описан последовательный алгоритм HOTSAX, на основе которого разработан параллельный алгоритм PhiDD.
Третья глава, «Параллельный алгоритм PhiDD», содержит детальное описание разработанного параллельного алгоритма PhiDD для многоядерного процессора Intel Xeon Phi.
В четвертой главе, «Вычислительные эксперименты», приведены результаты вычислительных экспериментов по исследованию предложенного алгоритма.
В заключении приведены основные итоги проделанной работы.
Данная выпускная квалификационная работа была посвящена разработке параллельного алгоритма поиска диссонансов временного ряда для многоядерных процессоров Intel Xeon Phi.
В ходе выполнения работы были получены следующие основные результаты:
1) проведен обзор последовательных и параллельных алгоритмов поиска диссонансов временных рядов на различных вычислительных системах;
2) изучена аппаратная архитектура и программная модель процессора Intel Xeon Phi (Knights Landing);
3) спроектирован и реализован параллельный алгоритм поиска диссонансов временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing);
4) проведены вычислительные эксперименты на реальных и синтетических данных, результаты экспериментов показали хорошую масштабируемость алгоритма PhiDD и превосходство в производительности над алгоритмами-аналогами.
По результатам исследования имеется принятая к публикации статья в серии Communications in Computer and Information Science издательства Springer (индексируется в Scopus). В ходе выпускной квалификационной работы были сделаны доклады на XIII международной научной конференции «Параллельные вычислительные технологии (ПаВТ) 2019» (2-4 апреля 2019 г, Калининград) и 72 й научной конференции студентов ЮУрГУ (Челябинск, 24 мая 2019 г).
В ходе выполнения работы были получены следующие основные результаты:
1) проведен обзор последовательных и параллельных алгоритмов поиска диссонансов временных рядов на различных вычислительных системах;
2) изучена аппаратная архитектура и программная модель процессора Intel Xeon Phi (Knights Landing);
3) спроектирован и реализован параллельный алгоритм поиска диссонансов временного ряда для многоядерных процессоров Intel Xeon Phi (Knights Landing);
4) проведены вычислительные эксперименты на реальных и синтетических данных, результаты экспериментов показали хорошую масштабируемость алгоритма PhiDD и превосходство в производительности над алгоритмами-аналогами.
По результатам исследования имеется принятая к публикации статья в серии Communications in Computer and Information Science издательства Springer (индексируется в Scopus). В ходе выпускной квалификационной работы были сделаны доклады на XIII международной научной конференции «Параллельные вычислительные технологии (ПаВТ) 2019» (2-4 апреля 2019 г, Калининград) и 72 й научной конференции студентов ЮУрГУ (Челябинск, 24 мая 2019 г).
