ИСТИНА |
Войти в систему Регистрация |
|
ИПМех РАН |
||
Поиск в ширину (BFS) является одним из основных алгоритмов обхода графа и базовым для многих алгоритмов анализа графов более высокого уровня. Поиск в ширину на графах является задачей с нерегулярным доступом к памяти и с нерегулярной зависимостью по данным. В докладе будет рассмотрена реализация алгоритма поиска в ширину (основного теста рейтинга Graph500) для обработки больших графов на одном узле с многоядерным процессором или графическим ускорителем. Будут описаны особенности реализации алгоритма на общей памяти, а также некоторые преобразования графа для ускорения доступа к памяти GPU.