Выполнение операций над биномиальной кучей с использованием технологии CUDA (Тонких Артём Петрович)

1.

федеральное государственное бюджетное образовательное учреждение
высшего образования
«Тольяттинский государственный университет»
КУРСОВАЯ РАБОТА
по дисциплине (учебному курсу)
«Технологии массивно-параллельных вычислений»
(наименование дисциплины (учебного курса))
на тему «Выполнение операций над биномиальной кучей с
использованием технологии CUDA»
Группа: Моп1702а
Студент: В.В. Жупиков
Руководитель Тонких Артём Петрович
Тольятти, 2020

2.

Цель данной работы заключается в анализе эффективности технологии CUDA и
последовательного алгоритма поиска в ширину в графе
Задачи: изучить способы поиска в ширину в графе, спроектировать последовательный алгоритм
поиска в ширину в графе, внедрит в последовательный алгоритм технологию CUDA, провести
эксперименты по сравнению быстродействия алгоритмов, проанализировать полученные
результаты и на их основе составить вывод более эффективного алгоритма.
Объект исследования – параллельная программа, выполняющая копирование файлов.
Предметом исследования является программы поиска графа в ширину, написанные с
использованием технологий OpenMP и CUDA.
В ходе исследования применялась методика оценки эффективности программного обеспечения,
а именно: для измерения времени выполнения программ использовалась стандартная
библиотека языка C++ – Chrono и для CUDA cudaEvent.

3.

Математическая модель
Рассмотрим алгоритм обхода графа в ширину. Пусть будет задан невзвешенный
ориентированный граф