Sun–Ni Law¶

Estimate scaled parallel speedup when usable memory capacity bounds workload growth, with Amdahl and Gustafson recovered as special choices of an application-specific growth factor.

Version: v3 · 2026-09-06 · History
Domain-specific #: 2896
Origin domain: parallel computing
Subdomain: performance modeling
Aliases: Sun and Ni's law, Sun-Ni's law, Memory-bounded speedup, Memory-bounded speedup model

Core Idea¶

The Sun–Ni law, originally called memory-bounded speedup, is a scaled parallel-performance model in which added processors bring added usable memory and that memory capacity limits how large a problem is selected. Sun and Ni introduced it beside fixed-size and fixed-time speedup: Amdahl asks how much faster a fixed workload runs, Gustafson scales workload to a fixed parallel time, and Sun–Ni scales workload to a memory-capacity bound.^[1]^[2]

For the simplified form, let p >= 1 be the processor or node count. Decompose a baseline workload into non-scaled sequential work W_s and parallelizable work W_p, and define

\[ f=\frac{W_p}{W_s+W_p},\qquad 1-f=\frac{W_s}{W_s+W_p}. \]

Let G(p) be the factor by which the parallelizable work grows when the available memory grows from the one-node baseline to the p-node capacity. Assuming ideal division of the scaled parallel work and omitting communication and other overhead, the one-processor time for the scaled workload is proportional to W_s+G(p)W_p, while the p-processor time is proportional to W_s+G(p)W_p/p. The memory-bounded speedup is therefore

\[ S_{MB}(p)= \frac{(1-f)+fG(p)}{(1-f)+fG(p)/p}. \]

This is a ratio for the same scaled workload in numerator and denominator; it is not the speedup of the original fixed job. In Sun and Ni's notation, the sequential fraction is k=1-f and the workload-growth factor is written bar g(p).^[2]

The exact special cases locate the model:

\[ G(p)=1 \quad\Longrightarrow\quad S_{MB}=\frac{1}{(1-f)+f/p} \]

is Amdahl's fixed-size formula, while

\[ G(p)=p \quad\Longrightarrow\quad S_{MB}=(1-f)+fp \]

is Gustafson's scaled-speedup formula.^[3]^[4] Other choices are application-specific. If work and memory are related by W=g(M), then the ideal global-data case gives

\[ G(p)=\frac{g(pM)}{g(M)}. \]

For g(M)=cM^b, this is G(p)=p^b. Replicated data, uneven allocation, communication, synchronization, and memory-access costs require the more general formulations or separate measured terms; they are not hidden inside the simplified equation. The 2023 retrospective by Sun and Lu explicitly treats “Sun-Ni's law” and “memory-bounded speedup” as interchangeable names and places the model in memory-centric computing history.^[5]

Structural Signature¶

Sig role-phrases:

the baseline workload — work decomposed into non-scaled sequential and scalable parallelizable portions
the resource multiplier — p processors or processor–memory nodes
the one-node memory baseline — usable capacity M available to the baseline workload
the aggregate capacity bound — usable memory available after resources are added
the work–memory relation — W=g(M), linking capacity to admissible problem work
the workload-growth factor — G(p), the scaled parallel work divided by its baseline value
the scaled workload — the larger job selected under the memory bound
the sequential reference time — one processor solving that same scaled workload
the parallel time — p processors solving the scaled workload under declared overhead assumptions
the memory-bounded speedup ratio — sequential reference time divided by parallel time
the endpoint tests — G(p)=1 gives Amdahl and G(p)=p gives Gustafson

The defining recognition test is not “memory affects performance.” It is the coordination of a resource count, a capacity-selected scaled workload, an application-specific work-growth factor, and a same-scaled-job speedup ratio. Without G(p), “memory-bounded” has no operational content; without the sequential reference for the scaled job, the reported ratio is a different metric.

What It Is Not¶

