What makes a workload "embarrassingly parallel", and what specific properties disqualify a workload from that label?
answer
- independent units, no communication during execution
- read own slice, write own slice
- disqualifiers: dependency, shared state, ordering, shared bottleneck
- per-worker locals merged once restores independence
- logical independence ≠ hardware independence
basics
~20 sEmbarrassingly parallel means the work splits into independent pieces that need no communication or coordination while running — each piece reads only its own input and writes only its own output. Cross-piece dependencies, shared mutable state, order sensitivity, or contention on one shared resource disqualify it.
solid answer
~1 minA workload is embarrassingly parallel when splitting it is trivial and the pieces never need to talk to each other during execution. Concretely: each unit reads only its own slice of input, writes only its own slice of output, needs no results from any other unit, and the combine step is either nothing or a simple associative reduction. Thumbnailing a directory of images, running the same simulation with 10,000 different seeds, checksumming a set of files. Disqualifiers, in the order they actually bite: - **Data dependencies** — unit *i* needs unit *i−1*'s result (running totals, prefix sums, sequential state machines). - **Shared mutable state** — a common accumulator, cache or collection touched by every worker; the synchronisation serialises the work. - **Ordering requirements** — output must be in input order, or side effects must occur in order. - **A shared bottleneck resource** — every worker hits the same disk, the same database connection, or saturates memory bandwidth. The code looks independent but the hardware is not. - **Uneven unit sizes** — technically still independent, but a single huge unit makes the tail dominate. The first three change your algorithm; the last two change your speedup while the algorithm stays valid.
code
text · 12 linesNOT independent (serialises on the lock, may also corrupt):
parallel for each chunk:
for item in chunk:
lock(results); results.append(f(item)); unlock(results)
Independent again (local accumulation, one merge at the end):
parallel for each chunk i:
local[i] = [] # private, no sharing
for item in chunk:
local[i].append(f(item))
# after all workers finish:
results = concatenate(local[0..n]) # order preserved by indexgo deeper
Define it as work that splits into pieces that do not need to communicate, and give an example such as processing each file or each image separately.
List the four required properties and name the concrete disqualifiers, especially the shared mutable accumulator and the per-worker-local fix.
Emphasise the hidden disqualifiers — a shared device, a small connection pool, memory bandwidth, skew — and explain why they cap speedup even when the code looks independent.
Treat the label as a risk assessment: near-linear scaling with low coordination risk if it truly holds, and otherwise a design decision about what coordination costs and whether parallelising is worth it at all.
## The definition A problem is **embarrassingly parallel** (sometimes "pleasingly parallel") when it decomposes into subproblems that are **independent**: during execution, no subproblem needs any information produced by another. There is no communication, no synchronisation on the hot path, and no ordering constraint between the pieces. Splitting is cheap, and merging is either unnecessary or a simple associative fold. The name is not a criticism — it means the parallelism is so obvious that almost nothing stands in the way of a near-linear speedup. These workloads are the ones where P workers actually approach P× throughput, which almost nothing else does. Canonical examples: - rendering each frame of an animation, or each tile of an image; - Monte Carlo simulation with independent random seeds; - applying a per-record transform (parse, validate, score, hash) to a large collection; - brute-force search over disjoint key ranges; - running the same test suite against 200 independent inputs. ## The four properties that must all hold 1. **Partitionable input** — you can compute each unit's slice cheaply, without walking the whole structure. An array or a file-offset range is trivially partitionable; a linked list is not, because finding the midpoint costs a full traversal, and the split cost eats the gain. 2. **No cross-unit data dependency** — unit *i*'s computation reads nothing that unit *j* produces. Formally, no read-after-write edge between units. 3. **No shared mutable state** — units may share *immutable* input freely (that costs nothing but cache), but must not both write the same location, or write one that another reads. 4. **Order-insensitive completion** — units may finish in any order, and the combine (if any) is associative and, if partitions can complete out of order, commutative too — or ordering is restored by writing results into indexed slots rather than appending. ## What disqualifies a workload **Sequential data dependence.** Anything of the form `state = f(state, item)` where `f` is not associative. Running balances, sequential decoders, iterative solvers where each step reads the previous iterate. Some of these can be rescued: a sum or max *is* associative, so a running-total-style loop can become a parallel reduction; a prefix sum can be done in parallel with a two-pass scan algorithm. But that is redesigning the algorithm, not parallelising the loop as written. **Shared mutable accumulator.** The most common mistake in practice. Workers append to a shared collection or increment a shared counter. Either it is unsynchronised — corrupt results, lost updates — or it is synchronised, and the lock serialises exactly the part every worker executes, so the speedup vanishes and you have paid coordination overhead on top. The fix is per-worker local accumulators merged once at the end, which restores independence. **Ordering requirements.** If output must preserve input order, appending from workers is wrong. Writing into pre-sized indexed slots preserves order at no cost; ordered *side effects* (writing to a stream, emitting events) are harder and often force a sequential merge stage. **A shared physical bottleneck.** The subtle one. Sixteen workers each reading their own file are logically independent, but if all sixteen files are on one spinning disk, the disk serialises them — and random seeks make it slower than one sequential reader. The same applies to a shared connection pool of size 4, a rate-limited API, or a memory-bandwidth-bound kernel where the cores saturate the bus long before they run out of arithmetic capacity. Logical independence does not imply hardware independence, and this is the reason a "perfectly parallel" job sometimes shows a 2× speedup on 16 cores. **Skew.** Independent but unequal units. If one unit is 40% of the total work, no scheduling fixes it — the wall clock is at least that unit's duration. Fix by splitting the large unit further (over-partitioning) if the work is divisible, or by sizing partitions by estimated cost rather than by item count. ## Why the label matters in an interview Saying "this is embarrassingly parallel" is a claim about expected speedup and about *risk*. If it holds, parallelising is low-risk and near-linear; if it doesn't, you are signing up for synchronisation, and the interesting question becomes what the coordination costs and whether it is worth doing at all. The valuable skill is spotting the hidden disqualifier — the shared cache, the ordered output, the one connection pool — rather than reciting the definition. A useful checklist to run on any candidate workload: - Can I compute each unit's input slice in O(1)? - Does any unit read something another unit writes? - Is there any shared mutable object on the hot path — counters, caches, collections, loggers? - Does anything depend on completion order or output order? - Do all units contend for the same disk, network, connection pool or memory bandwidth? - Are the units roughly equal in cost? Five noes and a yes to the last is a genuinely embarrassingly parallel workload.
- A job reads sixteen separate files with sixteen threads and gets barely any speedup. The code has no shared state — what is going on?The units are logically independent but not physically independent: they contend for one storage device, one filesystem cache, or a bandwidth-limited link. On a spinning disk, sixteen concurrent readers also turn sequential reads into random seeks and can be slower than one. Logical independence does not imply hardware independence, and the shared bottleneck sets the real ceiling.
- Can a computation with a sequential dependency ever be parallelised?Sometimes, by changing the algorithm rather than the loop. If the combining operation is associative — sum, max, count, min — the fold becomes a parallel reduction over partial results. Prefix-sum-shaped dependencies can be handled with a two-pass parallel scan. But if the step function is genuinely non-associative and each step depends on the last, the dependency chain is the algorithm and no scheduling helps.
saying these in an interview costs you the question
- Calling any loop over a collection embarrassingly parallel without checking for shared mutable state inside the body.
- Believing a lock around a shared accumulator preserves the speedup; it serialises the part every worker executes.
- Assuming independent code paths mean independent hardware — one disk, one connection pool, or memory bandwidth still serialises them.
- Ignoring output ordering requirements and appending results from workers in completion order.
- Overlooking skew: independent-but-unequal units make the largest unit the wall clock.