edited by
1,554 views
8 votes
8 votes

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

  1. $25\%$
  2. $33\:1/3\%$
  3. $50\%$
  4. $100\%$
edited by

3 Answers

Best answer
8 votes
8 votes

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

selected by
0 votes
0 votes

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

0 votes
0 votes
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.

Related questions

0 votes
0 votes
3 answers
2
Lucky sunda asked Feb 7, 2017
701 views
According to me option B is correct.
4 votes
4 votes
3 answers
4
smartmeet asked Feb 7, 2017
777 views
Given TMs and L = {x/Every halts on input x } which of the following is true about L?(A) L is recursively enumerable but not recursive(B) L is Recursive but not Context...