Комментарии 4
Шикарный материал. Спасибо большое.
Я сам когда-то занимался данной тематикой. Возник вопрос, данный алгоритм новый и придуман вами или все тот же, что и лет ~5 назад? Если нет, попробую использовать ваш :)
И еще один вопрос касательно структуры графов. Вы написали что используете RMAT. А что, если степень связности будет ниже, например, 5 или 6? Будет ли алгоритм также эффективен относительно CPU? Вопрос имеет прикладной характер, так как в некоторых задачах моделирования очень часто приходится переходить от сеток к графам.
И еще один вопрос касательно структуры графов. Вы написали что используете RMAT. А что, если степень связности будет ниже, например, 5 или 6? Будет ли алгоритм также эффективен относительно CPU? Вопрос имеет прикладной характер, так как в некоторых задачах моделирования очень часто приходится переходить от сеток к графам.
Если честно сказать, то он адаптирован для ГПУ и ЦПУ мой + я придумал, как надо организовать данные, чтобы алгоритм работал максимально эффективно. Причем положение данных позволяет выполнять обработку большинства алгоритмов намного быстрее, чем если бы граф находился в произвольном состоянии.
Безусловно, текущий алгоритм это совершенно новый и намного лучший алгоритм, чем был ~5 лет назад, опубликованный мной.
На счет моделирования — надо понять какой процент от общего времени занимают переходы и для чего при переходе использовать BFS ?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Самая быстрая и энергоэффективная реализация алгоритма BFS на различных параллельных архитектурах