The Surprising Subtleties of Zeroing a Register (2013) | Hacker News Reader

The Surprising Subtleties of Zeroing a Register (2013)

randomascii.wordpress.com

102 pointsingve22 comments

Author here - I just want to drop in to reiterate how awesome register renaming is. It's a bit weird to try and understand, but it is crucial to how these out-of-order processors run, and it is the trick which lets the register zeroing run so efficiently.

An x86-64 CPU has sixteen integer registers, but 100-200 physical integer registers. Every time an instruction writes to, say, RAX the renamer chooses an available physical register and does the write to it, recording the fact that RAX is now physical-register #137. This allows the breaking of dependency chains, thus allowing execution parallelism.

In the case of the zeroing instructions the register renamer says "RAX now maps to physical-register #0" where that is a register reserved for the purpose of being zero. No execution is needed. It's beautiful.

For more details read up on out-of-order execution and register renaming.

This is a good place to start: https://en.wikipedia.org/wiki/Tomasulo_algorithm.

Butler Lampson mentions register renaming as one of a dozen paradigmatic neat techniques in this 2015 presentation:

http://bwlampson.site/Slides/Hints%20and%20principles%20(HLF... Edit: corrected link

It's easy for software people not to ever encounter it!

> It's easy for software people not to ever encounter it!

Yep, because it does its magic without any intervention required.

One concrete example that I like is this:

mov rax,[rsi+0] mov [rdi+0],rax mov rax,[rsi+8] mov [rdi+8],rax

This moves sixteen bytes of memory, all of it going through rax. Without register renaming the third instruction can't run until the second instruction completes, because they're both using rax. With register renaming the third instruction uses a different physical register for rax, and the out-of-order engine can do the loads in parallel and the stores in parallel.

Before anybody freaks out - register renaming doesn't change the semantics of your program. It just makes your program run faster. It just means that you can write code like the above - there's no need to rearrange the instructions and use multiple temporary registers, because the CPU will do it for you, and will dirty fewer architectural registers.

I wonder how often (golang, let's say)

    x, y = y, x

Just becomes register renaming? What about

    array[i], array[j] = array[j], array[i]

?

Register renaming doesn't mean changing the name of registers you already have (which isn't really possible), it just adds new "virtual"/concurrent registers that conserve the semantics of operations. So what you say doesn't sound right to me: register renaming is actually a way of (re)labelling the results of small ALU jobs to be distributed for concurrent execution. It's not in any way about switching references around on live data as you suggest. Not 100% sure about this but the flavour of what I've read doesn't involve that kind of fancy footwork.

If the "x, y = y, x" is implemented using the x86 "swap" instruction then the CPU could implement the swap using register renaming, I think - with no execution unit activity required. I don't know if it does.

But everything that golang (or C or C++ or whatever) does has to be expressed in assembly language, and assembly language doesn't directly control register renaming - it's a hidden implementation detail.

Thanks. That clarifies things.

This is highly appreciated: the kind of advanced, specific knowledge that your average hacker might not know, but should improve their/our thought processes, efficiency, reliability security and general understanding of programming. This is one of the primary reasons HN is so valuable, and I do wish there were some good repository of the best of these kinds of article to browse, apart from searching HN, which like anything can be noisy.

As to the 4 instruction limit, see: https://www.realworldtech.com/sandy-bridge/5.

The register rename stage, which does the zeroing, can handle four instructions per cycle. It’s not immediately obvious from the picture, but after instructions are fetched from the uop cache, they are sent to a 28-entry decoder queue, which can act as a small loop buffer. From there, four uops per cycle are sent to the allocate/rename stage (which is part of the ROB block in the first picture).

It's said in the article, under the "Update: January 7, 2013" heading.

> CPU designers could create a design where an xor instruction was faster than a sub instruction. However that would mean that sub would take at least two clock cycles, since instruction lengths are integer cycle counts. Unless this modification let them at least double the clock speed it would be a net loss. It’s better to make xor take just as long as sub. You can’t make an xor instruction take, say, 0.6 cycles. But feel free to try.

Earlier, the article says that the process can perform four instructions per cycle. Just to confirm, this isn't normally referred to as taking "0.25 cycles per instruction", right?

There is some parallelism within in each CPU core so it can do four additions each cycle. But those don't happen after each other, they happen simultaniously. From an eagle eye's view it can look like 0.25 cycles per instruction, so on a higher abstraction level that's a valid view on it. But in reality they start and end at the same time each takes one cycle.

The Intel manuals sometimes use that as a shorthand, but no, it’s usually not. The difference is between throughout and latency. You can process four independent instructions per cycle in parallel (if none depend on the results of the others), but the results of a given instruction will take at least one cycle to be available for the next instruction that uses it as an input. (It takes 9 months to make a baby even though you can make more than one at a time.)

> You can process four independent instructions per cycle in parallel

is this down to pipelining, or is that separate?

Actual redundant hardware. There are multiple ALUs for example (although not all equal), multiple load/store units. But the bottleneck that prevents of going wider than 4 is often the rename up to 4 registers per clock.

Modern processors are superscalar. What this means is that you have multiple independent execution units that can be scheduled each cycle.

On Skylake, for instance, the execution units are:

Port 0: int ALU, FP ALU, vector ALU, integer multiply/divide, branch

Port 1: int ALU, FP ALU, vector ALU

Port 2: Load unit

Port 3: Load unit

Port 4: Store unit

Port 5: integer ALU, vector ALU

Port 6: integer ALU, branch

Port 7: Store unit [address component]

Every instruction (or, more accurately, every micro-op; instructions don't exist at this point) can get scheduled onto one of these ports if that port has the capability to process it.

Of course, there's also a limitation on the abilities of the instruction decode unit on how many instructions it can decode and convert into micro-ops each cycle.

Pipelining is necessary is well, but super-scalar is the key ingredient here - parallelism.

Pipelining means that instruction fetch, decode, execution, and retirement are done in separate stages, each one taking at least one cycle.

Super-scalar/parallelism means that there are multiple units for all of these stages so the CPU can fetch many instructions in parallel, decode many instructions in parallel, etc.

The cool/critical thing here is that many Intel CPUs can execute three XOR instructions in parallel but can retire four. Because the CPU recognizes XOR of an instruction with itself as a special case it skips the execution stage and can then process four per cycle.

Or, more likely in real code, the execution units are available for other instructions to use.

Strictly speaking pipelining isn't actually necessary, it's just hard to imagine why you'd bother with superscalar execution without first exhausting the relatively-lower-hanging-fruit of pipelining.

The time instructions take are usually boiled down to two metrics: reciprocal throughput (you can issue 1 instruction of this type every N cycles), and latency (an instruction can use the result of this instruction N cycles after it executes). Latency is necessarily an integer number of cycles, but reciprocal throughput can be less than 1 if there are multiple execution ports in a superscalar machine.

For example, the latency of a multiply instruction is usually about 3-4 cycles. But the reciprocal throughput is generally 1 (or 0.5 if you have two multiply units)--the execution unit is pipelined to allow a new input every cycle.

I recently had an interview at one of the big chip designers, and towards the end they gave a few basic computer architecture and assembly brainteaser questions. One of them was whether I was aware of a smaller instruction for zeroing a register, and I did manage to guess xor after a little thought. It's a trivial idea, but very satisfying to realize for the first time.

(2013)

The article was written in 2012, but was last updated in 2013, so dealer's choice?

Written December 29th and updated 9 days later. :)

Reply on news.ycombinator.com