Not Amdahl's law. Amdahl fixes workload size; Sun–Ni permits it to grow with usable memory and recovers Amdahl only when G(p)=1.
Not Gustafson's law. Gustafson fixes scaled parallel time; Sun–Ni selects scaled work by memory capacity and recovers Gustafson only when G(p)=p.
Not strong scaling. Strong scaling measures time reduction for one fixed problem; the Sun–Ni numerator and denominator concern a memory-scaled job.
Not ordinary weak scaling. Weak scaling commonly holds work per processor or elapsed time approximately fixed; Sun–Ni lets the work–memory function determine how total work grows.
Not Big O notation. g(M) may be estimated from algorithmic complexity, but the law computes a finite-resource speedup ratio with serial and parallel fractions.
Not the memory wall. The memory wall concerns a widening processor–memory performance gap; the simplified Sun–Ni bound is capacity, not latency or bandwidth.
Not a cache-miss, bandwidth, or NUMA model. Those mechanisms need explicit access and placement costs.
Not a guarantee of measured performance. Ideal division and omitted overhead make the simplified result a conditional estimate or bound.
Not a claim that more memory alone executes instructions. Capacity licenses a larger problem; processors perform the work.
Not a universal G(p). The growth factor depends on the algorithm, storage layout, replication, memory hierarchy, and what capacity is usable.
Not an empirical law of nature. It is an analytical performance model whose parameters and assumptions must be fitted or justified for a system.
Not the Universal Scalability Law or isoefficiency. Those frameworks model other scaling questions and overhead structures.

Scope of Application¶

Parallel-algorithm scalability analysis. The law compares fixed-size, fixed-time, and memory-bounded interpretations of speedup for an algorithm. Its work–memory relation makes explicit which larger instance becomes feasible as aggregate capacity grows.^[2]

Algorithm–architecture co-design. Two algorithms with similar arithmetic complexity can have different replication, locality, or storage requirements. Their effective G(p) values reveal how much of nominal aggregate memory can support a larger job, providing a capacity-sensitive complement to timing alone.

Dense numerical kernels. Matrix multiplication and related dense matrix operations have polynomial work–storage relations. These make the ideal growth factor derivable and also expose the communication-versus-replication trade-off in more realistic implementations.^[2]

Memory-hierarchy studies. The same capacity-bounded question can be posed at a declared tier—cache, local memory, or main memory—if M, the admissible workload, and data placement are defined at that tier. A cache-capacity model does not automatically predict latency or miss cost.

Memory-centric and data-intensive computing. The model's later influence includes treating data capacity and movement as first-class constraints rather than assuming compute alone selects the problem scale.^[5] Literal use still requires a quantified workload–capacity relation and speedup reference; “data centric” by itself is only context.

Clarity¶

The first clarifying distinction is workload growth versus speedup. G(p) says how the parallelizable work changes under the memory bound. S_MB(p) says how quickly the resulting scaled job is solved relative to one processor. They are not the same number. In particular, G(p)>p can make memory-bounded speedup exceed Gustafson's endpoint while the ideal formula remains no greater than p when the sequential work is nonnegative.

Second, g and G play different roles. Lowercase g relates work to memory, W=g(M). Uppercase G(p)=g(pM)/g(M) is a dimensionless growth factor in the ideal global-data case. Reusing one symbol for both without declaring its type creates unit errors.

Third, the fraction f belongs to the baseline work decomposition used in the simplified derivation. Scaling only the parallel work changes its share in the larger job. Substituting an independently measured fraction from a differently scaled run can invalidate the algebra.

Fourth, “available memory” means memory usable by the algorithm under the specified data layout. Nominal sum-of-node capacity can overstate it when read-only structures are replicated, when each node reserves system space, or when the decomposition cannot use all memory. The general factor G(p) can represent that loss; the ideal expression g(pM)/g(M) cannot simply be assumed.

Manages Complexity¶

Parallel scaling mixes at least four changes: processor count, memory capacity, problem size, and runtime. Fixed-size and fixed-time models each freeze one of those dimensions. Sun–Ni provides a third controlled comparison: let memory capacity select the enlarged problem, then compute the speedup for that same enlarged problem. This prevents a capacity-limited scientific workload from being judged solely by a fixed-job curve that no longer represents how the machine will be used.

The work–memory function compresses detailed input geometry into a growth factor. For square dense matrices, storage is quadratic in dimension and work is cubic, so increasing capacity by p suggests G(p)=p^(3/2) before replication and communication are considered. A design space that otherwise requires enumerating every feasible matrix dimension becomes a comparison of f, p, and G(p).

The compression also isolates the missing costs. If prediction and measurement diverge, the analyst can ask whether the baseline decomposition was wrong, usable capacity was overstated, data were replicated, work divided unevenly, or communication and access overhead were omitted. The law becomes a diagnostic baseline rather than an excuse to fold every performance effect into one unexplained efficiency number.

Abstract Reasoning¶

