Question

A certain program is executed on a multi-core system and consists of two parts: Part1 and Part2. Part1 is a single task that is purely sequential and can only be performed by a single processor core. Part2 consists of N independent tasks. Each task in Part2 takes half the time required for the single task in Part1 and must be performed by a single processor core.

a) If the number of cores is 16 and N (the number of independent tasks in Part2) is 32, what is the greatest percentage of the potential speedup that can be provided by the 16-core system compared to a using only one core for the entire program? Recall that the potential speedup is just the number of cores in the multi-core system.

b) For this 16-core system to achieve 80% of its potential speedup, how many independent tasks (each of which takes half the time required for the single task in Part 1) must Part2 contain? Your answer should be a whole number since there are no partial tasks.

c) Is increasing the number of tasks in Part2 an example of weak scaling or an example of strong scaling?

Answer 1

Answer a

Assuming that serial part takes time equal to X

Individual task in Parallel part takes half of the time of serial part = 0.5X

using Amdahl's

Here number of independent tasks in parallel part is 32 which means total time needed by parallel part if executed on single core machine = 32*0.5X = 16X

P is the fraction of parallel part execution time vs total execution time = 16/(16+1) = 16/17

Answer b

We know that maximum speedup of any application is limited by the fraction of sequential part. If sequential part fraction becomes zero then maximum speedup can be achieved will be equal to number of processors or cores running the application.

In this case maximum speedup will be 16 as number of cores = 16

To achieve 80% of this means speedup = 0.8*16 = 12.8 let's assume we need T number of independent tasks in parallel part.

so fraction of parallel part = T*0.5X/(T*0.5X+X) = 0.5T/(0.5T+1)

So number of independent tasks required to 80% of potential speedup with 16 cores is 118

Answer c

This is example of weak scaling as the number of processing elements are fixed but the problem size is increased per processing element.