CODEWITHSUNDEEP
cudagraph-theorygpu
scatman
scatman

Reputation: 14555

Graph algorithms on GPU

The current GPU execution and memory models are somehow limited (memory limit, limit of data structures, no recursion...).

Do you think it would be feasible to implement a graph theory problem on a GPU? For example, vertex cover? dominating set? independent set? max clique?....

Is it also feasible to have branch-and-bound algorithms on GPUs? Recursive backtracking?

Upvotes: 21

Views: 12238

Answers (2)

Pratik Deoghare
Pratik Deoghare

Reputation: 37172

You will be interested in

  1. Exploring the Limits of GPUs With Parallel Graph Algorithms

  2. Accelerating large graph algorithms on the GPU using CUDA.

Upvotes: 29

Nathan
Nathan

Reputation: 466

This is tangentially related to your question, but I've implemented a "recursive" backtracking algorithm for enumerating "self-avoiding walks" on a lattice (n.b.: the stack was simulated within the CUDA kernel, to avoid the overhead of creating local variables for a whole bunch of function calls). It's possible to do this efficiently, so I'm sure this can be adapted to a graph theoretical context. Here's a link to a seminar on the topic where I gave some general discussion about backtracking within the Single Instruction Multiple Data (SIMD) paradigm; it's a pdf of about 1MB in size http://bit.ly/9ForGS .

I don't claim to know about the wider literature on graph theoretical algorithms on GPUs, but hope the above helps a little.

(@TheMachineCharmer, thanks for the links.)

Upvotes: 5

Related Questions