Here is my proof

[aminer10]

Hello,

I have noticed that Robert Wessel didn't understood my ideas..

So i will prove it to you right now , so follow with me carefully please...

Let say we have 4 threads, and 4 cores, and let say that each
thread is running the same parallel code, and let say we have also a serial code inside some critical section, and let say that the parallel part is
0.1% and the serial part is 0.9%, so let say that the serial part
takes 1 second(it means 0.1%) and the parallel part takes 9 seconds(it means 0.9%), what i have tried to explain to you is that the Amadhl's law or equation  is not a correct law and it doesn't give a correct results,
here is why: so if the 4 threads are all looping and looping again
for a number of times running the same parallel code and the same serial code and let say that they are contending at the same time
for the critical section, this  is why i have called an ideal contention
scenario, so if they  are contending AT THE SAME TIME for the critical section(the serial part) they will run 4 serial parts in 4 seconds in one loop  and they will run 4 parallel parts in 9 seconds in one loop, hence it will take 13 seconds in one loop , but  if you run the parallel part and the serial part serially they will take 40 seconds, so the scalability will equal 40 seconds divide by 13 seconds = 3.07X, this is the result that gives us the Amdahl's law, it's 1 /(0.1 + 0.9/4) = 3.07X, but this is not the end of the story , so follow now carefully with me, so let divide the parallel part into 9 small parts  each equal to
1 seconds, and the serial part is equal to 1 second, so if the threads
are looping and not contending at the same time for the critical section and let say that when the threads are looping the first thread will be on the first small part equal to 1 seconds of the 9 small parts of the 9 seconds of the parallel part ,  the second thread will be on the second small part equal to 1 seconds of the 9 parts of the 9 seconds of the parallel part, and the third threads will be on the third small part equal to 1 second of the 9 parts of the 9 seconds of the parallel part , and the fourth thread will be on the third small part equal to 1 second of the 9 parts of the 9 seconds of the parallel part , so imagine the 4 threads
looping again and again and not changing there places like that , so
there will be no serial part at all, cause when each thread will be on the 1 second of the serial part the other threads will not be on the the same serial part, so this is a none contention scenario , so since
there is no serial part so the scalability will be perfect and
equal to 4X , so as you have noticed the Amdahl equation gives
the scalability of the ideal contention scenario all the threads
are contending at the same time so the scalability will equal 3.07X, but if they are not contending at all the scalability will be perfect
and equal to 4X, and if you have less contention this will scale
better than 3.07X,  so now i have proved to you that the Amdahl's law
doesn't give you a correct result.



Hope you have understood my arguments and my ideas against the
Amdahl's law.




Thank you,
Amine Moulay Ramdane.

[aminer10]

Hello,

I  correct some typos, please read gain...

I will prove it to you again, so follow with me carefully please...

Let say we have 4 threads, and 4 cores, and let say that each
thread is running the same parallel code, and let say we have also a serial code inside some critical section, and let say that the parallel part is
0.1% and the serial part is 0.9%, so let say that the serial part
takes 1 second(it means 0.1%) and the parallel part takes 9 seconds(it means 0.9%), what i have tried to explain to you is that the Amadhl's law or equation  is not a correct law and it doesn't give a correct results,
here is why: so if the 4 threads are all looping and looping again
for a number of times running the same parallel code and the same serial code and let say that they are contending at the same time
for the critical section, this  is why i have called an ideal contention
scenario, so if they  are contending AT THE SAME TIME for the critical section(the serial part) they will run 4 serial parts in 4 seconds in one loop  and they will run 4 parallel parts in 9 seconds in one loop, hence it will take 13 seconds in one loop , but  if you run the parallel part and the serial part serially they will take 40 seconds, so the scalability will equal 40 seconds divide by 13 seconds = 3.07X, this is the result that gives us the Amdahl's law, it's 1 /(0.1 + 0.9/4) = 3.07X, but this is not the end of the story , so follow now carefully with me, so let divide the parallel part into 9 small parts  each equal to
1 seconds, and the serial part is equal to 1 second, so if the threads
are looping and not contending at the same time for the critical section and let say that when the threads are looping the first thread will be on the first small part equal to 1 seconds of the 9 small parts of the 9 seconds of the parallel part ,  the second thread will be on the second small part equal to 1 seconds of the 9 parts of the 9 seconds of the parallel part, and the third threads will be on the third small part equal to 1 second of the 9 parts of the 9 seconds of the parallel part , and the fourth thread will be on the fourth small part equal to 1 second of the 9 parts of the 9 seconds of the parallel part , so imagine the 4 threads
looping again and again and not changing there places like that , so
there will be no serial part at all, cause when each thread will be on the 1 second of the serial part the other threads will not be on the the same serial part, so this is a none contention scenario , so since
there is no serial part so the scalability will be perfect and
equal to 4X , so as you have noticed the Amdahl equation gives
the scalability of the ideal contention scenario all the threads
are contending at the same time so the scalability will equal 3.07X, but if they are not contending at all the scalability will be perfect
and equal to 4X, and if you have less contention this will scale
better than 3.07X,  so now i have proved to you that the Amdahl's law
doesn't give you a correct result.



