Performance analysis

Speedup is a comparison, not an intrinsic property of a piece of code. Let T1 denote the elapsed time of an appropriate one-worker implementation and Tp the elapsed time of the parallel implementation on p processing resources for the same input and output requirements. The observed speedup is S(p)=T1/Tp. If one worker needs 80 seconds and eight workers need 14 seconds, the measured speedup is about 5.71. This is useful only after specifying what was held constant. If the parallel program uses a less accurate numerical method, skips verification, writes fewer files or measures cached input while the baseline includes disk loading, the ratio does not measure equivalent work. A trustworthy speedup experiment makes correctness and workload comparability explicit before discussing performance.

Wall-clock timing is usually preferable to summing worker CPU times because users care about completion latency. In an MPI job, the program's elapsed time is generally bounded by its slowest participating rank and any startup or teardown work inside the timed interval. In a multithreaded program, a thread may spend time blocked at a barrier without consuming much CPU. Summed CPU time can therefore increase as p increases even while wall-clock time decreases. Record both where possible, but do not confuse resource consumption with elapsed latency. A single stopwatch call around a parallel region may also include runtime initialization and first-use memory allocation; warm-up runs or carefully labeled cold-start measurements reveal whether that overhead matters for the target application.

Speedup curves should be read alongside absolute time. Consider two algorithms for a large graph: algorithm A takes 100 seconds on one worker and 20 seconds on eight; algorithm B takes 30 seconds on one and 12 seconds on eight. A has speedup 5, whereas B has speedup 2.5, yet B is substantially faster on eight workers. Choosing the largest speedup rather than the shortest valid elapsed time is a common reporting mistake. A poorly optimized serial baseline can artificially inflate a parallel speedup figure, and a hand-tuned single-thread baseline can reveal the real value of adding concurrency. Parallelism is not a substitute for algorithmic efficiency.

Distinguish strong scaling from weak scaling. Strong scaling holds the problem size fixed while increasing p; every worker ideally handles less work. Weak scaling increases the total problem size so that work per worker remains roughly constant. For a simulation with n grid cells per worker, a weak-scaling experiment might use n, 2n, 4n and 8n total cells at p equal to 1, 2, 4 and 8. In a perfectly weak-scalable application, time remains nearly constant. Strong scaling often deteriorates first because communication, synchronization and startup become a larger fraction of the shrinking local workload. Neither metric is better universally. Strong scaling matters when a fixed analysis must finish sooner; weak scaling matters when more hardware permits a larger experiment in the same elapsed time.

Some authors report superlinear speedup, where S(p)>p. Such a result is possible without violating physics. Splitting a dataset across workers may allow each partition to fit into faster cache, reducing memory misses enough that total work completes faster than the naive p-fold expectation. Parallel search may terminate early when a worker discovers a result that lets the algorithm prune remaining work. These effects depend on the model of equivalent work and should be described rather than concealed. Superlinear speedup is not evidence that computational laws were suspended; it signals that the single-worker and parallel memory or search behaviors differ.

Design a timing procedure that resists noise. Use a representative workload, validate a numerical checksum or output invariant, record hardware and thread placement, and repeat measurements. Report distributions rather than only the best result. For workloads with highly variable execution time, medians and quantiles may be more informative than the mean. If parallel speedup fluctuates greatly, inspect background processes, power management, NUMA placement, input cache state and scheduler contention. State whether thread pinning is enabled and whether simultaneous multithreading shares physical execution units. A requested worker count is not the same as an equal number of independent cores.

Measurement must also avoid hiding work. A GPU kernel launched from a CPU may be asynchronous: the launch call can return long before execution completes. Timing only the launch call measures enqueue latency, not device execution. A correct end-to-end timing includes an appropriate completion synchronization, whereas device events may measure an isolated kernel. Both perspectives are useful if labeled. Network collectives may overlap with computation, so adding independently measured component times can overstate total elapsed time. A profiler's timeline can show these overlaps more faithfully than a spreadsheet of individual durations.

A practical speedup report includes T1, every Tp, p, problem dimensions, correctness criteria, hardware characteristics, and the measured setup cost. Plot time and speedup together. Interpret unusual points in terms of cache, bandwidth and synchronization instead of smoothing them away. Most importantly, explain what decision the metric supports: whether to buy more cores, repartition a job, change an algorithm, or accept existing performance.

