ALEX_k_s 3 мар 2014 в 16:00

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

8 мин

17K

GPGPU *

Из песочницы

+42

Комментарии 19

Klukonin 3 мар 2014 в 19:15

Отличный пост.

Будет ли продолжение с реализацией на OpenCL и сравнением?

ALEX_k_s 3 мар 2014 в 19:24

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

egavrin 3 мар 2014 в 20:44

Реализация на OpenCL сама по себе хороша)

ALEX_k_s 4 мар 2014 в 06:24

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

mezastel 4 мар 2014 в 09:53

По сравнению с CUDA, OpenCL выглядит немного каторжно :)

rafuck 3 мар 2014 в 20:52

Пара вопросов.
1) так ли тут критичен double?
2) если веса положительны, как изменится производительность, если написать что-то в этом роде:

float diff = dist[st] - dist[en];
if (fabsf(diff) > w){
    int diffSign = signbit(diff);
    int offset   = (end-st)*diffSign;

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

ALEX_k_s 4 мар 2014 в 06:31

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

modif[0] = iter;

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

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

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

ALEX_k_s 4 мар 2014 в 07:25

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

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%.
Я все таки думаю, что вызовы двух функций дороже, чем ветвление.

rafuck 4 мар 2014 в 10:25

Да, я код набросал навскику ночью. Общую идею только. Вес, конечно, надо прибавлять, как и копирование в modif[0]. В любом случае, спасибо, что проверили. Тем не менее, я думаю, смени вы double на float, предложенный мной вариант оказался бы быстрее. И да, вычисление offset лучше поместить внутрь then ветви.
И еще, все-таки добавлю, что мотивация «не хочется» менять, не очень подходит в данном случае. Нужно все же реально оценивать, какую точность во входных данных вы имеете, какую хотите получить и как в алгоритме с устойчивостью к ошибкам округления и погрешностям во входных данных.

ALEX_k_s 4 мар 2014 в 17:05

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

rafuck 5 мар 2014 в 14:51

Какая связь между отрезком [0,1] и double мне не очень понятно. Вопросы на самом деле какие:
1) каковы порядки получаемых длин путей?
2) в каком соотношении эти величины находятся с весами?
Это, чтобы понять возникнут ли ситуации, когда при суммировании «больших» чисел с «маленькими», последние будет отброшены, так как не влезут в разрядную сетку.
И такие:
1) с какой точностью получены исходные данные?
2) какая точность требуется в расчетах?
Мотивация: DP устройств _намного_ меньше, чем SP.
Вы же пытаетесь какое-то мифическое время вызова DP-функций в противовес к SP-функциям поставить.

ALEX_k_s 5 мар 2014 в 16:49

Порядки получаемых длин от 1,5 — 3,0, веса лежат в полуинтервале (0, 1]
Исходные данные были в double и в double они выдаются обратно. Требуется double.

rafuck 5 мар 2014 в 17:33

Для таких величин во float вы будете иметь точность порядка 10^(-7), в double 10^(-15). Это означает, что минимальные веса должны иметь такие порядки, иначе их прямое суммирование не будет иметь смысла.

ALEX_k_s 5 мар 2014 в 17:36

Все величины весов имеют порядки 10¹⁶ и сравниваются именно с такой точностью при проверке полученного массива расстояний. Я не понимаю к чему вы клоните.

rafuck 5 мар 2014 в 18:24

Пытаюсь выяснить, можно ли обойтись одинарной точностью. Впрочем, как хотите, double, так double.
P.S. кстати, к 1.0 нельзя прибавить 10^(-16) в double. Посмотрите, я писал об этом выше. Но можете и проверить:

if (1.0 == 1.0 + 1e-16){
    printf("f = %.20lf\n", 1.0 + 1e-16);
}

wataru 5 мар 2014 в 05:32

Хотелось бы сравнить с Дейкстрой на обычном CPU.
Дело в том, что сложность используемого алгоритма O(VE) в худшем случае. Сложность Дейкстры с кучей же O((V+E) logV )
Даже для ваших специфических графов, алгоритм Дейкстры требует в миллионы раз меньше действий.

Правда, Дейкстра гораздо хуже параллелится, но все равно, если у вас не миллионы ядер, Форд-Белламан проигрывает по производительности.

ALEX_k_s 5 мар 2014 в 05:52

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

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

wataru 5 мар 2014 в 06:00

Простите, невнимательно прочитал статью. Это очень интересно, что оно настолько быстрее работает.

ALEX_k_s 5 мар 2014 в 06:06

Эффективное использование ресурсов GPU. Там, где производительность порядка 1 млрд дуг/сек, профилировщик NVVP показывает производительность L2 на high уровне при незначительных записях в массив dist, и чуть меньше high — при многочисленных записях. Эффективность чтения из глобальной памяти GPU — 100%, запись — где то 25% так как мало данных пишется. Производительность шины показывается на уровне выше среднего.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий