ВВЕДЕНИЕ 5
1. СОВРЕМЕННЫЕ АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ АНАЛИЗА
РЫНОЧНОЙ КОРЗИНЫ 8
1.1. Формальные определения и постановка задачи 8
1.2. Популярные существующие алгоритмы решения задачи анализа
рыночной корзины 9
1.3. Распространение многоядерных ускорителей Intel MIC 11
1.4. Обзор работ по тематике исследования 12
1.5. Выводы по разделу 14
2. ПРОЕКТИРОВАНИЕ 15
2.1. Описание алгоритма DIC 15
2.2. Принципы распараллеливания и модификации алгоритма DIC 17
2.3. Структура хранения данных 19
2.4. Выводы по разделу 20
3. РЕАЛИЗАЦИЯ 21
3.1. Модульная структура параллельного алгоритма DIC 21
3.2. Особенности реализации 22
3.3. Выводы по разделу 23
4. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ 24
4.1. Аппаратная платформа и данные 24
4.2. Время выполнения последовательного алгоритма 24
4.3. Время выполнения параллельного алгоритма 25
4.4 Ускорение параллельного алгоритма 26
4.5. Выводы по разделу 27
ЗАКЛЮЧЕНИЕ 28
ЛИТЕРАТУРА 29
Задача анализа рыночной корзины является одной из задач интеллектуального анализа данных [27], представляя собой поиск наиболее часто совместно покупаемых товаров (поиск ассоциативных правил [2]). Решение данной задачи позволяет определить список рекомендованных для покупателя товаров, основываясь на списке товаров, которые он собирается приобрести [12].
На сегодня в связи с глобализацией интернета наблюдается прогрессирующий рост электронной коммерции [20]. За 2015 год только через Amazon.com было продано более двух миллиардов товаров [1]. Сервисы электронной коммерции нуждаются в решении задачи анализа рыночной корзины своих посетителей для увеличения конверсии. В силу этого актуальной является задача динамического анализа рыночной корзины.
Базы данных в настоящее время имеют сверхбольшие размеры, а сервисы электронной коммерции обычно оперируют миллионами наименований товаров. В связи с этим для эффективного решения задачи анализа рыночной корзины требуются масштабируемые производительные алгоритмы, позволяющие решить задачу анализа рыночной корзины на основе выбранных пользователем товаров за короткое время [2].
На ноябрь 2015 года более 85 % списка TOP500 самых мощных суперкомпьютеров мира [22] основаны на кластерной архитектуре. Более 18% суперкомпьютеров из этого списка (включая первую строку списка) оснащены ускорителями на базе архитектуры Intel Many Integrated Core [6]. На сегодня наиболее часто используемым ускорителем из списка Intel MIC является сопроцессор Intel Xeon Phi.
Таким образом, актуальной является задача разработки параллельного алгоритма анализа рыночной корзины для ускорителей на базе архитектуры Intel MIC.
Цель и задачи исследования
Цель данной работы состояла в разработке и исследовании эффективности параллельного алгоритма решения задачи анализа рыночной корзины для многоядерного ускорителя Intel Xeon Phi. Для достижения данной цели необходимо было решить следующие задачи:
1) выполнить обзор существующих последовательных и параллельных алгоритмов решения задачи анализа рыночной корзины;
2) разработать параллельный алгоритм решения задачи анализа рыночной корзины для многоядерного ускорителя Intel Xeon Phi;
3) реализовать разработанный алгоритм и провести вычислительные эксперименты по исследованию производительности разработанного алгоритма.
Структура и объем работы
Работа состоит из введения, четырех глав, заключения и библиографии.
Объем работы составляет 31 страницу, объем библиографии - 26 наименований.
Содержание работы
Первый раздел, «Современные алгоритмы решения задачи анализа рыночной корзины», посвящен обзору существующих алгоритмов решения задачи анализа рыночной корзины. В данном разделе рассматриваются последовательные и параллельные решения в области анализа рыночной корзины.
Второй раздел, «Проектирование», содержит описание последовательного алгоритма, принципов его распараллеливания и описание используемых структур хранения данных.
Третий раздел, «Реализация», содержит описание модульной структуры программного комплекса решения задачи анализа рыночной корзины. Также в этом разделе описываются интерфейсы программного комплекса и основные аспекты реализации.
Четвертый раздел, «Вычислительные эксперименты», содержит результаты вычислительных экспериментов по исследованию производительности разработанного алгоритма.
В заключении в краткой форме излагаются итоги выполненного исследования и рассматриваются перспективы дальнейшего развития темы.
Цель данной работы состояла в разработке и исследовании эффективности параллельного алгоритма решения задачи анализа рыночной корзины для многоядерного ускорителя Intel Xeon Phi.
В ходе выполнения выпускной квалификационной работы магистра были решены следующие задачи:
1) выполнен обзор существующих последовательных и параллельных алгоритмов решения задачи анализа рыночной корзины;
2) разработан параллельный алгоритм решения задачи анализа рыночной корзины для многоядерного ускорителя Intel Xeon Phi;
3) разработанный алгоритм реализован и проведены вычислительные эксперименты по исследованию производительности разработанного алгоритма.
В качестве возможного направления дальнейших исследований интересной представляется задача модификации разработанного алгоритма для кластерных систем на базе многоядерных ускорителей Intel Xeon Phi.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