Hope you have understood my arguments and my ideas against the
Amdahl's law.

And of course in my example each thread have the same number of loops and the same number of work, and each thread is running on a separate core in my example. so that you understand more my example.


Thank you,
Amine Moulay Ramdane.

[aminer10]

I wrote:
> Hello,
>
> I think i know what is my mistake: the serial part in
> the Amdahl's law is not the critical section, you must not
> confuse the two.


But, Amine,  how can you say that the serial part of the Amdahl's law is not
the critical section ?


In my example if you don't have context switches , and you have the same
number of threads than the number of cores, and the time inside the critical
section is constant and the time inside the parallel part is constant, so the Amdahl's law can predict the worst case contention scenario , that means when all the threads are contending for the same critical section, hence you can predict the worst case contention scenario by just  calculating the time inside the critical section and the time inside the parallel part and doing the Amdahl calculation, this will give you the
exact result for the worst case contention scenario, so as you have
noticed the serial part of the Amdahl equation is not only the critical section, it's the critical section with a context, so you have to take
into consideration also the context, that means the context of the worst case contention scenario.


Thank you,
Amine Moulay Ramdane.

[aminer10]

Hello,

But how can we use the Amdahl's law to predict scalability ?

You can not use the Amdahl's to predict the exact scalability,
i think , and i have explained it to you that the Amdahl's laws
in parallel computing gives you the scalability in the worst case contention scenario , so the Amdahl's calculation in parallel computing looks like the calculation of  the worst case complexity in computer science, so it can help to give the scalability
of the worst case contention scenario, so that help also
to predict worst case scalability, and if the serial part have not
a constant running time and the parallel part have not a constant runnning time you can try to find and choose a maximum bound of
the time to run the serial part and a maximum bound of the time to run the parallel part
and do the Amdahl's calculation and this will give you the scalability
for the worst case contention scenario, so the scalability will be equal
or greater than the scalability that you will find with the Amdahl's equation.



Thank you,
Amine Moulay Ramdne.


 

[aminer10]

Hello,

But Amine, you have said that the Amdahl's law predict scalability
of the worst case contention scenario , so the Amdahl's calculation in parallel computing looks like the calculation of  the worst case complexity in computer science?

That's right, cause what is, in your opinion , the purpose of the Amdahl's law if it's not to predict worst case scalability by calculating the maximum bound of time time inside the critical sections and the maximum bound of the time inside the parallel part and doing the Amdahl's calculation to predict the worst case contention scenario
hence the worst case scalability, so i think this will predict that the scalability will be equal or greater to the result that we have
found with the Amdahl's law. This is the purpose of Amdahl's law:
it's also to predict the worst case scalability.



Thank you,
Amine Moulay Ramdane.
 

[aminer10]

I have wrote:
"But Amine, you have said that the Amdahl's law predict scalability
of the worst case contention scenario , so the Amdahl's calculation in parallel computing looks like the calculation of  the worst case complexity in computer science?

That's right, cause what is, in your opinion , the purpose of the Amdahl's law if it's not to predict worst case scalability by calculating the maximum bound of time time inside the critical sections and the maximum bound of the time inside the parallel part and doing the Amdahl's calculation to predict the worst case contention scenario
hence the worst case scalability? so i think this will predict that the scalability will be equal or greater to the result that we have
found with the Amdahl's law. This is the purpose of Amdahl's law:
it's also to predict the worst case scalability."


To do a better scalability prediction, you have to use the
same number of threads than the number of cores, and each
thread must run a a separate core, to avoid context switches
and you have to use Locks that lower better the cache-coherence traffic,
such us the scalable Anderson Lock or the scalable MCS Lock
or my scalable and distributed fair Lock, and try to find a maximum
bound of the time inside your critical sections and maximum bound
inside of the time inside the parallel part , and do the Amdahl's calculation with them to find the result of the worst case scalability, so the scalability will equal or be greater to this result. I think  this is the purpose of the Amdahl's law: to predict the worst case scalability.



Thank you,
Amine Moulay Ramdne.

[Gregg_S_Intel]

If the serial portion of the computation can be executed at the same time as the rest of the computation, then it's not serial, it's parallel.  So what you're saying is, Amdahl's Law never applies, because there's no such thing as serial work.

[jimdempseyatthecove]

Or to put it a different way: When you remove from consideration the serial portion of the code, then if you balance the load amongst available threads, you will have perfect scalability.

Amdahl's law encompances the serial portion of the code. In Amdahl's "law" there is no factor of overhead in entering and leaving parallel regions of code. Critical sections are a bit different than serial sections. With regard to critical sections, threads that have yet to reach an owned critical section, and threads that have passed through the critical section, can continue to run while the critical section is held. In non-contending situations, critical sections have no impact on scalability, whereas serial sections do. Under the unique situation where all threads reach the critical section simulteanously, use of critical section is more scalabile than use of serial, when there is more work to do in parallel following the critical section. i.e. upon exiting the critical section, the exiting thread continues and one of the waiting threads resumes.

Jim Dempsey