Calculate performance gains using Amdahl's Law

Question

I am puzzling with Amdahl's Law to determine performance gains and the serial application part and fail to figure out this one.

Known is the following:

S(N) = Speedup factor for (N) CPU's
N = Number of CPU's
f = The part of the program which is executed sequential
S(N) = N / ( 1 + f * ( N - 1 ) ) 

If I have 4 CPU's and a speedup factor (performance gain) of 3x. What would f be?

My guess:

S(N) = 3 (that's our performance gain using 4 CPU's)
N = 4

So entering these values in the formula:

3 = 4 / ( 1 + f * ( 4 - 1 ) )

Am I correct when I say that f = 0,11? Or do I need to set S(N) to 1 (so divide by 3)? Or am I doing something else wrong?

Extensive

Answer 1

A classmate of mine gave the (so far working/right) answer for this.

I made the following class: REMOVED TO COUNTERACT CONFUSION.

This should solve it.

EDIT:

Ok, the previuos answer is wrong, but I found the solution.

You first calculate The part that can be done parallel (it's on wikipedia but it took me a while to understand) and THEN you calculate the serial part.

so the final class becomes this:

/**
* @param s - The maximum performance profit. 
* @param n - The amount of processors that are usable..
* @return f - The sequential part of the program.
*/
public final double sequentialCalculation(final double s, final double n) {
    double p = 0; //the part that can be executed in parallel
    double f = 0;

    if (s <= 0) {
        throw new IllegalArgumentException("S > 0");
    }

    if (n <= 0) {
        throw new IllegalArgumentException("N > 0");
    }

    p = ((1 / s) - 1) / ((1 / n) - 1);

    f = 1 - p;

    return f;
}

You are welcome.

Cesura

Answer 2

I think you are thinking about it a little wrong if this is the equation you're supposed to be using, so let me try to explain.

f is the percentage (aka, 0 <= f <= 1) of the time your program spent in the part of the code that you didn't parallelize in the single core implementation. For example, if you have a program like this:

// this takes 15 seconds
init();

for (int i = 0; i < 10; i++) {
    // this takes 10 seconds, and will be split
    // between threads when in parallel
    calculate();
}

// this takes 5 seconds
finalize();

This will run (in serial) in 15+(10*10)+5=120 seconds. However, if implemented in parallel, there are 20 seconds of execution that can't be split amongst multiple cores. This means that even if the parallel piece is sped up so it only takes 10 seconds to perform all 10 iterations, the whole program will still take 30 seconds. This is what f helps tell us - how much of the problem can benefit from parallelization. In this example, as 20 seconds out of the total 120 must be done serially, f = 20/120 = 1/6.

Using this new value of f, you can get the speed up according to Amdahl. One disclaimer - this is far from the only way of measuring speed up, and different methods have their own advantages and disadvantages.

Sharynshashlik

Thanks Tyler, I mostly understand your answer. In my example I want to calculate the part which is done serially. I need to figure this out before I can get through the rest of my homework ;-) – Extensive