4
$\begingroup$

As I understand, all modern CPUs perform register renaming: given a sequence of instructions to interpret, they check which registers these instructions use, detect patterns where a register's previous value is overwritten, and then map the instruction sequence so that each instruction's "architectural" register is mapped to a physical register address in the register file.

My question is: How much overhead does this process add?

Register renaming allows the CPU to have many more registers than the encoding allows, and to better detect independent instructions that can be executed in parallel. And, okay, better instruction-level parallelism means faster execution, especially for high-latency operations like loads.

But to perform the algorithm I described, you basically have to do register allocation in the CPU, right? You have to dynamically allocate register indices, analyze the code to detect live ranges, maybe do some alias analysis if you also want to include spilled registers, etc. The idea that you can do all this work and still come out ahead just seems counter-intuitive to me.

Do CPU-makers just have some extremely efficient heuristics for JIT register allocation? Or is it a case of "this is extremely expensive to do, but even high overhead is worth it if we can get just a few more instructions per second for a given core"?

$\endgroup$

2 Answers 2

1
$\begingroup$

How much overhead does this process add?

The process is nowhere near as bad as you made it out to be, more on that next, but there is a more general misconception that I think underlies this question: it presumes that "taking time" while processing an instruction adds overall overhead. That is mostly not the case, as making a pipeline longer affects primarily branch mispredictions (and other restarts) but not the throughput under normal conditions, and usually not even the latency of individual instructions (unless it's a specific part of the pipeline that got longer). Making the pipeline longer is not free, but the cost shows up only in limited circumstances, not everywhere all the time.

But to perform the algorithm I described, you basically have to do register allocation in the CPU, right?

Yes, but since this happens as the code is running we have some advantages. For example, we do not need to come up with register names that would be valid statically. We're not statically rewriting the code. It's more like this:

  • Decode an instruction.
  • For every source operand, replace it with the newest physical register corresponding to that ISA-level register.
  • Allocate a physical register the destination operand, update the rename map accordingly.

There is no analysis of arbitrary blocks of code as a whole, it's nothing like what a compiler does, renaming is local, perhaps myopic.. But that's not a limitation, it's actually better that way: this allows a destination to be renamed differently across different iterations of a loop, enabling parallelism across the iterations of the loop. Renaming multiple instructions at once involves something that you might call analysis of the code, but only of a limited number instructions (eg 4, or however wide the renamer is) and only in a local context to "chain" the new name of a destination into the operands of the next instructions that are renamed within the same cycle.

Allocating a register is not a super heavy operation, the "free list" might be represented as a bitvector of available physical registers (with one pulled out using a priority decoder) or as a circular array (small RAM and two indices), either way it's not that big of a deal. Back in university I went with the bitvector approach, it seems that RISCV-BOOM does as well, such low level details are fairly scarce though.

Freeing physical registers can in the simplest case be done based on this principle: when the destination of an instruction is renamed, also record with it the previous name of the destination register. When this instruction retires, that previous name can be freed, since it corresponds to a register that no newer instruction can read (all newer instructions would read the new name). Back in university, that is the technique I used, and it seems that BOOM does too.

In practice there are several reasons why more complicated techniques are used. The register reclamation algorithm that I sketched is extremely conservative (there are more aggressive techniques), and does not work if multiple ISA-level registers can be renamed to the same physical register (which happens as a result of move-elimination aka zero-latency copying, and as a result of memory bypassing). You can read about some more advanced techniques in eg "Cost Effective Physical Register Sharing".

I'm not sure how reasonable it is to compare a modern pipeline with a hypothetical variant of that pipeline sans renaming (since that invalidates the design), but if I do it anyway, it may add a couple of stages:

  • Maybe a front-end stage specifically for Rename, but it depends. There should be some tendency towards extra front-end stages on average, since it adds logic, but whether that results in an extra stage depends on the specifics of the design. It may be possible to spread the renaming logic over stages that were already present (decode, enqueue-to-backend).
  • Maybe an extra back-end stage to read from an increasingly large physical register file. The bigger it is, the longer that will take. In the classic RISC pipeline there was no separate "register read" stage, but at least one separate stage for that is present in many modern pipelines. Note that even here, adding an extra pipeline stage is still not free but it also does not make instructions slower as such. The extra steps between the reservation station(s) and the actual execution units means that the "wakeup" logic has to(if we want dependent instructions to be able to execute back-to-back, and I do, because lacking that ability would actually add overhead to many instructions) wake up (make available for select/issue) instructions some cycles before its operands are available (in contrast with the classic Tomasulo algorithm where we wait until the operands have been broadcasted over the result bus), which is less bad than it looks since most instructions have a known fixed latency (so we can predict when their result will be available), but certainly an extra source of complications.

So to recap:

How much overhead does this process add?

I still don't know exactly how to answer that, but it's not as bad you probably thought.

$\endgroup$
0
$\begingroup$

Remapping registers costs zero time. It can be done easily while moving an instruction into the dispatch queue, so whatever time it takes is hidden. For example "R3 = R7 + R11", we lookup that R7 is currently held in RR65, R11 is currently held in RR43, RR113 is free so from now on RR113 will hold R3, and the instruction "RR113 = RR65 + RR43" is stored in the dispatch queue.

All you do is having many rename registers, and using whatever is free right now. There is no need for any clever register allocation algorithm.

And it should be obvious that you can't do out-of-order processing without rename registers. It's not "a few more instructions per second", having no rename registers would be a total disaster and absolutely kill performance. Take this sequence:

R1 = R2 / R3
Store R1 at address 2000
R1 = R4 + R5

Without rename registers, the third instruction would have to wait (needlessly) for the second one to finish. Which means it would have to wait for the slow division to finish.

$\endgroup$
8
  • $\begingroup$ "It's not 'a few more instructions per second', having no rename registers would be a total disaster and absolutely kill performance." The example you give doesn't support your claim too well, though. On most architecture's you'd expect an ADD to take about one cycle, so scheduling it in sequence wouldn't kill performance (assuming decoding and writeback are still pipelined). A slower operation like a load would be a better example. $\endgroup$ Jan 3, 2023 at 17:12
  • 1
    $\begingroup$ I gave an example in the exact same paragraph. And you focussed so much on proving me wrong that you missed the division. $\endgroup$
    – gnasher729
    Jan 3, 2023 at 20:07
  • 1
    $\begingroup$ "And it should be obvious that you can't do out-of-order processing without rename registers." Well it's not that obvious. The CDC 6600 had out-of-order execution two years before the first machine with register renaming (the IBM System/360 model 91). You just can't do it well; the 6600 had to halt instruction issue on a WAW hazard. $\endgroup$
    – Pseudonym
    Jan 4, 2023 at 13:25
  • $\begingroup$ Well, that was actually my example (just added a division first to make it painful) and it stops out-of-order execution. The second instruction storing to the same register cannot be executed out-of-order. You could have a shadow register for each register which wouldn’t be quite register renaming and allow two active instructions writing to the same register but not three. $\endgroup$
    – gnasher729
    Jan 5, 2023 at 8:54
  • $\begingroup$ Look, I'm sorry if I'm missing something, but I don't think this is a strong example? Register renaming doesn't change the fact that the DIV and the STORE will happen in sequence. The only thing register renaming gives you in that example is making the ADD happen sooner. But ADD is usually only one cycle. If the other two take 10 each, then (DIV => STORE => ADD) will take 21 cycles and (DIV => STORE, ADD) will take 20. Register renaming only saves one cycle in that example. $\endgroup$ Jan 8, 2023 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.