Ускорение параллельного поиска в ширину в графах при вычислениях на GPU

Abstract

Решается задача ускорения работы алгоритма поиска в ширину на графах при вычислениях с помощью графических процессоров. Ускорение алгоритма достигается посредством кодирования матрицы смежности графа специальным образом, учитывающим программно-аппаратную архитектуру 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 %.