Parallel speedup has a serial denominator

Prerequisites: Loops, dependencies, and basic fractions.

Learning objectives

• Apply Amdahl’s law with clearly defined fractions.
• Distinguish SIMD execution from independent threads.
• Identify bandwidth and reduction limits in a concrete loop.

Find work that can proceed together

SIMD, single instruction multiple data, applies one operation to several data elements in parallel lanes. Adding two arrays is a favorable example when each output element depends only on corresponding input elements. Four lanes can compute four additions per vector instruction, subject to alignment, instruction support, and memory delivery. Four lanes do not guarantee a fourfold reduction in program runtime.

A loop that updates a running value from its previous iteration contains a loop-carried dependency. A reduction such as summing an array can sometimes be reorganized into several partial sums, then combined. For exact integer arithmetic with an appropriate overflow contract, the regrouping may preserve results. Floating-point regrouping can change rounding and therefore requires an explicit numerical policy.

Separate the scalable portion

Amdahl’s law describes fixed-workload speedup when a fraction s of original execution time remains serial and the rest speeds up by a factor p. Normalizing original time to one gives new time s+(1−s)/p, so speedup is its reciprocal. If s=0.20 and p=8, new time is 0.20+0.80/8=0.30 and speedup is about 3.33. Even infinite acceleration of the parallel part cannot exceed fivefold speedup under this model.

The fraction must describe time in the original measured workload, not a fraction of source-code lines. Synchronization, partitioning, and communication may add costs absent from the formula. Increasing the input size can change the serial fraction, so fixed-workload and scaled-workload claims answer different questions.

Memory can become the shared bottleneck

Consider adding arrays of eight-byte numbers: read one element from A, read one from B, and write one result. A simple traffic model counts 24 bytes per element, ignoring allocation and writeback details. At a sustained memory bandwidth of 48 GB/s, that traffic limits the loop to about two billion elements per second. Adding arithmetic lanes cannot exceed this bandwidth bound without changing traffic or locality.

This arithmetic intensity is one addition per 24 bytes under the stated model. A more compute-heavy kernel can benefit differently from the same hardware. Write allocation, cache reuse, compression, and overlapping transfers can change actual traffic, so measure the implementation.

Parallel design starts with a dependency graph and a resource budget. Determine which operations can run simultaneously, how data reaches them, what synchronization preserves correctness, and which remaining resource becomes saturated. A core count or vector width is an input to that analysis, not the conclusion.

Primary reading

• Parallel Processing (MIT OpenCourseWare, Computation Structures).

Practice problem

A program spends 30% of its original runtime in work that cannot be accelerated. The remaining 70% achieves a measured fourfold speedup. Compute total speedup. Then add a synchronization overhead equal to 5% of original runtime and recompute. Explain why the overhead should not be multiplied by four.

Worked solution

Without new overhead, normalized runtime is 0.30+0.70/4=0.475. Total speedup is 1/0.475, approximately 2.105. Adding synchronization equal to 0.05 of original runtime gives 0.525 and speedup approximately 1.905. The overhead was already specified as a measured time contribution in the new execution relative to the original baseline. It is not part of the original parallel fraction, and no statement says that the accelerated computation also accelerates synchronization. Multiplying or dividing it by four would silently change the assumptions. A useful follow-up experiment would vary worker count while measuring computation and synchronization separately, since overhead often grows as workers contend or exchange more data.

Check your understanding

A program is 25% serial under a fixed-workload model. What is its infinite-worker speedup limit?

• 2
• 4
• 25
• Unlimited

Explanation

The serial quarter remains even if all other work takes zero time: 1/0.25=4.

Why might wider SIMD fail to speed up array addition?

• SIMD cannot perform addition.
• Memory bandwidth may already limit delivery of the required bytes.
• Independent elements require a serial dependency.
• Vector lanes always reduce cache capacity to zero.

Explanation

Extra arithmetic throughput does not remove a saturated data-transfer bottleneck.

Primary reading

• Parallel Processing: MIT OpenCourseWare, Computation Structures

Open the study and save your work →