Cost Efficiency¶

In parallel algorithms, cost efficiency means processor count times runtime matches the best relevant sequential work up to a constant factor.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13100
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Parallel Algorithms → Computer Science & Software Engineering
Aliases: Parallel Cost Optimality

Core Idea¶

In parallel-algorithm analysis, cost is conventionally \(C_p=pT_p\): \(p\) processors allocated for parallel running time \(T_p\). A parallel algorithm is cost efficient or cost optimal when that product grows asymptotically no faster than the best relevant sequential running time \(T_s\) for the same problem under a declared model. Since the parallel computation must perform enough work to solve the problem, the desired relation is \(pT_p=\Theta(T_s)\), not merely a small \(T_p\). Imperial College course notes state both \(C_p=pT_p\) and the equivalent constant-efficiency condition; CMU's work model makes the same processor-time comparison.^[1]^[2]

This criterion catches a deceptive kind of “speed.” Odd–even transposition sorting can use \(n\) line processors to sort \(n\) keys in \(n\) rounds, but its cost is order \(n^2\), while comparison sorting sequentially takes order \(n\log n\). Parallel time improved against some serial procedures, yet much processor-time was spent. By contrast, assigning each processor a block of an \(n\)-item sum and then reducing the partial sums can keep cost order \(n\) for an appropriate processor count in an ideal unit-cost model.^[3]^[4]

Structural Signature¶

Sig role-phrases:

Fixed computational problem: the parallel and sequential procedures must produce the same required result on the same input family. A weaker approximation cannot win an exact-work comparison without an explicit change of task.
Processor allocation \(p\): the count is charged even when some processors are idle; otherwise excess hardware disappears from the analysis.
Parallel latency \(T_p\): elapsed steps measured under the declared machine model, including communication when that model charges it.
Processor-time cost \(pT_p\): resource expenditure that can rise while latency falls.
Sequential comparator \(T_s\): best relevant one-processor time, or a proven sequential lower bound where available. A deliberately poor baseline can manufacture an apparent cost-optimal result.
Model boundary: PRAM-style unit operations, communication topology and scheduling assumptions determine what \(T_p\) means and what conclusion may transfer to hardware.^[1]^[4]^[3]

What It Is Not¶

Not lowest runtime alone. Spending \(n^2\) processors to get logarithmic latency may fail when sequential work is near linear.
Not speedup alone. Speedup depends on the chosen serial baseline; efficiency divides that speedup by processor count.
Not a bill in dollars. “Cost” here is a formal processor-time product, not machine rental, energy, memory traffic or total ownership expense.
Not proof of deployability. A cost-optimal theorem in an ideal shared-memory model may be bottlenecked by a real interconnect or synchronization cost not represented there.^[4]^[3]

Scope of Application¶

The criterion applies when algorithms for one problem are compared at a specified input size and processor scaling. Let \(E_p=T_s/(pT_p)\) be efficiency. If \(pT_p=\Theta(T_s)\), then \(E_p=\Theta(1)\): efficiency need not be one, but it stays bounded away from zero as input scales in the analyzed regime. The word “best” matters. If a sequential sum takes order \(n\), comparing a parallel sum only with an intentionally quadratic serial sum would be invalid. Similarly, for comparison sorting the relevant baseline is order \(n\log n\), not bubble sort's \(n^2\).^[1]^[2]

For a blockwise sum, assume ideal processors each add about \(n/p\) numbers locally, then a binary tree combines the \(p\) partial sums in \(O(\log p)\) rounds. This yields \(T_p=\Theta(n/p+\log p)\) and cost \(\Theta(n+p\log p)\). Choosing \(p=O(n/\log n)\) makes cost \(\Theta(n)\); near \(p=n/\log n\), runtime is \(\Theta(\log n)\). The result is a derived ideal-model schedule, not a hardware benchmark. Input movement, cache and network behavior can change actual timing.^[4]

The sorting example shows the other side. Wisconsin's course analysis gives \(n\) steps for \(n\) keys on a one-dimensional \(n\)-processor mesh and order \(n^2\) cost. The mesh topology also explains why reducing processors is not automatically a free fix: the parallel time may remain at least order \(n\) because information must traverse the line. A processor-count reduction is useful only after recalculating \(T_p\), not by algebraically reducing \(p\) while pretending \(T_p\) is unchanged.^[3]

Clarity¶

