Races in Maximal Independent Set Lonestar application

[AKKamath]

While going through the MIS application, I noticed a few data races which I note below.

Lines 89 and 101

->    if (dst != node && graph.node_data[dst] != NON_INDEPENDENT && prio[dst] >= max_prio)
      {
        if ((prio[dst] > max_prio) || dst > max_prio_node)
        {
          max_prio = prio[dst];
          max_prio_node = dst;
        }
      }
    }
    if (max_prio_node == node)
    {
      assert(graph.node_data[node] == UNMARKED);
->    graph.node_data[node] = MARKED;
    }

Line 101 uses a simple assignment, which can race with the node_data being read in line 89.

Lines 133 and 147

->  if (graph.node_data[dst] == MARKED)
    {
      drop = true;
    }
      ...
   if (graph.node_data[node] == UNMARKED)
   {
->     graph.node_data[node] = NON_INDEPENDENT;
   }

Same as the above case.

[AKKamath]

This definitely seems like a race. Could it cause problems because of caching? For example, the node_data is set by one thread in L1, but other threads outside the threadblock do not see this update.

[nicelhc13]

Hi, when we just check your comment, your point looks right. But note that this is compiler generated codes (https://dl.acm.org/doi/abs/10.1145/2983990.2984015)

I should look into this issue further but more optimizations were applied here.

Have you seen any correctness issue from this code? Could you help me to reproduce the bug?