Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

aminer10

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-09-2013
08:29 PM

26 Views

Here is my proof

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.

Link Copied

7 Replies

aminer10

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-09-2013
09:25 PM

26 Views

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

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-10-2013
09:50 AM

26 Views

> 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

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-10-2013
10:11 AM

26 Views

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

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-10-2013
10:59 AM

26 Views

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

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-10-2013
11:31 AM

26 Views

"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

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-10-2013
01:52 PM

26 Views

jimdempseyatthecove

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-11-2013
05:43 AM

26 Views

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

For more complete information about compiler optimizations, see our Optimization Notice.