# Work and depth of DAG - problem in understanding exam question

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

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?

$$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$$.