5 ms·

Most (all?) modern processors utilize out-of-order execution. The main advantage is that it increases IPC (instructions per cycle) in the long run. The high-le

by Cyph0n 8y ago

Most (all?) modern processors utilize out-of-order execution. The main advantage is that it increases IPC (instructions per cycle) in the long run. The high-level idea is that you queue up your instructions in a table of sorts and execute them as they're ready (i.e., based on dependencies). You then re-order the instructions at the end of the pipeline. The main challenges with this technique are: (1) handling exceptions and (2) speculative execution. For (1), you can use a re-order buffer. For (2), you would typically flush the instruction table noted above.

muizelaar 8y ago
The ARM Cortex-A55 is modern and in-order. Out-of-order CPUs tend to be large so if you want a small CPU you'll still go with in-order.
- zozbot123 8y ago
  Energy/power efficiency might be a more relevant concern than mere size - OOO execution is fast but energy intensive, for a given workload. (Granted, the latest process nodes might be a tad different, with "size" also impacting power consumption directly due to leakage currents. This stuff can get a bit complicated.)
- bogomipz 8y ago
  Interesting. Is lower power OOE an area of active research?
  - Symmetry 8y ago
    Well, to the extent that improved process brings lower power it's an area of stupendous research investment. If you just mean architecturally there are people looking at ways to use less power by being less flexible but still get most of the benefit but it's not a huge topic.
  - zozbot123 8y ago
    The Mill processor architecture deserves mention here, as it basically aims to bridge VLIW-like low power usage with OOO-like performance. The way it attempts to do this is too complex to explain in a short comment, you can find detailed info on their website - but broadly-speaking it involves all sorts of 'tweaks' to ordinary VLIW, that ultimately result in something a bit different. (It should also be noted though that the initial, instruction decoding stages of a Mill-like 'belt' architecture are a lot closer to OOO than an ordinary VLIW. So the projected power savings would seemingly have to come from elsewhere - but they can be quite significant nonetheless, so the effort is projected to be worthwhile.)
    - bogomipz 8y ago
      Interesting I remember hearing about this processor architecture. Is is still being actively developed? I didn't see much in the way of news on the Mill site.
      - opencl 8y ago
        There are a few recent forum posts indicating that they're still working on it at least, but it seems to be going extremely slowly. 5 years ago it had already been in development for 10 years and there was supposed to be silicon shipping in 2-3 years. 2 years ago they were talking about an FPGA prototype that has yet to show up.
    - marcosdumay 8y ago
      I imagine (because there are not that many details on the Mill out there) that the power savings come mainly from: - A post-compiler compilation step that adapts a binary for a specific chip, replacing a complex hardware control module by a one-time software run, so the only thing actually on the chip is the routing; - A very nice set of primitives that push the non-determinism into data, instead of flow control. - Cheap interruptions, cheap memory access, and every other detail rethought to be cheap.
cesarb 8y ago
> The main challenges with this technique are: (1) handling exceptions RISC-V has an advantage here: other than load/store and instruction fetch/decode, the instruction set is designed to not cause exceptions. For instance, integer division by zero is defined to return a specific value, instead of being an error.
- jabl 8y ago
  Also, RISC-V doesn't have a flags register. Instead fused cmp+jmp branching instructions.
  - kannanvijayan 8y ago
    This is interesting to hear, and surprising. What are the provisions for efficient handling of integer overflows & underflows? I took a quick look at the ISA spec and am trying to track down how this is handled, as a curiosity.
    - jabl 8y ago
      AFAIU, none. It's designed for C, essentially, where signed integer overflows are undefined. In practice, the easiest and fastest design is to have it wrap around, just like unsigned. I'm not sure I agree with that particular design decision, considering newer languages such as Rust that want to detect overflows. Then again, if/when such languages become more important, I guess RISC-V could add an extension featuring some kind of trapping overflow (or whatever mechanism is deemed best).
      - zozbot123 8y ago
        The RISC-V spec does claim that "many overflow checks can be cheaply implemented using branches" and then provides recommended instruction sequences. One could definitely imagine a RV implementation where e.g. macro-op fusion is used to systematically turn some of these recommended sequences into hardware-assisted branches. (Ref: search for the "Integer Computational Instructions" section in the RISC-V "user mode" reference. It should be section 2.4)
dbcurtis 8y ago
Let me add a couple thoughts: 1. You typically won't get very far without also implementing register renaming, such that the reorder buffer is actually much larger than the register file. 2. You need to distinguish between instructions that are "complete" (result is available for internal bypass to another instruction that is being speculatively executed) versus "retired" (all instructions before it have retired, the instruction can no longer raise an exception, you know for certain that it was not executed because of incorrect speculation). Canonical, architecturally visible state is only written on retirement. 3. Without good branch prediction, it is kind of pointless. A reasonable rule-of-thumb-Kentucky-windage estimate is that 20-25% of the instructions that you encounter in execution order (not static code analysis) are branches. So if you have 30 or more instructions active in the pipe, your branch prediction needs to be pretty good or you waste too much work. (Note that some branches are just "flakey" (hard to predict) but the compiler can usually do a decent job of identifying those ahead of time. Thus, modern processors include a conditional-move instruction which allows the compiler to manage speculation and replace the flakey branch with an instruction that does not pollute the branch target buffer. 4. Watching what happens in the simulator at the end of a pointer chasing loop is good humor. A strongly predicted branch gets mispredicted on: while(p!=NULL) {}, and all sorts of page-fault, memory-exception, arithmetic-exception logic lights up all over the place until something asserts "OOPS_NEVER_MIND", at which point all that fun stuff collapses in a smoldering heap. Watching that never gets old.

