A while back I wrote a blog on triangle counting in networks using CUDA (see <a href="http://sandbox.arrayfire.com/triangle-counting-in-graphs-on-the-gpu-part-1/" title="Part 1" target="_blank"> Part 1</a> for the post). In this post, I will cover in more detail the internals of the algorithm and the CUDA implementation. Before I take a deep dive into the details of the algorithm, I want to remind the reader that there are multiple ways for finding triangles in a graph. Our approach is based off the intersection of two adjacency lists and finding the common elements in both those lists. Two additional approaches would simply be to compare all the possible node-triplets in the graph or using via matrix multiplication of the incidence array. The last of these two approaches can be computationally  demanding, especially for sparse networks. This makes the adjacency list intersection approach preferable in most cases. For the intersection to be efficient, typically the lists are presorted. This by no means is an exaggerated requirement. 
An extended discussion on the pros and cons of the different approaches can be found in both the papers by <a href="http://www.emis.ams.org/journals/JGAA/accepted/2005/SchankWagner2005.9.2.pdf" title="Finding, counting and listing all triangles in large graphs, an experimental study" target="_blank">Shanck & Wagner</a> and in <a href="http://www.cc.gatech.edu/grads/o/ogreen3/_docs/2014LoadBalancecClusteringCoefficients.pdf" title="Load Balanced Clustering Coefficients" target="_blank">Green et al.</a> 

The significance of the adjacency lists being, while not exaggerated, is in fact important. The main reason is that the intersecting two sort lists is very similar conceptually to merging two sorted lists. Thus, parallel merge algorithms can adopted for the intersection.
The key difference between a merge and the intersection, is that most parallel merge algorithms offer exclusive writing (in terms of location) in the output array - meaning each thread is responsible for merging independent sections of the output and in fact each thread knows the exact position in the output array that it will write to. For intersection, this is more complicated as the exact position to which a thread will need to write to in a sorted fashion is dependent on the sorted input. Fortunately, in the case of triangle counting, the actual set of overlapping elements is not necessary - rather only the number of common elements is required. This in fact allows us to use the recently developed <a href="http://arxiv.org/pdf/1406.2628" title="Merge Path" target="_blank">MergePath</a> and <a href="http://www.cc.gatech.edu/~bader/papers/GPUMergePath-ICS2012.pdf" title="GPU Merge Path" target="_blank">GPU-MergePath</a> algorithms for our purposes. Merge Path is a visual approach for merging two sorted arrays into one sorted array. 

MergePath restates the problem of merging two sorted arrays into the traversal of a 2-d grid from the top-left corner to the bottom-right corner with the only legal moves being downwards and to the right. This can be seen in the figure below. The traversal of the grid is in fact dependent on the values of the input arrays (one has been placed at the top of the grid and the other has been placed on the left of the grid). The decision on either moving down or two the right is dependent on the location of the indices of the path. As the path starts at index (0,0), the values A[0] is compared with the value B[0]. Based on the comparison, the movement direction is decided on. The movement direction essentially increases the pointer-index of one of these arrays. Thus, only elements on the path are computed (compared).


<a href="http://sandbox.arrayfire.com/wp-content/uploads/2014/10/merge.png"><img src="http://sandbox.arrayfire.com/wp-content/uploads/2014/10/merge-300x300.png" alt="merge" width="300" height="300" class="alignnone size-medium wp-image-6952" /></a>

<a href="http://sandbox.arrayfire.com/wp-content/uploads/2014/10/intersect1.png"><img src="http://sandbox.arrayfire.com/wp-content/uploads/2014/10/intersect1-300x300.png" alt="intersect" width="300" height="300" class="alignnone size-medium wp-image-6955" /></a>


Using the Merge-Path concept, it is possible to partition the work into equal length paths such that each core is responsible for merging an equal number of elements. With a little augmentation to the movement pattern, we can in fact change Merge-Path to support intersection. This involves adding an additional move option: down-right. This move occurs when the elements pointed by the indices in both lists are equal. So why is all this important? Well, the simply truth is that this allows us to split the adjacency list intersection between multiple GPU threads. This also permits executing several different adjacency list executions concurrently in a single CUDA block.

In the next blog I will cover both performance and give some additional details on benefits of doing multiple list intersections concurrently.





