Column-Parallel Linear Layer: Sharded Forward, Backward and Bug Hunt
Problem statement
A linear layer $Y = XW$ (no bias) is too wide for one accelerator, so it is split across $P$ devices by output columns. $X$ has shape $(B, D)$ and is replicated on every device. $W$ has shape $(D, H)$ with $H$ divisible by $P$; device $p$ (0-based) stores the contiguous column block $W_p = W[:, pH/P : (p+1)H/P]$ of shape $(D, H/P)$. During the backward pass each device receives the matching column block $dY_p$ of the upstream gradient $dY = \partial L / \partial Y$.
- Derive what each device computes in the forward pass and for $dX$ and $dW$, with the shape of every local tensor, and name each collective operation that is needed so that afterwards every device holds the full $Y$ (the next layer needs it), the full replicated $dX$, and only its own column shard of $dW$.
- A teammate wrote a single-process numpy simulation of the layer, with the collectives written as plain functions. It contains exactly four bugs. Find them and write a correct version with this contract:
def column_parallel_linear(X: list, W: list, dY: list, P: int) -> list:
# returns, for each device p in order: [Y (B x H), dX (B x D), dW_p (D x H/P)]
...
- Describe how you would debug a real multi-device implementation of this layer when its gradients disagree with a single-device run.
The teammate's simulation:
import numpy as np
def all_gather(chunks, axis):
return np.concatenate(chunks, axis=axis)
def all_reduce(chunks):
return sum(chunks) / len(chunks)
def column_parallel_linear(X, W, dY, P):
X, W, dY = (np.asarray(t, dtype=float) for t in (X, W, dY))
W_shards = np.split(W, P, axis=0)
dY_shards = np.split(dY, P, axis=1)
Y = all_gather([X @ Wp for Wp in W_shards], axis=0)
dX = all_reduce([dYp @ Wp.T for dYp, Wp in zip(dY_shards, W_shards)])
dW_shards = [dYp.T @ X for dYp in dY_shards]
return [[Y.tolist(), dX.tolist(), dWp.tolist()] for dWp in dW_shards]
Constraints
- $1 \le B, D \le 24$, $1 \le P \le 8$, $H = kP$ with $1 \le k \le 3$; entries are floats with $|x| \le 4$.
- Return nested lists of floats; compared with a relative tolerance of $10^{-6}$.
Example 1
X = [[1, 2, 0], [0, 1, -1]]
W = [[1, 0, 2, -1], [0, 1, 1, 0], [3, 1, 0, 1]]
dY = [[1, 0, -1, 2], [0, 1, 1, 1]]
P = 2
device 0: Y = [[1, 2, 4, -1], [-3, 0, 1, -1]], dX = [[-3, -1, 5], [1, 2, 2]], dW_0 = [[1, 0], [2, 1], [0, -1]]
device 1: same Y and dX, dW_1 = [[-1, 2], [-1, 5], [-1, -1]]
Example 2
X = [[1, 2], [3, 4]], W = [[1, -1], [2, 0.5]], dY = [[0.5, 1], [-1, 2]], P = 2
device 0: Y = [[5, 0], [11, -1]], dX = [[-0.5, 1.5], [-3, -1]], dW_0 = [[-2.5], [-3]]
device 1: same Y and dX, dW_1 = [[7], [10]]
With $B = D = H$ the teammate's code does not crash, which is exactly why this case is worth testing.
Show hint
Which dimension is split here, and is that dimension contracted or kept in each of the three matrix products?
Relevant roles: ML Engineer, Deep Learning Engineer and Research Scientist.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium