Task Multithreading analysis for a Divide and Conquer algorithm

Question

Suppose an algorithm that receive an input array of $n$ elements and it performs a task over each element. All tasks are independent and take $O(k)$ each (being $k$ a variable). Since all tasks are independent this is a fully parallelizable problem.

I have a basic algorithm that uses the Divide and Conquer technique. It receive the input array $A$ and if $|A| > 1$ then it spawn a new thread to process the first half of $A$, and recursively call itself to process the second half. This recursions stops when the function is called with a single element, in which case it runs a series of steps that takes $O(k)$.

I´m using the Dynamic Multithreading model (Introduction to Algorithms, chapter 27) to analyze this algorithm. So, I have an execution graph with n "leafs", representing the basic cases ($|A| = 1$), and it needs $O(n)$ "internal nodes" to divide the work until it reaches the leafs. Given that the longest path has length $O(\log n)$ with a constant cost for each internal node, then the total cost will be $T_\infty = O(\log (n) + k)$ (which is the span). I also can get other measures like the total work $T_1 = O(n + kn)$, and the parallelism $\frac{T_1}{T_\infty} = \frac{n + nk}{k + \log n}$.

Another performance measure of interest is the speedup, which is defined as $\frac{T_1}{T_p}$ (where p is the number of processors used to compute $T_p$).

Finally my question is how do I get $T_p$ (analytically) so I can calculate the speedup? I cannot simply divide $T_1/p$ since in the first levels of the graph/tree I won't be using all the processors.

Is there any more elegant expression for this than simply dividing the height of the tree before and after $\log p$?

Answer 1

Since you know that you must process each element and tasks are independent, i.e., the algorithm is embarrassingly parallel, in the Dynamic Multithreading model you should simply use a parallel for instead of spawning threads as you do, and let the compiler implement this optimally.

The work (sequential time) is $T_1 = O(nk)$ because you need to process each element and each element requires O(k) time. The span is $T_\infty = O(log n + k)$, and the parallelism is $T_1 / T_\infty = nk / (log n + k)$. In general, you know that, regarding $T_p$, we can only say that:

$T_1/p \leq T_p \leq T_1/p + T_\infty$

$T_\infty \leq T_p \leq T_1/p + T_\infty$

This is because $T_p$ is a function of the work, span, size $n$ and scheduler behavior. And $T_\infty$ actually means for your algorithm $p = n$.

Now, let's analyze what happens to the speedup by using the Generalized Amdahl's law (derived by Lee). This law describes the speedup of parallel applications in which the computation is made of phases and in each phase a different number of processors is actually used. Think about each level of the directed acyclic graph corresponding to the computation as a phase.

Let $q_i$ be the percentage of a parallel application executed simultaneously by $i$ processors; then, we have:

${T_1} = \sum\limits_{i = 1}^p {{q_i}} {T_1}$

${T_p} = \sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} {T_1}$

Therefore, the speedup is

$\frac{{{T_1}}}{{{T_p}}} = \frac{{\sum\limits_{i = 1}^p {{q_i}} {T_1}}}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} {T_1}}} = \frac{{\sum\limits_{i = 1}^p {{q_i}} }}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }} = \frac{1}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }}$

Why is this useful? Because in general it allows you to derive useful bounds. For instance, assuming $q_i = 1/p$ then we can derive an upper bound for the speedup as follows:

$\frac{{{T_1}}}{{{T_p}}} = \frac{1}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }} = \frac{1}{{\frac{1}{p}\sum\limits_{i = 1}^p {\frac{1}{i}} }} = \frac{p}{{\sum\limits_{i = 1}^p {\frac{1}{i}} }} \leqslant \frac{p}{{\log p}}$

In your algorithm, $q_i$ is different from zero only for values of $p$ which are powers of 2; i.e., $q_i = 2^i, i = 0,...,\log p$. In the corresponding summation $q_i$ will be divided by $2^i$, giving rise to a summation in which each term is 1. As an example, for $p=16$ the nonzero $q_i$ values are 1,2,4,8,16 and these values must be divided respectively by 1,2,4,8,16 so the sum is 5 and the speedup is 1/5. In general, the speedup of your algorithm is:

$\frac{{{T_1}}}{{{T_p}}} = \frac{1}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }} = \frac{1}{{\sum\limits_{j = 0}^{\log p} {\frac{{{2^i}}}{{{2^i}}}} }} = \frac{1}{{(\log p) + 1}}$

Now compare this with the performances you can obtain in the message passing model, in which your algorithm is executed on $p$ processors. Since the algorithm is embarrassingly parallel, $T_p = O(\frac{n}{p} k)$ (domain decomposition is trivial and requires O(1) time) and the speedup is (as expected for an embarrassingly parallel algorithm) $T_1/T_p = p.$

Answer 2

I would say that the speedup is asymptotic to 1/p because it's only the top levels of the tree which can't use all processors (e.g. where the number of nodes is less than p). As n approaches infinity this becomes an ever smaller proportion of the algorithm.