There exists a program that must execute 10 12 instructions in order to solve so

Question

There exists a program that must execute 1012 instructions in order to solve some problem. There exists a single processor system that can solve the problem in 106 seconds. Therefore, on average, the single processor system executes 106 or 1,000,000 (a million) instructions per second. The program is subsequently parallelized for execution on a distributed-­memory system that has p processors, where each processor will execute 1012 / p instructions and each processor must send 109(p-1) messages. Assume there is no additional overhead in executing the parallel program such that the program will complete after each processor has executed all of its instructions and sent all of its messages and there will not be any delays due to things such as waiting for messages.

1. If it takes 10^(-9) seconds to send a message, how long will it take the program to run with 1,000 processors if each processor is as fast as the single processor (above) on which the serial program was run?

2. Answer the same question as above, however here it takes 10^(-3) seconds to send a message?

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 T
• Subjects

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