Parallelizing Bellman Ford Algorithm

November 10, 2016

Parallelizing Bellman-Ford Algorithm to solve Minimum Cost Flow Problem using GPU


We completed the parallelization of Bellman-Ford negative cycle algorithm with CUDA in order to use it in minimum cost flow problem solver. After gaining a deep understanding of algorithm we design a data structure in order to keep graph representation in such a way that it can be parallelized. We wrote segmented prefix algorithm for the relaxation part. On the parallel algorithm, we have used two strategies for the synchronization, i.e. explicit and implicit. When simulating the parallel algorithm, we have achieved a speed up of 2.2x when using explicit synchronization, and 2.9x when using implicit synchronization compared to sequential algorithm.

 

 

 

 

 

Share on Facebook
Share on Twitter
Please reload

Featured Posts

Histoper Data Collection is Successfully Launched in Arçelik's Factory

June 23, 2017

1/2
Please reload

Recent Posts

December 16, 2016

December 16, 2016

Please reload

Archive
Please reload

Search By Tags
Please reload

Follow Us
  • Facebook Basic Square
  • Twitter Basic Square
  • Google+ Basic Square