ИСТИНА

В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Breadth First Search (BFS) — поиска в ширину в неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. В докладе будет рассмотрена реализация алгоритма поиска в ширину (BFS) для обработки больших графов на кластерах с многоядерными процессорами и графическими ускорителями. Будут описаны оптимизации данного алгоритма на одном GPU, а также некоторые оптимизации для ускорения коммуникаций между узлами при использовании нескольких GPU.