Cost Efficiency¶
In parallel algorithms, cost efficiency means processor count times runtime matches the best relevant sequential work up to a constant factor.
Core Idea¶
In parallel algorithms, cost is \(pT_p\): processors allocated times parallel runtime. A parallel method is cost efficient when this product matches the best relevant sequential time for the same task up to a constant factor. Low runtime alone does not establish this; it may be bought with excessive processors. Constant asymptotic efficiency is the equivalent test.[^ref-07706f711827]
Scope of Application¶
For an ideal blockwise sum of \(n\) values, \(p\) processors do \(\Theta(n/p)\) local additions and combine partial sums in \(\Theta(\log p)\) tree rounds. Thus \(T_p=\Theta(n/p+\log p)\) and cost \(\Theta(n+p\log p)\). Choosing \(p\approx n/\log n\) gives cost \(\Theta(n)\), matching a sequential sum; choosing \(p=n\) gives \(\Theta(n\log n)\) cost. This is an ideal-model derivation, not a network benchmark.[^ref-49f9c9843559]
Clarity¶
Odd–even transposition sorts \(n\) keys on an \(n\)-processor line in \(n\) rounds, so its cost is order \(n^2\). That exceeds the order \(n\log n\) sequential comparison-sort benchmark. It is parallel and has linear latency but is not cost optimal. Do not compare it with a deliberately slow serial bubble sort.[^ref-b9695b4688f8]
Manages Complexity¶
The product \(pT_p\) exposes waste hidden by a time-only claim. It does not include every practical expense: topology, communication, cache behavior, energy and dollar cost need separate analysis. “Cost” here is a formal processor-time measure, not procurement cost.[^ref-49f9c9843559]
Abstract Reasoning¶
If \(T_s=\Theta(n)\), \(p=n\) and \(T_p=\Theta(\log n)\), then efficiency \(T_s/(pT_p)=\Theta(1/\log n)\) falls with scale. Reducing \(p\) can restore constant efficiency only after recalculating how local work and critical path change; it cannot be done by reducing \(p\) in the formula while holding runtime fictitiously fixed.[^ref-49f9c9843559]
Knowledge Transfer¶
The test transfers between parallel algorithms with valid same-problem sequential baselines and declared machine models. The live Ratio prime is the composition/presupposes prerequisite for comparing processor-work with sequential work; the verdict is not itself a quotient. The live Efficiency prime's undominated-frontier criterion is not guaranteed by fixed-factor asymptotic cost optimality. This named entry remains specific to parallel processor-time and does not mean energy- or dollar-efficiency.
[^ref-07706f711827]: Imperial College Parallel Algorithms lecture, p. 50/65. [^ref-49f9c9843559]: MIT Parallel Algorithms Notes #32, work/depth and simulation. [^ref-b9695b4688f8]: Wisconsin mesh-sorting notes, odd–even transposition cost.
Relationships to Other Abstractions¶
Current abstraction Cost Efficiency Domain-specific
Parents (1) — more general patterns this builds on
-
Cost Efficiency presupposes Ratio Prime
Cost efficiency presupposes a work-comparison ratio.
Hierarchy path (1) — routes to 1 parentless root
- Cost Efficiency → Ratio → Comparison → Self Checking
Neighborhood in Abstraction Space¶
Cost Efficiency sits in a sparse region of the domain-specific corpus (66th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Automatic parallelization — 0.86
- Sun–Ni Law — 0.86
- Analysis of algorithms — 0.84
- HBJ model — 0.84
- Program Profiling — 0.83
Computed from structural-signature embeddings · 2026-10-08