Vector processing and pipelining performance

Vector processing

Vector processing is the processing of vectors (one-dimensional arrays of data) by a single instruction that operates on all the elements. It avoids the loop overhead of scalar code and uses pipelined functional units. A vector instruction specifies the operation, the base addresses of the operands and the result, and the vector length: C(1:100) = A(1:100) + B(1:100) is one instruction, instead of a loop of 100 iterations with an index increment, test and branch each time. It is used in weather forecasting, seismic analysis, image processing and simulation (for example, Cray supercomputers).

A vector processor has vector registers, pipelined arithmetic units and interleaved memory banks that can supply one element per clock.

How pipelining improves performance

A pipeline of k segments with clock time tp can finish one task per clock after the first one. For n tasks:

• Non-pipelined time = n · tn, where tn = k · tp
• Pipelined time = (k + n - 1) · tp
• Speedup S = n · k · tp / ((k + n - 1) · tp) = n·k / (k + n - 1), which tends to k as n becomes large.

Example: k = 4 segments, tp = 20 ns, n = 100 tasks.

• Non-pipelined: 100 × 4 × 20 = 8000 ns
• Pipelined: (4 + 100 - 1) × 20 = 103 × 20 = 2060 ns
• Speedup = 8000 / 2060 = 3.88 (close to k = 4).
• Throughput rises from 1 task per 80 ns to about 1 per 20 ns.

For six tasks on 4 segments: S = (6 × 4) / (4 + 6 - 1) = 24/9 = 2.67 (see the space-time diagram below).

Segment |  1  2  3  4  5  6  7  8  9
------------------------------------
S1      | T1 T2 T3 T4 T5 T6  .  .  .
S2      |  . T1 T2 T3 T4 T5 T6  .  .
S3      |  .  . T1 T2 T3 T4 T5 T6  .
S4      |  .  .  . T1 T2 T3 T4 T5 T6

Pipelining raises throughput without making a single task faster; hazards (branches, dependencies) reduce the gain.