0
$\begingroup$

I have some problems understanding the following 2 question from an exam last year, which I am preparing for this week in Parallel Programming.

DAG

Determine the Work -> $W(n) = 7$ (#vertices)

Determine the Depth -> $D(n) = 4$ (longest path)

Determine average parallelism -> $\frac{W(n)}{D(n)} = 7/4$

Ok, now the 2 questions, which I have problems with:

What is the minimum number of processors that are needed to achieve depth?

For this question I only have a vague idea: $infinity$? Because if we use Brents theorem:

$$\frac{W(n)}{p} <=T_p(n) <= \frac{W(n)}{p} + D(n)$$

maybe we can achive depth? I am not sure.

What is the number of processors larger or equal to 2 that achieves the maximum efficiency for this problem?

That should be relatively easy, but I am not sure, how I should calculate the Speedup? I know several formulas, but I do not know how to calculate the fraction, which must be run sequentially ($S=\frac{p}{1+(p-1)f)}$) or the execution times.

Can someone point me in the right direction?

$\endgroup$

1 Answer 1

1
$\begingroup$

$D = 5$ (and is not a funtion of $n$ here) and goes $1 - 2 - 4 - 5 - 6$.

What is the minimum number of processors that are needed to achieve depth?

It clearly cannot be achieved with one processor, but here is a schedule that achieves it using two processors:

Time $P_1$ $P_2$
1 1 3
2 2
3 4
4 5 7
5 6

Since $T_2 = D$, speedup is simply $S_2 = T_1/T_2 = W/D = 7/5$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.