Gatebook mock

Question

Below is a precedence graph for a set of tasks to be executed on a parallel processing system $S$. 

Efficiency is defined as the ratio between the speedup and the number of processors. (The speedup is defined as the ratio of the time taken to perform a set of tasks on a single processor to the time taken to perform the same set of tasks on a parallel processor.) System $S$ has four processors $\text{CPU’s}$. If each of the tasks $T1,\dots,T8$ takes the same time, what is the efficiency of this precedence graph on $S$?

• A. $25\%$
• B. $33\:1/3\%$
• C. $50\%$
• D. $100\%$

Comments

Let time taken for a single task=1 sec

Then ,Time taken to perform 8 tasks on a single processor =8 as they have to be executed one after another.

Now, when there are 4 processor,(Say P1,P2,P3 and P4)

then allocation of tasks is done in this manner

At t=,P1-T1

At t=2, P1-T2

At t=3 ,P1-T3 P2-T4,P3-T5

At t=4,P1-T6 P2-T7,P3-T8

So total time taken=4s

Speedup=8/4=2

Efficiency=2/4=50%

---

You are right. I took 8 processors. Everthing is given in question itself☺

Answer 1

Here the key thing is :

We have 8 tasks(instructions)..So if we have one processor so task will be done sequentially so :

Time taken to 8 tasks to do sequentially = 8 time units ..Here the assumption is given :

Time taken by each instruction takes same amount of time..Hence it is 8 time units for sequential case..

Now if we consider the parallel case..So we see in the precedence graph.

a) T1 is done first

b) T2 is done next

c) T3,T4 and T5 next in parallel as we have 4 processors so we can assign 3 of them..

d) Then finally T6 , T7 and T8 similarly..

Hence in all we need now 4 time units..

Hence performance enhancement(speedup)   =   Time taken in sequential part / (Time taken in parallelised system)

                                                                  =   8 / 4

                                                                  =   2

Now efficiency is defined in the question as :

Efficiency  = Speed up / No of processors 

Hence efficiency           =       2 / 4

                                    =      50 % 

Hence C) is the correct answer..

Comments

@Habibkhan @Rahul Jain25 why are we doing just 3 processes at a time if we have got 4 processors? Is it to avoid deadlock? If yes,how would deadlock occur here?

---

shraddha priya because task $T_6$, $T_7$, $T_8$ are dependent on $T_3$, $T_4$, $T_5$.

Answer 2

Habib plz check this,

System has 4 processors. Time to complete each process i.e. Ti is same.

Reasoning :
T1 executes on Processor 1. other 3 processors are idle.
T2 executes on Processor 1, other 3 Processors are idle.
T3, T4, T5 can run parallely on different different processors. Now 3 processors are working and 1 are still unused.
T6, T7, T8 can run parallely on different different processors. now 3 processors are working and 1 are still idle.

Total 4*4 =16instance of processors(if serial). 8 out of 16 are working.(in pipeline)
Efficiency = (8/16)*100 = 50%

Similar question:

https://gateoverflow.in/52258/isro2011-10

Comments

5 processors are there in that question

Answer 3

Task	Time Taken On One Process System	Time Taken On Multi Process System
T1	1	1
T2	1	1
T3	1	1
T4	1
T5	1
T6	1	1
T7	1
T8	1
Total Time	8	4

$Speed Up = \frac{Total Time Taken On One Process}{Total Time Taken On Multiprocess}$

$Speed Up = \frac{8}{4} = 2$

$Efficiency = \frac{SpeedUp}{NumberOfProcessors}$

$Efficiency = \frac{2}{4} = 0.5 \approx 50\%$

PS: I did it like this and I hope it is not conceptually wrong.