netcl wiki
concepts

Winograd: Fast $3\times3$ Convolutions on GPUs

Winograd: Fast $3\times3$ Convolutions on GPUs

The Winograd algorithm $F(2 \times 2, 3 \times 3)$ (Lavin & Gray, 2016) accelerates 2D convolutions with $3 \times 3$ filters and stride 1. By transforming input spatial tiles and filter weights into the Winograd domain, it replaces expensive multiplications with cheap elementwise operations, achieving an immediate theoretical arithmetic reduction of $2.25\times$.

[!TIP] Theory & Curriculum Link: For the first-principles derivation of spatial filters, receptive fields, and the comparison with im2col GEMM, see Curriculum: Convolutions & Computer Vision.

1. Quick Example: Automated Kernel Selection

import numpy as np
from netcl.core.device import manager
from netcl.core.tensor import Tensor
import netcl.nn as nn

q = manager.default("auto").queue

# 1. 3x3 Conv2d layer (Winograd candidate: kernel_size=3, stride=1)
conv = nn.Conv2d(q, in_channels=64, out_channels=128, kernel_size=3, padding=1, bias=False)

# 2. Input image batch (Batch=4, Channels=64, Height=32, Width=32)
x = Tensor.from_host(q, np.random.randn(4, 64, 32, 32).astype(np.float32))

# 3. Forward pass (KernelSelector automatically picks Winograd or im2col)
out = conv(x)
print(f"Output Feature Map Shape: {out.shape}")  # (4, 128, 32, 32)

2. Mathematical Formulation: $F(2 \times 2, 3 \times 3)$

A standard direct convolution computes a $2 \times 2$ output tile from a $4 \times 4$ input patch using a $3 \times 3$ filter with:

$$2 \times 2 \times 3 \times 3 = 36 \text{ floating-point multiplications}$$

The Winograd minimal filtering algorithm reduces this to only $4 \times 4 = 16$ multiplications:

$$\frac{36}{16} = 2.25\times \text{ arithmetic reduction}$$

The Tile Transformation Equation

Let $\mathbf{d} \in \mathbb{R}^{4 \times 4}$ be an input tile, $\mathbf{g} \in \mathbb{R}^{3 \times 3}$ be the filter weights, and $\mathbf{Y} \in \mathbb{R}^{2 \times 2}$ be the resulting output tile:

$$\mathbf{Y} = \mathbf{A}^T \left[ (\mathbf{G} \mathbf{g} \mathbf{G}^T) \odot (\mathbf{B}^T \mathbf{d} \mathbf{B}) \right] \mathbf{A}$$

Where $\odot$ denotes the Hadamard elementwise matrix product.

The Transformation Matrices

The transformation matrices $\mathbf{B}^T$, $\mathbf{G}$, and $\mathbf{A}^T$ contain only fixed integer coefficients and powers of 2 ($\pm 1, \pm \frac{1}{2}, 0$). In OpenCL compute kernels, these transformations execute without floating-point multipliers, relying purely on additions and bit-shift operations:

$$\mathbf{B}^T = \begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix}$$

$$\mathbf{G} = \begin{bmatrix} 1 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1 \end{bmatrix}, \quad \mathbf{A}^T = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & -1 & -1 \end{bmatrix}$$

3. Execution Strategy in NetCL

In netcl, the runtime KernelSelector chooses between Winograd and im2col + GEMM based on layer hyperparameters and GPU hardware profiles:

  1. Filter Transformation (Offline): The transformation $\mathbf{U} = \mathbf{G} \mathbf{g} \mathbf{G}^T$ is precomputed once when weights are initialized and cached in constant GPU memory (__constant).
  2. Input Tile Transformation: Each GPU workgroup loads a $4 \times 4$ tile into on-chip local memory (__local) and applies $\mathbf{V} = \mathbf{B}^T \mathbf{d} \mathbf{B}$.
  3. Pointwise Multiplication: Elementwise multiplication $\mathbf{M} = \mathbf{U} \odot \mathbf{V}$ across all channel pairs.
  4. Output Tile Transformation: Inverse transformation $\mathbf{Y} = \mathbf{A}^T \mathbf{M} \mathbf{A}$ writes the final $2 \times 2$ output directly into global VRAM.

Comparison: Winograd vs. im2col

Feature Winograd $F(2 \times 2, 3 \times 3)$ im2col + GEMM
Filter Geometry Specialized for $3 \times 3$ filters Supports arbitrary sizes ($1 \times 1, 5 \times 5, 7 \times 7$)
Stride Restricted to stride 1 Stride 1, 2, 3, etc.
Intermediate Memory Zero temporary VRAM allocation Requires temporary column unrolling buffer
Multiplications 16 per tile 36 per tile
Numerical Stability Sensitive to half-precision rounding Numerically identical to standard convolution

4. Best Practices for Vision Pipelines

  1. Use Stride 1 for Winograd: For downsampling layers with stride=2, netcl automatically falls back to im2col GEMM.
  2. Channel Alignment: Maximum GPU memory bandwidth is achieved when channel counts are multiples of 16 or 32.
  3. FP16 Considerations: Because the transformation matrices contain division by 2, roundoff errors accumulate faster in deep ResNets under FP16. In mixed-precision mode, netcl keeps tile transformations in FP32 registers.