Question

A certain program consists of three independent parts A, B and C that can execute in parallel on separate processors within a multiprocessor system. None of the parts can be further subdivided and each part must execute on a single processor. Part A requires 78 billion cycles to complete, part B requires 40 billion cycles to complete and part C requires 62 billion cycles. The program is executed on an SMP system with 4 identical processors all running at the same 2 GHz clock rate.

a) How long does it take to execute the entire program (all 3 parts) if only one of the processors is used to execute the program (the other 3 processors remain idle)?

b) What is the minimum time required to execute the entire program (all 3 parts) if only two of the processors are used to execute the program (the other 2 processors remain idle)?

c) What is the minimum time required to execute the entire program (all 3 parts) if all 4 processors are used?

Answer 1

(a) If only 1 processor works, all the parts will be sequentially executed hence:
the total time required will be = (78+40+62) x 10^9 cycles / 2GHz = 90 seconds

(b) If only two processors are working then to avoid starvation of minimum time consuming program results
in executing Part B and C together on a processor while A on another processor (as it required highest cycles)
Hence the minimum time required will be: (40+62 = 102) billion cycles / 2GHz = 51 seconds

(c) With all the four processors working, the minimum time required will be that of the highest time consuming program (as they are running in parallel and can't be further subdivided hence leaving the 4th processor unused).
Hence the required time = 78 billion cycles / 2GHz = 39 seconds