> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-vii-selected-topics/26.-parallel-algorithms.md).

# 26. Parallel Algorithms

## Exercises

### 26.1-1

The execution trace of a serial algorithm is a chain of strands.

### 26.1-2

**Available in the latest revision of the IM.**

{% hint style="warning" %}
The IM doesn't answer the question how would the trace of `P-FIB(4)` in Figure 26.2 change. All orange circles and tan rectangles would become blue. Furthermore, there would be a dependency between the second blue strand and white circle in a procedure.
{% endhint %}

### 26.1-3

The building blocks for a trace of `P-FIB(5)` are depicted on Figure 26.2. You just need to add an additional rectangle on top with `P-FIB(4)` trace on the left and `P-FIB(3)` trace on the right (see also the invocation tree depicted in Figure 26.1). Both are pointing back to the last strand of `P-FIB(5)`.

The work is 29 units, whilst the span is 10 units. The parallelism is 2.9. To clearly track the parallel execution on 3 processors, the strands are labeled by their parent task:

* L, M, R: Designates the Left, Middle, and Right branches of identical subproblems (e.g., `P-FIB(3)_L` is the left subproblem of `P-FIB(4)`, while `P-FIB(3)_R` is the right subproblem directly called by `P-FIB(5)`).

{% hint style="info" %}
Processors are treated here as a pool of completely anonymous, identical, and interchangeable workers. Therefore, listing them in the table is just for convenience.
{% endhint %}

<table data-header-hidden data-search="false"><thead><tr><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td><strong>Time Step</strong></td><td><strong>Processor 1</strong></td><td><strong>Processor 2</strong></td><td><strong>Processor 3</strong></td></tr><tr><td>1</td><td><code>P-FIB(5)</code> Spawn</td><td><em>Idle</em></td><td><em>Idle</em></td></tr><tr><td>2</td><td><code>P-FIB(4)</code> Spawn</td><td><code>P-FIB(5)</code> Call</td><td><em>Idle</em></td></tr><tr><td>3</td><td><code>P-FIB(3)_L</code> Spawn</td><td><code>P-FIB(4)</code> Call</td><td><code>P-FIB(3)_R</code> Spawn</td></tr><tr><td>4</td><td><code>P-FIB(2)_LL</code> Spawn</td><td><code>P-FIB(3)_L</code> Call</td><td><code>P-FIB(2)_M</code> Spawn</td></tr><tr><td>5</td><td><code>P-FIB(2)_R</code> Spawn</td><td><code>P-FIB(2)_LL</code> Call</td><td><code>P-FIB(3)_R</code> Call</td></tr><tr><td>6</td><td><code>P-FIB(1)</code> Base <em>(from 2_LL)</em></td><td><code>P-FIB(0)</code> Base <em>(from 2_LL)</em></td><td><code>P-FIB(2)_M</code> Call</td></tr><tr><td>7</td><td><code>P-FIB(2)_LL</code> Sync</td><td><code>P-FIB(2)_R</code> Call</td><td><code>P-FIB(1)</code> Base <em>(from 3_L)</em></td></tr><tr><td>8</td><td><code>P-FIB(1)</code> Base <em>(from 2_M)</em></td><td><code>P-FIB(0)</code> Base <em>(from 2_M)</em></td><td><code>P-FIB(1)</code> Base <em>(from 2_R)</em></td></tr><tr><td>9</td><td><code>P-FIB(3)_L</code> Sync</td><td><code>P-FIB(2)_M</code> Sync</td><td><code>P-FIB(0)</code> Base <em>(from 2_R)</em></td></tr><tr><td>10</td><td><code>P-FIB(4)</code> Sync</td><td><code>P-FIB(2)_R</code> Sync</td><td><code>P-FIB(1)</code> Base <em>(from 3_R)</em></td></tr><tr><td>11</td><td><code>P-FIB(3)_R</code> Sync</td><td><em>Idle</em></td><td><em>Idle</em></td></tr><tr><td>12</td><td><code>P-FIB(5)</code> Sync</td><td><em>Idle</em></td><td><em>Idle</em></td></tr></tbody></table>

