4 ms·

This is no doubt obvious to hardware folks, but one enlightening moment is when I came to understand register renaming. Previously I had the (wrong) idea that

This is no doubt obvious to hardware folks, but one enlightening moment is when I came to understand register renaming. Previously I had the (wrong) idea that rdi, rsi, etc corresponded to physical bits. Register renaming involved some exotic notion where these registers might be saved and restored. Now I understand that rdi, rsi, etc. are nothing but compressed node identifiers in an interference graph. Ideally we'd have infinite registers: each instruction would read from previous registers and output to a new register. And so we would never reuse any register, and there'd be no data hazards. Alas we have finite bits in our ISA, so we must re-use registers. Register renaming is the technique of reconstructing an approximate infinite-register interference graph from its compressed form, and then re-mapping that onto a finite (but larger) set of physical registers. Mostly "register renaming" is a bad name. "Dynamic physical register allocation" is better.

zaarn 8y ago
While not quite infinite, what you want sounds awfully close to a belt machine; Each instruction reads data from positions on the belt and then puts a few values at the start of the belt. This causes values on the end to "fall off". The MILL CPU is an example of this architecture.
- ridiculous_fish 8y ago
  The belt approach is sort of hybrid between registers and stack architectures. A disadvantage is that values on the belt may be at unknown locations after branches: var x = something(); if (somethingElse() { stuff(); } print(x); // where is x?? Here x has to be spilled and reloaded. This is worse than a register machine where x can be assigned a register for its entire lifetime. I think this style of architecture is at its best for straight-line code, but suffers with branchy code, loops, etc. which will require a lot of spilling.
  - Symmetry 8y ago
    The main reason to adopt a belt is that you don't need to encode the destination (or destinations on an instruction that returns multiple values). Instruction cache pressure is typically a critical design constraint on VLIW machines which is presumably why they went this route. Also, that simplifies the compilers job and ties into the spiller design, etc.
deleted 8y ago
[deleted]
cgrand-net 8y ago
"Now I understand that rdi, rsi, etc. are nothing but compressed node identifiers in an interference graph. Ideally we'd have infinite registers: each instruction would read from previous registers and output to a new register. And so we would never reuse any register, and there'd be no data hazards" I'm under the impression that we don't see the causality flowing in the same direction. To me we first had a limited set of registers (imposed by the ISA), then to get better perf through out of order execution, cpus had to infer a deps graph and use register renaming. Ironically all this silicon is spent to recover information that was known to the compiler (eg through SSA) and lost during codegen (register allocation).
- nuriaion 8y ago
  The space in an instruction is very limited. (If the representation of an instruction needs more bits you need more bandwidth, more cache space etc.) So it can be beneficial to only address 8 registers but then have a detection for spilling of spilling to RAM etc. (It can even be beneficial to specify only 2 registers (a = a + b instead of a = b + c) and replace a copy of registers with a rename.
  - gpderetta 8y ago
    Exactly. In principle even memory can be renamed, although I'm not sure any current CPU actually does it (there are rumors). It would be great if the actual SSA graph could be directly passed from the compiler to the CPU, but what's saved by getting rid of renaming would probably be used to handle the much harder decoding. It would probably have implications for context switching overhead.
- Taniwha 8y ago
  And essentially that's the idea that the VLIWs with no interlocks have - one I worked on made the output registers of the execution stages architecturally visible
rayiner 8y ago
You’re really reconstructing a data depence graph not an interference graph. In an interference graph, there is an edge between nodes that are alive at the same time. That information remains implicit in the OOO machine (because a physical register stays allocated to a value through retirement). In a data dependence graph there are edges from operations to their operands. You need to reconstruct the data dependence links explicitly—during renaming you need to map the input operands to the correct renamed physical registers. This is where “renaming” comes from. You “rename” the architectural register operands in each instruction with the corresponding physical register or tag: https://www.d.umn.edu/~gshute/arch/register-renaming.xhtml https://www.d.umn.edu/~gshute/arch/register-renaming.xhtml. After renaming, the data dependence graph will be explicit in the reorder buffer.
- rayiner 8y ago
  A couple of more points. The architectural registers are real places. Say you write to RDX, don’t do anything with it for a million instructions, then read from it. Where does the data come from? There is an architectural register file and RDX is a specific register in it. The renaming is only temporary. An instruction doesn’t hang on to a ROB entry and rename register until every instruction that may use it has executed. When the instruction is retired in order, the value is written back to the architectural register file, and the rename register and ROB entry is freed for some other instruction. So the renaming is ephemeral, only lasting until retirement.
  - KMag 8y ago
    Interesting. I always figured there was just a lookup table mapping ISA registers to physical registers that was used by instruction decode, a bit vector (one bit per physical register) indicating which physical registers were in use, and each micro-op would carry with it which physical register(s) would be freed up upon instruction retirement. If a register might or might not be renamed, what's the advantage of usually storing a given register in a given location? Is the main reason power savings, so checking a single bit to check if a register has been renamed, before paying the power and time to perform a lookup in the renaming table? Is access to a renamed register then slower than access to a non-renamed register?
AtlasBarfed 8y ago
As was pointed out in another thread once which I don't recall, almost all aspects of assembly programming in x86 aren't really low level anymore. It's just another abstracted high-level language, although one that still mirrors/is tied to the fundamental idea of an x86 machine. As detailed in the article, x86 opcodes are translated/compiled on the fly to micro-ops. The registers are renamed as needed to squeeze data. Memory locations are actually fulfilled by any of three to five levels of cache, RAM, or swap. Cores are variable in their number of issues, and can share the same instruction pipelines in hyperthreading.
fosk 8y ago
> Ideally we'd have infinite registers: each instruction would read from previous registers and output to a new register. And so we would never reuse any register, and there'd be no data hazards. Crazy thought but would it be possible to build a decentralized and distributed CPU on top of the blockchain? Edit: to the downvotes, care to explain? I am genuinely curious to know the answer, and curiosity should be a driving factor in this community
- deepnotderp 8y ago
  Latency.
- KMag 8y ago
  If the blockchain in question is Turing-complete, then it would be possible (by trivial consequence of definition) to build an emulator for any other Turing-complete (or even non-Turing-complete) deterministic processor on the blockchain. However, the latency per operation would be prohibitively high for most purposes, unless each "CPU Instruction" is complex enough to greatly stretch definitions and lose meaningful distinctions. So, the answer to the most strait forward interpretation of your question is basically "Yes, it's obviously possible and likely trivial, but probably not practical"

zaarn 8y ago

While not quite infinite, what you want sounds awfully close to a belt machine; Each instruction reads data from positions on the belt and then puts a few values at the start of the belt. This causes values on the end to "fall off". The MILL CPU is an example of this architecture.

ridiculous_fish 8y ago
The belt approach is sort of hybrid between registers and stack architectures. A disadvantage is that values on the belt may be at unknown locations after branches: var x = something(); if (somethingElse() { stuff(); } print(x); // where is x?? Here x has to be spilled and reloaded. This is worse than a register machine where x can be assigned a register for its entire lifetime. I think this style of architecture is at its best for straight-line code, but suffers with branchy code, loops, etc. which will require a lot of spilling.
- Symmetry 8y ago
  The main reason to adopt a belt is that you don't need to encode the destination (or destinations on an instruction that returns multiple values). Instruction cache pressure is typically a critical design constraint on VLIW machines which is presumably why they went this route. Also, that simplifies the compilers job and ties into the spiller design, etc.

deleted 8y ago

[deleted]

cgrand-net 8y ago

"Now I understand that rdi, rsi, etc. are nothing but compressed node identifiers in an interference graph. Ideally we'd have infinite registers: each instruction would read from previous registers and output to a new register. And so we would never reuse any register, and there'd be no data hazards" I'm under the impression that we don't see the causality flowing in the same direction. To me we first had a limited set of registers (imposed by the ISA), then to get better perf through out of order execution, cpus had to infer a deps graph and use register renaming. Ironically all this silicon is spent to recover information that was known to the compiler (eg through SSA) and lost during codegen (register allocation).

nuriaion 8y ago
The space in an instruction is very limited. (If the representation of an instruction needs more bits you need more bandwidth, more cache space etc.) So it can be beneficial to only address 8 registers but then have a detection for spilling of spilling to RAM etc. (It can even be beneficial to specify only 2 registers (a = a + b instead of a = b + c) and replace a copy of registers with a rename.
- gpderetta 8y ago
  Exactly. In principle even memory can be renamed, although I'm not sure any current CPU actually does it (there are rumors). It would be great if the actual SSA graph could be directly passed from the compiler to the CPU, but what's saved by getting rid of renaming would probably be used to handle the much harder decoding. It would probably have implications for context switching overhead.
Taniwha 8y ago
And essentially that's the idea that the VLIWs with no interlocks have - one I worked on made the output registers of the execution stages architecturally visible

rayiner 8y ago

You’re really reconstructing a data depence graph not an interference graph. In an interference graph, there is an edge between nodes that are alive at the same time. That information remains implicit in the OOO machine (because a physical register stays allocated to a value through retirement). In a data dependence graph there are edges from operations to their operands. You need to reconstruct the data dependence links explicitly—during renaming you need to map the input operands to the correct renamed physical registers. This is where “renaming” comes from. You “rename” the architectural register operands in each instruction with the corresponding physical register or tag: https://www.d.umn.edu/~gshute/arch/register-renaming.xhtml https://www.d.umn.edu/~gshute/arch/register-renaming.xhtml. After renaming, the data dependence graph will be explicit in the reorder buffer.

rayiner 8y ago
A couple of more points. The architectural registers are real places. Say you write to RDX, don’t do anything with it for a million instructions, then read from it. Where does the data come from? There is an architectural register file and RDX is a specific register in it. The renaming is only temporary. An instruction doesn’t hang on to a ROB entry and rename register until every instruction that may use it has executed. When the instruction is retired in order, the value is written back to the architectural register file, and the rename register and ROB entry is freed for some other instruction. So the renaming is ephemeral, only lasting until retirement.
- KMag 8y ago
  Interesting. I always figured there was just a lookup table mapping ISA registers to physical registers that was used by instruction decode, a bit vector (one bit per physical register) indicating which physical registers were in use, and each micro-op would carry with it which physical register(s) would be freed up upon instruction retirement. If a register might or might not be renamed, what's the advantage of usually storing a given register in a given location? Is the main reason power savings, so checking a single bit to check if a register has been renamed, before paying the power and time to perform a lookup in the renaming table? Is access to a renamed register then slower than access to a non-renamed register?

AtlasBarfed 8y ago

As was pointed out in another thread once which I don't recall, almost all aspects of assembly programming in x86 aren't really low level anymore. It's just another abstracted high-level language, although one that still mirrors/is tied to the fundamental idea of an x86 machine. As detailed in the article, x86 opcodes are translated/compiled on the fly to micro-ops. The registers are renamed as needed to squeeze data. Memory locations are actually fulfilled by any of three to five levels of cache, RAM, or swap. Cores are variable in their number of issues, and can share the same instruction pipelines in hyperthreading.

fosk 8y ago

> Ideally we'd have infinite registers: each instruction would read from previous registers and output to a new register. And so we would never reuse any register, and there'd be no data hazards. Crazy thought but would it be possible to build a decentralized and distributed CPU on top of the blockchain? Edit: to the downvotes, care to explain? I am genuinely curious to know the answer, and curiosity should be a driving factor in this community

deepnotderp 8y ago
Latency.
KMag 8y ago
If the blockchain in question is Turing-complete, then it would be possible (by trivial consequence of definition) to build an emulator for any other Turing-complete (or even non-Turing-complete) deterministic processor on the blockchain. However, the latency per operation would be prohibitively high for most purposes, unless each "CPU Instruction" is complex enough to greatly stretch definitions and lose meaningful distinctions. So, the answer to the most strait forward interpretation of your question is basically "Yes, it's obviously possible and likely trivial, but probably not practical"