News for hackers. Stuff that matters.
Re:Why do CPUs have multiple cache levels? by rwmj on Monday August 08, 2016 @03:38AM (#12246055)
I was "enlightened" many years ago when I asked a colleague (a great electronic engineer) why we didn't do fast task switching by having two sets of registers. His reply was that this would require every regular access to a register to go through an extra gate (to decide which bank of registers you want to hit), making every access slightly slower.

Larger registers/caches/memories are slower because they need more address decoding, that time scaling approximately linearly as the storage doubles in size.

Re:Why do CPUs have multiple cache levels? by brigade on Monday August 08, 2016 @06:44AM (#12246693)
For all the siblings describing various forms of register banking, you're actually literally describing SMT in which one core executes two or more tasks at the same time, dividing the register set and other processor resources between the threads and effectively switching between the tasks every cycle. Modern x86, Power, and SPARC CPUs implement this, as do basically all GPUs for a while now, all for very good reasons.

Which is to say, it's quite easy for low-level architectural knowledge to become obsolete :p

Re:Why do CPUs have multiple cache levels? by nkurz on Monday August 08, 2016 @04:00PM (#12250479)
Which is to say, it's quite easy for low-level architectural knowledge to become obsolete

Great insight. It's also a reminder that "best practice" is for a given set of assumptions, and it's good to periodically revisit whether these assumptions still hold. If the assumption is that the speed of register access is the limiting factor, it's probably good intuition to avoid anything that would slow this down. If instead the situation has changed so that memory access is hundreds of times slower than memory access (rather than the about the same), giving up some speed of register access for increased parallelism might be a good tradeoff.

It's interesting to think of hyperthreading[1] as being an alternative to adding layers of cache, with GPU's being at the extreme. It's also interesting to ask why 2x hyperthreading has been chosen by Intel, while Power8 allows up to 8x. Is this just market differentiation, or is there something architectural that makes this the right choice for each? And does support for hyperthreading come at a cost in clock speed, or is this already too constrained by heat and power?

[1] While I like avoiding made-up marketing terms, I'm using 'hyperthreading' rather than "SMT" here to distinguish multiple register sets sharing a single core from multiple cores sharing a single cache, and from multiple processors sharing access to RAM (SMP). Is there a separate acronym to distinguish "multicore simultaneous multi threading"?

Re:Why do CPUs have multiple cache levels? by noobiemcfoob on Monday August 08, 2016 @10:06AM (#12247838)
> Which is to say, it's quite easy for low-level architectural knowledge to become obsolete

Truer words never spoken! It doesn't help that the industry has interests in keeping advances trade secrets. Knowledge becomes highly siloed and outmodded rather quickly.

Re:Why do CPUs have multiple cache levels? by bogomipz on Monday August 08, 2016 @03:48PM (#12250401)
I'm familiar with the term "register banking" is this the same as SMT? i.e if a functional unit is free I can execute another instruction there that would otherwise be waiting?
Re:Why do CPUs have multiple cache levels? by pkroll on Monday August 08, 2016 @04:29AM (#12246235)
As cesarb points out the ARM did that, and so did the Z-80 IIRC: basically, your friend was either trolling you or had no idea what he was saying. Addressing is done in parallel. The address decoding isn't the part that drinks time.
Re:Why do CPUs have multiple cache levels? by nhaehnle on Monday August 08, 2016 @04:43AM (#12246295)
No, he's right, although I can imagine that the impact wasn't too bad for early ARM and Z-80.

No matter how it is implemented concretely, decoding or "using" an address of N-bits needs N levels of logical circuitry. Each level of circuitry takes time for signals to pass through. Of course, the time taken within each level is less than the clock cycle time of your CPU, but it adds up. Too many levels, and you can't do the addressing in your allocated cycle time any more.

So there's a trade-off. That trade-off may well have been worth it for the Z-80 and early ARM, but you'll note that apparently ARM switched away from that model as well.

Re:Why do CPUs have multiple cache levels? by davrosthedalek on Monday August 08, 2016 @06:03AM (#12246542)
That's not really true. You can decode N-bits in one step, for example, via 2^N N-bit compares. For small N, that's totally doable.
Re:Why do CPUs have multiple cache levels? by anjc on Monday August 08, 2016 @07:05AM (#12246769)
You still have to then AND the output of that decoder with the data lines which go to the registers right? OP's friend just mentioned 1 extra gate in the data path, and I presume this would be it.
Re:Why do CPUs have multiple cache levels? by morcheeba on Monday August 08, 2016 @03:17PM (#12250197)
Yep, but a 7-input AND gate will have basically the same delay time as an 8-input AND gate. They don't scale linearly as it would if you stacked 6 or 7 gates in series (although that's typically how you do it in math or programming)

I like examples: 74AHC00 2-input gate has typ 4.5ns propagation delay at 25˚C/15pF/3-3.6v http://www.nxp.com/documents/data_sheet/74AHC_AHCT00.pdf

74AHC30 8-input gate has typ 5.0ns propagation delay at 25˚C/15pF/3-3.6v http://www.nxp.com/documents/data_sheet/74AHC_AHCT30.pdf

Re:Why do CPUs have multiple cache levels? by anjc on Monday August 08, 2016 @03:28PM (#12250282)
Oh of course yeah. I was picturing it as a separate AND when it could be bunged in with the ANDs for individual register selects and write/load enables and so on also. Cool, thanks.
Re:Why do CPUs have multiple cache levels? by Dylan16807 on Monday August 08, 2016 @07:21AM (#12246838)
Fanout isn't instant. If you want to power 2^N gates, you need N time to power them all from a source signal.
Re:Why do CPUs have multiple cache levels? by cfallin on Monday August 08, 2016 @11:19AM (#12248438)
Yep, the long bitlines are a large factor in timing for register files. The timing is something like O(n) for n storage lines because it grows linearly with capacitance.
Re:Why do CPUs have multiple cache levels? by anjc on Monday August 08, 2016 @05:52AM (#12246506)
You're implying that OP's friend thinks an extra gate would require another clock cycle or something? He's just talking about propagation delay which is obviously increased with extra logic on the bus (in the multiplexor, or the register-bank-select from a decoder anded with the data lines, say.)
Re:Why do CPUs have multiple cache levels? by cesarb on Monday August 08, 2016 @04:21AM (#12246213)
The 32-bit ARM architecture actually does this. It has a "fast interrupt" mode which switches half of the register file to a separate bank. (The newer 64-bit ARM architecture doesn't have this feature.)
Re:Why do CPUs have multiple cache levels? by DigitalJack on Monday August 08, 2016 @11:29AM (#12248518)
I thought the fast interrupt skipped some of the pushing and popping when entering and leaving the interrupt service routine. In other words, the routine was not allowed to touch certain registers, so they didn't have to be saved off.
Re:Why do CPUs have multiple cache levels? by monocasa on Monday August 08, 2016 @12:25PM (#12248934)
It can. On non-M ARMs, pushing and popping is done by the interrupt handler, not by the processor. So if you want a really low latency FIQ, you can just rely on the half of the register bank that gets swapped in, and avoid the parts that don't.
Re:Why do CPUs have multiple cache levels? by 2muchcoffeeman on Monday August 08, 2016 @10:48AM (#12248204)
I am not convinced by this explanation.

If I can afford to have double the number of registers (in one or 2 sets), surely the extra time cost of some extra logic is still far quicker than hitting the first level cache? Hitting a cache doesn't just incur the access cost, but we have to store the value in a register somewhere before we can act on it.

Or am I remembering my arch classes wrong?

Re:Why do CPUs have multiple cache levels? by cfallin on Monday August 08, 2016 @11:18AM (#12248422)
It's a quantitative tradeoff question -- for many programs it may be true at first that increasing the register count (say, from 16 to 32) allows more live values in-register and reduces memory traffic, but at a certain point there are diminishing returns, because the extra access time eventually becomes another cycle of latency and this hits all programs. Notable as well is that for many programs (and especially modern ones with large data sets), most cache misses occur because of accesses to large heap data structures, not because there were slightly too few registers and a few locals spilled to the stack.

There are also practical issues with increasing the architectural register set -- you'd have to define a new encoding for instructions, and this (i) adds significant cost (area, power, timing) to the instruction decoding logic, and (ii) imposes a giant cost on the software ecosystem -- new binaries, operating system support for context-switching, etc.

Re:Why do CPUs have multiple cache levels? by Merad on Monday August 08, 2016 @12:46PM (#12249073)
Cache on modern processors is so insanely fast it's already essentially an extension of the register file. IIRC, under ideal circumstances a L1 cache hit on Core i7 can take as little as 2-3 cycles, and averages about 4 cycles.
Re:Why do CPUs have multiple cache levels? by radarsat1 on Monday August 08, 2016 @09:46AM (#12247682)
> time scaling approximately linearly as the storage doubles in size.

scratches head...

... so.. logarithmic scaling with storage size?

Re:Why do CPUs have multiple cache levels? by seanmcdirmid on Monday August 08, 2016 @04:04AM (#12246145)
sounds similar to register windows on SPARC, which is rather used for procedure calls. It isn't so much that it is slow, just that when you have a decent level 1 cache it doesn't add much. Right about why small caches are faster.
Re:Why do CPUs have multiple cache levels? by Zardoz84 on Monday August 08, 2016 @12:09PM (#12248832)
Z80 did it to serve IRQs.
Re:Why do CPUs have multiple cache levels? by sargun on Monday August 08, 2016 @04:21AM (#12246212)
What's the "cost" of registers on an x86-64 chip? How hard would it be to introduce 10 more general purpose registers? Ones that are used by the kernel, say, and one set for user space.
Re:Why do CPUs have multiple cache levels? by vardump on Monday August 08, 2016 @04:29AM (#12246240)
Because you say kernel, I'm assuming you mean ability to switch a set of registers instead of pushing them on the stack when servicing an interrupt request.

Unfortunately you can't get away with just one set of spare registers on x86 interrupt handling. Interrupt can be interrupted by another interrupt. So practically they have to save registers anyways. Unless there'd be one set for each level...

So those "10 extra registers" would be practically useless.

Having written kernel device driver interrupt handlers, I can also say CPU time is not spent saving and restoring registers, but waiting for glacially slow PCI-e MMIO register loads and stores (don't have exact figures at hand, but I remember one access can take 300-800 nanoseconds, that's thousands of CPU clock cycles). During one such fetch you might be able to store and restore registers tens, if not hundreds of times. X86 interrupt handling is a bit like stopping a freight train to pick up a single letter.

However, that kind of feature can be very useful on a microcontroller to help lowering interrupt handling latency.

Re:Why do CPUs have multiple cache levels? by Dylan16807 on Monday August 08, 2016 @07:25AM (#12246856)
> Interrupt can be interrupted by another interrupt. So practically they have to save registers anyways.

Only when an interrupt actually does get interrupted. You could make the common case faster. Not that it matters if PCI-e is the bottleneck.

Re:Why do CPUs have multiple cache levels? by vardump on Monday August 08, 2016 @07:55AM (#12246995)
Then all interrupts need to be prepared for it and check for it anyways. Crucially, the code path that does the check might also get interrupted, even multiple times. No synchronization is possible, and even if it was, it'd be slower than simply saving the registers.

So what do you suggest could be done?

Re:Why do CPUs have multiple cache levels? by Dylan16807 on Monday August 08, 2016 @02:03PM (#12249673)
It doesn't matter if that code path gets interrupted. There's no need to synchronize anything. If interrupt A sees that the extra registers are idle, and then gets interrupted, that's okay. By the time the inner interrupt returns, even if the inner interrupt used them, they will be put back to idle, and A can safely switch to them. Everything else works the same as current hardware.

There's the cost of a branch, but you could remove that by making it a hardware feature. It's a branch that should predict well though.

Re:Why do CPUs have multiple cache levels? by CyberDildonics on Monday August 08, 2016 @10:31AM (#12248046)
Isn't a cache miss around 100 nanoseconds? This sounds like memory latency without all the out of order execution and other modern CPU features.
Re:Why do CPUs have multiple cache levels? by vardump on Monday August 08, 2016 @11:37AM (#12248584)
Nothing to do with (local) DRAM, everything to do with PCI-e bus.

Reading and writing to memory mapped I/O registers is how you send commands to peripherals, read their status, etc. These registers are not really memory at all, but representation on various logic states on the peripheral. So what you write is often not what you read back.

Note that I/O memory mapping has nothing to do with usermode memory mapping.

Re:Why do CPUs have multiple cache levels? by exDM69 on Monday August 08, 2016 @05:13AM (#12246393)
There are about 180 registers in the register file already. There are only names for 16 or so registers, the CPU internally does renaming for them. It would be possible to specify an API that leaves a part of the named registers reserved for kernel, but that wouldn't really help.

When an interrupt or system call happens, all the registers get pushed to the stack. The stack is typically in L1 cache (and subject to various CPU optimizations), so it's really fast to push the 16*64 bit registers to the stack.

System calls, interrupts and context switches are "slow" not because they have trivial overhead like pushing registers. What's really consuming the time is secondary effects like TLB flushes, changes to the page tables, polluting the branch predictor, etc. It takes a very long time for the CPU to "warm up" again after a context switch.

Re:Why do CPUs have multiple cache levels? by xxs on Monday August 08, 2016 @05:55AM (#12246518)
System calls are mode switch that's way faster than a context (i.e. process) switch. The latter virtually always has cold caches.

I've made the remark because it's fairly common to mistake mode and context switches.

Re:Why do CPUs have multiple cache levels? by exDM69 on Monday August 08, 2016 @05:58AM (#12246528)
Yes, and the x86-64 has a fast SYSCALL instruction.
Re:Why do CPUs have multiple cache levels? by monocasa on Monday August 08, 2016 @12:27PM (#12248946)
Fast being in the thousands of cycles last time I checked.
Re:Why do CPUs have multiple cache levels? by the_mitsuhiko on Monday August 08, 2016 @02:55PM (#12250031)
The whole syscall maybe but certainly not the method of invoking it.
Re:Why do CPUs have multiple cache levels? by bogomipz on Monday August 08, 2016 @07:30AM (#12246878)
Can you elaborate on both there being 180 registers and the CPU does renaming of them? Surely the RAX register in an X86_64 CPU is always the same physical location no?
Re:Why do CPUs have multiple cache levels? by Tuna-Fish on Monday August 08, 2016 @10:09AM (#12247866)
> Surely the RAX register in an X86_64 CPU is always the same physical location no?

No, it is not.

Modern CPUs all use Physical Register Files or PRFs for implementing OoO. The way they work is that there is one backing register file of ~150-200 registers, and a naming table in the frontend. Each register file in the backing table can be in one of 3 states -- waiting for data, contains data, or clean. Every time an instruction that writes data to a register is executed, during the register rename stage the renamer picks one register from the clean set, assigns that as the output of the uop and the current value of the logical register, and sets it as waiting for data.

That is, let's say you execute:

add RAX, RAX

and the current value of RAX in the rename table was PRF#1, with PRF#1 carrying data and all other physical registers clean. In the renamer, this would then turn into:

add PRF#2, PRF#1, PRF#1

if this instruction was immediately followed by another add, RAX, RAX, it would then turn into:

add, PRF#3, PRF#2, PRF2, and after renaming that instruction RAX points to PRF#3.

and so on. In PRF machines, architectural registers only exist as pointers into the PRF.

The reason for this design is that it makes OoO execution simple, and reduces unnecessary data movement. An instruction is ready to execute once all it's inputs have data in the PRF, and when it executes there is no need to move data into some special architectural register.

Registers are reaped from the "haves data" set into the clean set once no instruction or architectural register points at them. Note that multiple architectural registers can point to the same physical register: mov rax, rbx is resolved in the frontend just by pointing rax to the same register as rbx, and there is typically a special register for the value 0 that all common register-clearing operations use.

Re:Why do CPUs have multiple cache levels? by bogomipz on Monday August 08, 2016 @03:34PM (#12250306)
This was a fantastic explanation so thanks. A couple of questions:

PRF is Physical register file? As opposed to the logical which can point to different backing store(the actual SRAM.)

Register renaming and OoO operations are really enabled by micro-ops? In other words on a CPU with completely hard-wired control unit such things would never be possible.

Re:Why do CPUs have multiple cache levels? by Tuna-Fish on Monday August 08, 2016 @07:20PM (#12251478)
> PRF is Physical register file? As opposed to the logical which can point to different backing store(the actual SRAM.)

Yep. PRF means the single backing store where all values go, and PRF systems are named for it because they are usually contrasted to the other very common way to implement OoO, ROB-backed systems, where there is a specific location for the final architectural value, and possibly multiple in-progress values in the ROB. Intel used values in the ROB in all their CPUs up to Sandy Bridge, which was their first PRF design.

(The main difference between the types is that ROB-backed is faster in circuit delay, but moves more data than a PRF design, so on the same process they potentially clock higher but produce more heat. PRF-based designs are also easier to scale wider than the ROB-based design.)

> Register renaming and OoO operations are really enabled by micro-ops? In other words on a CPU with completely hard-wired control unit such things would never be possible.

No, you can do renaming and OoO well without uops, it just requires that your instruction set is designed to be amenable to it. Before x86 had uops, it couldn't do OoO and the competing RISC CPUs were way faster because of this. PPro added uops precisely because they made it possible for an x86 cpu to do OoO, and eventually x86 beat all the competing RISC chips at their own game.

Re:Why do CPUs have multiple cache levels? by monocasa on Monday August 08, 2016 @05:35PM (#12251041)
> PRF is Physical register file?

Yep, it's the actual renamed registers.

> Register renaming and OoO operations are really enabled by micro-ops? In other words on a CPU with completely hard-wired control unit such things would never be possible.

No, they're orthogonal concepts. The first OoO processor (the System 360 model 91) didn't have uops.

Re:Why do CPUs have multiple cache levels? by bogomipz on Monday August 08, 2016 @07:00PM (#12251396)
Sorry that shouldn't have said OoO, register renaming and micro-ops I meant.
Re:Why do CPUs have multiple cache levels? by monocasa on Monday August 08, 2016 @07:21PM (#12251480)
It did register renaming too. It was designed by Tomasulo of Tomasulo's algorithm.
Re:Why do CPUs have multiple cache levels? by bogomipz on Monday August 08, 2016 @08:48PM (#12251830)
Wow, this is kind of blowing my mind that they were doing this with a hard-wired control unit in 1969(I think I have the date right.) Big Blue, its easy now a days to forget just how amazing they were. Do you have links you can recommend? Thanks.
Re:Why do CPUs have multiple cache levels? by JoeAltmaier on Monday August 08, 2016 @10:12AM (#12247881)
And the 'Mill' design just uses a single pointer into a ring buffer? Cool.
Re:Why do CPUs have multiple cache levels? by Tuna-Fish on Monday August 08, 2016 @10:22AM (#12247970)
Actually, the Mill uses just the forwarding network which I completely ignored in this explanation.

The really short explanation about the forwarding network is that writing/reading the PRF takes too much time for you to read it and do work on the same cycle. If you operated on it alone, all operations that were dependent on each other would have multi-cycle latencies.

Since this sucks, in addition to the PRF the machines have a forwarding network, where the result of every instruction is broadcast to all the execution units of a similar type. If the broadcasted PRF number matches the register you want, it's read from the forwarding network instead of the PRF.

AFAICT, the Mill works by completely eschewing the final register file, and exclusively using the forwarding network with some local storage at each execution unit for the past values on the network.

Re:Why do CPUs have multiple cache levels? by JoeAltmaier on Monday August 08, 2016 @10:24AM (#12247990)
Excellent description! Thanks.
Re:Why do CPUs have multiple cache levels? by ikeyany on Monday August 08, 2016 @08:05AM (#12247037)
I am not who you responded to, but: the registers are always in the same physical location, but internally, they are virtually renamed for efficient reuse and to avoid resource contention. If the CPU knows the stream of assembly instructions to be executed, it can abstract away actual register names and show a larger number of registers than what's physically available.
Re:Why do CPUs have multiple cache levels? by Symmetry on Monday August 08, 2016 @11:26AM (#12248502)
A larger cost would be from the extra bits in the instruction stream it takes to specify the new registers and the resultant extra icache pressure.
Re:Why do CPUs have multiple cache levels? by joseraul on Monday August 08, 2016 @07:05AM (#12246766)

  it's really fast to push the 16*64 bit registers to the stack
Since the CPU has 180 registers (with only 16 names), why don't we need to push all 180 to store context?
Re:Why do CPUs have multiple cache levels? by Dylan16807 on Monday August 08, 2016 @07:41AM (#12246921)
All that extra state is there to help overlap instructions on a time scale of nanoseconds. Every instruction has its own name->register mapping. If you're switching to kernel mode or maybe if you miss a branch or for whatever other reason, the CPU consolidates you back down to running one instruction. Once that happens, you only have one name->register mapping and all the registers have their correct values. The hidden state is reduced to nothing and you only have to save the "real" state of those 16.
Re:Why do CPUs have multiple cache levels? by cfallin on Monday August 08, 2016 @11:24AM (#12248475)
To expand on another answer here -- there are more values in the PRF than there are names because "old" instructions in flight can refer to outdated versions of architectural registers (the names). But a new instruction can only see the latest versions of the architectural registers, so only those 16 actually matter w.r.t. future execution: when we switch back to the task, its new instructions will ony need the 16 live values.
Re:Why do CPUs have multiple cache levels? by exDM69 on Monday August 08, 2016 @07:08AM (#12246785)
Because the CPU works "as if" there were only 16.
Re:Why do CPUs have multiple cache levels? by bogomipz on Monday August 08, 2016 @03:22PM (#12250235)
But modern CPU TLBs even have context process IDs(CPIDs)now so many times the whole cache doesn't totally need to "warm up" again.
Re:Why do CPUs have multiple cache levels? by kqr on Monday August 08, 2016 @04:34AM (#12246256)
As far as I understand it, the x86 uses many more registers than you think "under the hood", and it's exposing just a few "virtual registers" that are mapped to any of the underlying ones. So what you're thinking of is already done to an extent, except the at the kernel-level it's invisible.

(Exposing more virtual registers have two main costs, then: you lose backwards compatibility for all programs that use the extended register set, and to back them up with the same technique you need several more real registers.)

Re:Why do CPUs have multiple cache levels? by unsigner on Monday August 08, 2016 @04:32AM (#12246248)
x86-64 chips have hundreds of general purpose registers; google "register renaming"
Re:Why do CPUs have multiple cache levels? by vardump on Monday August 08, 2016 @04:34AM (#12246260)
Hardly relevant in (obvious) interrupt service routine context. These registers you're talking about are only used for reordering instruction stream to avoid stalls. Nice for general performance, but useless when servicing interrupts.
Re:Why do CPUs have multiple cache levels? by amelius on Monday August 08, 2016 @06:19AM (#12246604)
His reply does not mean anything without a quantitative analysis.
Re:Why do CPUs have multiple cache levels? by posterboy on Monday August 08, 2016 @06:15AM (#12246583)
The idea is close to duplicating the whole core, thus we have multi-core solutions.