Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Amdahl's Law Example in C#

I was working with some paralization and that brought me looking into Amdahl's law. I've read a number of posts on the topic;

Calculate performance gains using Amdahl's Law

How to calculate Amadahl's Law for threading effectiveness

http://en.wikipedia.org/wiki/Amdahl%27s_law

...but was hoping to find a C# example showing it in practice. Searching has proved no results. In theory it should be possible to make a serial application, time the parallelisable parts, run a parallelised version, recording the length it takes the parallel parts and compare the difference (knowing how many processors are being used) to the result of Amdahl's function. Is this correct and is anyone aware of such an example existing?

like image 793
windowsgm Avatar asked Jan 14 '13 20:01

windowsgm


People also ask

What is Amdahl's Law with example?

Example: Let a program have a portion fE of its code enhanced to run 4 times faster (so fI = 4), to yield a system speedup 3.3 times faster (so S = 3.3).

How do you calculate speed using Amdahl's Law example?

To find this out, you simply need to divide how long the action took with a single core by how long it took with N cores. In our example, for two cores the speedup is 645.4/328.3 which equals 1.97 . Fill this in for each row and we can use these numbers to determine the parallelization fraction of the program.

What is Amdahl's Law in operating system?

In computer programming, Amdahl's law is that, in a program with parallel processing , a relatively few instruction s that have to be performed in sequence will have a limiting factor on program speedup such that adding more processor s may not make the program run faster.


1 Answers

Note: A complete working downloadable version of the program can be found on My Github Page

So with Amdahl's Law, we split the work in to "Work that must run in serial" and "Work that can be parallelized", so let's represent those two workloads as List<Action>:

var serialWorkLoad = new List<Action> { DoHeavyWork, DoHeavyWork };
var parallelizableWorkLoad = new List<Action> { DoHeavyWork, DoHeavyWork, DoHeavyWork, DoHeavyWork, DoHeavyWork, DoHeavyWork, DoHeavyWork, DoHeavyWork };

Where the DoHeavyWork delegate is abstracted brilliantly as:

static void DoHeavyWork()
{
    Thread.Sleep(500);
}

As you can see I've made the parallelizable workload a bit heavier for fun and to make a decent example of it.

Next we have to run both workloads in Serial to get our baseline:

var stopwatch = new Stopwatch();
stopwatch.Start();
// Run Serial-only batch of work
foreach (var serialWork in serialWorkLoad)
{
    serialWork();
}

var s1 = stopwatch.ElapsedMilliseconds;

// Run parallelizable batch of work in serial to get our baseline
foreach (var notParallelWork in parallelizableWorkLoad)
{
    notParallelWork();
}

stopwatch.Stop();
var s2 = stopwatch.ElapsedMilliseconds - s1;

At this point we have how long it took each workload to run in serial. Now, let's run it again, with the parallelizable portion parallelized.

stopwatch.Reset();
stopwatch.Start();
// Run Serial-only batch of work
foreach (var serialWork in serialWorkLoad)
{
    serialWork();
}

var p1 = stopwatch.ElapsedMilliseconds;

// Run parallelizable batch of work in with as many degrees of parallelism as we can
Parallel.ForEach(parallelizableWorkLoad, (workToDo) => workToDo()); // In Java this is Magic Unicorns

stopwatch.Stop();
var p2 = stopwatch.ElapsedMilliseconds - p1;

Now that we have the baseline and the parallelized version, we can calculate the speedup and report our findings:

var speedup = (double)(s1 + s2) / (p1 + p2);

Console.WriteLine("Serial took  : {2}ms, {0}ms for serial work and {1}ms for parallelizable work", s1, s2, s1 + s2);
Console.WriteLine("Parallel took: {2}ms, {0}ms for serial work and {1}ms for parallelizable work", p1, p2, p1 + p2);
Console.WriteLine("Speedup was {0:F}x", speedup);

And as Amdahl's Law tells you, it is hard to scale perfectly with the # of cores you have because of the serial-only work.

like image 62
Alex Moore Avatar answered Sep 23 '22 20:09

Alex Moore