Алгоритм Флойда-Уоршелла

Алгоритм Флойда-Уоршелла довольно прост (http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%...). Если реализовывать на CPU, то программа будет в три цикла и иметь сложность O(N^3).

  1. for k = 1 to n
  2.   for i = 1 to n
  3.     for j = 1 to n
  4.       W[i][j] = min(W[i][j], W[i][k] + W[k][j])

Но задача стоит в том, чтобы реализовать на GPU(CUDA). Здесь возникает вопрос, о том как произвести распараллеливание программы. На вход нам подается квадратная матрица размера [N][N], содержащая длины кратчайших путей между всеми вершинами графа(вес), для начало без отрицательного веса дуг. Чтобы понять как алгоритм работает на каждом шаге, можно просмотреть на эмуляторе (http://rain.ifmo.ru/cat/view.php/vis/graph-paths/floyd-warshall-2004) .
За основу алгоритма для начала хотел взять пример умножение матриц на разделяемой памяти (shared memory), но матрицу я должен пройти полностью для сравнения N раз и при каждом сравнении результат(если выполняется условие теста) мне нужно было записывать в исходную матрицу в глобальную память. Поэтому как мне более правильно реализовать просмотр матрицы в данном алгоритме, чтобы при следующем просмотре матрицы я обращался уже к измененной матрице с новыми данными?

Forums: