Разработка и имплементация эвристического алгоритма для решения задачи о раскраске графа с использованием графического процессора

<p>Дипломная работа на тему: &laquo;Разработка и имплементация эвристического алгоритма для решения задачи о раскраске графа с использованием графического процессора&raquo; содержит 68 страниц, 12 рисунков, 4 таблицы, 6 диаграмм и 32 использованных источника.</p><p>Целью дипломной работы является разработка, реализация и анализ эффективности эвристического алгоритма для решения задачи о раскраске графа с использованием графического процессора.</p><p>Объектом исследования выступает задача о раскраске графа.</p><p>Предметом исследования &ndash; новый эвристический алгоритм, позволяющий получить раскраску графа (вектор из n натуральных чисел) с помощью битовых операций над матрицей запрещенных цветов и матрицей смежности этого графа, используя графический процессор.</p><p>В связи с тем, что графические процессоры становятся все более универсальными вычислительными машинами, появляются технологии для программирования на них задач, не связанных с компьютерными играми и растеризацией. Поэтому, для повышения эффективности алгоритма раскраски графа рассматривается возможность его реализации с использованием графического процессора. Такой подход к решению задачи дает возможность использовать параллельные вычисления, распределяющие нагрузку между ресурсами CPU и графическим процессором. Сегодня он становится все более популярным.</p><p>В теоретической части работы анализируется архитектура графического процессора в сравнении с архитектурой центрального процессора, рассматриваются некоторые&nbsp; существующие алгоритмы раскраски графа. Кроме того, разрабатывается собственный быстрый последовательный алгоритм раскраски с использованием битовых операций над битовыми представлениями матрицы смежности графа и матрицы запрещенных цветов.&nbsp;</p><p>В практической части представлено 3 различные версии разработанного алгоритма последовательной раскраски с использованием графического процессора, которые отличаются методами работы с различными видами памяти GPU и его потоками. Производится сравнение скоростей работы этих имплементаций, и выявляется наиболее быстрая из них &ndash; алгоритм c использованием глобальной памяти для хранения матриц смежности и запрещенных цветов и использованием разделяемой памяти для битового массива, с которым работают 32 потока одновременно.</p><p>Предложенный алгоритм, реализованный с использованием GPU,&nbsp; показывает среднее ускорение в 2,3 раза по сравнению с реализацией этого же алгоритма на центральном процессоре. В статье А. Берилло &ldquo;NVIDIA CUDA - неграфические вычисления на графических процессорах&rdquo; говорится о том, что в среднем, при переносе вычислений на GPU, в задачах достигается ускорение в 5-30 раз по сравнению с быстрыми универсальными процессорами. &nbsp;&nbsp;Анализ имплементированного алгоритма показал, что частые операции обращения потоков к глобальной памяти графического процессора и зависимость данных друг от друга при выполнении шагов алгоритма явились факторами, замедляющими работу GPU.</p><p>Был сделан вывод, что графический процессор выгоднее использовать для работы с графикой информацией или для задач с большим объемом данных, над которым производятся простые операции.</p><p>При выполнении выпускной квалификационной работы были использованы методы теории графов и теории множеств, так как основой любого алгоритма раскраски графа являются понятия, теоремы, аксиомы этих двух теорий. Данные методы помогли понять математическую модель алгоритмов раскраски и в итоге успешно разработать и реализовать свой алгоритм на языке программирования C++ и этот же алгоритм с использованием графического процессора. Использование таких методов научного познания как формализация, анализ, синтез также помогали в получении и анализе результатов работы.</p>