Task: rodinia_bfs_levels
Category: Graph algorithms
Difficulty: 2
Tags: graph,BFS,frontier,level_synchronous,Rodinia
Source: Rodinia 3.1: https://github.com/HPC-FAIR/rodinia_3.1
Description: Level-synchronous breadth-first search computing graph distance labels from a source vertex.

Prompt template (YAML):
task_description: |
  Run level-synchronous breadth-first search on an unweighted graph stored in Rodinia-style
  node metadata plus a flat edge list.

  Each node `u` has `node_start[u]` and `node_degree[u]`, and its outgoing neighbors are stored in
  `edge_dst[node_start[u] : node_start[u] + node_degree[u]]`.
  Starting from `source`, compute the BFS hop distance to every node.

interface: |
  ```c
  // Single end-to-end call. Do H2D + kernel + D2H and synchronize before returning.
  // Called multiple times (warmup + timed); must be idempotent.
  extern "C" void solution_compute(
      int num_nodes,
      int num_edges,
      int source,
      const int* node_start,
      const int* node_degree,
      const int* edge_dst,
      int* out_dist
  );
  ```

input_size_notes: |
  - `node_start` and `node_degree` are length `num_nodes`.
  - `edge_dst` is length `num_edges`.
  - **small**: 20k nodes, avg degree 6
  - **medium**: 100k nodes, avg degree 8
  - **large**: 250k nodes, avg degree 8

output_contract: |
  - Output one integer BFS distance per node.
  - Unreachable nodes must be `-1`.
  - Output format is one integer per line.
  - Correctness mode is exact.

algorithm_background: |
  This is the classical Rodinia mask-based BFS pattern.
  Maintain three arrays: current frontier, next frontier, and visited.
  Repeatedly scan active frontier nodes, relax their outgoing neighbors, and build the next frontier
  until no new node is discovered.

hints_l2: |
  - Keep graph arrays on device after `solution_compute` setup phase.
  - Parallelize over frontier nodes or over all nodes with a frontier mask.
  - Use a compact frontier queue or bitmap to reduce wasted work.
  - Reduce host-device synchronization inside the BFS loop.

hints_l1: |
  ### 1. Persistent device allocations
  Allocate device copies of `node_start`, `node_degree`, `edge_dst`, frontier arrays, visited arrays,
  and distance output inside `solution_compute`.

  ### 2. Frontier expansion
  The Rodinia version scans all nodes and expands only active ones. A compact frontier queue may be faster.

  ### 3. Neighbor processing
  For each active node `u`, iterate from `node_start[u]` to `node_start[u] + node_degree[u]`.

  ### 4. Next-frontier update
  Mark newly discovered neighbors and assign `dist[v] = dist[u] + 1` exactly once.

  ### 5. Final copy-back
  Copy the distance array to `out_dist` after traversal completes.


CPU reference implementation (C):
#include <stdlib.h>
#include <string.h>

#ifdef __cplusplus
extern "C" {
#endif

static int g_num_nodes = 0;
static int g_num_edges = 0;
static int g_source = 0;
static const int* g_node_start = NULL;
static const int* g_node_degree = NULL;
static const int* g_edge_dst = NULL;

static unsigned char* g_graph_mask = NULL;
static unsigned char* g_updating_graph_mask = NULL;
static unsigned char* g_graph_visited = NULL;
static int* g_cost = NULL;

static void _orbench_old_init(int num_nodes, int num_edges, int source,
                   const int* node_start,
                   const int* node_degree,
                   const int* edge_dst) {
    g_num_nodes = num_nodes;
    g_num_edges = num_edges;
    g_source = source;
    g_node_start = node_start;
    g_node_degree = node_degree;
    g_edge_dst = edge_dst;

    g_graph_mask = (unsigned char*)calloc((size_t)num_nodes, sizeof(unsigned char));
    g_updating_graph_mask = (unsigned char*)calloc((size_t)num_nodes, sizeof(unsigned char));
    g_graph_visited = (unsigned char*)calloc((size_t)num_nodes, sizeof(unsigned char));
    g_cost = (int*)malloc((size_t)num_nodes * sizeof(int));

    for (int i = 0; i < num_nodes; ++i) g_cost[i] = -1;
    if (source >= 0 && source < num_nodes) {
        g_graph_mask[source] = 1;
        g_graph_visited[source] = 1;
        g_cost[source] = 0;
    }
}

static void _orbench_old_compute(int* out_dist) {
    if (!g_graph_mask || !g_updating_graph_mask || !g_graph_visited || !g_cost) return;

    int stop;
    do {
        stop = 0;
        for (int tid = 0; tid < g_num_nodes; ++tid) {
            if (g_graph_mask[tid]) {
                g_graph_mask[tid] = 0;
                int start = g_node_start[tid];
                int deg = g_node_degree[tid];
                for (int i = start; i < start + deg; ++i) {
                    int id = g_edge_dst[i];
                    if (!g_graph_visited[id]) {
                        g_cost[id] = g_cost[tid] + 1;
                        g_updating_graph_mask[id] = 1;
                    }
                }
            }
        }
        for (int tid = 0; tid < g_num_nodes; ++tid) {
            if (g_updating_graph_mask[tid]) {
                g_graph_mask[tid] = 1;
                g_graph_visited[tid] = 1;
                stop = 1;
                g_updating_graph_mask[tid] = 0;
            }
        }
    } while (stop);

    memcpy(out_dist, g_cost, (size_t)g_num_nodes * sizeof(int));
}



#ifdef __cplusplus
}
#endif

// ── Unified compute_only wrapper (auto-migrated) ──
void solution_compute(int num_nodes, int num_edges, int source, const int* node_start, const int* node_degree, const int* edge_dst, int* out_dist) {
    _orbench_old_init(num_nodes, num_edges, source, node_start, node_degree, edge_dst);
    _orbench_old_compute(out_dist);
}