← All problems
#10 2D Convolution Medium

Write a program that performs a 2D convolution operation on the GPU. Given an input matrix and a kernel (filter), compute the convolved output. The convolution should be performed with a "valid" boundary condition, meaning the kernel is only applied where it fully overlaps with the input.

Input (4x4) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Kernel (2x2) 0 1 1 0 Output[0][0] 7 1×0 + 2×1 + 5×1 + 6×0 = 0 + 2 + 5 + 0 = 7 kernel position output cell

The input consists of:

The output should be written to the output matrix (also a 1D array in row-major order). The output matrix will have dimensions:

The convolution operation is defined as:

\(output[i][j] = \sum_{m=0}^{kernel\_rows-1} \sum_{n=0}^{kernel\_cols-1} input[i+m][j+n] * kernel[m][n]\)

Implementation Requirements

Example 1:

Input:
input (3×3): \[ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \] kernel (2×2): \[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \] input_rows = 3
input_cols = 3
kernel_rows = 2
kernel_cols = 2

Output:
output (2×2): \[ \begin{bmatrix} 6 & 8 \\ 12 & 14 \end{bmatrix} \]

Example 2:

Input:
input (4×4): \[ \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 4 & 5 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix} \] kernel (1×3): \[ \begin{bmatrix} 1 & 0 & 1 \end{bmatrix} \] input_rows = 4
input_cols = 4
kernel_rows = 1
kernel_cols = 3

Output:
output (4×2): \[ \begin{bmatrix} 2 & 2 \\ 4 & 3 \\ 6 & 5 \\ 2 & 2 \end{bmatrix} \]

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.