He is the author of the blog "Mechanical Sympathy":
Among other things, he talks about: how the JVM can, at times, be faster than native code; lock-free algorithms and cache-coherence; performance and scalability in concurrent algorithms; fast logging systems.
Juicy stuff.
Monday, March 18, 2013
Monday, March 11, 2013
The End of multi-core Scalability is near
In 1988 Maurice Herlihy proved in his seminal paper "Impossibility and universality results for wait-free synchronization", that a Wait-Free consensus can be solved for any number of threads using a CAS. He didn't explain how it could be done, but in practice this means that you can use a CAS to write concurrent Wait-Free algorithms, as long as you don't put the CAS in a loop of retries. Doing that is a necessary but not sufficient condition.
Assuming you figure out how to implement whatever algorithm is that you want to make, in a Wait-Free way, there is still a problem: you usually want it to be Scalable, or have Low-Latency, or both. If you're only interested in Low-Latency, then you're safe, and the rest of this post doesn't apply, but if you need the algorithm to be Scalable, then you have a big problem, which can be summarized by the plot below, and has been extensively described in this post, and this:
You see, to be truly scalable with the number of cores/threads, an algorithm has to be Wait-Free-Population-Oblivious (WFPO), or very close to it. Creating such an algorithm is usually an insurmountable difficulty on its own, but even if you invent one, or copy from someone who has done it for you, there is still a problem, and the problem is related to the scalability of the CAS instruction on current CPUs.
The CAS instruction enforces cache-coherency on the variable that is being modified and its corresponding cache-line. This means that if several cores are contending for that cache-line, there must be an algorithm to solve this, and it's implemented as the MESI protocol or one of its variants.
The problem with this approach is that it causes the time required to ensure cache-line consistency to grow linearly with the number of cores competing for the cache-line. This means that the time required to complete a CAS operation grows linearly (or nearly) with the number of threads contending on the modified variable.
Let me repeat it because it's the single most important idea on this post: "The more threads you throw at an algorithm that uses CAS on a single variable, the slower it will be to complete each CAS operation".
For example, let us say you have a system with 32 cores, and you make an application that uses 4 threads, and is capable of doing 100M CAS per second per thread when they are competing on the same variable, then you can expect that if you run the same code with 8 threads that each thread will be capable of doing 50M CAS per second per thread. If you run it with 16 threads, you can expect each thread to complete no more than 25M CAS per second per thread, and so on, as you increase threads until you run out of cores.
The math is pretty simple, but let's spell it out here:
4 threads x 100M CAS = 400M CAS per second
8 threads x 50M CAS = 400M CAS per second
16 threads x 25M CAS = 400M CAS per second
Yes, they all do the same overall number of operations even though the first one is occupying only 4 cores and the third one is using up 16 cores.
Don't believe me? Then run this code snippet with a batchSize large enough to finish in a few seconds, and then repeat with a different number of threads and compare the times:
Why does this happen? Well, the details are long and obscure (at least to me), but it's all related to cache-coherency protocols, like MOESI and MESIF and stuff like that.
What can you do about it?
Nothing... unless you can come up with a cache-coherence protocol whose time to complete doesn't grow linearly with the number of cores.
Summarizing, even if we start inventing new WFPO algorithms, the limit on multi-core scalability is still there, and it is quite low, which means all our work was kind of in vain because the algorithm we so carefully designed to always finish in a finite number of steps, now uses instructions whose time to complete grows with the number of threads and therefore, is not scalable at all.
I don't know about you, but to me, this suckz :(
As such, I would like to address an open letter to the CPU architects and engineers at Intel, ARM, and AMD:
Dear CPU engineers,
Please design a cache-coherence protocol that scales with the number of cores reading/writing on a cache-line.
I know that what I'm asking of you might be impossible, but unless one of you comes up with a protocol where the time to access a dirty cache-line doesn't grow with the number of cores, then pretty soon the companies you work for will not be able to sell new CPUs with more cores, because no one will be able to use those new cores for anything useful.
Think about it, really. I mean, how many cores can you have on your smartphone/tablet/PC ?
8? 16? 32?
After a certain point it won't matter because, there will not be enough different applications running at the same time on the device, and we will lose the edge given by parallelization, and the bottleneck of concurrency will show up. It's true that many people install a gazilion apps in their smarthpones, but they aren't running them all simultaneously.
Parallelization will only take you so far, and at some point the future, unless you can come up with a way to allow developers to write scalable concurrent algorithms, you, or most of you, will be out of a job, because no one will buy the new CPUs your company makes.
Look at it from this perspective: Your job depends on it, so better start working on it now!
Thanks, and good luck.
Sincerely,
Pedro
Yes, I know, this is about as much good as writing a letter to Santa-Claus asking for a real-size-latest-model Ferrari, but hey, you gotta try.
I want to end on a slightly more positive note, and say that not all hope is lost in the land of scalable algorithms and data-structures:
First, in the more distant future, someone might come up with a better computer architecture than the current von-Neumann, that doesn't have the inherent physical limitations that we see today when the CPU accesses memory. Perhaps something more akin to neural-networks, or something even stranger, that will change the way we think about algorithms and computation in general. Whatever it may be, it is still a long way away, and no matter how smart are the people that come up with it, they still have to follow the laws of physics (particularly the 2nd law of thermodynamics).
Second, we already have things like Hadoop, that can scale algorithms almost limitless. I know it's a trick, they're changing concurrency into parallelization, and not all algorithms can be transformed in a such a way, with anything requiring a queue being a good counter-example. Still, for those algorithms that can be "map-reduced", the future (and present) looks promising, with lots of room for improvements and growth.
Third, we still have some more years until the scalability ceiling on Lock-Free and Wait-Free algorithms starts to be a real problem, so until then, enjoy the ride and the sunny weather, and let "Future You" take care of it ;)
Assuming you figure out how to implement whatever algorithm is that you want to make, in a Wait-Free way, there is still a problem: you usually want it to be Scalable, or have Low-Latency, or both. If you're only interested in Low-Latency, then you're safe, and the rest of this post doesn't apply, but if you need the algorithm to be Scalable, then you have a big problem, which can be summarized by the plot below, and has been extensively described in this post, and this:
You see, to be truly scalable with the number of cores/threads, an algorithm has to be Wait-Free-Population-Oblivious (WFPO), or very close to it. Creating such an algorithm is usually an insurmountable difficulty on its own, but even if you invent one, or copy from someone who has done it for you, there is still a problem, and the problem is related to the scalability of the CAS instruction on current CPUs.
The CAS instruction enforces cache-coherency on the variable that is being modified and its corresponding cache-line. This means that if several cores are contending for that cache-line, there must be an algorithm to solve this, and it's implemented as the MESI protocol or one of its variants.
The problem with this approach is that it causes the time required to ensure cache-line consistency to grow linearly with the number of cores competing for the cache-line. This means that the time required to complete a CAS operation grows linearly (or nearly) with the number of threads contending on the modified variable.
Let me repeat it because it's the single most important idea on this post: "The more threads you throw at an algorithm that uses CAS on a single variable, the slower it will be to complete each CAS operation".
For example, let us say you have a system with 32 cores, and you make an application that uses 4 threads, and is capable of doing 100M CAS per second per thread when they are competing on the same variable, then you can expect that if you run the same code with 8 threads that each thread will be capable of doing 50M CAS per second per thread. If you run it with 16 threads, you can expect each thread to complete no more than 25M CAS per second per thread, and so on, as you increase threads until you run out of cores.
The math is pretty simple, but let's spell it out here:
4 threads x 100M CAS = 400M CAS per second
8 threads x 50M CAS = 400M CAS per second
16 threads x 25M CAS = 400M CAS per second
Yes, they all do the same overall number of operations even though the first one is occupying only 4 cores and the third one is using up 16 cores.
Don't believe me? Then run this code snippet with a batchSize large enough to finish in a few seconds, and then repeat with a different number of threads and compare the times:
for (int i = 0; i <
batchSize/2; i++) {
counterLong.compareAndSet(0, 1);
counterLong.compareAndSet(1, 0);
}
or you can download this test at sourceforge.Why does this happen? Well, the details are long and obscure (at least to me), but it's all related to cache-coherency protocols, like MOESI and MESIF and stuff like that.
What can you do about it?
Nothing... unless you can come up with a cache-coherence protocol whose time to complete doesn't grow linearly with the number of cores.
Summarizing, even if we start inventing new WFPO algorithms, the limit on multi-core scalability is still there, and it is quite low, which means all our work was kind of in vain because the algorithm we so carefully designed to always finish in a finite number of steps, now uses instructions whose time to complete grows with the number of threads and therefore, is not scalable at all.
I don't know about you, but to me, this suckz :(
As such, I would like to address an open letter to the CPU architects and engineers at Intel, ARM, and AMD:
Please design a cache-coherence protocol that scales with the number of cores reading/writing on a cache-line.
I know that what I'm asking of you might be impossible, but unless one of you comes up with a protocol where the time to access a dirty cache-line doesn't grow with the number of cores, then pretty soon the companies you work for will not be able to sell new CPUs with more cores, because no one will be able to use those new cores for anything useful.
Think about it, really. I mean, how many cores can you have on your smartphone/tablet/PC ?
8? 16? 32?
After a certain point it won't matter because, there will not be enough different applications running at the same time on the device, and we will lose the edge given by parallelization, and the bottleneck of concurrency will show up. It's true that many people install a gazilion apps in their smarthpones, but they aren't running them all simultaneously.
Parallelization will only take you so far, and at some point the future, unless you can come up with a way to allow developers to write scalable concurrent algorithms, you, or most of you, will be out of a job, because no one will buy the new CPUs your company makes.
Look at it from this perspective: Your job depends on it, so better start working on it now!
Thanks, and good luck.
Sincerely,
Pedro
Yes, I know, this is about as much good as writing a letter to Santa-Claus asking for a real-size-latest-model Ferrari, but hey, you gotta try.
I want to end on a slightly more positive note, and say that not all hope is lost in the land of scalable algorithms and data-structures:
First, in the more distant future, someone might come up with a better computer architecture than the current von-Neumann, that doesn't have the inherent physical limitations that we see today when the CPU accesses memory. Perhaps something more akin to neural-networks, or something even stranger, that will change the way we think about algorithms and computation in general. Whatever it may be, it is still a long way away, and no matter how smart are the people that come up with it, they still have to follow the laws of physics (particularly the 2nd law of thermodynamics).
Second, we already have things like Hadoop, that can scale algorithms almost limitless. I know it's a trick, they're changing concurrency into parallelization, and not all algorithms can be transformed in a such a way, with anything requiring a queue being a good counter-example. Still, for those algorithms that can be "map-reduced", the future (and present) looks promising, with lots of room for improvements and growth.
Third, we still have some more years until the scalability ceiling on Lock-Free and Wait-Free algorithms starts to be a real problem, so until then, enjoy the ride and the sunny weather, and let "Future You" take care of it ;)
Friday, March 8, 2013
Why is Wait-Free so important?
Lock-Free (full synchronization)
Imagine a Lock-Free algorithm or data-structure with a single function, where this function spends all of its time doing synchronization.Let's say that each function call in single threaded mode takes 10 ns, and with every added thread that calls the same function, we will get contention on the synchronized state (variables).
It is easy to see, that if you have a single thread, the average number of times the function is called and returns, is 1 every 10 nanoseconds. Let's call this: the number of tasks per 10 ns. If you add more threads, they will increase the time the other threads take to complete, because only one will be able to win the consensus.
Remember that Lock-Free gives guarantee that one thread is making a progress, but it doesn't say which one, and in this particular case, every time one thread makes a progress (completes a task) the other threads will have to start over:
In the plot, W means that the thread has won and L stands for a loss, that implies a retry.
Lock-Free (small synchronization)
The above schematic doesn't accurately describe most of the Lock-Free algorithms in existence because, they don't spend all of their time doing synchronization, instead, the largest slice of time is usually spent doing some kind of calculation related to the algorithm itself, which doesn't necessarily require re-computation in case of another thread winning, and only a portion of the time is actually spent doing the synchronization.As such, let us imagine a case where the function takes 10 ns to complete its task, but only the first 2.5 nanoseconds are spent doing synchronization. It is easy to see that on average, per 10 ns, we could have multiple tasks running concurrently on multiple threads/cores, and up to 4 threads would be able to run simultaneously, as shown in the schematic below:
In the example described above, the synchronization time takes (at least) a quarter of the 10 ns of the time spent by the function.
Moreover, if draw a plot of the overall performance of this algorithm as the number of threads increases, we would see something that scales almost linearly up to 4 threads, and then hits a ceiling and doesn't go above it, and may even reduce the performance if the number of threads is further increased:
Notice we're assuming that we have more than 4 cores where we can run these 4 or more threads.
Wait-Free-Population-Oblivious
Consider now a different scenario, where the algorithm we have is Wait-Free-Population-Oblivious, or WFPO for short. Let us say that the algorithm is 3 times slower that the previous Lock-Free algorithm, such that it takes 30ns to complete a single task, but it is WFPO which by definition means that, as long as you have enough cores, all threads are guaranteed to make progress, and because it is WFPO and not just Wait-Free, the number of extra instructions does not depend on the number of threads and, therefore, remains (more or less) constant as the number of threads increases.The schematic would like like this:
The plot of the overall performance of this algorithm as the number of threads increases can be seen below:
Notice that the performance keeps on scaling until you run our of cores to run the new threads, or the synchronization primitives you are using, stop being WFPO due to some hardware limitation.
Algorithm optimization
Let's go back to the Lock-Free scenario with a synchronization during 1ns and imagine that some smart guy was able to optimize the time it takes to do the calculation, and now instead of taking 7.5 ns, it takes just 2.5 ns, which means that in single-thread mode the performance of the algorithm has just doubled. How much performance would we gain for the multi-threaded code?The answer is not trivial, and it is 0. The reason why it is zero, is because we can only run threads while there is no contention, so even if the rest of the code runs faster, each thread must still have to contend with the other threads and only one will win, while the other will have to contend again:
For the WFPO algorithm, if you manage to cut 5ns out of the computation portion, you get a performance increase of about 17% overall (5 ns / 30 ns) .
Now you say: Well, what if we can optimize the synchronization code in the Lock-Free algorithm so that goes from taking 2.5 ns to spending only 1 ns?
Yeah, you could do that, but you would probably have to re-design the whole synchronization part, which is the same as saying you made up a new Lock-Free consensus mechanism, which is in itself a publishable result and not an easy feat (to say the least). Only guys like Maurice Herlihy, Nir Shavit, or Doug Lea, are capable of that kind of thing... are you up to the task? ;)
Wait-Free
How about vanilla Wait-Free (non Population-Oblivious)?Well, it depends: if the number of operations grows very gently with the number of threads, then the performance may scale and increase.
If the number of operations increases quadratically with the number of threads, then you're probably out of luck, and that algorithm won't be much better than a Lock-Free one (or may be even worse).
Basically, non-Population-Oblivious Wait-Free algorithms and data-structures will have a behavior somewhere between the Lock-Free ones and the WFPOs.
Conclusion
Lock-Free algorithms and data-structures have an intrinsic scalability ceiling, which means that at a certain point, no matter how many more threads/cores you throw at the problem, it will not improve the overall performance and may in fact decrease it due to high contentionAdding more threads to a Lock-Free algorithm is good only to a certain point, and you would be surprised of how low that limit can be for certain algorithms and data-structures. If you're thinking of the future, or your application is meant to run on a large number of threads/cores, then aim for Wait-Free-Population-Oblivious, otherwise you're not going very far.
Summarizing in one sentence, forget about Lock-Free and regular Wait-Free, if you want to design an algorithm that scales for a large number of threads, you need something that is Wait-Free-Population-Oblivious!
Actually, the title of this post should have been: "Why is Wait-Free-Population-Oblivious so important"?
Subscribe to:
Posts (Atom)