các chủ đề GPU hiện tại bị hạn chế một phần nào đó (giới hạn bộ nhớ, giới hạn cấu trúc dữ liệu, không đệ quy ...).Thuật toán đồ thị trên GPU
bạn có nghĩ rằng việc triển khai vấn đề lý thuyết đồ thị trên GPU có khả thi hay không. ví dụ bìa đỉnh? thống trị? tập hợp độc lập? max clique? ....
cũng có khả thi để có các thuật toán nhánh và ràng buộc trên GPU không? Rectrive backtracking?
này hơi liên quan đến câu hỏi của bạn, nhưng tôi đã thực hiện một "đệ quy" backtracking thuật toán cho liệt kê "tầng lớp xã hội tự tránh" trên mạng (nb: ngăn xếp đã được mô phỏng trong hạt nhân CUDA, để tránh chi phí tạo các biến cục bộ cho toàn bộ các cuộc gọi hàm). Có thể thực hiện điều này một cách hiệu quả, vì vậy tôi chắc chắn điều này có thể được điều chỉnh theo ngữ cảnh lý thuyết đồ thị. Dưới đây là một liên kết đến một hội thảo về chủ đề mà tôi đã đưa ra một số cuộc thảo luận chung về backtracking trong mô hình đơn lẻ nhiều dữ liệu (SIMD); đó là bản pdf có kích thước khoảng 1MB http://bit.ly/9ForGS.
Tôi không yêu cầu biết về tài liệu rộng hơn về các thuật toán lý thuyết đồ thị trên GPU, nhưng hy vọng ở trên sẽ giúp ích một chút.
(. @TheMachineCharmer, nhờ những liên kết)
Hãy thêm thế này, đã xuất hiện trong thời gian trung bình: [Đẩy mạnh CUDA Graph Thuật toán tại Maximum Warp] (http: //citeseerx.ist.psu. edu/viewdoc/download? doi = 10.1.1.220.1923 & rep = rep1 & type = pdf). Đối với các đồ thị nhất định, nó sẽ cải thiện đáng kể so với kết quả thứ hai mà bạn liên kết đến. –