ИСТИНА

В последнее время все большую роль играют графические ускорители (GPU) в неграфических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. В качестве примера таких задач можно назвать Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе и Breadth First Search (BFS) – поиска в ширину в неориентированном графе. Последняя задача используется в качестве основного теста для рейтинга Graph500, который был создан для оценки производительности вычислительных систем при обработке большого количества данных. Для решения данных задач с помощью центрального процессора (CPU) существует, по крайней мере, два известных алгоритма: алгоритм Дейкстры и алгоритм Форда—Беллмана. Также существуют параллельные реализации алгоритмов поиска в ширину и поиска кратчайшего пути в графе на GPU.