Question

Another different program consists of a purely sequential part that requires 20 seconds to execute on a single-core processor. The sequential part must execute first and is followed by a parallel part containing 4 independent tasks each of which takes 12 seconds to run?

a) What is the total execution time for the entire program on the single-core processor?

b) Compared to the single-core processor, what is the actual speedup achieved by running the program on a 4-core version of the processor?

c) What speedup is predicted by Amdahl’s law for the program running on the 4-core system compared to the single-core system?

Recall that for multi-processor or multi-core systems Amdahl’s law states:

            Speedup = N / [f + N(1-f)]

where f is the fraction of the total execution time accounted for by the parallel part and N is the number of cores on the multi-core system.

Answer 1

Answer a

As processor is single core, each program will be running in sequential manner whether sequential program or parallel.

Total time to execute = 20 seconds + 4*12 seconds = 68 seconds

Answer 2

Speed up can be achieved if we introduce multiple cores for parallel program to be run on. With 4 cores, sequential program will be running on one core first then after that independent 4 tasks of parallel program can be executed on individual core simultaneously.

Total time to execute = 20 Seconds + 12 seconds = 32 seconds.

Speedup = 68/32 = 2.125

Answer 3

According to Amdahl's law

Cores N = 4 cores

Fraction f = (12*4)/68 = 12/17 [Total execution time of parallel part versus total execution time]