"Code that runs OK-ish on that CPU averages around 1 instruction per cycle, well-optimized code around 3 instructions per cycle."
Is unoptimized code really that bad?
I thought between modern compilers and supporting 4 op/cycle with out-of-order execution, a new Kaby Lake cpu would get more than 1 cycle overall. Or are the branch delays just killing the performance? (Code is small relative to data, most of it should be in cache most of the time)
Moreover, optimized code is able to do more with less (by not repeating itself). Unoptimized code sits and does the same thing over and over.
Then there's parallelism (threads and, in particular, SIMD); use right, it works great. Use wrong and it only expands your memory bandwidth requirements (and kills your effective instructions per cycle).
The author wrote "OK-ish" code. I think code that is OK is one that was compiled with -o3, like basically all code in release mode. 'optimized' in this context should mean somebody spent time to make it faster.
In this discussion, doing something 'over and over', or doing less with more is a consideration at a higher level, and shouldn't play into this. This is about instructions per cycle, so being able to only do one instruction per cycle on average should only be due to continuous streams of dependent instructions, waiting on branches and waiting on memory.
I'm not disputing that ... I just thought that out-of-order execution was supposed to deal with that to an extend, with tens to even hundreds instruction in flight at a time.
There are so many execution ports compared to the throughput of decoding, renaming and retiring, that they are rarely the bottleneck. As ant6n correctly pointed, memory latency, branch prediction, dependency chain length, decoding and renaming are, in that order, normally the bottleneck even for hand optimized assembler code.
Absolutely. Compilers can't do much about poor locality and most code is not written with locality in mind. And in many cases locality isn't really much of an option anyway; for instance, think about a key-value dictionary much larger than cache, responding to random requests. People have contrived ways of trying to make these cache-friendly but they generally end up slower than a really well-optimized hash lookup. You can improve it further in some cases by using prefetching extensively and trading memory bandwidth for latency, but as the article points out that can actually be a really terrible idea. So without further knowledge of the workload there just isn't a lot you can do.
To refine: popular compilers don't do much about poor locality. It's very possible do this but you need the language to permit it and the compiler engineering done. Data optimizations have for some reason received too litlte attention for a long time.
For example, most key-value dictionaries could shave off 50-90% of their memory use if the value ranges and key counts were optimized for, along with unboxing.
Saturating the execution ports in a modern CPU is something compilers demonstrably have a difficult time doing automatically because the the code involved in this optimization has poor locality by definition. Compilers tend to have a bit of tunnel vision to a very local context so that operation relationships are easily analyzed.
Optimizing this requires detecting patterns in scattered parts of the code and reorganizing the code in a functionally neutral way. Not difficult to do but the human programmer has to do the work because it requires a higher level view of code sequencing relationships. It doesn't produce code that is any less obvious or readable in my experience. Even on older Sandybridge CPUs, I often saw upwards of 2x throughput by mildly reorganizing perfectly correct C++ for better operation concurrency. Writing code that is well-optimized in this regard becomes natural with awareness and experience.
Optimizing cache line hit rates has an even higher throughput improvement than execution port saturation but is a similar optimization.
I don't think it's even possible any more. Haswell and later are 8-wide designs, but can only fetch+decode and retire 4 instructions per cycle (peak). So one would need ops that decode to 2+ execution-unit independent µops.
Linear data-dependent algorithms are also such a huge pain: "Why does that only shovel 500 MB/s?" Well... five instructions long dependency chain, that's why!
(Yes, the last bit may be a bit unrelated to the discussion at hand)
The µop cache (trace cache went out the window) doesn't help with fetching instructions AIUI, but accelerates decoding them. So the 4 insns/cycle fetch bandwidth is not changed by that.
> five instructions long dependency chain, what's why!
Skylake apparently has up to 224 instructions in flight. So during those dependent 5 instructions, theoretically it could be doing some of the next hundred. Or the previous hundred.
I simply find it hard to believe that Intel would design monsters with so many out-of-order instructions, but still every random bit of software will constantly get completely stalled by dependent instructions.
> So during those 5 instructions, theoretically it could be doing some of the next hundred.
Not if the next iteration of the loop not only branches on the previous result (okay, that one's easy on the predictors), but also depends on the previous iteration :)
--
The basic idea behind these designs is that
a) most software is a fat, ugly blob of shit which sometimes calls into
b) specific functions implementing high-performance algorithms (be it compression, encryption, hashing, ..., image manipulation, ...)
So for b) you want a capable design to have high throughput, and that also plays well with a) because it means that the core can spend most of it's time blocking on memory or executing an instruction or two every couple cycles. It also means that SMT works very, very well, since now you got two fat blobs smearing their shit around, but the core has more than enough resources to deal with that. That's why SMT gives 50++ % speed-ups for many applications. Because they're fat blobs.
That doesn't strike me as true. It appears more likely that these cpu monsters with OOE and register renaming are like just-in-time trace optimizers that can use run-time values to improve the optimization. That is, take shitty code, and try to run it as fast as possible, and try to squeeze multiple instructions per cycle out of it, by optimizing over hundreds of instructions in real time.
If the intention was just to speed up hand-tuned library functions, it would be much easier to ask the library-hand-tuners to figure out instruction dependencies ahead of time (instead of doing re-ordering) and to provide a lot of registers (instead of doing renaming).
> If the intention was just to speed up hand-tuned library functions, it would be much easier to ask the library-hand-tuners to figure out instruction dependencies ahead of time (instead of doing re-ordering) and to provide a lot of registers (instead of doing renaming).
That's not a scaleable approach, i.e. only works for some set of parameters that are then set in stone after that. Changing the parameters means changing the ISA.
An ISA that did something similar was Itanium and it failed spectacularly. On the other hand, the idea to offload these optimizations to the CPU is quite old. E.g. "SPARC" is for "scaleable processor architecture" -- the scaleable part mostly refers to the number of register windows the CPUs have.
On the other hand, other processors do this with great success. Examples here are the extremely primitive cores used in HPC accelerators for the TOP500, or those used in GPUs. There this works since code can be hand-tailored to a specific computer, or because the problem itself and algorithmic approaches ensure that a compiler can generate good SIMT code (in the case of GPUs).
> are like just-in-time trace optimizers that can use run-time values to improve the optimization.
Practically no optimizations found in CPUs do that (looking at "run-time values"). Or I'm misreading you here.
That's not true. One just needs to _add_ to the ISA. That's exactly what SSE and AVX do: oodles of registers, oodles of compute power. Apparently those are to be used by those specialized libraries you mention.
OOO, register-renaming, and having the ability of hundreds of instruction in flight (!) seem more about improving general computing performance.
> Practically no optimizations found in CPUs do that (looking at "run-time values"). Or I'm misreading you here.
Modern CPUs are like essentially like trace optimizers that do depend on run-time values. For one, there's the branch predictor. Secondly, instructions may execute as soon as the dependent data becomes available. So it's possible that some memory load happens quickly because data is in L1, compared to another independent instruction doing a memory load from main memory. Since the data from one instruction arrived earlier, it can get scheduled ahead of the other -- in real time.
Put another way, he's saying if the dataset doesn't fit in cache, it's bottlenecked on memory rather than the CPU's computational resources. It might still be good code.
Transforming an arbitrary computational task to a perfectly balanced "n operations of computation per n bytes of data accessed" suited to hardware du jour is a not a generally solved problem, as much as programmers like to talk about memory/speed tradeoffs.
I understand the overall point of the article is about memory blocking cpu; but the author uses the idea of instruction through-put instruction-memory/cycle a way to show that the throughput isn't enough just to execute code. So in order to make that argument, you'd have to look at the instruction through-put without the assumption of memory accesses slowing you down.
Otherwise the point comparing cpu speed vs memory speed is moot, if you start with the assumption that cpu speed is bound by memory speed to begin with.
> Transforming an arbitrary computational task to a perfectly balanced ...
I think that's halting problem level difficulty there. We can probably do neat things for special cases, but i seriously doubt it's generally solvable.
I thought between modern compilers and supporting 4 op/cycle with out-of-order execution, a new Kaby Lake cpu would get more than 1 cycle overall. Or are the branch delays just killing the performance?
The problem at the level of how many operations per cycle is data dependencies. A lot of code is assignments to variables and subsequent use of those variables in calculations, etc. Simplistic example:
a = 1;
b = 2;
c = a + b;
The assignment to variable "c" stalls until "a" and "b" assignments are completed. Obviously, in real life the assignments of "a" and "b" would generally be other complicated assignments that are dependent on other variables, functions, calculations, etc.
The x86 is additionally hampered by its relative lack of registers. This is hidden to some extent by using register renaming so that the CPU actually has multiple instances of register e.g. AX and tracks the dependencies.
Skylake has up to 224 instructions in flight [1], apparently on multiple branches. This compares to your 3 instruction example.
I think it's a valid question whether this doesn't imply we get more than 1 instruction/cycle, even for code that isn't hand-optimized (i.e. just usual code optimized by the compiler), assuming that the work load isn't data-memory bound.
You will get the number of instructions in parallel that is the minimum of (a) the number of instructions that can be handled by the hardware simultaneously and (b) the number of instructions that don't have inter-dependencies.
My example was not a 3 instruction example. It was a minimum example of data dependencies. In the example, until the CPU can resolve what the value of the variable (register) "a" is, it cannot do the calculation for the variable "c". Most programs have a high level of data inter-dependencies. Conditional branches are major class of data inter-dependency - the CPU cannot execute code beyond the branch[1] until it knows which branch it will take.
There is a class of programs that are "embarrassingly parallel" that having more execution units will speed them up, ideally linearly (graphics GPUs are a classic example). "Garden variety" programs end up under utilizing execution units because the execution unit assigned to calculate "c" (from my example) will be stalled waiting for execution units assigned to calculate "a" and "b" to complete their calculations.
This is related to the long unrealized, and still unrealized, promise of VLIW architectures.
[1] A small-ish lie: many processors nowadays do "speculative execution" where they guess which branch will be taken and execute ahead. If they guess right, they win. If they guess wrong, they throw away the work they did and restart the execution on the other branch.
Even with an embarrassingly parallel problem, you need to have enough compute work per memory access to achieve anything like full utilization. Suppose you're doing a pairwise multiplication of two huge arrays. That's as embarrassingly parallel as it gets. Even better, it's a perfect fit for SIMD. But as the article shows, you'll get nowhere near the theoretical throughput of 4 instructions/cycle since there's not enough main memory bandwidth. You could add infinitely large issue and retire queues and infinitely many execution units to the out-of-order core. You'd still be bottlenecked by memory bandwidth.
Memory bandwidth holds back a number of "revolutionary" advances in computing, both in the sense of FPGAs, ASICs, and new processor types, not to mention Indium Phosphide parts that clock at 50 GHz and could go to 200 or more.
Which way was the association, more CPUs -> faster CPU-GPU transfer, or slower? By "physical CPUs" I assume you mean cores in a single socket, but in pre-Haswell multi-socket systems, the uncore clock speed was tied to the core clock speed, so idle CPUs that enter a low power state can actually cause horrible performance because cache coherence snoop signals have to wait for the low-power/slow CPUs to respond. See https://software.intel.com/en-us/forums/intel-moderncode-for...
> I assumed it was because with newer intel CPUs the PCI bridge moved to the die, away from the motherboard, so there was CPU affinity for the GPU.
Actually, the PCIe controller doesn't even have to be on-die. The same issue existed in earlier systems where PCIe was in the northbridge, which was attached to the first socket. Sometimes other sockets had their own NBs and own PCI buses too and things were even more interesting.
I heard years ago about people pinning their GPU-accelerated applications to the "right" CPUs.
The article is very optimistic about memory availability per cycle, reality is way worse.
As an example, on my Macbook Air 2011 with ~10 GB/s of maximum ram bandwidth, random access to memory can take 100 time more than a sequential one.
This in C, with full optimizations and using a very low overhead read loop.
Using the same metrics of the author:
best case: ~ 3 bytes per cycle
(around 6 Gigabyte per second of available bandwidth)
worst case: ~ 0.024 bytes per cycle
(every scheduler, prefetch, already open column mostly defied)
Note that worst case uses 10 seconds (!) to read and sum in a random way all the cells of an array of 100.000.000 of 4 byte integers, exactly once. Main loop is light enough not to influence the test.
That's about 40 megabytes per second out of 6.000 available.
Right, the article focuses on bandwidth while in many cases it's about latency of dependent memory operations (which has improved by even a lower factor than what's described in the article). Your typical pointer chasing code won't come anywhere near the maximum memory bandwidth mentioned in the article (50 gb/sec).
>worst case: ~ 0.024 bytes per cycle (every scheduler, prefetch, already open column mostly defied)
>That's about 40 megabytes per second
Wow, that is an explosive conclusion. It's very hard for me to come to terms with. 40 MB per second is the sustained read of a spinning platter hard drive
(Did I say 40? I meant 160 MB/sec...) So more like 1/4 of the sequential read speed off of a spinning platter of rust. Ten seconds is insane.
I don't care how many times you're bouncing back and forth and invalidating caches and pipelines and prefetches and schedulers, you simply shouldn't be able to ruin things that badly. It is off from what I would expect by (easily) an order of magnitude.
I know you say that the main loop is very light - but aren't there other aspects to your build system and operating system that might be affecting this test? To say something very obvious, couldn't the Operating System scheduler not be giving your process the appropriate number of cycles? There is a lot more that I could say in this direction but let's just do something simpler:
-> Could you try your experiment without an operating system?
For example here are some people who booted a raspberry pi without an operating system -
Perhaps before going that far you could simply boot into a Linux image that was simply not compiled with any hardware support to do anything. (After all you really don't need to do anything except return to the shell.) Or simply see what happens if you boot into Linux and try it.
If you get an instantly different result simply booting Linux on the same hardware then you instantly have an explosive blog post: "summing 100k 4-byte integers randomly takes 10 seconds on Mac OS X but only 1 second under Linux".
I realize there is a HUGE difference (HUGE) between sequential and random. But I just wanted to get across how insanely slow 40 MB/second straight to RAM is. That should not be possible, no matter how much you defy caches and scheduling and so forth, unless you get the Mac to swap pages out of RAM onto an SSD or something! So not using an operating system would really help here.
Could you try it? I'm not saying I don't believe you but - wow, that is insane.
† I just noticed you wrote "Macbook air 2011". If you want to look at 2011 hard drive speeds, a quick glance still sees some quoting 140 MB/sec so it still seems correct to me, but I just quoted 2017 figures.
Your parent poster doesn't provide details, but this is not really crazy.
From https://gist.github.com/jboner/2841832, main memory latency is 100 ns; so we get 10 million fetches per second. You could get 40 MB by e.g. assuming that you have 4 one-byte requests in flight at the same time.
Hi, I've posted a few details and a sample program over here.
As you correctly notice, latency is a big issue on modern machines, way worse (in proportion) than it was in the late eighties.
But as soon as the wheels start turning, they spit out a lot of bytes, for sure!
Hi!
Memory is definitely an issue today, especially with big fat server processors...
Here is the small program I wrote, first allocates an array, then writes a random placed linked list that touches all the array cells (e.g. start->|4|6|2|5|3|end , so it goes to cell 1, then 4, then 5, then 3,2,6 and done.
Then it reads the same array from start to finish, just to sum contents. This is fast and goes to 6-8 GB/s, depending on unrelated memory pressure from video and os tasks. This is the advertised speed. So I don't think it's a swap issue (and my SSD is way faster :-) I've also tried with smaller and bigger arrays. Just ensure it stays in real memory.
Moving around in a big array is very hard on the memory controller:
- no prefetch possible;
- row and column changes at every access (almost), so commands have to be issued to burst terminate, close row, close bank, precharge maybe, open bank, activate row, fetch address, and who knows;
- no advantage from interleave;
- no advantage from a fat 64 or 128 bit bus;
It is the combined time needed for each and every memory read (due to randomization) that cause performance to drop.
This is the code I've been using. I've modified it to work on unices (OSX has an issue with timeval struct), but have not tested on them. It compiles, may need to be altered a bit. Launch it with ./a.out <array_size> <random seed>. You will note that, as soon as the array moves out of caches, hell breaks loose. Works with gcc or clang.
Thank you. This is very good and thank you for sharing. You should probably copy the usage information from your comment here to the top of the file, so they're not separated.
I tried it and got the same result you suggested (I used a code running site but it shouldn't matter, the VM it runs in should have virtualized operations that shouldn't slow it down by a complete order of magnitude so I roughly trust the results I'm seeing.)
FYI, here is the output with 10m items. (It times out if I try to increase it further, but that is just because the code-running site kills programs that run longer than a set time)
ht_size: 10000000
sizeof(int): 4
seed: 256
start run
roll 64: -2004260032
time (seconds:+nanoseconds) 1s:270464 ns
sequential run: roll 64: -2004260032
time (seconds:+nanoseconds) 0s:281244 ns
so if that is 1.27 sec for 10mill it should obviously be around 12 seconds for 100 million. Just brutal. I had no idea things could be so bad.
> Wow, that is an explosive conclusion. It's very hard for me to come to terms with. 40 MB per second is the sustained read of a spinning platter hard drive
Parent is talking about random access. So compare with random access to spinning rust :)
40MB/s for random RAM access is totally reasonable. Dynamic RAM (DRAM), the kind of RAM used in computers nowadays, is organized and accessed in "rows" of few kB. If you read random addresses, chances are good that almost every read will miss all CPU caches and hit a DRAM row other than any currently opened row (there is maybe a few dozen rows out of millions opened at any time, depending on the number and internal organization of RAM modules). Opening and closing a new row takes tRP+tRAS which is 13+35ns on some random DDR3 RAM I have laying here. This is 20M individual accesses per second.
I now understand how it's reasonable, as in, correct. But I don't understand the fundamental reason for this. Okay, so every time a row is read, if it's not in cache it'll get cached. But why does it have to be that way?
Couldn't there be a mode, "hey don't fully open these rows, I just one want one random byte as fast as possible!"
I compared it with spinning disks just to show how unreasonable the total is. I realize that the whole design isn't built around this idea of picking off a byte at a time.
But don't you think there could be applications that have PRECISELY, exactly this usage pattern?
For example, what percent of your neurons are firing at the moment? Very, very low.
For some future applications, getitng a 10x speedup in random memory reads of single bytes might totally increase that application by a lot. Even if desktops aren't built this way today, I'm super-surprised that when the whole system isn't doing anything else, there is no way to get that kind of raw access without asking for whole rows at a time.
It's this way because in the 80s/90s computer architects simulated different kinds of CPU/memory system designs running existing C programs and measured that it's best to focus on caching and compromise on main memory random access. Then CPU vendors made such systems and they outsold/performed cacheless systems. And after that memory module standardization kept the direction, because memory cost per byte was more in demand than random access performance.
Yes, there are of course workloads that don't like that. But programs adapt to hardware over time too, so co-evolution has weeded out these access patterns from high-performance programs that can be structured differently.
You could make a computer that uses DRAM differently, but it would be expensive because you couldn't use mass market memory modules.
(Exception: some CPUs use in-package fast DRAM as last level cache).
There have been some custom hardware supercomputer designs (Tera MTA line) that were optimized for cache hostile workloads.
> Couldn't there be a mode, "hey don't fully open these rows, I just one want one random byte as fast as possible!"
As fast as possible is exactly tRP+tRAS. Since the whole row is read in parallel to RAM's internal SRAM buffer, opening only part of it would make no difference.
> What do you mean by "tRP + tRAS"?
Ever heard of RAM timings? I'm afraid at some point you will have to read how DRAM works to understand more. There was a link in my last post.
Super, super dumb question here, but now that memory is approaching an incredibly low $/byte ratio, would it be possible to use a large portion of the available memory to "index" the location of bytes to improve access time?
I'm fairly certain it's impossible to create a full and accurate index while still having a useful amount of RAM left over but could you perform some kind of extreme compression, even hashing each "row"? That way a CPU could eliminate X number of rows in its search due to the likelihood that the hash couldn't be generated if it contained that byte of data. I'm obviously a layman but I think that if statistical branch prediction works, there must be a way to use excessive amounts of memory to make random access into a predictive process.
Not sure what you mean. You always know which row contains any given address, the problem is that "seeking" in DRAM takes tens of nanoseconds (for contemporary chips), regardless of DRAM's clock speed or DDR/GDDR/LPDDR 1/2/3/4/5/6/7. Seeking in your "index" would take time too.
The only way to get good performance from DRAM is to always write data sequentially in the same order they will be read. Then you get full sequential throughput both for writing and reading and this is many GB/s and keeps increasing with clock speed. But that's a software optimization.
Otherwise caching is beneficial, but the cache has to be SRAM to have low random access latency. SRAM is physically larger and power hungry, half of a modern CPU is cache and it's still only a few MB.
Just as a point of reference, I currently see around 1.25 - 1.5 op/cycle on carefully crafted highly parallel lock-free, stall-free code... say running on 8 threads. Code that has 0.01% branch misprediction.
Unfortunately in my case as others mention, access to the I/O ports and memory latency, is a real limiting factor. The CPU is just... waiting
Getting to the Holy Grail that Ryg talks about of 3 instructions per cycle is really hard with non-vectorizable workloads - like screwing around with hash tables that have no chance of fitting in L1/L3, and not being able to really make much use of SIMD, even if you are paying attention to cache-lines.
Most apps barely scrape by at 0.5 instructions/cycle or worse and spend most of the time bouncing on the kernel for stupid stuff. Not good.
I don't think that idea makes sense. A lot of stack space is unused at any particular time. There's not a one-size-fits-all partition that makes sense, and it's not something that programs could easily tune either.
Some obvious stack-related ideas that are worth exploring IMHO are (1) using the stack pointer to guide the prefetcher, to run ahead of cache misses when you return from subroutines and go up the stack; and (2) having an instruction that helps avoid unneeded cache misses when going down the stack; for example, a dedicated instruction for decrementing the stack pointer which zeros entire cache lines directly in L1 without loading them. Or perhaps, for more generality, an instruction for marking any arbitrary address range in this way.
Who knows, at least the first one might already be in use in some microarchitectures!
Yes I agree that a lot of stack space goes unused right now, that is for sure, but the nice thing about the stack it is definitely thread/core local, and if you did have fast-stack capability we would definitely use it.
What I was thinking about was a separate bus to a per thread stack space with no competitors. That seems interesting, and I don't think it would be that hard to add.
I really like your ideas there, especially number 1, that's very smart.
It's good to see some attention paid to the subject, but it's not exactly a new revelation.
Probably 15-20 years ago, my computer architecture professor commented that, while CPUs of the past had relatively anemic number-crunching powers, all the pipelining and high clock speeds and other advancements in more recent CPUs had changed that, but corresponding advancements in memory bandwidth had not been made.
Which in turn meant that the way you go about optimizing code needed to change. In the past it had been mostly about finding ways to eliminate instructions or simplify expressions, because the things that were holding you back were the ALU and the ability to plow through instructions. With all those things sped up massively but less improvement in RAM, it became very important to start thinking about memory access patterns and caches.
We even had a homework assignment to optimize a matrix multiply, and the lesson learned was that the dominating factor wasn't what the code looks like the innermost loop, it was which direction you proceed through the matrices (row by row vs. column by column) because that determines memory access patterns.
> Note that we’re 40 years of Moore’s law scaling later and the available memory bandwidth per instruction has gone down substantially.
This is unfair, and (this is me being unfair now) this article is missing the woods for the trees.
There were engineering pressures which resulted in the current ratios. I think it is fairer to say that the current situation — where there's about (hand-waving) 1 byte per instruction of bandwidth per core — reflects the kinds of tasks we expect our machines to be doing. It is very rare to find a task which is memory speed bound. There's almost always substantial processing to be done with data.
It's not even that hard to increase memory bandwidth. You "just" double up memory channels. This is of course expensive, which in turn is a back-pressure which results in architectures designed around the current sweet-spot.
I'm also puzzled the author thinks the situation is "worse". Pretty much every desktop class machine I've used from about 1990-2005 was extremely starved of memory bandwidth, and cores did a far worse job of hiding latency (OOO renames etc). What we have today feels fairly comfortable, to me at least, with some outlier tasks where you might want more (and then obtain specialist hardware).
This is a long-winded way of saying: the current core vs memory speed ratio is a sweet-spot of cost vs efficiency, and works well given the tasks and algorithms we execute on these machines. What we had in the olden days was just a case of unoptimized architecture, which hadn't converged yet.
> It is very rare to find a task which is memory speed bound. There's almost always substantial processing to be done with data.
One could argue that memory speed doesn't matter because memory latency has remained (relatively) constant since the advent of DDR. Can't process something while you're waiting for that cache miss to complete.
I don't think it's worse. The (possibly missing) context of this post is a Compute Shader running on a GPU spending more time writing out the results of a computation than actually doing the computation.
As I read this post, the moral of the story is just to try to write your code in such a way as to always have that substantial work to do with the data. Prefer one big pass over everything to several smaller passes, each of which must write out results, especially on a GPU. Try to actually have 11 instructions per byte of memory access.
I don't think the intent is to make any argument in particular about the state of CPU or GPU design or anything of the sort.
A commonly recurring subject on the 6502 forums is what a "modern" 6502 would look like. It always boils down to not really being able to replicate the 1-cycle access to any byte in RAM. Changes to the memory access model requires changing everything to being unrecognizable as a 6502 derivative, in programming style.
Of course, you could put 64KB of SRAM on the CPU die, but the size and power of the RAM would dwarf the processor, and you'd get an old-school 6502, arguably not a modern take on the concept. If you want more memory, you simply can't replicate the 1980s access model at anything approaching today's speeds.
TLB (page table) is already kept in the CPU, in SRAM. Memory controller is as well.
If users can manage cache, they can write code that is efficient with current architecture as well. I'm not seeing this.
69 comments
[ 1.7 ms ] story [ 152 ms ] threadIs unoptimized code really that bad?
I thought between modern compilers and supporting 4 op/cycle with out-of-order execution, a new Kaby Lake cpu would get more than 1 cycle overall. Or are the branch delays just killing the performance? (Code is small relative to data, most of it should be in cache most of the time)
Moreover, optimized code is able to do more with less (by not repeating itself). Unoptimized code sits and does the same thing over and over.
Then there's parallelism (threads and, in particular, SIMD); use right, it works great. Use wrong and it only expands your memory bandwidth requirements (and kills your effective instructions per cycle).
In this discussion, doing something 'over and over', or doing less with more is a consideration at a higher level, and shouldn't play into this. This is about instructions per cycle, so being able to only do one instruction per cycle on average should only be due to continuous streams of dependent instructions, waiting on branches and waiting on memory.
Not enough by itself. The code will likely be pretty bad, unless you'll also add -march=native.
Absolutely. Compilers can't do much about poor locality and most code is not written with locality in mind. And in many cases locality isn't really much of an option anyway; for instance, think about a key-value dictionary much larger than cache, responding to random requests. People have contrived ways of trying to make these cache-friendly but they generally end up slower than a really well-optimized hash lookup. You can improve it further in some cases by using prefetching extensively and trading memory bandwidth for latency, but as the article points out that can actually be a really terrible idea. So without further knowledge of the workload there just isn't a lot you can do.
For example, most key-value dictionaries could shave off 50-90% of their memory use if the value ranges and key counts were optimized for, along with unboxing.
Most application code is far worse and stalls (sadly - almost literally) every few instructions for L2 / memory.
> (Code is small relative to data, most of it should be in cache most of the time)
Not if your application is dragging two and a half invasive runtimes around.
Cheers to that :/
Optimizing this requires detecting patterns in scattered parts of the code and reorganizing the code in a functionally neutral way. Not difficult to do but the human programmer has to do the work because it requires a higher level view of code sequencing relationships. It doesn't produce code that is any less obvious or readable in my experience. Even on older Sandybridge CPUs, I often saw upwards of 2x throughput by mildly reorganizing perfectly correct C++ for better operation concurrency. Writing code that is well-optimized in this regard becomes natural with awareness and experience.
Optimizing cache line hit rates has an even higher throughput improvement than execution port saturation but is a similar optimization.
Linear data-dependent algorithms are also such a huge pain: "Why does that only shovel 500 MB/s?" Well... five instructions long dependency chain, that's why!
(Yes, the last bit may be a bit unrelated to the discussion at hand)
That's where the Trace Cache helps in tight loops.
Skylake apparently has up to 224 instructions in flight. So during those dependent 5 instructions, theoretically it could be doing some of the next hundred. Or the previous hundred.
I simply find it hard to believe that Intel would design monsters with so many out-of-order instructions, but still every random bit of software will constantly get completely stalled by dependent instructions.
Not if the next iteration of the loop not only branches on the previous result (okay, that one's easy on the predictors), but also depends on the previous iteration :)
--
The basic idea behind these designs is that
a) most software is a fat, ugly blob of shit which sometimes calls into
b) specific functions implementing high-performance algorithms (be it compression, encryption, hashing, ..., image manipulation, ...)
So for b) you want a capable design to have high throughput, and that also plays well with a) because it means that the core can spend most of it's time blocking on memory or executing an instruction or two every couple cycles. It also means that SMT works very, very well, since now you got two fat blobs smearing their shit around, but the core has more than enough resources to deal with that. That's why SMT gives 50++ % speed-ups for many applications. Because they're fat blobs.
If the intention was just to speed up hand-tuned library functions, it would be much easier to ask the library-hand-tuners to figure out instruction dependencies ahead of time (instead of doing re-ordering) and to provide a lot of registers (instead of doing renaming).
That's not a scaleable approach, i.e. only works for some set of parameters that are then set in stone after that. Changing the parameters means changing the ISA.
An ISA that did something similar was Itanium and it failed spectacularly. On the other hand, the idea to offload these optimizations to the CPU is quite old. E.g. "SPARC" is for "scaleable processor architecture" -- the scaleable part mostly refers to the number of register windows the CPUs have.
On the other hand, other processors do this with great success. Examples here are the extremely primitive cores used in HPC accelerators for the TOP500, or those used in GPUs. There this works since code can be hand-tailored to a specific computer, or because the problem itself and algorithmic approaches ensure that a compiler can generate good SIMT code (in the case of GPUs).
> are like just-in-time trace optimizers that can use run-time values to improve the optimization.
Practically no optimizations found in CPUs do that (looking at "run-time values"). Or I'm misreading you here.
That's not true. One just needs to _add_ to the ISA. That's exactly what SSE and AVX do: oodles of registers, oodles of compute power. Apparently those are to be used by those specialized libraries you mention.
OOO, register-renaming, and having the ability of hundreds of instruction in flight (!) seem more about improving general computing performance.
> Practically no optimizations found in CPUs do that (looking at "run-time values"). Or I'm misreading you here.
Modern CPUs are like essentially like trace optimizers that do depend on run-time values. For one, there's the branch predictor. Secondly, instructions may execute as soon as the dependent data becomes available. So it's possible that some memory load happens quickly because data is in L1, compared to another independent instruction doing a memory load from main memory. Since the data from one instruction arrived earlier, it can get scheduled ahead of the other -- in real time.
Transforming an arbitrary computational task to a perfectly balanced "n operations of computation per n bytes of data accessed" suited to hardware du jour is a not a generally solved problem, as much as programmers like to talk about memory/speed tradeoffs.
Otherwise the point comparing cpu speed vs memory speed is moot, if you start with the assumption that cpu speed is bound by memory speed to begin with.
I think that's halting problem level difficulty there. We can probably do neat things for special cases, but i seriously doubt it's generally solvable.
The problem at the level of how many operations per cycle is data dependencies. A lot of code is assignments to variables and subsequent use of those variables in calculations, etc. Simplistic example:
The assignment to variable "c" stalls until "a" and "b" assignments are completed. Obviously, in real life the assignments of "a" and "b" would generally be other complicated assignments that are dependent on other variables, functions, calculations, etc.The x86 is additionally hampered by its relative lack of registers. This is hidden to some extent by using register renaming so that the CPU actually has multiple instances of register e.g. AX and tracks the dependencies.
Ref:
https://en.wikipedia.org/wiki/Register_allocation
https://en.wikipedia.org/wiki/Register_renaming
I think it's a valid question whether this doesn't imply we get more than 1 instruction/cycle, even for code that isn't hand-optimized (i.e. just usual code optimized by the compiler), assuming that the work load isn't data-memory bound.
[1] http://www.anandtech.com/show/9582/intel-skylake-mobile-desk...
My example was not a 3 instruction example. It was a minimum example of data dependencies. In the example, until the CPU can resolve what the value of the variable (register) "a" is, it cannot do the calculation for the variable "c". Most programs have a high level of data inter-dependencies. Conditional branches are major class of data inter-dependency - the CPU cannot execute code beyond the branch[1] until it knows which branch it will take.
There is a class of programs that are "embarrassingly parallel" that having more execution units will speed them up, ideally linearly (graphics GPUs are a classic example). "Garden variety" programs end up under utilizing execution units because the execution unit assigned to calculate "c" (from my example) will be stalled waiting for execution units assigned to calculate "a" and "b" to complete their calculations.
This is related to the long unrealized, and still unrealized, promise of VLIW architectures.
https://en.wikipedia.org/wiki/Very_long_instruction_word
[1] A small-ish lie: many processors nowadays do "speculative execution" where they guess which branch will be taken and execute ahead. If they guess right, they win. If they guess wrong, they throw away the work they did and restart the execution on the other branch.
Worth a read if you are just scanning the comments.
I assumed it was because with newer intel CPUs the PCI bridge moved to the die, away from the motherboard, so there was CPU affinity for the GPU.
The difference in bandwidth was around 15%
single cpu was faster than dual.
This was a xeon x56 vs an e5-26
On the z620 the second proc was on a removable daughter board, so it was simple test.
on the e5-26 it was most pronounced, the x56 was less obvious
This is exacerbated if the QPI links are already busy.
Actually, the PCIe controller doesn't even have to be on-die. The same issue existed in earlier systems where PCIe was in the northbridge, which was attached to the first socket. Sometimes other sockets had their own NBs and own PCI buses too and things were even more interesting.
I heard years ago about people pinning their GPU-accelerated applications to the "right" CPUs.
and Memory Wall https://www.google.co.in/search?q=memory+wall+computer+archi...
As an example, on my Macbook Air 2011 with ~10 GB/s of maximum ram bandwidth, random access to memory can take 100 time more than a sequential one.
This in C, with full optimizations and using a very low overhead read loop.
Using the same metrics of the author:
best case: ~ 3 bytes per cycle
(around 6 Gigabyte per second of available bandwidth)
worst case: ~ 0.024 bytes per cycle (every scheduler, prefetch, already open column mostly defied)
Note that worst case uses 10 seconds (!) to read and sum in a random way all the cells of an array of 100.000.000 of 4 byte integers, exactly once. Main loop is light enough not to influence the test.
That's about 40 megabytes per second out of 6.000 available.
What can I say.. CPU designers are truly wizards!
>That's about 40 megabytes per second
Wow, that is an explosive conclusion. It's very hard for me to come to terms with. 40 MB per second is the sustained read of a spinning platter hard drive
http://hdd.userbenchmark.com/ (click any line)†
(Did I say 40? I meant 160 MB/sec...) So more like 1/4 of the sequential read speed off of a spinning platter of rust. Ten seconds is insane.
I don't care how many times you're bouncing back and forth and invalidating caches and pipelines and prefetches and schedulers, you simply shouldn't be able to ruin things that badly. It is off from what I would expect by (easily) an order of magnitude.
I know you say that the main loop is very light - but aren't there other aspects to your build system and operating system that might be affecting this test? To say something very obvious, couldn't the Operating System scheduler not be giving your process the appropriate number of cycles? There is a lot more that I could say in this direction but let's just do something simpler:
-> Could you try your experiment without an operating system?
For example here are some people who booted a raspberry pi without an operating system -
https://www.google.com/search?q=chess+without+an+operating+s...
Perhaps before going that far you could simply boot into a Linux image that was simply not compiled with any hardware support to do anything. (After all you really don't need to do anything except return to the shell.) Or simply see what happens if you boot into Linux and try it.
If you get an instantly different result simply booting Linux on the same hardware then you instantly have an explosive blog post: "summing 100k 4-byte integers randomly takes 10 seconds on Mac OS X but only 1 second under Linux".
I realize there is a HUGE difference (HUGE) between sequential and random. But I just wanted to get across how insanely slow 40 MB/second straight to RAM is. That should not be possible, no matter how much you defy caches and scheduling and so forth, unless you get the Mac to swap pages out of RAM onto an SSD or something! So not using an operating system would really help here.
Could you try it? I'm not saying I don't believe you but - wow, that is insane.
† I just noticed you wrote "Macbook air 2011". If you want to look at 2011 hard drive speeds, a quick glance still sees some quoting 140 MB/sec so it still seems correct to me, but I just quoted 2017 figures.
From https://gist.github.com/jboner/2841832, main memory latency is 100 ns; so we get 10 million fetches per second. You could get 40 MB by e.g. assuming that you have 4 one-byte requests in flight at the same time.
As they say, RAM is the new disk.
But as soon as the wheels start turning, they spit out a lot of bytes, for sure!
Here is the small program I wrote, first allocates an array, then writes a random placed linked list that touches all the array cells (e.g. start->|4|6|2|5|3|end , so it goes to cell 1, then 4, then 5, then 3,2,6 and done.
Then it reads the same array from start to finish, just to sum contents. This is fast and goes to 6-8 GB/s, depending on unrelated memory pressure from video and os tasks. This is the advertised speed. So I don't think it's a swap issue (and my SSD is way faster :-) I've also tried with smaller and bigger arrays. Just ensure it stays in real memory.
Moving around in a big array is very hard on the memory controller: - no prefetch possible; - row and column changes at every access (almost), so commands have to be issued to burst terminate, close row, close bank, precharge maybe, open bank, activate row, fetch address, and who knows; - no advantage from interleave; - no advantage from a fat 64 or 128 bit bus;
It is the combined time needed for each and every memory read (due to randomization) that cause performance to drop.
This is the code I've been using. I've modified it to work on unices (OSX has an issue with timeval struct), but have not tested on them. It compiles, may need to be altered a bit. Launch it with ./a.out <array_size> <random seed>. You will note that, as soon as the array moves out of caches, hell breaks loose. Works with gcc or clang.
https://godbolt.org/g/qX39tL
I tried it and got the same result you suggested (I used a code running site but it shouldn't matter, the VM it runs in should have virtualized operations that shouldn't slow it down by a complete order of magnitude so I roughly trust the results I'm seeing.)
FYI, here is the output with 10m items. (It times out if I try to increase it further, but that is just because the code-running site kills programs that run longer than a set time)
so if that is 1.27 sec for 10mill it should obviously be around 12 seconds for 100 million. Just brutal. I had no idea things could be so bad.Thanks so much for sharing your program with us!
Parent is talking about random access. So compare with random access to spinning rust :)
40MB/s for random RAM access is totally reasonable. Dynamic RAM (DRAM), the kind of RAM used in computers nowadays, is organized and accessed in "rows" of few kB. If you read random addresses, chances are good that almost every read will miss all CPU caches and hit a DRAM row other than any currently opened row (there is maybe a few dozen rows out of millions opened at any time, depending on the number and internal organization of RAM modules). Opening and closing a new row takes tRP+tRAS which is 13+35ns on some random DDR3 RAM I have laying here. This is 20M individual accesses per second.
https://en.wikipedia.org/wiki/Dynamic_RAM
I now understand how it's reasonable, as in, correct. But I don't understand the fundamental reason for this. Okay, so every time a row is read, if it's not in cache it'll get cached. But why does it have to be that way?
Couldn't there be a mode, "hey don't fully open these rows, I just one want one random byte as fast as possible!"
I compared it with spinning disks just to show how unreasonable the total is. I realize that the whole design isn't built around this idea of picking off a byte at a time.
But don't you think there could be applications that have PRECISELY, exactly this usage pattern?
For example, what percent of your neurons are firing at the moment? Very, very low.
For some future applications, getitng a 10x speedup in random memory reads of single bytes might totally increase that application by a lot. Even if desktops aren't built this way today, I'm super-surprised that when the whole system isn't doing anything else, there is no way to get that kind of raw access without asking for whole rows at a time.
Yes, there are of course workloads that don't like that. But programs adapt to hardware over time too, so co-evolution has weeded out these access patterns from high-performance programs that can be structured differently.
You could make a computer that uses DRAM differently, but it would be expensive because you couldn't use mass market memory modules.
(Exception: some CPUs use in-package fast DRAM as last level cache).
There have been some custom hardware supercomputer designs (Tera MTA line) that were optimized for cache hostile workloads.
As fast as possible is exactly tRP+tRAS. Since the whole row is read in parallel to RAM's internal SRAM buffer, opening only part of it would make no difference.
> What do you mean by "tRP + tRAS"?
Ever heard of RAM timings? I'm afraid at some point you will have to read how DRAM works to understand more. There was a link in my last post.
I'm fairly certain it's impossible to create a full and accurate index while still having a useful amount of RAM left over but could you perform some kind of extreme compression, even hashing each "row"? That way a CPU could eliminate X number of rows in its search due to the likelihood that the hash couldn't be generated if it contained that byte of data. I'm obviously a layman but I think that if statistical branch prediction works, there must be a way to use excessive amounts of memory to make random access into a predictive process.
The only way to get good performance from DRAM is to always write data sequentially in the same order they will be read. Then you get full sequential throughput both for writing and reading and this is many GB/s and keeps increasing with clock speed. But that's a software optimization.
Otherwise caching is beneficial, but the cache has to be SRAM to have low random access latency. SRAM is physically larger and power hungry, half of a modern CPU is cache and it's still only a few MB.
Just as a point of reference, I currently see around 1.25 - 1.5 op/cycle on carefully crafted highly parallel lock-free, stall-free code... say running on 8 threads. Code that has 0.01% branch misprediction.
Unfortunately in my case as others mention, access to the I/O ports and memory latency, is a real limiting factor. The CPU is just... waiting
Getting to the Holy Grail that Ryg talks about of 3 instructions per cycle is really hard with non-vectorizable workloads - like screwing around with hash tables that have no chance of fitting in L1/L3, and not being able to really make much use of SIMD, even if you are paying attention to cache-lines.
Most apps barely scrape by at 0.5 instructions/cycle or worse and spend most of the time bouncing on the kernel for stupid stuff. Not good.
Absolutely <3 performance freaks!
Not so critical on GPU's but would make a huge difference for CPU's and languages that can take benefit.
Give me a meg or two to play with. Would make a huge difference for data heavy workloads.
You could even go as far as having a separate cache just for stack.
I mean, by its very definition it is isolated. It's the "register file" of CISC machines
Some obvious stack-related ideas that are worth exploring IMHO are (1) using the stack pointer to guide the prefetcher, to run ahead of cache misses when you return from subroutines and go up the stack; and (2) having an instruction that helps avoid unneeded cache misses when going down the stack; for example, a dedicated instruction for decrementing the stack pointer which zeros entire cache lines directly in L1 without loading them. Or perhaps, for more generality, an instruction for marking any arbitrary address range in this way.
Who knows, at least the first one might already be in use in some microarchitectures!
What I was thinking about was a separate bus to a per thread stack space with no competitors. That seems interesting, and I don't think it would be that hard to add.
I really like your ideas there, especially number 1, that's very smart.
Number 2 is clever as well.
> Who knows etc..
ORLY? Good to know.
Probably 15-20 years ago, my computer architecture professor commented that, while CPUs of the past had relatively anemic number-crunching powers, all the pipelining and high clock speeds and other advancements in more recent CPUs had changed that, but corresponding advancements in memory bandwidth had not been made.
Which in turn meant that the way you go about optimizing code needed to change. In the past it had been mostly about finding ways to eliminate instructions or simplify expressions, because the things that were holding you back were the ALU and the ability to plow through instructions. With all those things sped up massively but less improvement in RAM, it became very important to start thinking about memory access patterns and caches.
We even had a homework assignment to optimize a matrix multiply, and the lesson learned was that the dominating factor wasn't what the code looks like the innermost loop, it was which direction you proceed through the matrices (row by row vs. column by column) because that determines memory access patterns.
There's been talk about hundreds of cores, all with local memory, but this will only speed up a certain subset of computing problems...
https://en.wikipedia.org/wiki/Wait_state
This is unfair, and (this is me being unfair now) this article is missing the woods for the trees.
There were engineering pressures which resulted in the current ratios. I think it is fairer to say that the current situation — where there's about (hand-waving) 1 byte per instruction of bandwidth per core — reflects the kinds of tasks we expect our machines to be doing. It is very rare to find a task which is memory speed bound. There's almost always substantial processing to be done with data.
It's not even that hard to increase memory bandwidth. You "just" double up memory channels. This is of course expensive, which in turn is a back-pressure which results in architectures designed around the current sweet-spot.
I'm also puzzled the author thinks the situation is "worse". Pretty much every desktop class machine I've used from about 1990-2005 was extremely starved of memory bandwidth, and cores did a far worse job of hiding latency (OOO renames etc). What we have today feels fairly comfortable, to me at least, with some outlier tasks where you might want more (and then obtain specialist hardware).
This is a long-winded way of saying: the current core vs memory speed ratio is a sweet-spot of cost vs efficiency, and works well given the tasks and algorithms we execute on these machines. What we had in the olden days was just a case of unoptimized architecture, which hadn't converged yet.
One could argue that memory speed doesn't matter because memory latency has remained (relatively) constant since the advent of DDR. Can't process something while you're waiting for that cache miss to complete.
As I read this post, the moral of the story is just to try to write your code in such a way as to always have that substantial work to do with the data. Prefer one big pass over everything to several smaller passes, each of which must write out results, especially on a GPU. Try to actually have 11 instructions per byte of memory access.
I don't think the intent is to make any argument in particular about the state of CPU or GPU design or anything of the sort.
Of course, you could put 64KB of SRAM on the CPU die, but the size and power of the RAM would dwarf the processor, and you'd get an old-school 6502, arguably not a modern take on the concept. If you want more memory, you simply can't replicate the 1980s access model at anything approaching today's speeds.
I wonder if there are any practical applications that could benefit from such a thing.