please help

The Gateway to Computer Science Excellence

+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

- $55$ and $45$ seconds
- $80$ and $20$ seconds
- $75$ and $25$ seconds
- $60$ and $40$ seconds

+19 votes

Best answer

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.

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.

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

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,297 answers

198,265 comments

104,979 users