Question

Suppose a program must execute 1012 instructions to solve a particular problem. Suppose further that a single processor system can solve the problem in 106 seconds. So, on average, the single processor system executes 106 instructions per second. Now suppose that the program has been parallelized for execution on a distributed-memory system. Suppose also that if the parallel program uses p processors, each processor will execute 1012/p instructions and each processor must send 109(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 of its messages, and there won’t be any delays due to things such as waiting for messages.

a. Suppose it takes 10-9 seconds to send a message. How long will it take the program to run with 100 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 100 processors?

Answer 1

a. If the program is run with 100 processors and each processor is as fast as the single processor on which the serial program was run, it will take 1012/100 + 109(99) × 10-9 seconds for the program to run. This works out to be about 10.011 seconds.

b. If it takes 10-3 seconds to send a message, it will take 1012/100 + 109(99) × 10-3 seconds for the program to run. This works out to be about 9.991 seconds.