Races in Connected Components Lonestar application

[AKKamath]

While going through the cc.cu file of Lonestar, I noticed a few races, which I note below.

Line 257

     index_type x = edge_src[edge];
     index_type y = graph.getAbsDestination(edge);
     index_type mx = x > y ? x : y;
     index_type mn = x > y ? y : x;
->  graph.node_data[mx] = mn;

Explanation: Multiple edges can have the same value for mx. Assigning mn to that node will then create a race. This can be avoided by using a CAS operation on graph.node_data[mx] which checks if the data is unset, and only sets to mn in that case.

Line 343 and 346

    node_data_type p_u = graph.node_data[node];
-> node_data_type p_v = graph.node_data[p_u];
    if (p_u != p_v)
    {
->    graph.node_data[node] = p_v;
      ret_val.reduce(true);
      continue;
      continue;
    }

One thread may be reading graph.node_data[p_u] while another node is assigning graph.node_data[node] = p_v leading to a race. Since the assignment is through a normal store operation, it may also end up getting cached, and not visible to the thread reading the node_data.

Lines 311, 312, 321

    index_type u = edge_src[edge];
    index_type v = graph.getAbsDestination(edge);
-> node_data_type p_u = graph.node_data[u];
-> node_data_type p_v = graph.node_data[v];
    index_type mx = p_u > p_v ? p_u : p_v;
    index_type mn = p_u > p_v ? p_v : p_u;
    if (mx == mn)
    {
        marks[edge] = 1;
    }
    else
    {
->    graph.node_data[mx] = mn;
        ret_val.reduce(true);
        continue;
        continue;
      }

Similar to the first case.

[roshandathathri]

Thanks for the suggestions. Please feel to create PRs to address these issues if you're interested.