Аннотация
В данной статье хочу рассказать как можно эффективно распараллелить алгоритм BFS — поиск в ширину в графе с использованием графических ускорителей. В статье будет приведен подробный анализ полученного алгоритма. Вычисления выполнялись на одном GPU GTX Titan архитектуры Kepler.
Введение
В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе. Решение данной задачи рассмотрено мной в этой статье. Вторым примером задачи на неструктурных сетках является задача Breadth First Search (BFS) — поиска в ширину в неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. Также она немного проще, чем поиск кратчайшего пути. На данный момент алгоритм BFS используется как основной тест для рейтинга Graph500. Далее рассмотрим, как можно использовать идеи решения задачи SSSP в задаче BFS. Про архитектуру GPU компании Nvidia и об упомянутых алгоритмах уже много написано, поэтому в этой статье я не стану дополнительно писать про это. Так же, надеюсь, что понятия warp, cuda блок, SMX, и прочие базовые вещи, связанные с CUDA читателю знакомы.
BEING SPACES: заведения коммерческого типа, похожие на жилые комнаты, которые находятся в общественных местах и где можно не только заказать покушать или какое-нибудь развлечение, но самое главное, что они предоставляют территорию вне офиса и вне дома, где можно просто посидеть, посмотреть телевизор, почитать книжку, встретиться с друзьями и сотрудниками.
Фото: 
