Parallel and Distributed Convolution

Parallel and Distributed Convolution #

A convolution applies the same small filter at many positions. Each output can be computed independently once its input window is available. If workers split a single image, windows near their boundaries can reach into another worker’s region. A halo supplies the missing pixels.

  • Convolution as broadcast, multiply, and reduce
  • Padding, index mapping, and output size
  • Row partitioning, halo exchange, and crop and merge
  • Communication cost, strong scaling, and strips versus tiles

1. From One Window to a Parallel Kernel ☆ #

Position a filter over a window, multiply corresponding entries and sum the products. Deep-learning libraries commonly call this operation convolution even though the filter is applied without reversal, which is mathematically cross-correlation. For one input channel, square kernel F of width k, padded input Xp, and unit stride:

\[ Y[i,j] = \sum_{u=0}^{k-1}\sum_{v=0}^{k-1}X_p[i+u,j+v]F[u,v] \]

Broadcasting means reusing the same filter across windows. Reduction means summing the products within each window, not combining all output positions. Windows overlap in their reads, but independent output positions can be assigned to different threads. A GPU implementation can tile the input to reuse nearby values instead of materialising every window as a separate array.

For a dense convolution with input and output channel counts Cin and Cout, each output value sums k² × Cin products. Approximate work for Hout × Wout output positions:

\[ \mathrm{MACs}=H_{\mathrm{out}}W_{\mathrm{out}} k^2 C_{\mathrm{in}}C_{\mathrm{out}},\qquad \mathrm{FLOPs}\approx 2\,\mathrm{MACs} \]

The FLOP convention counts a multiply and add separately. It does not include padding, communication, or the other layers of a network.

2. Padding and Coordinates ☆ #

Padding defines what the filter sees at the outer image boundary. For stride 1 and no dilation, the output height equals the input height plus top and bottom padding, minus the filter height, plus one. Width follows the same rule.

\[ H_{\mathrm{out}}=H+p_t+p_b-k+1,\qquad W_{\mathrm{out}}=W+p_l+p_r-k+1 \]

To preserve shape, use total padding k − 1 in each dimension. Here we put the smaller half above and to the left: a 3 × 3 kernel gets one element on each side; a 2 × 2 kernel gets one below and one to the right. Giving the 2 × 2 kernel one on both sides would instead produce an output one position larger in each dimension.

A padded index maps back to the original by subtracting the top and left offsets. If the result falls outside the original image, the value is zero under zero padding. For output row i, the original input rows needed are i − pt through i + pb. This relationship determines how much input each worker must read.

3. Owned Rows, Halos, and Cropping ☆ #

Assign each worker an interval of output rows. For P ≤ H and worker w from 0 to P − 1, a balanced way to split H rows is:

\[ s_w=\left\lfloor\frac{wH}{P}\right\rfloor,\quad e_w=\left\lfloor\frac{(w+1)H}{P}\right\rfloor,\quad [\ell_w,r_w)=[\max(0,s_w-p_t),\min(H,e_w+p_b)) \]

The worker owns the half-open range from sw to ew and reads the wider range from ℓw to rw. For ten rows and three workers, the owned ranges are [0, 3), [3, 6), and [6, 10).

A halo is real input from outside the worker’s owned region. Use zero padding only where the global image ends. Once the local same-size convolution finishes, retain ew − sw output rows from local offset sw − ℓw. Stack the retained rows in global order. Cropping discards extra local output positions computed for the halo; it does not delete any row from the final result.

flowchart TD
    I["Partition output rows"]
    I --> A["Worker 0: extend with halo"]
    I --> B["Worker 1: extend with halo"]
    A --> C["Compute and crop"]
    B --> D["Compute and crop"]
    C --> M["Stack owned rows"]
    D --> M
    style I fill:#E1F5FE
    style A fill:#FFF9C4
    style B fill:#FFF9C4
    style C fill:#EDE7F6
    style D fill:#EDE7F6
    style M fill:#C8E6C9

Worked Example: Two Workers, One Seam #

Take a 4 × 4 image containing 1 to 16 in row order and this filter:

\[ F=\begin{bmatrix}1&0\\0&-1\end{bmatrix} \qquad Y=\begin{bmatrix} -5&-5&-5&4\\ -5&-5&-5&8\\ -5&-5&-5&12\\ 13&14&15&16 \end{bmatrix} \]

An output subtracts the bottom-right pixel of its window from the top-left, using zeros beyond the right or bottom edge. For instance, Y[0,0] = 1 − 6 = −5. At the seam, Y[1,0] = 5 − 10 = −5; replacing row 2 with zeros would give the wrong result, 5.

WorkerOutput rows ownedReal input rows readLocal output kept
00, 10, 1, 2First two rows; discard output for halo row 2
12, 32, 3Both rows; zero padding below is at the true image boundary

The merged matrix above is the reference result. Integer arithmetic yields exact agreement; floating-point implementations can differ slightly if they change reduction order.

4. Communication and Strong Scaling ☆ #

In shared memory, a worker can read its halo from the shared input. In distributed memory, neighbouring workers exchange boundary data. A worker can post transfers, compute interior rows while data travel, then compute the seam once the receives complete. Whether the exchange is hidden depends on network progress and how much independent work is available.

For an interior row strip of width W, Cin input channels, and element size b bytes, the receive volume per layer is:

\[ V_{\mathrm{recv}}=(p_t+p_b) W C_{\mathrm{in}} b \quad\text{bytes} \]

This counts receives only, with full halos; edge workers may need less. For W = 1,024, Cin = 64 and a 3 × 3 kernel with FP16 values, an interior worker receives 262,144 bytes (256 KiB). At an assumed 25 GB/s, that payload takes about 10.5 μs before startup and protocol costs. With H = 1,024, eight equal strips and 64 output channels, each owns 128 output rows, or about 4.83 billion MACs.

Strong scaling fixes the image and increases workers. For a strip implementation that also computes temporary outputs for its halo rows, the extra rows relative to owned rows are approximately:

\[ f_{\mathrm{extra}}\approx\frac{k-1}{H/P} \]

At eight workers, two extra rows over 128 owned rows are 1.56%; at 128 workers, two over eight are 25%. This ratio describes halo rows, not elapsed time. A kernel that computes only owned outputs avoids redundant output arithmetic but still needs the halo inputs.

5. Strips, Tiles, or Whole Images? #

SplitUse it whenMain cost
Whole images across workersThere are enough independent images and each fits locallyTraining may still need gradient synchronisation
Row strips within an imageOne image is large and a simple partition sufficesHalo rows cross the full image width
Two-dimensional tilesStrips are too thin or their halos are too largeMore neighbours, including corner data when needed

For a 1,024 × 1,024 image on 64 workers with a one-pixel halo, a 16 × 1,024 interior strip needs 2,048 halo values per channel. A 128 × 128 interior tile needs 516, including the four corners. Both own 16,384 positions. Tiles reduce payload here, while message count and topology can change the runtime comparison.

Quick Checks #

  • Why not zero-pad at a worker boundary? It replaces real neighbour values and changes seam outputs.
  • Why can more workers make a fixed image slower? The local region shrinks, while halo volume and message startup do not shrink at the same rate.
  • What makes the assembled result correct? Every owned output sees the same input window as the sequential calculation, and every owned row appears once.

Further Reading #


Home | M3: Scale-Out Systems