Task: pathfinder_grid_dp
Category: Operations research
Difficulty: 2
Tags: wavefront,grid_traversal,dynamic_programming,stencil_like,double_buffering
Source: Rodinia 3.1: https://github.com/HPC-FAIR/rodinia_3.1
Description: Grid shortest-path dynamic program with row-to-row dependencies and per-column last-row costs.

Prompt template (YAML):
# PathFinder Grid Shortest-Path DP -- Prompt Template

task_description: |
  Given a weighted 2D grid `wall[rows][cols]`, compute the minimum path cost to every
  destination column in the last row.

  A path starts in the first row and moves one row downward at a time.
  From column `c`, the next step may go to `c-1`, `c`, or `c+1` (subject to bounds).

  Dynamic-programming recurrence:

    DP[r][c] = wall[r][c] + min(DP[r-1][c-1], DP[r-1][c], DP[r-1][c+1])

  Base case:

    DP[0][c] = wall[0][c]

  Output `out_costs[c] = DP[rows-1][c]` for all columns `c`.

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 rows,
      int cols,
      const int* wall,
      int* out_costs
  );
  ```

input_size_notes: |
  - `wall` stores nonnegative integer costs in row-major order.
  - **small**: rows=2048, cols=512
  - **medium**: rows=8192, cols=1024
  - **large**: rows=32768, cols=2048
  - Output length is always `cols`.

output_contract: |
  - `out_costs[c]` must equal the minimum accumulated path cost ending at last-row column `c`.
  - Output must match the CPU reference exactly (integer values; task uses `atol = 0`).
  - `solution_compute` must be idempotent and synchronized before returning.

algorithm_background: |
  This is a classic row-wise wavefront DP.

  Only the previous row is needed to compute the current row, so memory can be reduced from
  O(rows*cols) to O(cols) using two buffers:

    prev[c] = DP[r-1][c]
    next[c] = DP[r][c]

  For each row r >= 1 and column c:
    best = prev[c]
    if c > 0:        best = min(best, prev[c-1])
    if c + 1 < cols: best = min(best, prev[c+1])
    next[c] = wall[r*cols + c] + best

  Then swap `prev` and `next`.

hints_l2: |
  - Keep `wall` on GPU persistently after `solution_compute` setup phase.
  - Use two device buffers for previous/current row costs.
  - Launch one row-update kernel per row, with one thread per column.
  - Copy only the final row back to host at the end.

hints_l1: |
  ### 1. Persistent device state
  In `solution_compute` setup phase, allocate device memory for `wall`, `prev`, and `next`, and copy `wall` to device once.

  ### 2. Initialization
  Initialize `prev[c] = wall[c]` from the first row.

  ### 3. Row-update kernel
  For each row `r` from 1 to `rows-1`, launch a kernel over columns:
  - load `prev[c]`
  - read `prev[c-1]` and `prev[c+1]` when valid
  - compute the local minimum
  - write `next[c] = wall[r*cols + c] + min_neighbor`

  ### 4. Swap buffers
  After each row, swap `prev` and `next` pointers.

  ### 5. Shared-memory optimization
  For better performance, tile columns into blocks and cache a tile of `prev` in shared memory,
  including one halo element on each side.

  ### 6. Launch-overhead reduction
  Since there is one dependent step per row, reducing launch overhead may matter on large inputs.
  Consider persistent kernels or CUDA Graphs only if correctness remains straightforward.


CPU reference implementation (C):
// Adapted from the Rodinia Pathfinder benchmark core recurrence
// Source repo: https://github.com/yuhc/gpu-rodinia
// Original file: openmp/pathfinder/pathfinder.cpp

#include <stdlib.h>
#include <string.h>

#ifdef __cplusplus
extern "C" {
#endif

static int g_rows = 0;
static int g_cols = 0;
static const int* g_wall = NULL;
static int* g_prev = NULL;
static int* g_next = NULL;

static int i_min(int a, int b) {
    return (a <= b) ? a : b;
}

static void _orbench_old_init(int rows, int cols, const int* wall) {
    g_rows = rows;
    g_cols = cols;
    g_wall = wall;

    if (g_prev) free(g_prev);
    if (g_next) free(g_next);
    g_prev = (int*)malloc((size_t)cols * sizeof(int));
    g_next = (int*)malloc((size_t)cols * sizeof(int));
}

static void _orbench_old_compute(int* out_costs) {
    if (!g_wall || !g_prev || !g_next || g_rows <= 0 || g_cols <= 0 || !out_costs) {
        return;
    }

    memcpy(g_prev, g_wall, (size_t)g_cols * sizeof(int));

    if (g_rows == 1) {
        memcpy(out_costs, g_prev, (size_t)g_cols * sizeof(int));
        return;
    }

    int* src = g_prev;
    int* dst = g_next;

    for (int r = 1; r < g_rows; ++r) {
        const int* row = g_wall + (size_t)r * (size_t)g_cols;
        for (int c = 0; c < g_cols; ++c) {
            int best = src[c];
            if (c > 0) {
                best = i_min(best, src[c - 1]);
            }
            if (c + 1 < g_cols) {
                best = i_min(best, src[c + 1]);
            }
            dst[c] = row[c] + best;
        }
        int* tmp = src;
        src = dst;
        dst = tmp;
    }

    memcpy(out_costs, src, (size_t)g_cols * sizeof(int));
}



#ifdef __cplusplus
}
#endif

// ── Unified compute_only wrapper (auto-migrated) ──
void solution_compute(int rows, int cols, const int* wall, int* out_costs) {
    _orbench_old_init(rows, cols, wall);
    _orbench_old_compute(out_costs);
}