27-6 Randomized multithreaded algorithms

Just as with ordinary serial algorithms, we sometimes want to implement randomized multithreaded algorithms. This problem explores how to adapt the various performance measures in order to handle the expected behavior of such algorithms. It also asks you to design and analyze a multithreaded algorithm for randomized quicksort.

a. Explain how to modify the work law $\text{(27.2)}$, span law $\text{(27.3)}$, and greedy scheduler bound $\text{(27.4)}$ to work with expectations when $T_P$, $T_1$, and $T_\infty$ are all random variables.

b. Consider a randomized multithreaded algorithm for which $1\%$ of the time we have $T_1 = 10^4$ and $T_{10,000} = 1$, but for $99\%$ of the time we have $T_1 = T_{10,000} = 10^9$. Argue that the speedup of a randomized multithreaded algorithm should be defined as $\text E[T_1]/\text E[T_P]$, rather than $\text E[T_1 / T_P]$.

c. Argue that the parallelism of a randomized multithreaded algorithm should be defined as the ratio $\text E[T_1] / \text E[T_\infty]$.

d. Multithread the $\text{RANDOMIZED-QUICKSORT}$ algorithm on page 179 by using nested parallelism. (Do not parallelize $\text{RANDOMIZED-PARTITION}$.) Give the pseudocode for your $\text{P-RANDOMIZED-QUICKSORT}$ algorithm.

e. Analyze your multithreaded algorithm for randomized quicksort. ($\textit{Hint:}$ Review the analysis of $\text{RANDOMIZED-SELECT}$ on page 216.)

a.

$$\begin{aligned} \text E[T_P] & \ge \text E[T_1] / P \\ \text E[T_P] & \ge \text E[T_\infty] \\ \text E[T_P] & \le \text E[T_1]/P + \text E[T_\infty]. \end{aligned}$$

b.

$$\text E[T_1] \approx \text E[T_{10,000}] \approx 9.9 \times 10^8, \text E[T_1]/\text E[T_P] = 1.$$

$$\text E[T_1 / T_{10,000}] = 10^4 * 0.01 + 0.99 = 100.99.$$

c. Same as the above.

d.

RANDOMIZED-QUICKSORT(A, p, r)
    if p < r
        q = RANDOM-PARTITION(A, p, r)
    spawn RANDOMIZED-QUICKSORT(A, p, q - 1)
    RANDOMIZED-QUICKSORT(A, q + 1, r)
    sync

e.

$$\begin{aligned} \text E[T_1] & = O(n\lg n) \\ \text E[T_\infty] & = O(\lg n) \\ \text E[T_1] / \text E[T_\infty] & = O(n). \end{aligned}$$