Suppose a program must execute 1012 instructions in order to solve a particular

Question

Suppose a program must execute 1012 instructions in order to solve a particular problem. Suppose further that a single processor system can solve the problem in 106 seconds (about 11.6 days). So, on average, the single processor system executes 106 (a million) instructions per second. Now, suppose that the program has been parallelized for execution on a distributed-memory system. If the parallel program uses p processors, each processor executes (10 12)/p instructions and must send (10 9)(p-1) messages. Finally, suppose that there is no additional overhead in executing the parallel program. That is, the program will complete after each processor has executed all of its instructions and sent all its messages, and there won't be any delays due to waiting for messages. a) Suppose it takes 10'9 seconds to send a message. How long will it take the program to run with 1000 processors, if each processor is as fast as the single processor on which the serial program was run? b) Suppose it takes 10'3 seconds to send a message. How long will it take the program to run with 1000 processors?

Explanation / Answer

ANSWER:

p=1000

No. of instructions executed by every processor = 10^9

Hence to execute instructions, time taken = 10^3 sec.

No. of messages = 10^9(999)

a) Total time = Time due to execution + time due to sending of messages = 999 + 1000 = 1999 sec.

b) Total time = 1000 + 10^6*999 = 999*(10^6) sec

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.