We all know that the most serious weakness of GPU processing is flow control. Thus, problems in graph theory are not delicious for CUDA. I raise here one of the most basic problems: marking connected nodes in a graph.

The problem is quite simple in the abstract: Given a graph of N nodes and E arcs, each of which connects two different nodes; let’s mark all nodes that are directly/indirectly connected to a certain node.

People have tackled with such problems for classic parallel-processing systems. A good example is here: http://computation.pa.msu.edu/NO/ConnCompPresentation.html. Now comes the CUDA turn.

It is very straightforward to generate testing data. Judging candidates is quite objective: the fastest takes all.