最近在看CUDA，剛好有一個類似的項目，就拿來練練手。

項目地址：github.com/Sanzona/Bellman-Ford

Bellman Ford

Bellman Ford是求最短路的算法，可以處理帶有負邊的圖，也可以用來判斷負環。
算法的主要思想是：每次遍歷所有的邊并更新每條邊相鄰的點，遍歷N-1次后就可以得到源點到其他點的最短路，對于N個點的圖任意兩點的最短路徑長度不超過N-1。

CUDA

CUDA（Compute Unified Device Architecture，統一計算架構），是一種由NVIDIA推出的通用并行計算架構，該架構使GPU能夠解決復雜的計算問題。
硬件層面分為：SP(streaming processor)、SM(streaming multiprocessor)。
軟件層面分為：grid、block、thread、wrap。

streaming processor

sp是CUDA最基本的處理單元，又稱為CUDA core。

streaming multiprocessor

SM由多個SP組成，SM中包括wrap scheduler、register、shared memory等，CUDA將register和shared memory分配個SM中的threads，SM中的資源數決定了SM中active wrap的個數。

grid、block、thread、wrap

grid、block、thread、wrap是CUDA編程上的概念，方便程序設計。
每個kernel函數都會運行在GPU的一個Grid上。

Grid包含多個Blocks，每個Grid一共有三個維度。

Block包含多個threads，每個Block同樣有三個維度，Block內部的thread可以通過shared
memory通信和同步，不同Block之間的thread互不干擾。

wrap是GPU執行時的調度單位，wrap由32個thread組成，每個wrap在同一時刻執行相同的指令（SIMT），wrap的切換沒有開銷，不需要保存上下文。

thread是最小的執行單位，每個thread有自己的程序計數器和狀態寄存器。

SIMT

gpu分配多個thread執行kernel函數，這些thread以32個為一組分成多個wrap，這些wrap輪流進入SM執行相同過的指令。

設計思路

relaxWithGridStride()：對應Bellman-Ford的松弛操作。
updateDistanceWithGridStride()：更新松弛操作的結果。
updatePredWithGridStride()：在Bellman-Ford完成之后求前驅節點。

其他

在多線程更新dis數組和pred數組時，會出現時序競態的問題，原項目作者沒有考慮完全，我在他的基礎上將atomicExch()改為atomicMin()這樣可以保證多線程下dis的正確性，但是仍然不能保證pred更新的正確性，因為沒有找到合適的CUDA lock unlock的寫法，所以我把前驅節點的計算放到Bellman-Ford完成之后再進行，同時也減少了運行的時間。

參考文獻

Bellman–Ford algorithm
sengorajkumar/gpu_graph_algorithms
Bellman-Ford Single Source Shortest Path Algorithm on GPU using CUDA

總結

以上是生活随笔為你收集整理的用CUDA实现Bellman-Ford的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。