Question

11. (12 pts.)Consider a program where 25% of its execution is serial and the remainder is parallel (i.e., its performance scales linearly in the number of cores for an arbitrary number of cores). The performance of the serial portion of the program is directly proportional to memory access latencies.

1) Which is better enhancement,

a)Enhance the system with 3 cores,

b) Reduce the serial processing time by half.

Show your work.

2) What is the maximum speedup that can be achieved for a) and b)? (show your work)

Answer 1

The Amdahl's law states that speed is equal to (Time with serial implementation)/(Time with parallel implementation)

ie, Speed up

S_n=1 ∕ (S+(P/n)

Where, S_n -> Speed up

S -> Time to execute Serial portion of program

P ->Time to execute Parallel portion of program

n -> Number of cores

1)

In the given question 25% of program is sequential and 75% is parallel

now let us look in both enhancements

a) Enhance the system with 3 cores

S_n=1 ∕ (S+(P/n)

here, S=25%

P=75%

n=3

there for S_n=1 / ((0.25)+(0.75) / 3)

=1 / ((0.25)+(0.25))

=1 / (0.5)

= 2

b) Reduce the serial processing time by half.

  S_n=1 ∕ (S+(P/n)

here S=0.25 / 2 = 0.125

P=0.75

nothing said about number of cores so let us take it as 1

there for S_n=1 / ((0.125)+(0.75))

= 1 / (0.875)

= 1.142

Enhancing system with 3 cores is better

2) From the above work we can understand that maximum speed up of a is 2 and for b it is only 1.142