In: Computer Science
A program must execute 1012 instructions to solve a problem. A single processor system can solve the problem in 106 seconds. Thus on average the single processor system executes 106 or 1-million instructions per second.
We have a new program that has been parallelized for execution on a distributed-memory system. This parallel program uses (p) processors. Here each processor will execute 1012/p instructions and each processor must send 109(p-1) messages. We will assume there is not additional overhead for the parallel program and that the program will complete after each processor has executed all of its instructions and sent all of its messages (there are no delays for things like waiting for messages).
2.a. If it takes 10-3 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 where the serial program was run?
2.b. If we upgrade our network and it now takes only 10-9 seconds to send a message. Same question – how long to run on the same 1000 processors now?