Parallel efficiency describes how productively additional resources contribute to speedup. Under the conventional strong-scaling definition, E(p)=S(p)/p=T1/(p Tp). If the previous eight-worker job has S(8)=5.71, its efficiency is approximately 0.714, or 71.4 percent. This ratio compares observed performance to ideal linear scaling. It does not mean 71.4 percent of the CPU transistors are busy, nor does it uniquely identify where time was wasted. A worker can execute useful instructions at full occupancy while moving so much redundant data that total efficiency remains low. Conversely, a pipeline can retain high user throughput while particular stages have low CPU utilization.

The idea of parallel overhead makes the ratio concrete. A common definition is To=p Tp-T1, the total extra processor-time relative to the baseline. For T1=80 seconds, p=8 and Tp=14 seconds, To=112-80=32 processor-seconds. This overhead may include idle time, communication, synchronization, scheduler management, redundant calculations and differences in algorithm behavior. The definition assumes comparable useful work and is not an additive decomposition into directly measured subcategories. To assign causes, instrument those categories separately. Multiplying elapsed time by processor count also assumes those resources were allocated for the entire measured interval, which may not hold for elastic cloud jobs.

Efficiency typically falls during strong scaling because fixed or slowly shrinking costs occupy a growing portion of runtime. Suppose 12 seconds of work cannot be parallelized while 108 seconds can. On one worker the job takes 120 seconds. With six ideal workers on the parallel portion, the time becomes 12+108/6=30 seconds. Speedup is four and efficiency is 4/6, or two-thirds. Increasing to twelve workers gives 12+9=21 seconds; speedup rises to about 5.71, but efficiency falls to 47.6 percent. Both observations can be true simultaneously. A decision maker who only sees speedup may overbuy hardware; one who only sees efficiency may underestimate the value of faster completion for a time-critical task.

The cost of computing provides another perspective. If an allocation costs c currency units per worker-hour, a run with p workers and elapsed time Tp hours costs approximately cpTp, excluding storage, networking and minimum billing periods. Eight workers completing in one hour cost eight worker-hours. Four workers taking 1.6 hours consume 6.4 worker-hours. The eight-worker configuration finishes sooner but uses 25 percent more billed compute. An urgent weather warning might justify the extra expenditure; a nightly batch with a comfortable deadline might not. Efficiency is therefore related to economic cost, but cloud pricing tiers and reserved hardware complicate simple linear comparisons.

Weak-scaling efficiency is defined differently in many texts. A commonly used ratio compares baseline per-worker time to the time of a scaled workload: Ew(p)=T1(n)/Tp(pn), where n is per-worker problem size. If the baseline with n items takes 10 seconds and p workers on pn items take 13 seconds, weak-scaling efficiency is about 76.9 percent. It is misleading to apply the strong-scaling expression T1(pn)/(p Tp(pn)) without explaining the difference, because the serial time for pn items may itself exhibit nonlinear cache behavior. Report the definition alongside the numbers.

Isoefficiency asks how quickly the problem must grow to retain a chosen efficiency as the processor count increases. In an idealized overhead model, E=W/(W+To(W,p)) where W is useful serial work and To is total parallel overhead. To hold E at a fixed target, W must grow proportionally to To. For a simple tree reduction with logarithmic coordination overhead, increasing p can require the useful workload to rise to offset that coordination. Exact isoefficiency functions depend on the parallel algorithm and communication topology, not on a machine's processor count alone. A small, permanently fixed workload may have no economically sensible path to high efficiency on thousands of devices.

Useful efficiency diagnosis separates balance efficiency from communication and computation efficiency. If worker times to finish their assigned local tasks are 8, 8, 8 and 16 seconds, the average active-computation time is 10 seconds, while the slowest takes 16. A simple balance metric is 10/16=62.5 percent. This does not by itself account for waits, network transfers or overlap, but it points toward a skewed partition. Another metric might use the ratio of useful time to worker occupancy time. Different profilers use different definitions, so compare named formulas rather than superficially similar percentages.

Before recommending more hardware, ask whether the application has a deadline, a spending ceiling, an energy limit, or a throughput service-level goal. The best configuration is often the smallest p that meets the deadline with acceptable reliability. Parallel efficiency remains a valuable diagnostic, but it becomes actionable only when paired with absolute runtime, resource cost and a plausible performance model.