“Work” and “cost” are related but not always interchangeable. In an ideal model where all \(p\) processors are charged for the full \(T_p\), cost is \(pT_p\). A work–span analysis may count actual operations separately and schedule them on \(p\) processors. If many processors wait, operation count can be small while charged cost is large. A careful claim names which model and quantity it uses.^[4]^[2]

Asymptotic optimality also does not mean smallest measured runtime on a finite machine. Two implementations may both have cost \(\Theta(n)\), but constants, memory layout or communication can make one much slower at practical \(n\). The criterion is a scaling screen, not a benchmark replacement. Conversely, a nonoptimal algorithm can be worth using when latency is critical and hardware is available; the term diagnoses total work, not the user's complete objective.

Manages Complexity¶

Parallel performance presents at least two quantities, speed and resource count. Multiplying them creates a single test of whether time was bought by disproportionate processor commitment. A short latency no longer hides an army of idle or underused processors. Comparing that product with a sequential frontier lets the analyst distinguish genuine parallelization from merely distributing avoidable work.^[1]^[2]

The simplification intentionally discards memory, energy, dollar cost and sometimes communication detail. Those may dominate a real design. Cost efficiency should therefore be paired with the machine model and a deployment metric when making procurement or systems claims. It answers “is processor-time asymptotically economical in this model?” and does not answer “is this the cheapest cluster run?”

Abstract Reasoning¶

Suppose \(T_s=\Theta(n)\) and a candidate has \(T_p=\Theta(\log n)\) on \(p=n\) processors. Its cost is \(\Theta(n\log n)\), so \(E_p=\Theta(1/\log n)\): the efficiency shrinks as \(n\) grows. The block-reduction schedule keeps the same asymptotic \(\log n\) latency while reducing processors to about \(n/\log n\), yielding \(pT_p=\Theta(n)\) under the stated ideal model. The saving comes from having each processor perform \(\Theta(\log n)\) local additions before the tree combine; it is not a free disappearance of arithmetic.^[4]

For odd–even sorting, \(p=n\), \(T_p=\Theta(n)\), so \(C_p=\Theta(n^2)\). Relative to \(T_s=\Theta(n\log n)\) comparison sorting, the ratio \(C_p/T_s=\Theta(n/\log n)\) diverges. This is a mathematically specific failure even though the parallel runtime is linear. Change the machine topology or sorting algorithm and both the runtime and verdict must be recalculated.^[3]^[2]

Knowledge Transfer¶

The criterion transfers literally among parallel reductions, sorting, graph algorithms and other computations when a valid sequential benchmark and machine model are fixed. It helps assess scalability without depending on the problem's subject matter. What does not travel automatically is the same processor count or communication assumption: an \(O(n)\)-cost reduction on an ideal shared-memory machine may need a different schedule on a network.^[4]

The live Ratio prime supplies the ordered quantitative comparison needed to assess processor-work against sequential computational work. It is a prerequisite, not the verdict itself. The live Efficiency prime instead requires undominated feasible resource use; fixed-factor asymptotic work optimality need not meet that stronger frontier criterion. Calling an electricity-efficient data center “cost efficient” in the present sense would change the denominator and resource dimensions, so that is lexical similarity rather than literal transfer.

Examples¶

Blocked parallel sum¶

Divide \(n\) values among \(p\) processors. Each creates one partial sum in \(\Theta(n/p)\) local steps; a bounded-fan-in tree adds the \(p\) partial sums in \(\Theta(\log p)\) rounds. Thus \(T_p=\Theta(n/p+\log p)\) and \(pT_p=\Theta(n+p\log p)\). Set \(p\approx n/\log n\): local work and tree depth are both order \(\log n\), cost order \(n\), matching sequential addition. If \(p=n\), local work shrinks to constant but the tree still takes \(\log n\), and charged cost rises to \(n\log n\).^[4]

Mapped back: the fixed task is exact summation; \(p\) is allocated processors; \(T_p\) includes local blocks and tree depth; the product is compared with \(\Theta(n)\) sequential additions; the result presumes ideal unit-cost arithmetic and tree communication.

Odd–even transposition sort¶

Place one key at each of \(n\) processors on a line. Odd and even neighbor pairs alternately compare/exchange; Wisconsin's analysis gives \(n\) rounds. On an \(n\)-processor machine this has \(n^2\) processor-rounds. A sequential comparison sort needs order \(n\log n\), so this implementation is not cost-optimal despite its parallel execution. The line's diameter and communication pattern limit how much mere processor throttling can help.^[3]^[2]

