Parallel Johnson’s Algorithm | :D

We implemented Johnson's Algorithm for all-pairs shortest path from scratch using OpenMP and CUDA. We also measured and analyzed the performance improvements in different parts of the program and on graphs with different number of nodes and different graph densities. Our OpenMP implementation achieved a best speedup of 6.97x on GHC machines. Our CUDA implementation achieved a best speedup of 16.37x on GHC machines.

Name		Name	Last commit message	Last commit date
Latest commit History 109 Commits
graphs		graphs
Makefile		Makefile
README.md		README.md
bellman_ford.cpp		bellman_ford.cpp
benchmark.py		benchmark.py
cycletimer.cpp		cycletimer.cpp
cycletimer.hpp		cycletimer.hpp
dijkstra.cpp		dijkstra.cpp
graph.py		graph.py
instrument.cpp		instrument.cpp
instrument.hpp		instrument.hpp
johnson-boost.cpp		johnson-boost.cpp
johnson-boost.hpp		johnson-boost.hpp
johnson.cpp		johnson.cpp
johnson.cu		johnson.cu
johnson.hpp		johnson.hpp
regress.py		regress.py

fangzhouxie/spring2020_15618_project

Folders and files

Latest commit

History

Repository files navigation

Parallel Johnson’s Algorithm | :D

About

Resources

Stars

Watchers

Forks

Languages