Реализация алгоритма SSSP на GPU

Да, эти оценки верны и вы правы — в параллельной версии просматривается примерно в 20 раз больше ребер. Наверно не сделал акцент на том, что последний график показывает на сколько быстрее мой алгоритм на GPU с оптимизированной версией на CPU алгоритма Дейкстры с кучей…

Для сравнения производительности на CPU использовался оптимизированный алгоритм Дейкстры. Никаких оптимизаций в виде перестановки данных перед работой на CPU не производились

Реализация алгоритма SSSP на GPU

Так как в данном случае значения весов лежат в отрезке [0,1], то double крайне обязателен. Можно проверить на сколько быстро работают эти функции(singbit и abs) на double и float. Я думаю, что один вызов double функции по времени меньше, чем два вызова такой же float функции.

Реализация алгоритма SSSP на GPU

Попробовал вставить такой код:

double diff = dist[st] - dist[en];
int diffSign = signbit(diff);
int offset   = (en-st)*diffSign;
if (fabs(diff) > w)
{
	dist1[st + offset] = dist[en - offset] + w;
	modif[0] = iter;
}

и такой, который был предложен выше — производительность хуже на средних графах на 8-10%, на больших 4-6%.
Я все таки думаю, что вызовы двух функций дороже, чем ветвление.

Реализация алгоритма SSSP на GPU

1) double конечно критичен. Именно для этой задаче — генератор построен на double и не хочется менять. Но а вообще, если при решении какой либо задачи, например, поиска маршрута, нужен float — то конечно не критично, даже лучше — больше данных в L2 поместится
2) Хорошо придумали. Это можно проверить и на double — аналогичная функция взятия знака есть и в double. Только вот не будет ли вызовы функций дольше, чем дивергенция в варпе? Надо будет проверить. Только тут забыли про

modif[0] = iter;

Это важно, так как в этот момент происходят записи и массива dist. (пробовал убрать эту строку — получалось по другому). Ведь все построено на том, что ранние варпы успеют обновить массив для более поздних.
Еще не ясно зачем такое присваивание:

dist1[st + offset] = dist[end - offset];

Получается вес вы не прибавляете?

Реализация алгоритма SSSP на GPU

интересно чем она хороша? просто я как вспомню, что там надо возиться с инициализацией и писать ядра в виде string — то сразу не хочется опять вспоминать… и много версий этого CL. Смысл переписывать есть только в том случае, если есть AMD R290x ), а так — всегда можно на CUDA встроиться.

Реализация алгоритма SSSP на GPU

А нужно ли? Тестировать на AMD негде, а на GTX думаю не должно быть разницы так как транслируется все в те же cuda функции.