How to calculate Amadahl's Law for threading effectiveness

Question

Its easy to find and understand the function definition for Amadahl's Law, but all of the working examples I was able to find were either too vague or too academic/cerebreal for my tiny pea brain to understand.

Amadahl's Law takes to parameters: F, the % of a task that cannot be improved via multi-threading, and N, the number of threads to use.

How does one calculate F with any degree of accuracy?

How do you look at a piece of code and determine whether that will be improved by multi-threading?

Answer 1

It's relatively easy to say which parts of your code certainly won't benefit from multi-threading: sequential parts. If you have to carry out a series of small steps in order, muli-threading won't help because you always need to wait for one step to be done before starting the next. Many common tasks aren't (necessarily) sequential in this sense: for example, searching a list for a number of items. If you want to extract every red item from a list, you can share parts of the list among several threads and collect all the red items from each part into a final result list. The difficulty in concurrent programming lies in finding efficient ways of doing this for real problems.

At a lower level you can talk about data dependency: a particular instruction or block depends on a previous block if it uses the results of that block's calculations in its own. So (pseudocode):

Block one:
load r1 into r2
add r1 to r3 into r4


Block two:
load r4 into r1
add 3 to r4 into r4

block two depends on block one: they must be executed in order. Here:

Block one:
load r1 into r2
add r1 to r3 into r4

Block two:
load r1 into r3
add 3 to r1 into r1

that isn't the case. This isn't directly useful for concurrency, but hopefully it illustrates the point more concretely. It also illustrates another problem in handling concurrency: as abstract blocks functionality these two can be run in parallel, but in the concrete example given here they're reading/writing some of the same registers, so a compiler/pipeliner/whatever would have to do more work to make them run together. This is all very complex, but is covered beautifully in http://www.amazon.com/Computer-Architecture-Quantitative-Approach-Edition/dp/1558605967.

Which other parts don't benefit from multi-threading depends on your programming environment and machine architecture.

As for how to get a percentage, there's probably some hand-waving involved in a practical case - I doubt you'll ever get a precise number. If you divide your code up into functional units and profile the execution time in each, that would give you a roughly appropriate weighting. Then if one part that takes up 90% of the execution time can be improved with multi-threading, you say that 90% of your 'task' can be so improved.

Answer 2

Amdahl divides all work into two groups: Perfectly parallelizable and not at all parallelizable.

Think of the latter one as the piece of work that you can't ever get rid of. You can get rid of the former perfectly bay adding resources.

If you read a text file and process it line by line, you can never get rid of reading the file sequentially to parse the lines. You can parallelize the individual lines however. If reading the files take 1s your code will never run any faster than that.

For real code, you can hook up a profiler to see how much time is spend on each part. Hopefully, you can classify each part into one of the categories. Once you have done that you can easily estimate the speed-up and it will be pretty accurate.

Answer 3

You should look on the algorithm not to the code if you want to see what can be improved by multithreading.

Typically, parallel algorithms should be designed as parallel from the ground up. It is much harder to "parallelize" code instead of the algorithm itself.

Look on dependencies in memory access (spatial dependencies), look on the sequence of operations (temporal dependencies), know your computer architecture in deails and you will know how to build a proper algorithm for your task.

According to formula itself - Wiki has very good explanation http://en.wikipedia.org/wiki/Amdahl's_law