Use this protocol:

Define the baseline problem and decompose its work into W_s and W_p.
Specify what one “processor” or node includes, especially its usable memory M.
Derive or measure the application relation W=g(M) for the selected problem family and storage layout.
Determine whether aggregate usable capacity is pM; if replication or reservation prevents this, derive G(p) directly.
State whether only parallelizable work scales and whether W_s remains fixed.
Compute the ideal simplified ratio, then add communication, imbalance, access, or synchronization costs separately if the decision needs them.
Run both endpoint checks: G=1 must reproduce Amdahl and G=p Gustafson.
Compare prediction with measured scaled-work performance without relabeling it fixed-work speedup.

The model licenses useful deductions. Increasing G(p) at fixed p and 0<f<1 raises S_MB toward p, because more of the scaled job lies in the parallel portion. If f=0, no workload-growth choice produces speedup; if f=1, the ideal ratio is exactly p for every positive G. Replication that reduces effective G moves the result toward the Amdahl endpoint. A calculated speedup above p under these simplified nonnegative-work assumptions signals an algebra or measurement mismatch, or an effect outside the model such as a different memory hierarchy in the reference run.

Knowledge Transfer¶

Literal transfer occurs across parallel numerical kernels, memory-capacity planning, cache-tier analysis, and data-intensive architecture studies when the same roles remain: resources add usable capacity, capacity selects a scaled workload through g, the workload is decomposed, and speedup compares one versus p processors on that scaled job. The specific G(p) changes; the model grammar does not.

Transfer from a global-data algorithm to one with replication is a qualified variant, not a rename. The aggregate memory may still grow as pM, while the capacity available to unique problem data grows more slowly. Recomputing G(p) preserves the model; assuming the global-data value does not.

Outside parallel computing, “growth under a resource constraint” transfers as Scalability and Constraint. The exact Sun–Ni identity does not transfer to an organization, ecosystem, or budget merely because capacity limits growth. Those analogies lack the processor count, sequential/parallel decomposition, work–memory function, and scaled-job speedup reference.

Examples¶

Canonical example: locating the three scaling assumptions¶

Take p=8 and baseline parallel fraction f=0.75.

For fixed size, G(8)=1:

\[ S_{MB}=\frac{1}{0.25+0.75/8}=2.9091. \]

For an intermediate memory-grown workload, let G(8)=4:

\[ S_{MB}=\frac{0.25+0.75(4)}{0.25+0.75(4)/8} =\frac{3.25}{0.625}=5.2. \]

For Gustafson's endpoint, G(8)=8:

\[ S_{MB}=0.25+0.75(8)=6.25. \]

The values describe different problem-growth assumptions. They are not three timings of one fixed workload.

Mapped back: the baseline workload has sequential fraction 0.25 and parallel fraction 0.75; eight processor–memory nodes supply the resource multiplier; a declared capacity relation supplies each G(8); that factor selects the scaled workload; the numerator is its one-processor reference time; the denominator is its ideal eight-processor time; their ratio is the memory-bounded speedup; and G=1 and G=8 verify the Amdahl and Gustafson endpoints.

Applied example: dense square matrix multiplication¶

For classical multiplication of dense n by n matrices, storage grows as n^2 and arithmetic work as n^3. Ignoring constants and assuming aggregate memory can hold unique global data, W therefore grows as M^(3/2). With p=16,

\[ G(16)=16^{3/2}=64. \]

If f=0.9, then

\[ S_{MB}(16)= \frac{0.1+0.9(64)}{0.1+0.9(64)/16} =\frac{57.7}{3.7}=15.5946. \]

For the same p and f, Amdahl's G=1 endpoint gives 6.4, and Gustafson's G=16 endpoint gives 14.5. The capacity-selected matrix problem has more reusable arithmetic per stored datum, so the ideal memory-bounded estimate lies above the fixed-time endpoint but below the 16-processor ideal. Real distributed algorithms may replicate matrix panels and communicate them; those costs reduce effective growth or add runtime and must be modeled rather than credited to the law.^[2]

Mapped back: matrix dimension defines the problem family; one node's matrix storage supplies M; sixteen nodes supply the nominal aggregate capacity; W proportional M^(3/2) is the work–memory relation; G=64 is the ideal workload-growth factor; f=0.9 supplies the baseline decomposition; the larger matrix product is the scaled workload; and the one-versus-sixteen-processor times for that same job form the reported 15.5946 ratio, subject to the declared no-replication/no-overhead assumptions.

