In this blog I will finalize the work that we completed on triangle counting in graphs on the GPU using CUDA. The two previous blogs can be found: <a href="http://sandbox.arrayfire.com/triangle-counting-in-graphs-on-the-gpu-part-1/" title="Part 1" target="_blank"> Part 1</a> and <a href="http://sandbox.arrayfire.com/triangle-counting-in-graphs-on-the-gpu-part-2/" title="Part 2" target="_blank"> Part 2</a>. The first part introduces the significance of the problem and the second part explains the algorithms that we used in our solution. 

Next week we will present this work in finer detail in the <a href="http://cass-mt.pnnl.gov/irregularworkshop.aspx" title="IA^3" target="_blank">Workshop on Irregular Applications: Architectures and Algorithms</a> which will take place as part of <a href="http://sc14.supercomputing.org/" title="SC'14" target="_blank">Supercomputing 2014</a>.

Previously, we discussed that the performance of the triangle counting is dependent on the algorithm and the CUDA kernel. Our implementation gives the data scientist control over several important parameters:
<ul>
<li>Number of threads blocks - the number of threads blocks that will be created impacts the number of vertices of each thread block is responsible for. Each thread block receives an equal number of vertices that it will be responsible for the triangle counting via the adjacency list intersection approach.A small number of thread blocks can cause workload imbalance due to the fact that many real-world networks follow a power law distribution. It is possible to allocate a single thread-block to each vertex due to the large number of available thread-blocks - this however can also increase overhead. As such it is necessary to find a good balance over-allocating and under-allocating - we used 16000 thread blocks.</li>
<li>Number of concurrent intersections (in a thread block) - while it is feasible to allocate an entire thread block for a single intersection, this will typically bring about poor performance due to under utilization. Perhaps the single most important requirement for utilizing a thread-block is to ensure that the size of the thread-block is greater than the size of a warp. For adjacency list intersection this can cause an under utilization of the warp (and the thread-block) due to the sparsity found in social networks where many vertices only have a handful of adjacent vertices. As such an entire warp in not necessary for the intersection. The other extreme to allocating an entire warp to a single intersection, is to allocate a single thread for every intersection for a specific vertex. Once again, this can lead to under-utilization as there are not enough threads to utilize the entire. </li>
<li>Number of threads per intersection</li>
</ul>




