# An Evaluation of Directive-Based Parallelization on the GPU Using a Parboil Benchmark
## 5 Implementation Details
### Breadth-First Search (BFS)  
The OpenACC implementation of BFS is based on the CUDA implementation presented in [44]. In each iteration threads process, the queue representing the current \"frontier\" of nodes form a new queue, representing a \"frontier\" of nodes for the next iteration. For this application to work correctly, a comparison of the current and the calculated cost of visitation, as well as the update of the node color, need to be atomic. These are far too complex for the OpenACC atomic directives and require CUDA-style atomics for their implementation. In addition, as with the CUDA version, all necessary buffers are transferred to the GPU only once before the parallel region with the usage of the data directive to minimize the memory footprint. The code of the OpenACC implementation is given in Listing 1. The variables input_queue and output_queue represent the current and the next \"frontier\" of nodes for visiting in the current and the next iteration.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Application** & **Short Description** & **Type** \\ \hline BFS & Breadth-First Search graph traversal algorithm & Memory bound \\ \hline CUTCP & Cutoff-limited Coulombic Potential physics & Compute bound \\  & simulation & Compute bound \\ \hline Histo & Histogramming operation & Memory bound \\ \hline LBM & Lattice-Boltzman Method simulation in fluid dynamics & Memory bound \\ \hline MRI-Gridding & MRI Cartesian Gridding, a step in magnetic resonance imaging & Memory bound \\ \hline MRI-Q & MRI non-cartesian Q matrix calculation used in MRI image reconstruction & Compute bound \\ \hline SAD & Sum of Absolute Differences, part of the H.264/AVC video encoder & Memory bound \\ \hline SGEMM & Dense linear algebra single precision general matrix multiplication operation & Memory bound \\ \hline SpMV & Sparse Matrix-Dense Vector Multiplication for iterative solvers & Memory bound \\ \hline Stencil & Iterative Jacobi PDE solver of the heat equation on a 3D-structured grid & Memory bound \\ \hline TPACF & Two-Point Angular Correlation Function calculation in astronomy & Memory bound \\ \hline \hline \end{tabular}
\end{table}
Table 1: Parboil Benchmark Suite Applications.  
```
1#pragmaaccdatacopyin(queue0[0:number_of_nodes],nodes[0:number_of_nodes],{}
2 edges[0:number_of_edges],colors[0:number_of_nodes]){}
3 copy(costs[0:number_of_nodes])create(queue1[0:number_of_nodes],{}
4 while(counter>0){}
5 intnew_counter=0;
6
7
8#pragmaaccparallelloopcopy(new_counter)
9 for(inti=0;i<counter;++i){
10 int*input_queue=(k&1)=0?queue0:queue1;
11 int*output_queue=(k&1)=0?queue1:queue0;
12
13 intn=input_queue[i];
14
15 colors[n]=BLACK;
16 intstart=node[n].edges_start;
17 intend=nodes[n].edges_start+nodes[n].edges_count;
18
19 for(inte=start;e<end;++e){
20 intid=edges[e].node;
21
22 intcurrent_cost=edges[e].cost+costs[n];
23//notetheusageoftheCUDAstyleatomicfunction
24 intoriginal_cost=atomicMin(&costs[id],current_cost);
25
26 if(original_cost>current_cost){
27//notetheusageoftheCUDAstyleatomicfunction
28 intcurrent_color=atomicExch(&colors[id],GRAY);
29 if(current_color==WTHIE){
30 costs[id]=current_cost;
31 intnext=0;
32
33#pragmaaccatomiccapture
34{
35 next=new_counter;
36 new_counter+=1;
37}
38 output_queue[next]=id;
39}
40}
41}
42}
43}
44}
45}
46 counter=new_counter;
47k++;
48}
```  
Listing 1: OpenACC implementation of the BFS application.