• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Комоско Лариса Федоровна
Разработка и имплементация эвристического алгоритма для решения задачи о раскраске графа с использованием графического процессора
Бакалавриат
2014
Дипломная работа на тему: «Разработка и имплементация эвристического алгоритма для решения задачи о раскраске графа с использованием графического процессора» содержит 68 страниц, 12 рисунков, 4 таблицы, 6 диаграмм и 32 использованных источника.Целью дипломной работы является разработка, реализация и анализ эффективности эвристического алгоритма для решения задачи о раскраске графа с использованием графического процессора.Объектом исследования выступает задача о раскраске графа.Предметом исследования – новый эвристический алгоритм, позволяющий получить раскраску графа (вектор из n натуральных чисел) с помощью битовых операций над матрицей запрещенных цветов и матрицей смежности этого графа, используя графический процессор.В связи с тем, что графические процессоры становятся все более универсальными вычислительными машинами, появляются технологии для программирования на них задач, не связанных с компьютерными играми и растеризацией. Поэтому, для повышения эффективности алгоритма раскраски графа рассматривается возможность его реализации с использованием графического процессора. Такой подход к решению задачи дает возможность использовать параллельные вычисления, распределяющие нагрузку между ресурсами CPU и графическим процессором. Сегодня он становится все более популярным.В теоретической части работы анализируется архитектура графического процессора в сравнении с архитектурой центрального процессора, рассматриваются некоторые существующие алгоритмы раскраски графа. Кроме того, разрабатывается собственный быстрый последовательный алгоритм раскраски с использованием битовых операций над битовыми представлениями матрицы смежности графа и матрицы запрещенных цветов. В практической части представлено 3 различные версии разработанного алгоритма последовательной раскраски с использованием графического процессора, которые отличаются методами работы с различными видами памяти GPU и его потоками. Производится сравнение скоростей работы этих имплементаций, и выявляется наиболее быстрая из них – алгоритм c использованием глобальной памяти для хранения матриц смежности и запрещенных цветов и использованием разделяемой памяти для битового массива, с которым работают 32 потока одновременно.Предложенный алгоритм, реализованный с использованием GPU, показывает среднее ускорение в 2,3 раза по сравнению с реализацией этого же алгоритма на центральном процессоре. В статье А. Берилло “NVIDIA CUDA - неграфические вычисления на графических процессорах” говорится о том, что в среднем, при переносе вычислений на GPU, в задачах достигается ускорение в 5-30 раз по сравнению с быстрыми универсальными процессорами. Анализ имплементированного алгоритма показал, что частые операции обращения потоков к глобальной памяти графического процессора и зависимость данных друг от друга при выполнении шагов алгоритма явились факторами, замедляющими работу GPU.Был сделан вывод, что графический процессор выгоднее использовать для работы с графикой информацией или для задач с большим объемом данных, над которым производятся простые операции.При выполнении выпускной квалификационной работы были использованы методы теории графов и теории множеств, так как основой любого алгоритма раскраски графа являются понятия, теоремы, аксиомы этих двух теорий. Данные методы помогли понять математическую модель алгоритмов раскраски и в итоге успешно разработать и реализовать свой алгоритм на языке программирования C++ и этот же алгоритм с использованием графического процессора. Использование таких методов научного познания как формализация, анализ, синтез также помогали в получении и анализе результатов работы.

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Расширенный поиск ВКР