Нужно реализовать параллельный BFS. От Вас требуется написать последовательную версию алгоритма (seq, обычный BFS из курса алгоритмов) и параллельную версию (par). Протестировать надо на кубическом графе со стороной 300 и источником в (0, 0, 0). (Усреднить по 5 запускам) Сравнить время работы par на 4 процессах и seq на одном процессе - у Вас должно быть раза в 3 быстрее. (Если будет медленнее, то выставление баллов оставляется на моё усмотрение.) Учтите, что Ваш BFS должен работать на любом графе, если Вам дан его список смежности. Также нужно сопроводить тестами на корректность работы алгоритма.
Нужен код на гитхабе и результаты запусков в README.md. Код, который запускает, тоже должен лежать в репо.
- C++20 компилятор
- CMake 3.17+
- parlib в /third_party
Как на лекции с мини оптимизациями
| Run | Seq algo | Par algo |
|---|---|---|
| 1 | 691 | 219 |
| 2 | 666 | 214 |
| 3 | 647 | 203 |
| 4 | 660 | 217 |
| 5 | 659 | 202 |
| avg | 664.6 | 211 |
Speedup = 3.14976
Снимок экрана прикрепил
есть и разные семейства графов(циклы, цепочки, пустые, клики), есть и модель Эрдеша-Реньи, есть и на код
mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j4
./bfs
./unit_tests