ISRO2018-71

Question

A particular parallel program computation requires $100$ sec when executed on a single processor, if $40\%$ of this computation is inherently sequential (i.e. will not benefit from additional processors), then theoretically best possible elapsed times of this program running with $2$ and $4$ processors, respectively, are:

1. $20$ sec and $10$ sec
2. $30$ sec and $15$ sec
3. $50$ sec and $25$ sec
4. $70$ sec and $55$ sec

Answer 1

40% sequential means 40 seconds.

Rest 60 % will be divided into 30 -30 % each parallely by the two processors hence total 40+30=70 sec

If four processors then 15% each, hence total 40+15=55 sec

Ans is D

Comments

What about $4$ processors case.

---

Already given right?

---

@Arjun Sir

Yes, it is correct.

I didn't t see that small line.

Answer 2

Option (D) is correct.

Answer 3

Ans should be option C.  

For 2 processors ___40 sec for sequential, by the time other processor will complete 40% remaining instructions. Now 20% instructions left. Both can perform 10% each. So total time is 50 sec.

Similarly for 4 processors.

Comments

For 4 processors, why can’t we do like, 

P1    P2   P3   P4 

15    15    15   15

10    10    10   10 

 

First, the 60% is divided into 4 and then, the 40% work is also divided into 4. So the total time elapsed can be 25 

Answer 4

D→

let us consider we have 100 instructions and takes 100s to complete

given that 40 instructions are sequential and 60 are branch

now when we use multiple processors time due branch will decrese whereas sequential instructions wont be affected

when 2 processors are used 60 instructions will be run on 2 processors parallelly so it’ll take 30s time

Time =40+30=70

when 4 processors are used 60 instructions will be run on 4 processors parallelly so it’ll take 15s time

Time =40+15=55