### 26.1-4

We build upon the proof of Theorem 26.1. Clearly, $$T\_P=k+i$$, where $$k$$ is the number of complete steps and $$i$$ is the number of incomplete steps. We know that $$i \le T\_\infty$$. We can express the total work as

$$
T\_1 \ge kP + i \implies k \le \frac{T\_1 - i}{P}.
$$

This gives

$$
T\_P \le \frac{T\_1 - i}{P} + i= \frac{T\_1 + (P - 1)i}{P}.
$$

The RHS is a monotonically increasing function with respect to $$i$$. It attains its maximum value for $$i=T\_\infty$$, thus

$$
T\_P \le \frac{T\_1 - T\_\infty}{P} + T\_\infty.
$$

### 26.1-5

Consider a computation trace executing on $$P$$ processors that consists of two distinct structural components:

* A single sequential chain of $$k$$ strands (critical path): $$C\_1 \rightarrow C\_2 \rightarrow \dots \rightarrow C\_k$$.
* A disconnected pool of $$k \times P$$ entirely independent strands: $$I\_1, I\_2, \dots, I\_{kP}$$.

All independent strands and the first chain strand are ready to execute at time step 1. The two extreme scenarios are:

1. The scheduler consistently advances the chain. In each step $$j$$, the scheduler assigns the ready chain strand $$C\_j$$ to one processor, and assigns $$P-1$$ independent strands to the remaining processors. After $$k$$ steps, the sequential chain is fully complete and there are $$k$$ remaining independent strands (these can be again executed in parallel). The total time becomes $$k + \lceil k/P \rceil \to k+1$$, as $$P \to \infty$$.
2. Tthe scheduler ignores the chain, choosing instead to exhaust the independent strands first. After $$k$$ steps, the chain is still "intact." The total time becomes $$2k$$.

### 26.1-6

**Available in the latest revision of the IM.**

### 26.1-7

**Available in the latest revision of the IM.**

### 26.1-8

**Available in the latest revision of the IM.**

### 26.1-9

**Available in the latest revision of the IM.**

### 26.1-10

**Available in the latest revision of the IM.**

### 26.2-1

<figure><img src="https://1997161-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FlBSM5MLFKTKipGIIw1fs%2Fuploads%2FmmdcEDz4bMDryx9sCiN5%2Ffigure_26_2_1.svg?alt=media&amp;token=5dd2d83a-9eb5-4d16-8748-b3340b244dbd" alt=""><figcaption><p>The strands are illustrated using the book's convention with one difference noted below. The critical path is depicted with thick lines. The work is 17 units, the span is 8 units. The parallelism is 2.125.</p></figcaption></figure>

{% hint style="info" %}
In Figure 26.4 (see the book), while the circles look identical, their true computational weights are drastically different. The strands in base cases have weights $$\Theta(n)$$. Here, strands are kept at the same granularity.
{% endhint %}

### 26.2-2

The execution is divided into the following sequential blocks:

1. **Initial Setup (1 strand)**: Line 4 allocates the temporary matrix $$D$$.
2. **Phase 1: Initialize** $$D$$ **(13 strands)**: Lines 5-7 form a doubly nested parallel for loop. Using the binary divide-and-conquer trace pattern, this $$2 \times 2$$ expansion creates 3 strands for the outer loop dispatch/sync, 6 strands for the inner loops, and 4 single-strand base cases $$d\_{ij} = 0$$.
3. **Partitioning (1 strand)**: Line 8 is sequential index arithmetic that must complete before the recursions spawn.
4. **Phase 2: 8 Recursive Spawns (17 strands)**: Lines 9-16 consist of 8 explicit spawn instructions. A parent thread executing $$k$$ sequential spawns creates a chain of $$k$$ strands. This produces 8 parent spawn strands, 8 independent child base cases ($$n=1$$, which execute sequentially and return), and 1 final sync strand.
5. **Phase 3: Update** $$C$$ **(13 strands)**: Lines 18-20 form another $$2 \times 2$$ doubly nested parallel for loop, mirroring Phase 1 exactly.

