1. 首頁
  2. 問答
  3. GPU上的圖算法

GPU上的圖算法

2010-03-12 59 views
21

當前GPU線程在某種程度上受到限制（內存限制，數據結構限制，無遞歸...）。GPU上的圖算法

你認爲在GPU上實現圖論的問題是可行的嗎？例如頂點覆蓋？支配一套？獨立設置？ max clique？....

在GPU上有分支定界算法嗎？遞歸回溯？

來源

2010-03-12 scatman

回答

4

這是相切關係到你的問題，但我已經實現了「遞歸」回溯算法枚舉「自迴避行走」在網格（注：堆棧進行了模擬的CUDA內核中，以避免爲一大堆函數調用創建局部變量的開銷）。可以有效地做到這一點，所以我相信這可以適應圖論的上下文。這裏是一個關於這個主題的研討會的鏈接，我在單指令多數據（SIMD）範例內給出了關於回溯的一般性討論;這是一個pdf大小約爲1MB的http://bit.ly/9ForGS。

我不主張知道關於GPU上圖論算法的更廣泛文獻，但希望上面的內容有所幫助。

（@TheMachineCharmer，感謝您的鏈接）

來源

2010-03-15 11:32:42 Nathan

相關問題

 相關問題