The Parallelization Problem: Why GPUs Hated RNNs

Modern GPUs are extreme parallel processors. An NVIDIA A100 has 6,912 CUDA cores plus 432 specialized tensor cores; an H100 pushes that further. Their entire architectural personality is "do thousands of multiply-accumulates at the same instant." But a vanilla RNN is fundamentally serial across the sequence axis — and you cannot get blood from that stone.

The reason is dependency, not implementation. To compute h[t] the network needs h[t-1], which needs h[t-2], and so on back to h[0]. No matter how many cores you have, this chain of length n must be walked one step at a time.

Self-attention sidesteps the chain entirely. Every position is computed from the same set of input embeddings, so all n position-wise updates happen in a single matmul. Doubling the sequence length doesn't double wall-clock time — it scales the matmul, which the GPU was built for.

Receipts from the original paper

In the 2017 Transformer paper, the base model trained in 12 hours on 8 P100 GPUs (3.3 × 10¹⁸ FLOPs total) and the big model in 3.5 days. Comparable RNN-based systems (e.g. Google's deep LSTM stacks for translation) needed an order of magnitude more training time for similar quality. The shape of the architecture, not just the FLOP count, decided how well the hardware could be utilized.

Code

Sequential vs parallel — the wall-clock difference·python

# RNN: cannot start step t until step t-1 is done
for t in range(seq_len):
    h[t] = f(h[t-1], x[t])      # sequential dependency

# Self-attention: all positions in one matmul
# Q, K, V are (seq_len, d_k); attention is one matrix product
scores = Q @ K.T / sqrt(d_k)    # (seq_len, seq_len)
weights = softmax(scores)
out = weights @ V                # (seq_len, d_v)
# GPU lays out all seq_len positions across thousands of cores

Quick benchmark sketch (PyTorch)·python

import torch, time
n, d = 1024, 512
x = torch.randn(n, d, device='cuda')

# RNN-style sequential update
h = torch.zeros(d, device='cuda')
W = torch.randn(d, d, device='cuda')
torch.cuda.synchronize(); t0 = time.time()
for t in range(n):
    h = torch.tanh(W @ h + x[t])
torch.cuda.synchronize(); print('RNN-like:', time.time() - t0)

# Single matmul (attention-style)
W2 = torch.randn(d, d, device='cuda')
torch.cuda.synchronize(); t0 = time.time()
out = x @ W2
torch.cuda.synchronize(); print('Matmul:  ', time.time() - t0)
# Even ignoring softmax/divisions, the gap is enormous.

The Parallelization Problem: Why GPUs Hated RNNs

Receipts from the original paper

Code

External links

Exercise

Progress

Comments 0