The work is 45 units, the span is 26 units. The parallelism is $$\approx 1.73$$.

### 26.2-3

**Available in the latest revision of the IM.**

### 26.2-4

**Available in the latest revision of the IM.**

### 26.2-5

**Available in the latest revision of the IM.**

### 26.3-1

Establish a constant integer (e.g., `THRESHOLD`), which represents the problem size where sequential execution outpaces the overhead of parallel dispatching and memory allocation.

```
P-MERGE-COARSENED(A, p, q, r)
1  n = r - p + 1
2  if n <= THRESHOLD
3      MERGE(A, p, q, r)    // Standard serial merge
4      return
5  let B[p : r] be a new array
6  P-MERGE-AUX(A, p, q, q + 1, r, B, p)
7  parallel for i = p to r
8      A[i] = B[i]
```

To fully realize the performance gains of coarsening, this identical threshold logic must also be applied inside `P-MERGE-AUX`. Because `P-MERGE` acts primarily as a wrapper, calling it on a massive array will drop straight into `P-MERGE-AUX`. If the auxiliary function lacks a size check, it will continue to recursively spawn tasks all the way down to trivial base cases, reintroducing the exact thread-management bottlenecks the threshold was designed to prevent.

```
P-MERGE-AUX-COARSENED(A, p1, r1, p2, r2, B, p3)
1  n1 = r1 - p1 + 1
2  n2 = r2 - p2 + 1
3  if n1 + n2 <= THRESHOLD
4      S-MERGE-AUX(A, p1, r1, p2, r2, B, p3)    // Serial version of P-MERGE-AUX
5      return
6
7  // Original P-MERGE-AUX divide-and-conquer logic
...
```

### 26.3-2

We define a helper function `EXACT-MEDIAN-SPLIT(A, p1, r1, p2, r2)` that returns three values: a boolean indicating whether the true median was found in the first or second subarray, and the two split indices $$q\_1$$ and $$q\_2$$ such that the elements to the left of the split sum exactly to $$\lfloor n/2 \rfloor$$. By finding the true median of the combined subarrays, this variant guarantees that the total remaining workload is partitioned perfectly in half.

```
P-TRUE-MEDIAN-MERGE-AUX(A, p1, r1, p2, r2, B, p3)
1   if p1 > r1 and p2 > r2
2       return
3
4   // Find the exact median of all elements across both subarrays
5   (is_in_first, q1, q2) = FIND-TRUE-MEDIAN-SPLIT(A, p1, r1, p2, r2)
6   q3 = p3 + (q1 - p1) + (q2 - p2)
7
8   if is_in_first
9       B[q3] = A[q1]
10      // Recursively merge A[p1 : q1 - 1] and A[p2 : q2 - 1] into B[p3 : q3 - 1].
11      spawn P-TRUE-MEDIAN-MERGE-AUX(A, p1, q1 - 1, p2, q2 - 1, B, p3)
12      // Recursively merge A[q1 + 1 : r1] and A[q2 : r2] into B[q3 + 1 : r3].
13      spawn P-TRUE-MEDIAN-MERGE-AUX(A, q1 + 1, r1, q2, r2, B, q3 + 1)
14  else B[q3] = A[q2]
15      // Recursively merge A[p1 : q1 - 1] and A[p2 : q2 - 1] into B[p3 : q3 - 1].
16      spawn P-TRUE-MEDIAN-MERGE-AUX(A, p1, q1 - 1, p2, q2 - 1, B, p3)
17      // Recursively merge A[q1 : r1] and A[q2 + 1 : r2] into B[q3 + 1 : r3].
18      spawn P-TRUE-MEDIAN-MERGE-AUX(A, q1, r1, q2 + 1, r2, B, q3 + 1)
19  sync
```

The asymptotic bounds of work, span and parallelism are entirely unchanged.

### 26.3-3

