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.

C++
1
2
3
4
5
6
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} \]
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用