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

Please reload

Recent Posts

December 16, 2016

December 16, 2016

Please reload

Please reload

Search By Tags
Please reload

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

Ul. Vasil Glavinov (Tifani),

br 14 Vl. 1 020,

1000 Skopje Centar

+389 23 118 158

Macedonia Office