Самая быстрая и энергоэффективная реализация алгоритма BFS на различных параллельных архитектурах

[ZaMaZaN4iK]

Шикарный материал. Спасибо большое.

[Lopros]

Я сам когда-то занимался данной тематикой. Возник вопрос, данный алгоритм новый и придуман вами или все тот же, что и лет ~5 назад? Если нет, попробую использовать ваш :)

И еще один вопрос касательно структуры графов. Вы написали что используете RMAT. А что, если степень связности будет ниже, например, 5 или 6? Будет ли алгоритм также эффективен относительно CPU? Вопрос имеет прикладной характер, так как в некоторых задачах моделирования очень часто приходится переходить от сеток к графам.

[ALEX_k_s]

Если честно сказать, то он адаптирован для ГПУ и ЦПУ мой + я придумал, как надо организовать данные, чтобы алгоритм работал максимально эффективно. Причем положение данных позволяет выполнять обработку большинства алгоритмов намного быстрее, чем если бы граф находился в произвольном состоянии.
Безусловно, текущий алгоритм это совершенно новый и намного лучший алгоритм, чем был ~5 лет назад, опубликованный мной.

На счет моделирования — надо понять какой процент от общего времени занимают переходы и для чего при переходе использовать BFS ?

[Lopros]

Переходы делаются нечасто и стоят дешево (не больше 1%). Поэтому больше интересует эффективность самих графовых алгоритмов (максимальный поток в сети, кратчайший путь, кратчайших путь во взвешенном графе и т.д.) на GPU и сопроцессорах относительно CPU.