Structural Tensions¶

Fixed work versus useful scaled work. A fixed-job speedup is easy to compare, while a larger feasible problem may better represent the value of a larger machine. Diagnostic: state whether numerator and denominator solve the original job or the memory-selected scaled job.
Nominal capacity versus usable capacity. Summed memory looks like pM, but replication, reservation, and layout can leave less for unique data. Diagnostic: derive G(p) from the actual placement rather than chassis specifications.
Compact growth factor versus mechanism detail. G(p) makes models comparable, but can hide why capacity converts to work. Diagnostic: keep g(M), storage complexity, and replication assumptions alongside the ratio.
Ideal arithmetic versus observed runtime. The simplified equation exposes the serial fraction cleanly, but omits communication, imbalance, and access latency. Diagnostic: treat the result as a baseline and itemize residual costs before comparing with measurements.
More work versus more speedup. A high G means a larger job is admitted, not that memory itself accelerates each operation. Diagnostic: keep the workload-growth factor separate from the speedup ratio.
Endpoint unification versus false interpolation. Amdahl and Gustafson are exact special cases, but an application may have G(p)>p or an irregular non-power relation rather than lie numerically between them. Diagnostic: compute G from the application instead of choosing it to fit a desired law.
Cross-layer reuse versus cross-layer equivocation. Capacity-bounded reasoning can be applied at cache or main memory, but M and the admissible dataset change by layer. Diagnostic: name the memory tier and its usable capacity before transferring parameters.
Model autonomy versus reduction to parents. Sun–Ni is a named law with a distinctive formula and endpoint tests, while its portable skeleton is simply scalability under constraint. Diagnostic: retain the named node when G(p) and scaled-job speedup do inferential work; route generic growth under limits to Scalability and Constraint.

Structural–Framed Character¶

Spectrum placement: Sun–Ni Law is a structural-leaning domain-specific abstraction. Its formula is formal; its variables and admissible measurements remain bounded to parallel-performance practice.

Vocabulary travels — limited. Processor count, parallelizable fraction, usable memory, workload growth, and speedup retain technical meanings inside parallel-performance analysis and cannot be freely substituted elsewhere.
Evaluative weight — low. Selecting which larger workload is useful is a design judgment, but the ratio is conditional mathematics once the workload and assumptions are declared.
Institutional origin — low. Benchmark and reporting conventions affect measurement practice, not whether the formula follows from its assumptions.
Human-practice-bound — moderate. Experts must identify usable capacity, the work decomposition, and G(p) for a particular algorithm and architecture, although the resulting calculation is formal.
Import versus recognize — recognition within its domain. Across parallel systems with the same capacity-selected workload grammar, use is literal; outside that substrate, resource-growth comparisons belong to broader abstractions rather than to Sun–Ni by name.

The portable skeleton is Scalability plus Constraint: added resources alter the feasible workload through a binding capacity, and outcomes are compared under that declared growth rule. Those parents travel beyond parallel computing; the Sun–Ni formula and G(p) obligations remain domain-bound.

Its character: a formal capacity-bounded scaling model whose inputs are empirically instantiated by a particular parallel algorithm and memory architecture.

Structural Core vs. Domain Accent¶

What is skeletal: add resources, let a binding capacity determine how much work can be admitted, compare outcomes at the old and new resource levels, and make the constraint–growth relation explicit.

What is domain-bound: processors or nodes, sequential and parallel work, one-node versus aggregate memory, W=g(M), the factor G(p), a same-scaled-job runtime ratio, and the exact Amdahl/Gustafson special cases.

Why not prime: stripping the computing terms yields Scalability under a Constraint, both already cataloged. Keeping enough structure to recognize Sun–Ni requires a parallel workload decomposition and memory-bounded speedup formula that do not travel literally to unrelated substrates. The candidate therefore fails the prime portability bar while remaining more than a routine composition: its parents do not entail G(p), the reference workload, or the endpoint identities.

Scalability — strict subsumption. Sun–Ni is a specialized parallel-computing scalability model relating added resources, problem-size growth, and speedup. This is a proposed live-DAG parent.
Constraint — strict presupposition. Memory capacity is the constitutive bound used to select the scaled workload. This is a proposed live-DAG parent.
Big O Notation — related, no direct edge. Complexity estimates can help derive g(M), but asymptotic notation does not supply the finite-resource speedup model.
Bottleneck — related, no direct edge. Memory may be a performance bottleneck, but the capacity-bound model is defined without asserting that latency or bandwidth dominates measured runtime.
Concurrency — related, no direct edge. Parallel work executes concurrently, but that broad fact does not locate the distinctive scaling model.
Ratio — related, no direct edge. Speedup is a ratio internal to the law, too generic to add a minimal parent.