Amdahl's law gives a mathematical upper bound on strong-scaling speedup under a deliberately simplified model. Suppose fraction f of the one-processor runtime is inherently serial and the remainder 1-f is perfectly divisible among p workers with no additional overhead. Then S(p)=1/[f+(1-f)/p]. As p grows without bound, the speedup approaches 1/f when f is positive. For f=0.05, no number of workers can reduce ideal runtime below five percent of its original value, so the asymptotic speedup limit is twenty. This bound follows directly from the serial portion: even infinitely fast parallel work cannot remove the time required by truly serial dependencies.

The strength of the model is its clarity; its weakness is the rigidity of its assumptions. Fraction f is measured relative to one particular input, algorithm and baseline. If a new implementation replaces a serial stage with a parallel algorithm, changes a data structure or moves expensive preprocessing outside the measured region, f can change. The law does not decree that five percent of every program must forever remain serial. It says that a fixed irreducibly serial portion bounds speedup for the specified computation. Communication and scheduling overhead normally make achieved speedup lower than the ideal Amdahl prediction. Cache effects can occasionally create superlinear behavior, showing why the simple denominator is not a full runtime model.

Compute an example carefully. A pipeline spends 30 seconds parsing an input file, 270 seconds in a parallelizable analysis and no other significant time. On one worker it needs 300 seconds, so f=0.1. On ten workers, ideal time is 30+270/10=57 seconds. Speedup is 300/57≈5.263, not ten. On one hundred workers, ideal time is 30+2.7=32.7 seconds, speedup≈9.174. Increasing hardware tenfold from ten to one hundred workers saves only 24.3 seconds. Before ordering more resources, it may be better to reduce the parsing stage or overlap it with processing, if dependencies permit.

An extended model adds overhead explicitly: Tp=Tserial+Tparallel/p+Tcommunication(p)+Tscheduling(p)+Timbalance(p). The extra terms need not be monotone or independent. Increasing p can reduce local arithmetic while creating more messages or barriers. For tiny task sizes, scheduling cost may dominate. For collective communication, startup time can grow with the depth of the communication tree. Load imbalance can worsen if work is uneven or if one shared resource becomes congested. Treat the expression as an accounting guide: it prompts measurements rather than magically predicting behavior from a single parameter.

Amdahl and Gustafson address different questions. Gustafson's scaled-speedup argument considers a workload that grows with processor count while keeping observed parallel runtime roughly constant. If a fixed fraction of a parallel run is serial, the amount of parallelizable work completed can grow with p. This does not contradict Amdahl; it changes the problem-size assumption. Amdahl answers, 'How much faster can I finish this fixed job?' Gustafson asks, 'How much larger a job can I complete with more hardware in a comparable time?' A research team deciding whether to solve a finer grid may care more about the second question, while a production API with fixed-sized requests may care more about the first.

The serial fraction also arises from algorithmic dependency depth. In a DAG with total work W and span S, the maximum ideal parallelism is W/S. A task graph with W=2,000 arbitrary time units and S=100 has inherent parallelism of twenty; no scheduler can gain an unlimited improvement from hundreds of processors. The span bound differs from Amdahl's two-class partition because the dependency chain need not correspond to a single designated serial stage. Reducing span by restructuring dependencies can be more valuable than simply increasing p. Parallel prefix methods are an instructive example: they trade additional total operations for a shorter dependency chain, potentially accelerating large workloads.

A useful reverse calculation estimates the serial fraction implied by measured speedup if the ideal law were exactly applicable. Given p and S, the expression f=[1/S-1/p]/[1-1/p]. For p=8 and S=4, f=(0.25-0.125)/(0.875)≈0.142857. Do not present this inferred f as a direct measurement of code that is structurally serial. It absorbs the real application's communication and other overhead, so it is better described as an effective serial fraction. Comparing the effective fraction across problem sizes can reveal whether coordination dominates small jobs or memory traffic grows for large jobs.

Amdahl's law is most useful early in a design discussion. It demands a believable accounting of serial and parallel work, helps set realistic expectations, and exposes diminishing returns. Its least useful application is to report a single universal maximum speedup without stating workload, baseline or overhead. The engineering response to an Amdahl limit is not necessarily more threads; it may be a better algorithm, batched I/O, pipeline restructuring, asynchronous coordination, or a different performance target.

