Пример готовой курсовой работы по предмету: Программирование
Содержание
ВВЕДЕНИЕ 3
ГЛАВА 1. ЗАДАЧА ПОИСКА КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ И СПОСОБ ЕЕ ОПТИМИЗАЦИИ 5
1.1 Основные понятия и определения теории графов 5
1.2 Представление графа 6
1.3 Задача поиска всех кратчайших путей 7
1.4 Последовательный алгоритм Флойда 8
1.5 Технология CUDA 9
ГЛАВА
2. РАЗРАБОТКА ПАРАЛЛЕЛЬНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ 10
2.1 Параллельная схема 10
2.2Анализ эффективности 10
ГЛАВА
3. РАЗРАБОТКА ПРОГРАММЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ МЕТОДОМ ФЛОЙДА 12
3.1 Реализация параллелизма на CUDA 12
3.2 Компиляция и сборка 13
ГЛАВА
4. ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ 15
4.1 Спецификации GeForce GT 215 15
4.2 Проведение вычислительных экспериментов 16
ЗАКЛЮЧЕНИЕ 21
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 22
ПРИЛОЖЕНИЕ 23
Выдержка из текста
Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для ее решения.
У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.
Значимость данной задачи определяется ее различными практическими применениями. Например в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками.
При расчете траекторий и направлений большое значение играет быстродействие алгоритма, за счет которого найден путь. С помощью распараллеливания программы можно добиться увеличения скорости описка.
Устройства для превращения персональных компьютеров в маленькие суперкомпьютеры известны довольно давно. Ещё в 80-х годах прошлого века на рынке предлагались так называемые транспьютеры, которые вставлялись в распространенные тогда слоты расширения ISA. Первое время их производительность в соответствующих задачах впечатляла, но затем рост быстродействия универсальных процессоров ускорился, они усилили свои позиции в параллельных вычислениях, и смысла в транспьютерах не осталось. Хотя подобные устройства существуют и сейчас — это разнообразные специализированные ускорители. Но зачастую сфера их применения узка и особого распространения такие ускорители не получили.
С тех пор, как на графических процессорах стали доступны неграфические вычисления, многое изменилось. Можно найти не один пример того, как кластер из нескольких машин с мощными видеокартами мог поспорить с бешено дорогими суперкомпьютерами.
Благодаря CUDA возможно оптимизировать лишь ту частью приложения, которую можно распараллелить. В решении задач на компьютере все большее значение играет скорость расчетов, которую можно существенно увеличить, разделив задачу на подзадачи.
Идея распараллеливания основана на том, что большинство задач может быть разделено на набор меньших задач, которые могут быть решены одновременно.
Список использованной литературы
1. Боресков А.В., Харламов А.А. Основы работы с технологией CUDA.-М.:ДМК Пресс. 2010 – 232с.
2. Википедия. Свободная энциклопедия [Электронный ресурс]
: Свободная энциклопедия = http://ru.wikipedia.org. — Режим доступа: http://ru.wikipedia.org/wiki/CUDA. — Дата обращения 10.12.2013.
3. Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664. — ISBN 5-9502-0057-8(М.: Наука, 1987. 383c.)
4. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М: Мир, 1984. 455с.
5. CUDA Programming Guide. Chapter 1. Introduction to CUDA→ 1.2 CUDA: A New Architecture for Computing on the GPU
