Logo BSU

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ: https://elib.bsu.by/handle/123456789/152621
Заглавие документа: Ускорение параллельного поиска в ширину в графах при вычислениях на GPU
Авторы: Козик, А. А.
Побегайло, А. П.
Тема: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетика
Дата публикации: 2015
Издатель: Минск : БГУ
Библиографическое описание источника: Вестник БГУ. Серия 1, Физика. Математика. Информатика. - 2015. - № 2. - С. 102-107
Аннотация: Решается задача ускорения работы алгоритма поиска в ширину на графах при вычислениях с помощью графических процессоров. Ускорение алгоритма достигается посредством кодирования матрицы смежности графа специальным образом, учитывающим программно-аппаратную архитектуру CUDA, что дает возможность значительно улучшить производительность рассматриваемого алгоритма при исполнении на этой платформе. Представленный способ кодирования матрицы смежности позволяет снизить накладные расходы на операции чтения /записи из глобальной памяти, необходимый объем памяти для представления графа, а также существенно уменьшить время, затрачиваемое на загрузку данных, которое в других случаях может превышать время выполнения самого алгоритма. Предложенная реализация параллельного алгоритма поиска в ширину может быть использована при решении задач, включающих поиск кратчайшего пути в графах, для случайных графов с высокой вероятностью появления ребра. Несмотря на избыточность вычислений, при высоких значениях вероятности p – появления ребра графа – полезная нагрузка на GPU остается на уровне 96,7 %. = The article solves the problem of accelerating parallel breadth first search algorithm on GPU. Acceleration of the algorithm is obtained by special coding of graph adjacency matrix, taking into account CUDA architecture. This coding improves the algorithm efficiency on CUDA platform because reduces the number of read /write operations from the global memory and the time needed to load data. The proposed implementation of the algorithm can be used for solving problems on graph, which use breadth first search as basis computation and have not very sparse adjacency matrix. Despite the redundancy calculation, if the probability of graph edges occurrences is high then the payload on GPU remains at the level 96,7 %.
URI документа: http://elib.bsu.by/handle/123456789/152621
ISSN: 1561-834X
Лицензия: info:eu-repo/semantics/openAccess
Располагается в коллекциях:2015, №2 (май)

Полный текст документа:
Файл Описание РазмерФормат 
102-107.pdf459,7 kBAdobe PDFОткрыть
Показать полное описание документа Статистика Google Scholar



Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.