Сортировки на системах с общей памятью
ВВЕДЕНИЕ
На сегодняшний день при написании программы, которая осуществляет некую работу с данными, очень важна скорость работы с ними. Для работы с большим количеством информации эффективным решением будет использование вычислительной мощности GPU(Graphics Processing Unit). Актуальность данной работы заключается в том, что на сегодняшний день, при проектировании и кодировании программы, большое внимание уделяют её эффективности и, чтобы достичь положительных результатов, используют различные параллельные алгоритмы, разработка которых является довольно непростой задачей. Цель работы: анализ эффективности применения технологий CUDA в алгоритме пирамидальной сортировки. Задачи: изучить материал по пирамидальной сортировке и её реализации, изучить материал по программно-аппаратной архитектуре параллельных вычислений CUDA, создать последовательный и параллельный алгоритмы пирамидальной сортировки, а также реализовать данное решение в виде программного кода, провести эксперименты с ними, проанализировать все результаты и сделать по ним выводы. В ходе исследования применялась методика оценки эффективности программного обеспечения, а именно: пользовательская библиотека time.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ 4
1 МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ 5
1.1 Характеристика объекта исследования 5
1.2 Разработка последовательной программы 8
2 ПРОЕКТИРОВАНИЕ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА И РЕАЛИЗАЦИЯ ПРОГРАММЫ 11
2.1 Обзор технологий параллельного программного обеспечения 11
2.2 Реализация параллельного выполнения задачи с помощью технологии CUDA 19
3 АНАЛИЗ ЭФФЕКТИВНОСТИ 25
3.1 Разработка методики оценки эффективности 25
3.2 Проведение экспериментов и анализ результатов 26
ЗАКЛЮЧЕНИЕ 29
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 30
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Келвин Лин, Лоуренс Снайдер. Принципы параллельного программирования. Учебное пособие. – Москва: Издательство МГУ, 2017. – 388c.
2. Малявко А.А. Параллельное программирование на основе технологий openmp, mpi, cuda 2-е изд., испр. и доп.; Учебное пособие для академического бакалавриата – Москва: ЮРАЙТ, 2017. – 117с.
3. Серебряков В. А. Теория и реализация языков программирования: Учебное пособие – М.: МЗ Пресс, 2014. -352 с.: ил.
4. Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. p. 52.
5. Стенли, Б. Липпман Язык программирования C++. Базовый курс / Стенли Б. Липпман, Жози Лажойе , Барбара Э. Му. - М.: Вильямс, 2014. - 484 c.
6. Ник, Рендольф Visual Studio 2010 для профессионалов / Рендольф Ник. - М.: Диалектика / Вильямс, 2016. - 282 c.
7. Пол, Ирэ Объектно-ориентированное программирование с использованием C++ / Ирэ Пол. - М.: ДиаСофт Лтд, 2014. - 480 c.
8. Литвиненко Н.А. Технология программирования на С++. — П.: БХВ-Петербург, 2014. — 281 с.;
9. Субъективный объективизм [Электронный ресурс]: Добро пожаловать в параллельный мир. Часть 1: Мир многопоточный. – Режим доступа: http://scrutator.me/post/2012/04/04/parallel-world-p1.aspx;
10. Ральф Джонсон Приемы объектно-ориентированного проектирования. Паттерны проектирования - М.: Питер, 2016. - 957 c.
В исследовании, которое будет приведено далее, не будет использовано формулы (3.2), поскольку формула (3.1) даст и так точное значение по сравнению со второй формулой. Для оценки эффективности каждого алгоритма (последовательного и распараллеленного технологией CUDA) необходимо поочерёдно предоставить одинаковую вычислительную нагрузку на каждый алгоритм. Также, будет необходимо замерить время выполнения каждого алгоритма при различных размерах вычислений. Основным параметром вычислительной нагрузки будет являться размерность массивов их количество Время работы будет замерено с помощью функции clock из библиотеки time. Конечно, технология CUDA предоставляет свои методы для измерения времени, но, в конце концов, было решено использовать стандартную функцию. А для более точных измерений времени в распараллеленном коде было решено применять пользовательскую библиотеку time, которая предоставляет точные методы измерения времени выполнения программного кода.
После экспериментов будет составлена таблица, в которой будут содержаться результаты замеров времени работы двух алгоритмов. Также в данной таблице будут высчитаны коэффициенты ускорения. И после каждой таблицы, для наглядности, будет представлен график. А в конце будет подведён итог по эффективности применённой технологии.