Comments 19
Отличный пост.
Будет ли продолжение с реализацией на OpenCL и сравнением?
Будет ли продолжение с реализацией на OpenCL и сравнением?
А нужно ли? Тестировать на AMD негде, а на GTX думаю не должно быть разницы так как транслируется все в те же cuda функции.
Реализация на OpenCL сама по себе хороша)
интересно чем она хороша? просто я как вспомню, что там надо возиться с инициализацией и писать ядра в виде string — то сразу не хочется опять вспоминать… и много версий этого CL. Смысл переписывать есть только в том случае, если есть AMD R290x ), а так — всегда можно на CUDA встроиться.
По сравнению с CUDA, OpenCL выглядит немного каторжно :)
Пара вопросов.
1) так ли тут критичен double?
2) если веса положительны, как изменится производительность, если написать что-то в этом роде:
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];
}
1) double конечно критичен. Именно для этой задаче — генератор построен на double и не хочется менять. Но а вообще, если при решении какой либо задачи, например, поиска маршрута, нужен float — то конечно не критично, даже лучше — больше данных в L2 поместится
2) Хорошо придумали. Это можно проверить и на double — аналогичная функция взятия знака есть и в double. Только вот не будет ли вызовы функций дольше, чем дивергенция в варпе? Надо будет проверить. Только тут забыли про
Это важно, так как в этот момент происходят записи и массива dist. (пробовал убрать эту строку — получалось по другому). Ведь все построено на том, что ранние варпы успеют обновить массив для более поздних.
Еще не ясно зачем такое присваивание:
Получается вес вы не прибавляете?
2) Хорошо придумали. Это можно проверить и на double — аналогичная функция взятия знака есть и в double. Только вот не будет ли вызовы функций дольше, чем дивергенция в варпе? Надо будет проверить. Только тут забыли про
modif[0] = iter;
Это важно, так как в этот момент происходят записи и массива dist. (пробовал убрать эту строку — получалось по другому). Ведь все построено на том, что ранние варпы успеют обновить массив для более поздних.
Еще не ясно зачем такое присваивание:
dist1[st + offset] = dist[end - offset];
Получается вес вы не прибавляете?
Попробовал вставить такой код:
и такой, который был предложен выше — производительность хуже на средних графах на 8-10%, на больших 4-6%.
Я все таки думаю, что вызовы двух функций дороже, чем ветвление.
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%.
Я все таки думаю, что вызовы двух функций дороже, чем ветвление.
Да, я код набросал навскику ночью. Общую идею только. Вес, конечно, надо прибавлять, как и копирование в modif[0]. В любом случае, спасибо, что проверили. Тем не менее, я думаю, смени вы double на float, предложенный мной вариант оказался бы быстрее. И да, вычисление offset лучше поместить внутрь then ветви.
И еще, все-таки добавлю, что мотивация «не хочется» менять, не очень подходит в данном случае. Нужно все же реально оценивать, какую точность во входных данных вы имеете, какую хотите получить и как в алгоритме с устойчивостью к ошибкам округления и погрешностям во входных данных.
И еще, все-таки добавлю, что мотивация «не хочется» менять, не очень подходит в данном случае. Нужно все же реально оценивать, какую точность во входных данных вы имеете, какую хотите получить и как в алгоритме с устойчивостью к ошибкам округления и погрешностям во входных данных.
Так как в данном случае значения весов лежат в отрезке [0,1], то double крайне обязателен. Можно проверить на сколько быстро работают эти функции(singbit и abs) на double и float. Я думаю, что один вызов double функции по времени меньше, чем два вызова такой же float функции.
Какая связь между отрезком [0,1] и double мне не очень понятно. Вопросы на самом деле какие:
1) каковы порядки получаемых длин путей?
2) в каком соотношении эти величины находятся с весами?
Это, чтобы понять возникнут ли ситуации, когда при суммировании «больших» чисел с «маленькими», последние будет отброшены, так как не влезут в разрядную сетку.
И такие:
1) с какой точностью получены исходные данные?
2) какая точность требуется в расчетах?
Мотивация: DP устройств _намного_ меньше, чем SP.
Вы же пытаетесь какое-то мифическое время вызова DP-функций в противовес к SP-функциям поставить.
1) каковы порядки получаемых длин путей?
2) в каком соотношении эти величины находятся с весами?
Это, чтобы понять возникнут ли ситуации, когда при суммировании «больших» чисел с «маленькими», последние будет отброшены, так как не влезут в разрядную сетку.
И такие:
1) с какой точностью получены исходные данные?
2) какая точность требуется в расчетах?
Мотивация: DP устройств _намного_ меньше, чем SP.
Вы же пытаетесь какое-то мифическое время вызова DP-функций в противовес к SP-функциям поставить.
Порядки получаемых длин от 1,5 — 3,0, веса лежат в полуинтервале (0, 1]
Исходные данные были в double и в double они выдаются обратно. Требуется double.
Исходные данные были в double и в double они выдаются обратно. Требуется double.
Для таких величин во float вы будете иметь точность порядка 10^(-7), в double 10^(-15). Это означает, что минимальные веса должны иметь такие порядки, иначе их прямое суммирование не будет иметь смысла.
Хотелось бы сравнить с Дейкстрой на обычном CPU.
Дело в том, что сложность используемого алгоритма O(VE) в худшем случае. Сложность Дейкстры с кучей же O((V+E) logV )
Даже для ваших специфических графов, алгоритм Дейкстры требует в миллионы раз меньше действий.
Правда, Дейкстра гораздо хуже параллелится, но все равно, если у вас не миллионы ядер, Форд-Белламан проигрывает по производительности.
Дело в том, что сложность используемого алгоритма O(VE) в худшем случае. Сложность Дейкстры с кучей же O((V+E) logV )
Даже для ваших специфических графов, алгоритм Дейкстры требует в миллионы раз меньше действий.
Правда, Дейкстра гораздо хуже параллелится, но все равно, если у вас не миллионы ядер, Форд-Белламан проигрывает по производительности.
Да, эти оценки верны и вы правы — в параллельной версии просматривается примерно в 20 раз больше ребер. Наверно не сделал акцент на том, что последний график показывает на сколько быстрее мой алгоритм на GPU с оптимизированной версией на CPU алгоритма Дейкстры с кучей…
Для сравнения производительности на CPU использовался оптимизированный алгоритм Дейкстры. Никаких оптимизаций в виде перестановки данных перед работой на CPU не производились
Простите, невнимательно прочитал статью. Это очень интересно, что оно настолько быстрее работает.
Эффективное использование ресурсов GPU. Там, где производительность порядка 1 млрд дуг/сек, профилировщик NVVP показывает производительность L2 на high уровне при незначительных записях в массив dist, и чуть меньше high — при многочисленных записях. Эффективность чтения из глобальной памяти GPU — 100%, запись — где то 25% так как мало данных пишется. Производительность шины показывается на уровне выше среднего.
Sign up to leave a comment.
Реализация алгоритма SSSP на GPU