Parallel algorithms move data as well as execute instructions. On a modern machine, moving a byte between distant memory domains can be more expensive than performing several arithmetic operations on a cached value. Communication therefore belongs inside the algorithm's cost model. For a message of n bytes, the alpha-beta approximation T=alpha+beta n separates fixed startup from variable transfer cost. In a collective operation, the number of communication steps also matters. A tree-shaped reduction on p participants may require roughly ceil(log2 p) dependent stages, each with startup and payload costs, while a naive gather to one root may introduce a bottleneck. Implementations optimize differently for small and large payloads; no single formula describes every collective on every network.

Distinguish latency, bandwidth and injection rate. Latency measures time before data can be observed at its destination. Bandwidth describes sustained transfer rate for sufficiently large payloads. Injection rate limits how quickly a node can introduce data into the network, even if link capacity is high. If an application sends thousands of 64-byte updates to distinct peers, it can saturate message processing long before reaching the network's advertised gigabytes-per-second bandwidth. Combining updates into larger batches may help, provided batching does not introduce unacceptable application latency. An experiment should sweep payload sizes, destinations and concurrency to distinguish these limits.

A three-dimensional stencil illustrates geometry-driven communication. Partition an N-by-N-by-N grid among p workers in roughly cubic subdomains. Local volume is approximately N^3/p and surface area scales roughly as (N/p^(1/3))^2. For a fixed global N, local computational work falls as 1/p but boundary data per worker falls more slowly, approximately as p^(-2/3). Thus the ratio of communication to computation worsens as p grows. Strong scaling eventually reaches a point where border exchange dominates local updates. The precise threshold depends on bandwidth, latency, halo thickness, overlapping communication and machine topology. This scaling argument is more informative than assuming that parallel time is simply serial time divided by p.

Topology changes cost. Two GPUs within one node may communicate through a high-speed interconnect, while GPUs across nodes communicate through the network and host or device adapters. A process may be physically near some peers and far from others. Placing highly communicating subdomains on nearby devices can reduce hops, but mapping decisions have to respect memory capacity and balance. A ring exchange, for example, sends between neighbors; a dense all-to-all transpose places pressure on many paths. A communication graph constructed from expected data transfers can guide process placement more effectively than arbitrary rank numbering.

Overlap between communication and computation is desirable only when independent work exists. In a stencil solver, interior cells do not depend on the newly exchanged halo, so they can potentially be computed while the halo is in flight. Boundary cells must wait. Let C be interior computation time and M communication time. If they execute completely separately, their combined contribution is C+M. If they overlap perfectly, it is max(C,M), saving min(C,M). Real overlap can be incomplete because progression needs CPU time, memory controllers are shared, or the communication library does not make independent progress. Record a timeline; subtracting measured C and M from a total runtime without checking concurrency can yield misleading conclusions.

Communication avoidance often changes algorithms. A blocked matrix multiplication loads tiles into faster memory and performs many arithmetic operations per loaded byte. A stencil code can perform multiple local time steps before communicating again, but wider halos and redundant computations may be required to maintain correctness. A reduction can use hierarchical aggregation to lower network message count. These methods trade compute, memory and implementation complexity against data movement. Choose based on the bottleneck being measured. If the code already saturates arithmetic units with data resident in cache, extra blocking logic may not help.

Communication cost has a correctness dimension as well. A message must have the expected type, count and iteration tag. Receiving a late update into the wrong buffer can silently create a plausible but incorrect numerical field. Buffer lifetime for nonblocking operations is part of the program's synchronization contract. Collective operations require compatible participation and communicator membership. Sending more data than a receiver has allocated must be prevented or handled safely. A performance optimization that reduces synchronization points without establishing the resulting happens-before relationships may speed up a program while making its output nondeterministic or wrong.

A sound communication study records payload distribution, number of messages, collective frequency, time in waits, topology, data packing cost and overlap. Compare the measured profile against a simple alpha-beta hypothesis and investigate deviations. The best parallel design minimizes communication on the critical path, not blindly the total byte count: sometimes transferring extra data early enables the later computation to proceed without a costly wait.