5,496 views
4 votes
4 votes

A particular parallel program computation requires $100$ seconds when executed on a single CPU. If $20$% of this computation is strictly sequential, then theoretically the best possible elapsed times for this program running on $2$ CPUs and $4$ CPUs respectively are 

  1. $55$ and $45$ seconds
  2. $80$ and $20$ seconds
  3. $75$ and $25$ seconds
  4. $60$ and $40$ seconds

2 Answers

Best answer
21 votes
21 votes

I think answer is (D)

2 CPU :- CPU1 spends 20 secs for sequential instructions. Remaining 80 secs work is divided such that CPU1 does 40 sec work and CPU2 does 40 sec work. But CPU2 cannot start processing until CPU1 finishes its 20 sec work. Hence time required is 20 + 40 = 60sec.

4 CPU :- CPU1 spends 20 secs for sequential instructions. Remaining 80 secs work is divided such that CPU1 does 20 sec work, CPU2 does 20 sec work, CPU3 does 20 sec work and , CPU4 does 20 sec work. But CPU2, CPU3, CPU4 cannot start processing until CPU1 finishes its 20 sec work. Hence time required is 20 + 20 = 40sec.

selected by
1 votes
1 votes
This is actually an aptitude question and little bit of brain requirement question.

There are two methods to solve this question .

method1 is simple but very effective to apply in isro exam where time is very important constraint. I will not discuss method 1 because you can strike this method by your own. simplyby hit and trial.

method 2: CONVENTIONAL METHOD

Suppose we have x instructions or computations and each instruction or computation takes y seconds to execute.

according to question, on one cpu 20% of x = 0.2xy sec (sequential execution) + (100 - .2xy)second = 100 seconds.

and,   xy = 100 seconds( when one cpu)

 

let q = (100 - .2xy) seconds .

now, if two cpus then, 0.2xy + 1/2q = 50 + 0.1xy = 50 + 0,1*100 = 60 seconds  (as xy = 100 seconds explained above)

Similarly, if 4 cpus then, 0,2xy + 1/4q= 25 + 0.15xy = 40 seconds.
Answer:

Related questions

7 votes
7 votes
2 answers
1
makhdoom ghaya asked May 12, 2016
12,892 views
If a program $P$ calls two subprograms $P1$ and $P2$ and $P1$ can fail $50$% of the time and $P2$ can fail $40$% of the time, what is the failure rate of program $P$?$50$...
5 votes
5 votes
7 answers
3
8 votes
8 votes
9 answers
4