Parallelizing Bellman Ford Algorithm

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.

Featured Posts
Recent Posts
Search By Tags
No tags yet.
Follow Us
  • Facebook Basic Square
  • Twitter Basic Square
  • Google+ Basic Square

Macedonia Office

Ul. Vasil Glavinov (Tifani),

br 14 Vl. 1 020,

1000 Skopje Centar

+389 23 118 158