Relationships to Other Abstractions¶

Current abstraction Sun–Ni Law Domain-specific

Parents (2) — more general patterns this builds on

Sun–Ni Law is a kind of Scalability Prime

Scalability — strict subsumption. Sun–Ni is a specialized parallel-computing scalability model relating added resources, problem-size growth, and speedup.
Sun–Ni Law presupposes Constraint Prime

Constraint — strict presupposition. Memory capacity is the constitutive bound used to select the scaled workload.

Hierarchy paths (2) — routes to 2 parentless roots

Sun–Ni Law → Scalability → Scale

Show alternative path (1)

Neighborhood in Abstraction Space¶

Sun–Ni Law sits in a sparse region of the domain-specific corpus (84^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Amdahl's law. Amdahl holds workload fixed. Tell: set G(p)=1; if problem size cannot grow, the Sun–Ni formula collapses to Amdahl.
Gustafson's law. Gustafson uses fixed-time scaled speedup. Tell: set G(p)=p; otherwise capacity, not time, selected a different growth factor.
Strong scaling. Strong scaling times one unchanged job as processors increase. Tell: check whether the numerator references the original or enlarged workload.
Weak scaling. Weak scaling usually holds work per processor constant. Tell: Sun–Ni instead derives total growth from usable memory through g or G.
Memory wall. The memory wall is the processor–memory speed disparity. Tell: latency or bandwidth gaps do not appear in the simplified capacity formula.
Memory hierarchy. A hierarchy organizes storage tiers by capacity and access properties. Tell: it supplies a possible substrate, not the scaled-speedup ratio.
Big O Notation. Big O classifies asymptotic function growth. Tell: it has no serial fraction, processor count, or same-job timing numerator.
Isoefficiency. Isoefficiency asks how problem size must grow to maintain a chosen parallel efficiency as processors increase. Tell: its held quantity is efficiency, not memory capacity.
Universal Scalability Law. That model adds contention and coherency penalties to a throughput curve. Tell: its parameters model coordination costs rather than a work–memory relation.
Memory-bandwidth roofline reasoning. Roofline-style models bound attained performance by arithmetic intensity and bandwidth. Tell: their bound is operations per time, not problem size admitted by capacity.
Speedup as a generic metric. Generic speedup is a reference-time ratio. Tell: Sun–Ni fixes which scaled workload the two times must share and how that workload is capacity-selected.
Superlinear speedup. Superlinear measurements can arise from cache or search effects. Tell: the simplified nonnegative-work Sun–Ni equation is at most p; an above-p observation invokes effects outside it.
Koomey's law. Koomey describes a historical trend in computations per unit energy. Tell: it is empirical time-series scaling, not a conditional parallel workload model.
Moore's law. Moore describes semiconductor component-density trends. Tell: it supplies neither a workload decomposition nor a speedup ratio.

References¶

[1] Xian-He Sun and Lionel M. Ni, “Another View on Parallel Speedup,” Proceedings of Supercomputing '90, 324–333 (1990), DOI 10.1109/SUPERC.1990.130037, HKUST record. registry ↩

[2] Xian-He Sun and Lionel M. Ni, “Scalable Problems and Memory-Bounded Speedup,” Journal of Parallel and Distributed Computing 19(1), 27–37 (1993), DOI 10.1006/jpdc.1993.1087, author-hosted PDF. registry ↩a ↩b ↩c ↩d ↩e

[3] Gene M. Amdahl, “Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities,” AFIPS Spring Joint Computer Conference, 483–485 (1967), DOI 10.1145/1465482.1465560. registry ↩

[4] John L. Gustafson, “Reevaluating Amdahl's Law,” Communications of the ACM 31(5), 532–533 (1988), DOI 10.1145/42411.42415. registry ↩

[5] Xian-He Sun and Xiaoyang Lu, “The Memory-Bounded Speedup Model and Its Impacts in Computing,” Journal of Computer Science and Technology 38(1), 64–79 (2023), DOI 10.1007/s11390-022-2911-1. registry ↩a ↩b