Open victorsongyw opened 3 years ago
BF work reduction: relax edges only when needed Method 1: Use a boolean array to keep track of nodes that had an update in the last iteration. Only relax edges for those nodes. https://towardsdatascience.com/bellman-ford-single-source-shortest-path-algorithm-on-gpu-using-cuda-a358da20144b Method 2: Workfront Sweep: add vertices to a queue, process until queue is empty. This paper also presents further work-reducing techniques, but this might deviate from our original project approach. https://escholarship.org/content/qt8qr166v2/qt8qr166v2.pdf?t=n0m9vk
Implement Delta-Stepping instead of Dijkstra's https://escholarship.org/content/qt8qr166v2/qt8qr166v2.pdf?t=n0m9vk The delta-stepping paper: https://www.cs.utexas.edu/~pingali/CS395T/2012sp/papers/delta-stepping.pdf
Implement dynamic work scheduling / deferring outliers I expect this to be ineffective. This paper has more detaiils: https://www.researchgate.net/publication/310663607_A_Dynamic_Approach_for_Workload_Partitioning_on_GPU_Architectures This one is better and talks about Dijkstra's: Dynamic Work Scheduling for GPU Systems http://www.par.univie.ac.at/publications/download/TR-10-3.pdf
BF work reduction: relax edges only when needed Method 1: Use a boolean array to keep track of nodes that had an update in the last iteration. Only relax edges for those nodes. https://towardsdatascience.com/bellman-ford-single-source-shortest-path-algorithm-on-gpu-using-cuda-a358da20144b Method 2: Workfront Sweep: add vertices to a queue, process until queue is empty. This paper also presents further work-reducing techniques, but this might deviate from our original project approach. https://escholarship.org/content/qt8qr166v2/qt8qr166v2.pdf?t=n0m9vk
Implement Delta-Stepping instead of Dijkstra's https://escholarship.org/content/qt8qr166v2/qt8qr166v2.pdf?t=n0m9vk The delta-stepping paper: https://www.cs.utexas.edu/~pingali/CS395T/2012sp/papers/delta-stepping.pdf
Implement dynamic work scheduling / deferring outliers I expect this to be ineffective. This paper has more detaiils: https://www.researchgate.net/publication/310663607_A_Dynamic_Approach_for_Workload_Partitioning_on_GPU_Architectures This one is better and talks about Dijkstra's: Dynamic Work Scheduling for GPU Systems http://www.par.univie.ac.at/publications/download/TR-10-3.pdf