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

[foxin]

Можете поподробнее рассказать о подготовке к бенчмаркам? Разогреве и прочем.

[ALEX_k_s]

Всего три этапа: чтение данных сгенерированного графа в формате CSR; далее этап преобразования данных, описанные в SSSP; собственно счёт.
Какой этап вас конкретно интересует? И что понимается под разогревом?

[DustCn]

Время загрузки сгенерированного графа на карту учитывалось?

[ALEX_k_s]

Нет. Если его учесть, то время счёта будет равно 1/3 от общего. Тем более если вы считаете разные алгоритмы на графах, то загружать будете один раз.

[DustCn]

То есть проблема передачи данных через PCIe никак не решена, а это печалька. Учитывая что кроме синтетики graph500 просто сортировка графа это часть какого то более сложного решения и нужно таскать туда-сюда данные…

На текущий момент обычная серверная нода IVB@2.6Ghz с 64Гб памяти всего лишь раза в 3 медленнее, с HSW отрыв будет еще меньше. Если вы в тройку упадете по скорости с передачей данных на карту, то это будет паритет уже на IVB и городить огород с картами нет смысла.

Да и… Предположим у вас граф более 2Гб, что будете делать?

[ALEX_k_s]

А в чем собственно проблема? Эти данные закачиваются туда один раз. Предположим вам надо разметить граф хотя бы 32 раза. Тогда на карту будет одна закачка и 32 раза запустится алгоритм. То есть получаем, что на 32 точки 31 работает со скоростью Х, а 1 — Х / 3. Итоговая скорость с учетом копирования уменьшится примерно на 3-4%.
Если же по алгоритму планируется добавление новых дуг, то это тоже можно предусмотреть и добавлять в уже выделенное место.

На Титан помещается граф и на 4Гб, просто для его обработки не хватило памяти, так как был не эффективно написан алгоритм сортировки. Для многих карт я еще пока не думал что делать.

[DustCn]

Чтобы перевести разговор в плоскость конкретики нужно взять пару приложений и посмотреть как это интегрируется туда.