Mapped back: the fixed task is sorting \(n\) keys; \(p=n\); \(T_p=\Theta(n)\) mesh rounds; \(pT_p=\Theta(n^2)\); the benchmark is \(\Theta(n\log n)\); the declared model is neighbor exchange on a one-dimensional mesh.

Structural Tensions¶

Latency reduction versus processor-time economy. Increasing \(p\) may shorten the local portion of \(T_p\), but if the critical-path term remains, the total \(pT_p\) rises. Throttling processors can restore cost efficiency while leaving a slower elapsed result. In the sum case, \(n\) processors and \(n/\log n\) processors can have the same asymptotic latency but different cost; in other tasks the latency tradeoff may be sharper. Diagnostic: does the marginal latency reduction justify the added processor-time relative to the sequential bound?^[4]^[1]

Clean theorem versus machine realism. An ideal work/depth model isolates avoidable algorithmic work and yields clear asymptotic statements. A topology-aware model includes communication and can overturn a claimed practical gain, but its result is less portable across machines. The Wisconsin mesh result embodies a communication constraint that a generic processor-time expression alone does not explain. Diagnostic: is this a theorem in the declared model, or a prediction for hardware whose data movement has actually been included?^[3]^[4]

Structural–Framed Character¶

The relation \(pT_p/T_s\) is mathematically structural after the problem, baseline and machine model are fixed. The named criterion leans framed because analysts choose which processors count, what communication costs, what serial algorithm is admissible and whether asymptotic economy is the valued objective. “Optimal” is evaluative, but only relative to that declared resource and frontier; it does not praise the algorithm in every operational sense. Its vocabulary comes from parallel-computing research and travels naturally among computational problems, not into unrelated budgeting without changing the measure. Human design practice chooses a schedule, while the algebraic verdict follows from that choice under the model. Importing the phrase for an energy-efficient building is metaphor; recognizing another parallel algorithm with bounded \(pT_p/T_s\) is literal. Its character: a model-framed but formally testable efficiency criterion specialized to parallel processor-time.^[1]^[2]

Structural Core vs. Domain Accent¶

The skeletal relation is a processor-work comparison against a same-problem sequential benchmark, using the live Ratio prime as a necessary quantitative prerequisite. The domain-bound mechanism is processor-time \(pT_p\), parallel latency, a sequential algorithmic frontier and machine assumptions. The name fails the prime bar because a hospital's staffing efficiency or a turbine's energy efficiency does not use this processor-time test, even though the broad input/output comparison resembles it. This cost-efficiency verdict is not the ratio itself, and the live Efficiency prime's undominated-frontier requirement is not a strict genus here.

This entry presupposes Ratio.

The live Ratio prime is the strict prerequisite under composition/presupposes: processor-work is compared with a sequential baseline by a quotient or equivalent multiplicative relation. The cost-efficiency verdict is not itself the quotient, and the live Efficiency prime's undominated-frontier criterion need not hold under fixed-factor asymptotic work optimality. Speedup is related but insufficient: a speedup figure must be normalized by \(p\) and compared to a sound sequential baseline before cost efficiency follows.

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 (66^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

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

Not to Be Confused With¶

Parallel runtime optimality: smallest time may spend asymptotically excessive processor-time.
Work-efficient schedule: actual operation count can differ from charged \(pT_p\) when processors idle; state the model.^[4]
Economic cost: hardware rent and energy use can dominate while asymptotic processor-time remains optimal.
Odd–even versus Batcher's odd–even sorting: the neighbor transposition procedure here is a different algorithm from an odd–even merge sorting network.^[3]

References¶

[1] Imperial College, Parallel Algorithms, Performance Metrics, p. 50/65, cost \(C_p=pT_p\) and efficiency. registry ↩a ↩b ↩c ↩d ↩e ↩f

[2] Carnegie Mellon, “Parallel Models of Computation”, work \(W=Pt\), efficient comparison sorting discussion. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g

[3] University of Wisconsin, “Introduction to parallel sorting on mesh-based topologies,” §15, even–odd transposition \(n\) rounds and \(O(n^2)\) cost. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h

[4] MIT 6.854, Parallel Algorithms Notes #32, work/depth and processor simulation; blocked-sum algebra here is explicitly derived under the ideal model. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k