CPU vs GPU Floyd Warshall Test

Floyd Warshall is a min path algorithm,  https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm that can calculate the optimal distance between any two nodes in a graph. 

Because of the way it works is easy to be translated in a parallel implementation that can run on a GPU using CUDA. 

How the tests where performed. 

• For each test a random graph is generated with a predefined number of nodes and stored in a array, this makes it easier to reference the data from the kernel (the code that is executed on the GPU).
• The kernel is executed once for each node (basically the outer loop from the algorithm)
  
• The iterative version is executed
• The results of both version are compared to be sure are returning the same values. 
• A test is executed multiple times to have an idea of the running time variance. 

Hardware used:

• https://www.techpowerup.com/gpu-specs/geforce-rtx-3050-mobile.c3788
  
• https://www.techpowerup.com/cpu-specs/ryzen-5-6600h.c2525

Below are the results with random graphs having between 500 and 5000 nodes. 

 

 Results:

#nodes	CPU TIME	GPU TIME
1000	0.751253	0.12836
1000	0.749888	0.124435
1000	0.759052	0.125294
1500	2.644143	0.316551
1500	2.639754	0.331018
1500	2.838966	0.328152
2000	6.841911	0.701491
2000	7.035439	0.697618
2000	6.923238	0.708921
2500	13.468929	1.389693
2500	12.79955	1.377885
2500	13.012448	1.372046
3000	21.833133	2.219689
3000	21.917228	2.231695
3000	22.02113	2.232096
3500	34.55523	3.341517
3500	34.392655	3.342961
3500	34.984248	3.343004
4000	51.395259	4.92573
4000	50.19292	4.926259
4000	51.375857	4.92464
4500	73.01885	7.136843
4500	70.625245	7.134519
4500	70.281992	7.131598
5000	98.194036	9.573494
5000	96.340744	9.572075
5000	97.659462	9.573266