Questions: Parallel Algorithms and the PRAM Model

Question 1

An algorithm performs W = O(n) total work and has depth D = O(log n). Using Brent's theorem, what is the running time on p = n / log n processors?

• A. O(n)
• B. O(log n)
• C. O(log^2 n)
• D. O(n / log n)

Answer: (B)

Brent's theorem gives time O(W/p + D) = O(n / (n/log n) + log n) = O(log n + log n) = O(log n). This is optimal: with n/log n processors, we achieve O(log n) parallel time while keeping the total work O(n), which matches the sequential lower bound. The algorithm is said to be work-efficient because its total work equals the best sequential algorithm's running time. Work-efficiency is the gold standard in parallel algorithm design -- it means no computation is wasted.

Question 2

The class NC contains exactly those problems solvable in O(log^k n) depth with O(n^c) total work for constants k and c. A problem that is P-complete under logspace reductions is in NC if and only if NC = P.

• T. True
• F. False

Answer: True

P-complete problems are the hardest problems in P with respect to logspace (or NC) reductions. If any P-complete problem were in NC, then every problem in P would reduce to it in NC, placing all of P in NC. Since NC is contained in P (polylog depth with polynomial work implies polynomial sequential time), this would give NC = P. The canonical P-complete problem is the Circuit Value Problem (evaluating a given Boolean circuit on a given input). The widespread belief that NC != P means these problems are considered inherently sequential -- they resist efficient parallelization.

Question 3

The parallel prefix (scan) operation computes all prefix sums of an array of n elements. What are its work and depth, and why is this operation fundamental to parallel algorithm design?

Model answer: Parallel prefix computes all prefix sums (y_i = x_1 + x_2 + ... + x_i for i = 1..n) in O(n) work and O(log n) depth, matching the sequential lower bound for work while achieving exponential parallel speedup in depth. The operation generalizes beyond addition to any associative operator (max, min, AND, OR, concatenation). It is fundamental because a vast number of parallel algorithms reduce to prefix computation: parallel compaction (removing gaps from arrays), radix sort, carry-lookahead addition, tree computations, and load balancing. Parallel prefix is to parallel algorithms what divide-and-conquer is to sequential algorithms -- a universal building block.

The Blelloch up-sweep / down-sweep construction builds a balanced binary tree over the input. The up-sweep computes partial sums bottom-up (log n levels, n/2 + n/4 + ... = n-1 operations). The down-sweep propagates prefix sums top-down, again in log n levels with O(n) work. The construction is work-efficient (O(n) total work = sequential optimum) and achieves O(log n) depth. By Brent's theorem, this runs in O(n/p + log n) time on p processors.

Question 4

PRAM models differ in how they handle concurrent memory access. The EREW (Exclusive Read Exclusive Write) model is strictly weaker than CRCW (Concurrent Read Concurrent Write) -- some problems require asymptotically more depth on EREW than CRCW.

• T. True
• F. False

Answer: True

The CRCW PRAM can compute the OR of n bits in O(1) depth (all processors write 1 to a shared cell if their bit is 1, using priority or arbitrary write resolution). On the EREW PRAM, computing OR requires Omega(log n) depth because information from n inputs must be combined through a tree of exclusive operations. More precisely, any CRCW algorithm with depth D can be simulated on an EREW PRAM with depth O(D * log n), so the models differ by at most a logarithmic factor. This hierarchy (EREW subset CREW subset CRCW) parallels practical considerations: concurrent writes require more complex hardware or software coordination.

Question 5

Why is work-efficiency considered more important than minimizing depth in practical parallel algorithm design?

Model answer: A work-efficient algorithm (total work matching the best sequential algorithm) ensures that adding processors yields proportional speedup via Brent's theorem: time = O(W/p + D). If the work exceeds the sequential optimum by a factor c (work-inefficient), the algorithm wastes computation, and the parallel running time can never beat the sequential time by more than a factor of p/c regardless of depth. In practice, the number of processors p is finite, so the W/p term dominates for large inputs, making work-efficiency the primary determinant of real-world parallel performance. An algorithm with O(n log n) work and O(log n) depth is often worse in practice than one with O(n) work and O(log^2 n) depth when p is moderate.

This connects to Amdahl's Law and the broader principle that parallelism helps only when work is not wasted. The ideal parallel algorithm is simultaneously work-efficient (W equals sequential optimal) and has polylogarithmic depth. Some problems admit such algorithms (prefix sums, list ranking, connected components via Shiloach-Vishkin), while others seem to require a work-depth tradeoff.