2.6k views

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.6k views
0
@arjun sir

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.

by (299 points)
selected
0
In 2 CPU system, once 20% sequential instructions executed rest 80% can be executed parallel by 2 CPUs which can be done in 40 sec time. similarly for 4 CPU 20% instructions can be executed in 20 sec and remaining 80% instructions can be divided equally by 4 CPUs and can complete in 20sec because parallel system as mentioned in Q. so total time for 4 CPU system = 20 + 20 = 40 sec.
0
in 2 CPU first 20% work will finish then only 80% of work will be divided
therefore 20 + 40 = 60 secs
+1 vote
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.
by (345 points)