04 / 06 · Overlap the work

MVM Costs

A single MVM consists of a load transfer, MVM execution, and a store transfer.

First, one operation without overlap

Each bar is a complete load → MVM → store. Blue and orange are transfers; green is computation. The full height is elapsed time.

$T_{\text{total}} = T_{\text{load}} + T_{\text{MVM}} + T_{\text{store}}$

An N × N array transfers 4N bytes each way. At B bytes/cycle, each transfer takes ⌈4N/B⌉ cycles in this illustration. The execution slider sets one whole-MVM delay, equal across all sizes.

More bandwidth shrinks the transfer segments. It leaves the green segment unchanged.

The total-time curve follows:

$$T(N)=2\left\lceil\frac{4N}{B}\right\rceil+b$$

$$T(N)\approx\frac{8}{B}N+b$$

Here $B$ is transfer bandwidth and $b=T_{\text{MVM}}$ is the execution cost. Transfer time grows linearly with $N$, while execution adds a fixed cost. The second equation ignores whole-cycle rounding. The graph uses a logarithmic size axis to keep smaller arrays readable.

Now overlap successive MVMs

Keep a 256 × 256 matrix programmed. Follow one color across load, compute and store: it represents one input and its result. Only one MVM computes at a time.

The input buffer sets a boundary

There is one input buffer. The next load starts only after compute has captured the current input. That is why load 3 may wait for compute 2, even when the transfer link is free.

This timeline gives input and output separate links, each with bandwidth B, and assumes enough output storage. Blank space is waiting. It is a scheduling illustration, not a measured SST trace; the controls affect this timeline only.

The slowest stage sets the pace

$T_{\text{pace}} = \max\left( T_{\text{load}},T_{\text{MVM}},T_{\text{store}} \right)$

$T_{\text{pipeline}} = T_{\text{total}} + (q - 1)T_{\text{pace}}$

Here q is the task count. The first task fills the pipeline; later tasks finish one pace interval apart. Reported runtime includes the final store. With a shared input/output link, transfers also compete with each other; the next chapter measures that case.

Select “Balanced stages.” At 32 B/cycle and 32 MVM cycles, all three stages take the same time. Five MVMs take 480 cycles serially or 224 with overlap: 2.14× faster. The neighboring examples change the bandwidth or execution delay to expose the slower stage.

Scheduling rules and speedup

Stage	When it can begin
Load input	The previous load has finished and compute has taken that input, freeing the input buffer.
MVM execution	The new input is ready and the previous MVM has finished computing.
Store output	The result is ready and the previous store has finished.

$S = \frac{qT_{\text{total}}}{T_{\text{total}} + (q - 1)T_{\text{pace}}}$

For k equal-duration stages, each taking T_stage, this simplifies to:

$S = \frac{qkT_{\text{stage}}}{(k + q - 1)T_{\text{stage}}} = \frac{qk}{k + q - 1}$

Here k = 3. With many tasks the balanced case approaches 3×; unequal stages give less benefit.

Parameters in the simulation

cost_per_mvm_cycles

Execution time for one analog MVM, $T_{\text{MVM}}$, in cycles. Input and output transfers are separate.