Parallel speedup and critical paths
Predict the largest request-latency reduction available from shortening one recorded GPU interval
Before you begin
Follow a linked prerequisite when you cannot explain it from memory. Background skills without links are stated as abilities rather than hidden terminology.
- Units, work, and rates
- Fractions
A CUDA-event benchmark shows that a new attention kernel runs four times faster than the old attention kernel for a 4,096-token prompt. An end-to-end server log shows that time to first token falls only from 100 milliseconds to 92 milliseconds. The two measurements cover different intervals: the CUDA events surround one GPU program, while the server timestamps include request admission, every model operation, sampling, and response delivery.
A timeline captured with NVIDIA Nsight Systems shows where the optimized attention interval sits among the other work. Matrix projections, normalization, feed-forward layers, CPU scheduling, and network delivery remain unchanged. Some GPU work also overlaps CPU preparation. Only the part of the old attention interval that lies on the request's longest chain of required operations can reduce the final 100-millisecond latency.
Amdahl's law names and calculates that limit. The lesson first measures the fraction of original request time that the change can actually shorten, then predicts end-to-end speedup. A dependency diagram supplies a second model for parallel work: total work sums all operation durations, while the critical path follows the longest ordered chain that must finish before the response can continue.
Derive Amdahl's law from elapsed time
Normalize the original elapsed time to 1. Let p be the fraction affected by the proposed optimization. The unaffected fraction is 1−p. If the affected work becomes s times faster, its new duration is p/s. The new normalized time is therefore (1−p)+p/s, and total speedup is the reciprocal of that time.
The limit becomes clear when s grows without bound. The optimized time term approaches zero, but the unchanged time term remains. If p is 0.08, even removing the targeted GPU interval entirely can produce at most 1/(1−0.08), or about 1.087× speedup. Calculate this limit before investing in an isolated optimization.
Choose the affected fraction correctly
The fraction p refers to original elapsed time that the proposed change can reduce. Do not use the targeted interval's fraction after optimization. Do not include work that occurs concurrently under another operation unless the change will expose or shorten the critical path.
The intervention can also add time. A faster attention kernel may require a layout conversion or an extra dispatch. Add this overhead to the new-time denominator. If the optimization reduces memory enough to permit a larger batch, model that capacity benefit separately because it changes the operating point rather than only the original latency decomposition.
Work, span, and synchronization
A dependency graph contains operations as nodes and ordering constraints as edges. Work is the sum of all node durations under a chosen cost model. Span is the duration of the longest dependent path through the graph. Unlimited processors cannot reduce execution below the span because every operation on that path must wait for its predecessor.
Barriers and collectives add dependencies between workers. If seven workers reach a barrier at 9 milliseconds and one arrives at 13 milliseconds, the next phase begins after 13 milliseconds. Average worker time does not control progress. The last-arrival rule explains why a small tail of slow ranks can create large aggregate idle time.
Strong scaling and weak scaling
Strong scaling keeps the complete problem fixed while adding processors. Ideal strong scaling divides the time by the processor count. Real scaling eventually stops because each worker receives less compute while communication, launch, synchronization, and imbalance do not shrink at the same rate.
Weak scaling increases problem size with processor count and asks whether elapsed time remains approximately constant. Training with more GPUs and a proportionally larger global batch can demonstrate weak-scaling throughput while leaving the time for the original batch unchanged or worse. Report which quantity is fixed so the result answers a defined question.
When a small direct speedup is still useful
Amdahl's law bounds direct elapsed-time improvement under the current decomposition. The law does not say that every small direct gain has low value. A kernel change can reduce peak memory, eliminate a synchronization point, or enable a different parallel schedule. Capacity and scheduling effects change the decomposition and require a new model.
Keep the models separate. First report the direct latency effect for the original workload. Then report the enabled batch, context, or topology change and evaluate it under its own objective. This prevents an architectural benefit from being attributed to an unrelated microbenchmark number.
S = 1 / ((1 − p) + p/s)Raise the local speedup and watch the unaffected fraction become the limit.
Worked example: Calculating the end-to-end effect of a faster attention kernel
An attention kernel is four times faster in isolation. Before the change, the kernel accounts for 30% of end-to-end request latency at the target prompt length and concurrency.
- Normalize original request time to 1. The unaffected fraction is 0.70. The affected fraction becomes 0.30/4 = 0.075. New time is 0.775, so expected speedup is 1/0.775, or about 1.29×.
- Measure integration costs. Suppose a required layout conversion and dispatch add 0.02 in units of original request time. New time becomes 0.70 + 0.075 + 0.02 = 0.795, and expected speedup falls to about 1.26×.
- Inspect overlap. If half of the original attention interval was hidden beneath independent CPU or GPU work, the fraction removable from the critical path was smaller than 0.30. Recalculate p from the dependency timeline rather than from the sum of kernel durations.
- Repeat the decomposition across workload groups. Attention can occupy a larger fraction during long prefill and a smaller fraction during short decode. Weight each group by the declared production distribution before making a fleet-wide claim.
- Model memory capacity separately. If the new kernel removes a large temporary allocation and permits more concurrent sequences, measure throughput and latency at the new operating point. Do not add this benefit to the original latency fraction without a second calculation.
Conclusion: Amdahl's law calculates the maximum direct effect of the kernel change and includes integration costs. Use a separate model when the change also enables a system-architecture change.
Common errors
- Using the fraction measured after the optimization. The parameter p describes original elapsed time affected by the proposed change.
- Adding durations from concurrently executing operations and treating the sum as critical-path time. Overlapped work is not independently removable.
- Ignoring integration overhead because the isolated kernel benchmark did not include it. Layout conversion, dispatch, and synchronization belong in the end-to-end model.
- Describing a larger global batch as strong scaling. When problem size changes with processor count, report weak scaling and time-to-quality separately.
Reference summary
total speedup = 1 / ((1 − p) + p/s)Suppose the attention CUDA kernels occupy 40 milliseconds on the critical path of an original 100-millisecond request. All other required stages occupy 60 milliseconds. A twofold attention improvement reduces the attention interval to 20 milliseconds, so predicted request time becomes 60 + 20 = 80 milliseconds and speedup becomes 100/80 = 1.25×. The calculation explains why a large isolated kernel result can produce a modest request result.
- Strong scaling holds total problem size fixed while increasing the number of processors. Per-processor work falls, so communication and synchronization eventually dominate.
- Weak scaling increases problem size in proportion to the processor count. A weak-scaling experiment asks whether elapsed time stays approximately constant as the system performs more total work.
- The critical path is the longest chain of dependent operations. Additional processors cannot reduce latency below the time required by this chain.
- A barrier makes every participant wait for the last arrival. A small amount of imbalance at each worker can therefore become visible idle time across the complete group.
Knowledge check
A CUDA kernel becomes ten times faster and originally occupied 8 milliseconds of a 100-millisecond critical path. Calculate the predicted request latency and speedup. Which profiler timeline and integration measurements must confirm that all 8 milliseconds were removable?
Show the answer guide
- The optimized interval falls from 8 ms to 8/10 = 0.8 ms, so the predicted request latency is 92 ms of unaffected work plus 0.8 ms, or 92.8 ms.
- The predicted end-to-end speedup is 100/92.8 = approximately 1.078×, even though the isolated kernel is 10× faster.
- A before-and-after dependency timeline must show that the complete original 8 ms interval lay on the request's critical path rather than overlapping independent CPU, transfer, or GPU work.
- The integrated request measurement must use identical entry and exit events and should fall by approximately 7.2 ms if no new wait or bottleneck replaces the removed time.
- The same workload and correctness checks must confirm that the contender did not shorten the request by changing work, output length, or numerical behavior.
Plot an Amdahl speedup curve
Model a 100 ms request containing one 8 ms critical-path stage. Calculate total latency and speedup when that stage is accelerated by 1×, 2×, 5×, 10×, 100×, and infinitely. Repeat after changing the stage to 40 ms, without changing the remaining request work.
Evidence to keep: Keep the two calculation tables, a plot of stage speedup against total speedup, the asymptotic latency for each case, and a written conclusion explaining why critical-path share determines the value of the local optimization.
Amdahl's law and span describe one execution graph. The next section examines many requests competing for a service with finite capacity.
Sources and further reading
The lesson explanations synthesize primary papers and official references. Follow the originals for proofs, exact APIs, architecture details, and version-sensitive behavior.
- Amdahl, Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities↗
- Little, A Proof for the Queuing Formula: L = λW↗
- Roofline: An Insightful Visual Performance Model↗
- NVIDIA Nsight Systems User Guide↗
Official reference for capturing and reading CPU, CUDA API, GPU workload, and communication timelines.
- Nsight Compute Profiling Guide↗
- MLPerf Training Benchmark↗