by Cyph0n 8y ago

muizelaar 8y ago

The ARM Cortex-A55 is modern and in-order. Out-of-order CPUs tend to be large so if you want a small CPU you'll still go with in-order.

zozbot123 8y ago
Energy/power efficiency might be a more relevant concern than mere size - OOO execution is fast but energy intensive, for a given workload. (Granted, the latest process nodes might be a tad different, with "size" also impacting power consumption directly due to leakage currents. This stuff can get a bit complicated.)
bogomipz 8y ago
Interesting. Is lower power OOE an area of active research?
- Symmetry 8y ago
  Well, to the extent that improved process brings lower power it's an area of stupendous research investment. If you just mean architecturally there are people looking at ways to use less power by being less flexible but still get most of the benefit but it's not a huge topic.
- zozbot123 8y ago
  The Mill processor architecture deserves mention here, as it basically aims to bridge VLIW-like low power usage with OOO-like performance. The way it attempts to do this is too complex to explain in a short comment, you can find detailed info on their website - but broadly-speaking it involves all sorts of 'tweaks' to ordinary VLIW, that ultimately result in something a bit different. (It should also be noted though that the initial, instruction decoding stages of a Mill-like 'belt' architecture are a lot closer to OOO than an ordinary VLIW. So the projected power savings would seemingly have to come from elsewhere - but they can be quite significant nonetheless, so the effort is projected to be worthwhile.)
  - bogomipz 8y ago
    Interesting I remember hearing about this processor architecture. Is is still being actively developed? I didn't see much in the way of news on the Mill site.
    - opencl 8y ago
      There are a few recent forum posts indicating that they're still working on it at least, but it seems to be going extremely slowly. 5 years ago it had already been in development for 10 years and there was supposed to be silicon shipping in 2-3 years. 2 years ago they were talking about an FPGA prototype that has yet to show up.
  - marcosdumay 8y ago
    I imagine (because there are not that many details on the Mill out there) that the power savings come mainly from: - A post-compiler compilation step that adapts a binary for a specific chip, replacing a complex hardware control module by a one-time software run, so the only thing actually on the chip is the routing; - A very nice set of primitives that push the non-determinism into data, instead of flow control. - Cheap interruptions, cheap memory access, and every other detail rethought to be cheap.

cesarb 8y ago

> The main challenges with this technique are: (1) handling exceptions RISC-V has an advantage here: other than load/store and instruction fetch/decode, the instruction set is designed to not cause exceptions. For instance, integer division by zero is defined to return a specific value, instead of being an error.

jabl 8y ago
Also, RISC-V doesn't have a flags register. Instead fused cmp+jmp branching instructions.
- kannanvijayan 8y ago
  This is interesting to hear, and surprising. What are the provisions for efficient handling of integer overflows & underflows? I took a quick look at the ISA spec and am trying to track down how this is handled, as a curiosity.
  - jabl 8y ago
    AFAIU, none. It's designed for C, essentially, where signed integer overflows are undefined. In practice, the easiest and fastest design is to have it wrap around, just like unsigned. I'm not sure I agree with that particular design decision, considering newer languages such as Rust that want to detect overflows. Then again, if/when such languages become more important, I guess RISC-V could add an extension featuring some kind of trapping overflow (or whatever mechanism is deemed best).
    - zozbot123 8y ago
      The RISC-V spec does claim that "many overflow checks can be cheaply implemented using branches" and then provides recommended instruction sequences. One could definitely imagine a RV implementation where e.g. macro-op fusion is used to systematically turn some of these recommended sequences into hardware-assisted branches. (Ref: search for the "Integer Computational Instructions" section in the RISC-V "user mode" reference. It should be section 2.4)

dbcurtis 8y ago

Let me add a couple thoughts: 1. You typically won't get very far without also implementing register renaming, such that the reorder buffer is actually much larger than the register file. 2. You need to distinguish between instructions that are "complete" (result is available for internal bypass to another instruction that is being speculatively executed) versus "retired" (all instructions before it have retired, the instruction can no longer raise an exception, you know for certain that it was not executed because of incorrect speculation). Canonical, architecturally visible state is only written on retirement. 3. Without good branch prediction, it is kind of pointless. A reasonable rule-of-thumb-Kentucky-windage estimate is that 20-25% of the instructions that you encounter in execution order (not static code analysis) are branches. So if you have 30 or more instructions active in the pipe, your branch prediction needs to be pretty good or you waste too much work. (Note that some branches are just "flakey" (hard to predict) but the compiler can usually do a decent job of identifying those ahead of time. Thus, modern processors include a conditional-move instruction which allows the compiler to manage speculation and replace the flakey branch with an instruction that does not pollute the branch target buffer. 4. Watching what happens in the simulator at the end of a pointer chasing loop is good humor. A strongly predicted branch gets mispredicted on: while(p!=NULL) {}, and all sorts of page-fault, memory-exception, arithmetic-exception logic lights up all over the place until something asserts "OOPS_NEVER_MIND", at which point all that fun stuff collapses in a smoldering heap. Watching that never gets old.