Question

Consider the message-passing formulation of the quicksort algorithm presented in Section 9.4.3 . Compute the exact (that is, using ts , t_w , and t_c ) parallel run time and efficiency of the algorithm under the assumption of perfect pivots. Compute the various components of the isoefficiency function of your formulation when:

a: t_c = 1, t_w = 1, t_s = 1
b: t_c = 1, t_w = 1, t_s = 10
c: t_c = 1, t_w = 10, t_s = 100
for cases in which the desired efficiency is 0.50, 0.75, and 0.95. Does the scalability of this formulation depend on the desired efficiency and the architectural characteristics of the machine?

Answer 1

The parallel run time and efficiency of the quicksort algorithm can be computed using the message-passing formulation presented in Section 9.4.3 of the reference material.

Step-by-step explanation:

The parallel run time and efficiency of the quicksort algorithm can be computed using the message-passing formulation presented in Section 9.4.3 of the reference material:

1. For the case of perfect pivots, the parallel run time (TP) is determined by the time it takes to perform the comparisons (ts), the time it takes to send messages between processes (t_w), and the time it takes to perform computations (t_c).
2. To compute the parallel run time, we can use the following formula:

TP = ts + t_w + t_c

The efficiency (E) is calculated by dividing the sequential run time (TC) by the parallel run time:

E = TC / TP

By substituting the values of ts, t_w, and t_c, we can compute the parallel run time and efficiency for different scenarios.