I am using CUDA to build an undirected graph from a list of nodes. Each node has a coordinate in 3-dimensions and my program creates an edge between two nodes if the nodes are separated by less than some cutoff distance d.
Now I am storing the edges in the form of an adjacency list. The problem is, I have 1024 threads computing pairwise distances asynchronously. Once an edge is 'discovered' between nodes A and B, I need to increment the number of edges for node A and place node B at the 'next-available' position in the adjacency list.
Here, CUDA is giving me nightmares. I want the adjacency-list-update process to be critical, but CUDA does not seem to provide anything beyond atomicAdd(). As a result, I am getting unpredictable behavior and a different adjacency list every time I run the code.
Is there a way to asynchronously create the adjacency list? Perhaps through a more clever data structure?