To achieve a highly parallel partition algorithm, we use a parallel prefix sum (see [Problem 26-4](#id-26-4-parallel-reductions-and-scan-prefix-computations)) to compute the exact destination indices for elements smaller than and greater than the pivot. This avoids race conditions by ensuring every element knows its precise, unique location in the auxiliary array before any data is moved.

{% hint style="info" %}
Many standard libraries of mainstream programming languages offer a parallel prefix sum function, for example, in Java it is [java.util.Arrays.parallelPrefix](https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#parallelPrefix-int:A-int-int-java.util.function.IntBinaryOperator-) (there are many overloaded variants).
{% endhint %}

```
P-PARTITION(A, p, r)
1  let B[p : r], LT[p : r], GT[p : r] be new arrays
2  x = A[r]
3  
4  // Phase 1: Populate indicator arrays
5  parallel for i = p to r - 1
6      if A[i] <= x
7          LT[i] = 1
8          GT[i] = 0
9      else LT[i] = 0
10         GT[i] = 1
11 LT[r] = 0
12 GT[r] = 0
13 
14 // Phase 2: Compute exact output positions using parallel prefix sums
15 P_LT = P-PREFIX-SUM(LT, p, r)
16 P_GT = P-PREFIX-SUM(GT, p, r)
17 
18 // Phase 3: Route elements to temporary array B
19 pivot_pos = p + P_LT[r - 1]
20 B[pivot_pos] = x
21 
22 parallel for i = p to r - 1
23     if A[i] <= x
24         B[p + P_LT[i] - 1] = A[i]
25     else B[pivot_pos + P_GT[i]] = A[i]
26 
27 // Phase 4: Copy back to original array
28 parallel for i = p to r
29     A[i] = B[i]
30     
31 return pivot_pos
```

Apparently the work is $$T\_1(n) = \Theta(n)$$. The span of the parallel prefix sum is $$\Theta(\log n)$$, so the total span is $$T\_\infty(n) = \Theta(\log n)$$. This results in $$\Theta(n / \log n)$$ parallelism.

### 26.3-4

To parallelize the Fast Fourier Transform (FFT), we must break the serial dependencies in two specific areas of the original algorithm: the partitioning of the input array into even and odd elements, and the iterative computation of $$\omega$$ in the final loop. By replacing the serial assignments with parallel for loops and explicitly calculating $$\omega = \omega\_n^k$$ independently for each iteration (assuming complex exponentiation executes in $$\Theta(1)$$ time), we can fully parallelize the combine phase. We also introduce a `spawn` and `sync` to execute the two recursive subproblems concurrently.

```
P-FFT(a, n)
1  if n == 1
2      return a
3  let a_even, a_odd, and y be new arrays
4  
5  // Parallelize the partition of even and odd indices
6  parallel for k = 0 to (n / 2) - 1
7      a_even[k] = a[2k]
8      a_odd[k] = a[2k + 1]
9      
10 // Execute recursive FFTs in parallel
11 y_even = spawn P-FFT(a_even, n / 2)
12 y_odd = P-FFT(a_odd, n / 2)
13 sync
14 
15 ω_n = e^{2πi/n}
16 
17 // Parallelize the combine phase
18 parallel for k = 0 to (n / 2) - 1
19     ω = ω_n^k
20     y[k] = y_even[k] + ω * y_odd[k]
21     y[k + (n / 2)] = y_even[k] - ω * y_odd[k]
22     
23 return y
```

The recurrence for the work is $$T\_1(n) = 2T\_1(n/2) + \Theta(n)$$. By Case 2 of the Master Theorem, the total work is exactly identical to the serial algorithm $$T\_1(n) = \Theta(n \log n)$$.

The recurrence for the span is $$T\_\infty(n) = T\_\infty(n/2) + \Theta(\log n)$$.  This falls under Case 2 of the Master Theorem yielding a total span of $$T\_\infty(n) = \Theta(\log^2 n)$$.

Thus, the parallelism is $$\Theta\left(\frac{n}{\log n}\right)$$.

### ★ 26.3-5

To parallelize `SELECT`, we parallelize the iterative grouping and sorting phase, as well as the array partitioning phase. However, the algorithm contains strict data dependencies between its recursive steps: we must find the median of medians before we can partition the array, and we must finish partitioning before we know which side to recurse into. This forces the two recursive calls to execute sequentially. The code below uses `P-PARTITION` from [Exercise 26.3-3](#id-26.3-3) (the altered variant below also accepts the pivot as an input argument).

```
P-SELECT(A, p, r, i)
1  // Handle non-multiples of 5 serially (at most 4 iterations)
2  while (r - p + 1) mod 5 != 0
3      for j = p + 1 to r
4          if A[p] > A[j]
5              exchange A[p] with A[j]
6      if i == 1
7          return A[p]
8      p = p + 1
9      i = i - 1
10
11 g = (r - p + 1) / 5
12 // Sort the 5-element groups in parallel
13 parallel for j = p to p + g - 1
14     sort <A[j], A[j + g], A[j + 2g], A[j + 3g], A[j + 4g]> in place
15 
16 // Find the median of the medians
17 x = P-SELECT(A, p + 2g, p + 3g - 1, ceil(g / 2))
18 
19 // Parallel partition around the pivot x
20 q = P-PARTITION-AROUND(A, p, r, x)
21 
22 // Recursively search the appropriate partition
23 k = q - p + 1
24 if i == k
25     return A[q]
26 elseif i < k
27     return P-SELECT(A, p, q - 1, i)
28 else 
29     return P-SELECT(A, q + 1, r, i - k)
```

The total work resolves to $$T\_1(n) = \Theta(n)$$ as before (see the analysis of `SELECT` in Section 9.3 of the book).&#x20;

The span recurrence is

$$
T\_\infty(n) \le T\_\infty(n/5) + T\_\infty(7n/10) + \Theta(\log n).
$$

Applying the Akra-Bazzi method, the solution is determined by the power $$p$$ that satisfies $$(1/5)^p + (7/10)^p = 1$$. Solving this yields $$p \approx 0.839$$. Therefore, the span is $$T\_\infty(n) = \Theta(n^p) \approx \Theta(n^{0.839})$$.

Thus, the parallelism is

$$
\frac{T\_1(n)}{T\_\infty(n)} = \Theta\left(\frac{n}{n^p}\right) = \Theta(n^{1 -p}) \approx \Theta(n^{0.161}).
$$

## Problems

### 26-1 Implementing parallel loops using recursive spawning

**Available in the latest revision of the IM.**

### 26-2 Avoiding a temporary matrix in recursive matrix multiplication

**Available in the latest revision of the IM.**

### 26-3 Parallel matrix algorithms

#### a.

```
P-LU-DECOMPOSITION(A, n)
1  let L and U be new n × n matrices
2  // Initialize L and U in parallel
3  parallel for i = 1 to n
4      L[i, i] = 1
5      parallel for j = 1 to i - 1
6          U[i, j] = 0
7      parallel for j = i + 1 to n
8          L[i, j] = 0
9  for k = 1 to n
10     U[k, k] = A[k, k]
11     parallel for i = k + 1 to n
12         L[i, k] = A[i, k] / A[k, k]
13         U[k, i] = A[k, i]
14     parallel for i = k + 1 to n
15         parallel for j = k + 1 to n
16             A[i, j] = A[i, j] - L[i, k] * U[k, j]
17 return L and U
```

The overall work remains $$T\_1 = \Theta(n^3)$$, while the span is $$T\_\infty = \Theta(n \log n).$$ Thus, the parallelism is $$\Theta(n^2/\log n)$$.

#### b.

```
P-LUP-DECOMPOSITION(A, n)
1  let π[1 : n] be a new array
2  parallel for i = 1 to n
3      π[i] = i
4  for k = 1 to n
5      // Replace the sequential search with a parallel reduction
6      k' = P-MAX-ABS-INDEX(A, k, n, k)
7      p = |A[k', k]|
8      if p == 0
9          error "singular matrix"
10     exchange π[k] with π[k']
11     parallel for i = 1 to n
12         exchange A[k, i] with A[k', i]
13     parallel for i = k + 1 to n
14         A[i, k] = A[i, k] / A[k, k]
15         parallel for j = k + 1 to n
16             A[i, j] = A[i, j] - A[i, k] * A[k, j]

P-MAX-ABS-INDEX(A, low, high, col)
1  if low == high
2      return low
3  mid = floor((low + high) / 2)
4  spawn left_idx = P-MAX-ABS-INDEX(A, low, mid, col)
5  right_idx = P-MAX-ABS-INDEX(A, mid + 1, high, col)
6  sync
7  if |A[left_idx, col]| >= |A[right_idx, col]|
8      return left_idx
9  else return right_idx
```

The overall work remains $$T\_1 = \Theta(n^3)$$, while the span is $$T\_\infty = \Theta(n \log n).$$ Thus, the parallelism is $$\Theta(n^2/\log n)$$.

#### c.

```
P-LUP-SOLVE(L, U, pi, b, n)
1  let x, y, and t be new vectors of length n
2  for i = 1 to n
3      parallel for j = 1 to i - 1
4          t[j] = L[i, j] * y[j]
5      y[i] = b[pi[i]] - P-REDUCE-SUM(t, 1, i - 1)
6  for i = n downto 1
7      parallel for j = i + 1 to n
8          t[j] = U[i, j] * x[j]
9      x[i] = (y[i] - P-REDUCE-SUM(t, i + 1, n)) / U[i, i]
10 return x
```

Because forward substitution and back substitution are inherently iterative processes, the outer for loops (lines 2 and 6) contain strict loop-carried dependencies. For example, $$y\_i$$ cannot be computed until all previous $$y\_1 \dots y\_{i-1}$$ are fully evaluated. Therefore, the outer loops must execute sequentially.

The total number of operations remains unchanged from the sequential version. Thus, $$T\_1 = \Theta(n^2)$$.

The sequential outer loops run $$n$$ times. Inside each iteration, the parallel for executes in $$\Theta(1)$$ span, and the `P-REDUCE-SUM` evaluates the sum using a binary reduction tree in $$\Theta(\log n)$$ span. The implementation is omitted, since the book already contains all the details. Multiplying the sequential outer bound by the parallel inner bound yields a total span of $$T\_\infty = \Theta(n \log n)$$.

The parallelism is $$O(n/\log n)$$.

#### d.

```
P-SPD-INVERT(A, A_inv, n)
1  if n == 1
2      A_inv[1, 1] = 1 / A[1, 1]
3      return
4  Partition A into n/2 x n/2 submatrices B, C_T, C, D
5  Partition A_inv into n/2 x n/2 submatrices R, T, U, V
6  let B_inv, W, W_T, X, S, Y, Y_T, and Z be new n/2 x n/2 matrices
7  P-SPD-INVERT(B, B_inv, n/2)
8  P-MATRIX-MULTIPLY-RECURSIVE(C, B_inv, W, n/2)
9  P-MATRIX-TRANSPOSE(W, W_T, n/2)
10 P-MATRIX-MULTIPLY-RECURSIVE(W, C_T, X, n/2)
11 P-MATRIX-SUBTRACT(D, X, S, n/2)
12 P-SPD-INVERT(S, V, n/2)
13 P-MATRIX-MULTIPLY-RECURSIVE(V, W, Y, n/2)
14 P-MATRIX-TRANSPOSE(Y, Y_T, n/2)
15 P-MATRIX-MULTIPLY-RECURSIVE(W_T, Y, Z, n/2)
16 spawn P-MATRIX-ADD(B_inv, Z, R, n/2)
17 spawn P-MATRIX-NEGATE(Y_T, T, n/2)
18 P-MATRIX-NEGATE(Y, U, n/2)
19 sync
```

The pseudocode uses the `P-MATRIX-MULTIPLY-RECURSIVE` procedure from the book. The other matrix procedures can be implemented in a similar fashion and are simpler than multiplication.

The work is $$T\_1 = \Theta(M(n))$$ as before.

The two recursive calls (lines 7 and 12) must be executed sequentially. Computing the Schur-complement $$S$$ requires the matrix $$B^{-1}$$ to be fully resolved, and computing $$S^{-1}$$ inherently depends on $$S$$ being fully constructed. The recurrence for the span is

$$
T\_\infty(n) = 2T\_\infty(n/2) + \Theta(\log^2 n) \implies T\_\infty(n)=\Theta(n).
$$

This yields $$\Theta(M(n)/n)$$ parallelism.

### 26-4 Parallel reductions and scan (prefix) computations

**Available in the latest revision of the IM (except part (f) presented below).**

#### f.

To eliminate the temporary array $$t$$, we can store the intermediate prefix sums directly in the output array $$y$$. Because every recursive split calculates a midpoint $$k = \lfloor(i+j)/2\rfloor$$, and $$k$$ always represents the unique rightmost index of the left subproblem, each internal node of the recursion tree maps to a distinct index in $$y$$. We can safely write the intermediate sum of the left subarray into $$y\[k]$$ during the upward phase, and read it during the downward phase before replacing it with the final prefix sum.

```
P-SCAN-3(x, n)
1  let y[1 : n] be a new array
2  y[1] = x[1]
3  if n > 1
4      P-SCAN-UP(x, y, 2, n)
5      P-SCAN-DOWN(x[1], x, y, 2, n)
6  return y

P-SCAN-UP(x, y, i, j)
1  if i == j
2      return x[i]
3  else k = floor((i + j) / 2)
4      y[k] = spawn P-SCAN-UP(x, y, i, k)
5      right = P-SCAN-UP(x, y, k + 1, j)
6      sync
7      return y[k] ⊗ right

P-SCAN-DOWN(v, x, y, i, j)
1  if i == j
2      y[i] = v ⊗ x[i]
3  else k = floor((i + j) / 2)
4      right_v = v ⊗ y[k] // Avoids a race condition
5      spawn P-SCAN-DOWN(v, x, y, i, k)
6      P-SCAN-DOWN(right_v, x, y, k + 1, j)
7      sync
```

### 26-5 Parallelizing a simple stencil calculation

**Available in the latest revision of the IM.**

{% hint style="warning" %}
The IM doesn't expand on the inherent parallelism. A 2D stencil operation on an $$n \times n$$ matrix must compute exactly $$n^2$$ elements. Assuming the `BASE-CASE` function executes in $$\Theta(1)$$ time, the total computational work is $$T\_1 = \Theta(n^2)$$. The strict data dependencies of a standard stencil (where a cell depends on its immediate top and left neighbors) require the matrix to be evaluated sequentially across its anti-diagonals. There are exactly $$2n - 1$$ anti-diagonals in an $$n \times n$$ grid. If a hypothetical parallel machine could execute all independent tasks on an anti-diagonal simultaneously without any thread-dispatching overhead, the longest path through the execution graph would be exactly $$2n - 1$$ steps. Therefore, the inherent theoretical span of the mathematical problem is $$T\_\infty = \Theta(n)$$. This yields the maximal inherent parallelism $$T\_1 / T\_\infty = \Theta(n^2) / \Theta(n) = \Theta(n)$$.
{% endhint %}

### 26-6 Randomized parallel algorithms

#### a.

* **Expected work aw**: $$E\[T\_P] \ge E\[T\_1] / P$$
* **Expected span law**: $$E\[T\_P] \ge E\[T\_\infty]$$
* **Expected greedy scheduler bound**: $$E\[T\_P] \le E\[T\_1] / P + E\[T\_\infty]$$

These modifications are justified by two fundamental properties of expected values:

1. **Monotonicity of Expectation**: If a random variable $$X$$ is always greater than or equal to a random variable $$Y$$ (i.e., $$X \ge Y$$ for every possible outcome), then $$E\[X] \ge E\[Y]$$. Because the original work law ($$T\_P \ge T\_1 / P$$) and span law ($$T\_P \ge T\_\infty$$) hold true for every single valid execution trace, their expected values strictly preserve these inequalities.
2. **Linearity of Expectation**: The expectation of a sum of random variables is the sum of their individual expectations, regardless of whether the variables are independent. Taking the expectation of both sides of the original greedy scheduler bound ($$T\_P \le T\_1 / P + T\_\infty$$) yields $$E\[T\_P] \le E\[T\_1 / P + T\_\infty]$$. Applying linearity strictly separates the right side into $$E\[T\_1] / P + E\[T\_\infty]$$.

#### b.

To evaluate the correct definition of randomized speedup, we must calculate the exact values for both proposed formulas using the probabilities provided. First, we calculate the expected total work ($$E\[T\_1]$$) and the expected parallel execution time ($$E\[T\_P]$$ where $$P = 10,000$$):

* $$E\[T\_1] = 0.01(10^4) + 0.99(10^9) = 990,000,100$$
* $$E\[T\_{10,000}] = 0.01(1) + 0.99(10^9) = 990,000,000.01$$

Next, we evaluate the first definition of speedup, the ratio of the expectations:

$$
\frac{E\[T\_1]}{E\[T\_{10,000}]} = \frac{990,000,100}{990,000,000.01} \approx 1.
$$

Finally, we evaluate the second definition, the expected value of the individual speedup ratios:

$$
E\left\[\frac{T\_1}{T\_{10,000}}\right] = 0.01 \left(\frac{10^4}{1}\right) + 0.99 \left(\frac{10^9}{10^9}\right) \approx 100.
$$

Defining speedup as $$E\[T\_1/T\_P]$$ results in a reported speedup of roughly 100x. However, this is a massive mathematical distortion. The algorithm only achieves a high speedup ratio during the rare 1% case, which is a trivially small computational workload ($$10^4$$ operations). During the heavy 99% case ($$10^9$$ operations), the algorithm achieves literally zero parallel speedup ($$T\_1 = T\_P$$). Because the 99% case dominates the actual execution time of the system, running this algorithm repeatedly in the real world will not make your program 100 times faster. Therefore, defining speedup as $$\frac{E\[T\_1]}{E\[T\_P]}$$ correctly anchors the metric to the true physical execution time of the system over many runs, preventing tiny, anomalous edge cases from skewing the macroscopic performance analysis.

#### c.

This is a corollary of part (b), if we treat parallelism as a maximal speedup.

#### d.

```
P-RANDOMIZED-QUICKSORT (A, p, r)
1  if p < r
2      q = RANDOMIZED-PARTITION (A, p, r)
3      spawn P-RANDOMIZED-QUICKSORT (A, p, q - 1)
4      P-RANDOMIZED-QUICKSORT (A, q + 1, r)
5      sync
```

#### e.

$$
\frac{E\[T\_1]}{E\[T\_\infty]} = \frac{\Theta(n \log n)}{\Theta(n)} = \Theta(\log n).
$$

#### f.

```
P-RANDOMIZED-PARTITION(A, p, r)
1  i = RANDOM(p, r)
2  exchange A[r] with A[i]
3  return P-PARTITION(A, p, r)

P-RANDOMIZED-SELECT(A, p, r, i)
1  if p == r
2      return A[p]
3  q = P-RANDOMIZED-PARTITION(A, p, r)
4  k = q - p + 1
5  if i == k
6      return A[q]
7  elseif i < k return P-RANDOMIZED-SELECT(A, p, q - 1, i)
8  else return P-RANDOMIZED-SELECT(A, q + 1, r, i - k)
```

The expected work is $$E\[T\_1(n)] \le E\[T\_1(3n/4)] + \Theta(n) = \Theta(n)$$. The expected span is $$E\[T\_\infty(n)] \le E\[T\_\infty(3n/4)] + \Theta(\log n) = \Theta(\log^2 n)$$. This yields an excellent parallelism

$$
\frac{E\[T\_1(n)]}{E\[T\_\infty(n)]} = \Theta\left(\frac{n}{\log^2 n}\right).
$$