Multi-core and multi-threading performance
scalibq.wordpress.com
scalibq.wordpress.com
When he says "speedup...is limited", he means that in the mathematical sense. I.e., if you had infinite processors the program would not take zero time to complete.
Adding cores is still great when you have many threads and processes competing for CPU time. If your workload is blocking on network or disk, it means you have enough cores. Anyone who would expect additional cores to significantly speed up a single, single-threaded, application is simply in error.
If this is a myth, I don't know anyone who believes it.
9 women can't create an infant in a month?
I stand corrected. :-)
I'm not trying to pick on the article, I like it overall. I took an interest in the Anand article when I learned you could build a 64-core box for about $4000.
This is the article it's in response to http://www.anandtech.com/show/5057/the-bulldozer-aftermath-d... the crux of which is:
Some, including sources inside AMD, have blamed Global Foundries for not delivering higher clocked SKUs. Sure, the clock speed targets for Interlagos were probably closer to 3GHz instead of 2.3GHz. But that does not explain why the extra integer cores do not deliver. We were promised up to 50% higher performance thanks to the 33% extra cores, but we got 20% at the most.
So the real questions seem to be:
Is Interlagos' perfomance disappointing on pure-parallel benchmarks as well, or just those with a noticeable serial bottleneck?
If there is poor scalability, what is the cause?
and perhaps most importantly: Will my kind of workload actually benefit from Interlagos' more cores?
I think that probably what's happening is that even the pure parallel benchmarks are not scaling linearly relative to the previous generation of chips, the reason is a combination of architectural changes in the core itself and memory bus contention, and the target market for these chips is VPS hosts running hundreds of VM images.
It is interesting why they don't scale linearly and I agree that it's probably a combination of memory bus contention and/or the chip itself being a little slower.
The whole bulldozer thing seemed like a marketing stunt rather than thoughtful pursuit of higher performance to me. Given the frequency and cost of cache miss rates, Intel HT seems to get the same work done on fewer watts.
Once the upcoming chip changes get explained to the Marketing Department, however, maybe it kinda starts to sound like Marketing.
I feel like AMD saw the benchmarks available for matrix math and went for it, rather than thinking about what real-world performance profiles looked like.
But for the average parallel programs, you are (currently) right, I guess.
See https://en.wikipedia.org/wiki/Embarrassingly_parallel
Again, you said "most parallel", and not "average parallel", and this is what I have commented on.
For most embarrassingly parallel problems, a Hadoop or BOINC-like cluster made from commodity hardware may always be cheapest. But "real" supercomputers and clusters will spend the most money to reduce bottlenecks precisely because they want to run those programs that are the most limited by them.
The parent said "most parallel programs", which I translated to embarrassingly parallel problems.
> But "real" supercomputers and clusters will spend the most money to reduce bottlenecks precisely because they want to run those programs that are the most limited by them.
I agree, but from the talks I have heard most time (= money) is spent trying to work around these bottlenecks as good as possible in software (i.e. incremental algorithms, pipelining, ...) to keep the machines busy. Then again, I hear a lot more talks about software than hardware, so you may be very right. If you have any particular example in mind, I would love to read about it!
Once the a computer is actually in place (especially in a University setting), the interesting work begins, trying to write the best code for it and even improve the existing algorithms.
It seems like there are computer purchases motivated by "this machine will run our existing code faster" and those motivated by "this machine will allow us to write code for it that will prove something faster". A supercomputer seems, almost by definition, the latter.
There's a big class of "embarrassingly parallel" tasks, which usually are only limited by how quickly you can move your data to where it needs to be.
For example, to compute a nice image of points near the Mandelbrot set, you only need to move the requested parameters (4 floats) to the CPU, let it churn for a long time, and retrieve the resulting pixels (3 bytes each).
You can solve SETI by moving data around or without moving data around, but that doesn't change the inherent fact that it is a EP algorithm.
Say instead of the Mandelbrot set we're talking about generating large vectors of random numbers. This task should obviously have no data dependencies and there are algorithms that can generate random numbers much faster than an external CPU bus can transfer them to memory.
If raw bandwidth limitations mean that our CPUs see only 10% utilization is this still a "fully EP" problem? Because it should easily achieve full CPU utilization on most any machine, couldn't we say that Mandlebrot is more EP than the RNG problem?
It's more a symptom of people looking for one absolute measure of performance, because it's simply easier (less computationally expensive for the human brain) than dealing with a multi-variable valuation problem. IQ is another example, it's easier to deal with just that number instead of considering the whole person. Engine displacement (ie. 2.2L engine) is another - there's a range of variables such as max torque and max horsepower, and which engine speed maximizes those, etc.
Let's say there are three tasks, A, B, and C. C depends on A and B, but A is 4x as costly as B. Adding more cores doesn't get around that inherently sequential part, so because of overhead and cost considerations it isn't worth it to parallelize. This applies to most computational tasks: as you add more cores, the effect of the sequential part dominates more and more and you get decreasing benefits.
But what if you have one beefy processor to deal with the heavily sequential parts, and a multitude of less impressive ones to deal with the easily parallelizable parts? Doesn't that give you the best of both worlds?
Is it technically infeasible for some reason?
If one of your core is idle, the CPU will load it, if there is work to be done.
I don't know the answer myself, and would be interested if someone could clarify why Intel don't make quad cores with one core being faster than the others.
My best guess is that it's hard to keep things in sync if you have different cores on different frequencies or multipliers.
One problem that surfaces is that such asymmetric systems are harder to write software for, which can make them a bit unpopular.
The most obvious example is dynamic overclocking, where one core (that ideally works on a sequential part) gets a higher frequency (the other cores are usually underclocked at the same time). Intel calls this Turbo Boost: http://en.wikipedia.org/wiki/Intel_Turbo_Boost
In Hyper-Threading enabled cores, you also have varying performance per core, i.e. if one core only hosts one active thread that is CPU-bound the execution is faster than if one HT-core hosts two CPU-bound threads.
So, it is technically feasible, but at the same time makes scheduling for the OS harder.
Edit: And it also makes app performance less predictable. And it's one of the reasons why you need to run serious benchmarks more than a couple of times.
Nowadays, those CPUs can be on one chip: http://en.wikipedia.org/wiki/Heterogeneous_computing, http://en.wikibooks.org/wiki/Microprocessor_Design/Multi-Cor....
Also, if one builds an embedded CPU from building blocks, it is easy to put in small CPUs that perform tasks completely independent of the 'real' CPU. For example, there could be a tiny CPU that controls battery charging or tracks GPS. I do not know whether this really is done though; it could be more convenient to use of-the-shelf components for that because they are more suited for the job or because pin-outs typically are too great in demand.
In these cases the bottleneck is software fees and the easiest solution is to use higher quality cores.
I.e. an app which is heavily affected by Amdahls law doesn't really profit from more cores, where as highly parallel apps do profit a lot (see reference to Niagara architecture at the end).
What I find strange is that the article first introduces the difference between multitasking and multithreading in a rather lengthy manner, and then uses Amdahl's law, which only applies to multithreading. Especially, there is a gap on what is stated first: > "So multitasking means you are using multiple applications at the same time. Which you always do, these days." With the conclusion: > "With multi-core, your mileage may vary, depending on the algorithms used by the application (to what extent are they parallelized, and to what extent do they have to remain sequential?), and on the performance of the individual cores."
His discussion is all well when you have one app that is really needing the power and the other multitasking apps don't need much CPU (e.g. playing mp3 and such). Which is the case for most desktop systems, I'd say. For servers, it can be really different, and you could either have many processes running or one process is heavily optimized for multithreading and avoids Amdahl's law nicely. Then the discussion is kinda void.
Problems that are split up over many cores, processes or even clusters of machines always have some serial component, and that serial component determines the minimum run-time for the whole computation.
So even if all the rest of the work would be reduced to '0' then there would still be that serial component left, whatever it was.
This is not at all about playing mp3s or server loads such as web serving that are embarrassingly parallel and that can be run in a shared nothing environment. It is all about computing solutions to problems where there is some shared state between the various parts of the computation.
In computations like that the serial bits are visible as bottle-necks in the data flow, either because there is a synchronization point and some kind of reduction of the data that can only be done in a serial fashion, an ordering or some other operation that can only be done by a limited number of the total available cores. Those sections, and only those sections will put a lower limit on how fast you can solve that particular problem for a given data set.
That said, Amdahl's law does NOT apply to problems, it applies to programs: https://en.wikipedia.org/wiki/Amdahl%27s_law What I was trying to say is that, from my experience, if you take an existing program and try to parallelize it with minimal effort (e.g. parallelize all loops), then you may end up with having a serious percentage of serial code. (Or you don't, because your data is large enough, see Gustafson's law: https://en.wikipedia.org/wiki/Gustafson%27s_Law ) However, if you put in more effort and re-architect the program, you'll usually worry about a lot of problems, but Amdahl's law is not one of them. Yes, you didn't "avoid" Amdahl's law (and you can find counter-examples where Amdahl's law is a real concern).
I actually heard a talk about ordering in in-memory databases. It basically comes down to Gustafson's law: If your dataset is rather small, the overhead of parallelization (some of which can be attributed to Amdahl's law) isn't worth it, you just do it on one core. But because your dataset is small, it is so fast that nobody cares. If your dataset is large, each core sorts a subset. Then you start aggregating, and the final aggregation is serial. However, because you already have sorted lists, you can use a different algorithm that merges this very quickly (but would perform bad on unsorted data). I can't remember any specific numbers, but the bottom line was that even with a very beefy server that had 4 sockets and plenty of cores, the serial part wasn't an issue in terms of overall performance. Keep in mind that the author talked about a Multi-core myth and not a Many-core myth.
Again, I don't argue that near-linear speedup is possible for most problems. Most often it's not. But naming Amdahl's law as the only reason is wrong.
The comment about people wanting a single absolute measure of something is also spot on.
The biggest bottlenecks to me were (and still are) memory and the network. Mult-cores are nice, but given the choice I'd still trade additional CPU's for more memory or a faster network.
Nothing else a home user could buy could do pre-emptive multitasking in 1985... Or even 1995 AFAIK.
http://en.wikipedia.org/wiki/Torch_Computers
based on a 68010.
Honestly never heard of these though, thanks.