3 ms·

The problem is how do you know if your just decoded instruction isn't just the operands for another legal instruction?

dragontamer 5y ago
When you get to instruction X, "size cache" says "size 2", and this allows you to process instruction X+2 in parallel. You look at instruction X+2, and "size cache" says "size 4", which allows you to look at instruction X+6 in parallel. Finally, you look at instruction X+10, and it says "size 8", which ends with +18 as where the instruction pointer ends. This was sequentially described at first, but the parallel version is called Prefix Sum: https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Prefix_sum . This allows you to take a set of sums (like say 0, 2, 4, 8) and in parallel, figure out [2, 6, 10, 18], with 18 being the new location of the instruction pointer, and [0, 2, 6, 10] being the 4 instructions you process this clock tick. A parallel adder across say, 32-bytes would be able to perform this prefix sum very quickly, probably within a clock tick. These sorts of parallel structures (aka: butterfly circuits) are extremely common in practice, your carry-lookahead adders need them, as well as PDEP / PEXT. Intel's single-cycle PDEP/PEXT is way more complicated than what I'm proposing here, I kid you not. (Seriously, the dude who decided to make single-clock cycle PDEP/PEXT or single-clock cycle AESRound would have spent more time than the size-cache that Intel is now using on instruction decoding)
- Veliladon 5y ago
  The problem is that you don't know the instruction length until you've decoded it so where is the size cache getting the size?
  - dragontamer 5y ago
    > The problem is that you don't know the instruction length until you've decoded it so where is the size cache getting the size? You are aware that x86 _CURRENTLY_ (ie: without size-cache) decodes 4-instructions per clock tick, right? That's in parallel, as currently implemented. Intel just seems to think the size-cache is a potential solution for going faster. I've given it some thought and it seems like it could very well be worth the 4-bits (or so) per byte it'd cost. ---------- A parallel size-calculator would also be O(n) work and O(log(n)) depth, by using a parallel regex/finite automata on calculating the sizes for arbitrary lengths upwards.
    - Veliladon 5y ago
      That's only second stage decoding. In the fetch/pre-decode stage there is a specific piece of hardware that partially decodes 16 byte chunks of instruction streams before inserting instructions into the instruction queue for the decode from macro-op to uop. It can only handle 6 instructions per clock and 16 bytes per clock. If you have 7 instructions in a 16 byte block it takes two cycles to process that block. If you have only 2 instructions in that 16 byte block you only get those two instructions. It also only looks for instruction length and branching to feed the branch predictor, spitting the same instructions back out albeit fused and tagged with index numbers for insertion into the instruction queue ready for the second stage decoders. This is the length that Intel has to go to in order to keep the EUs fed. Apple/ARM? Every 4 bytes there's an instruction.
      - dragontamer 5y ago
        I'm talking 1st stage decoding actually. I'm ignoring the uOp cache. The 2nd stage uop can go 6-per or 7-per clock tick. But 1st stage (which executes in practice when the uop cache is thrashing) would still go 4-instructions per clock tick just fine. > This is the length that Intel has to go to in order to keep the EUs fed. Yeah. And the task described is O(n) total work and O(log(n)) depth. So... not a big difference? I'd have my doubts that the instruction-length portion of the decoder was taking up a significant amount of power.

When you get to instruction X, "size cache" says "size 2", and this allows you to process instruction X+2 in parallel. You look at instruction X+2, and "size cache" says "size 4", which allows you to look at instruction X+6 in parallel. Finally, you look at instruction X+10, and it says "size 8", which ends with +18 as where the instruction pointer ends. This was sequentially described at first, but the parallel version is called Prefix Sum: https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Prefix_sum . This allows you to take a set of sums (like say 0, 2, 4, 8) and in parallel, figure out [2, 6, 10, 18], with 18 being the new location of the instruction pointer, and [0, 2, 6, 10] being the 4 instructions you process this clock tick. A parallel adder across say, 32-bytes would be able to perform this prefix sum very quickly, probably within a clock tick. These sorts of parallel structures (aka: butterfly circuits) are extremely common in practice, your carry-lookahead adders need them, as well as PDEP / PEXT. Intel's single-cycle PDEP/PEXT is way more complicated than what I'm proposing here, I kid you not. (Seriously, the dude who decided to make single-clock cycle PDEP/PEXT or single-clock cycle AESRound would have spent more time than the size-cache that Intel is now using on instruction decoding)

Veliladon 5y ago
The problem is that you don't know the instruction length until you've decoded it so where is the size cache getting the size?
- dragontamer 5y ago
  > The problem is that you don't know the instruction length until you've decoded it so where is the size cache getting the size? You are aware that x86 _CURRENTLY_ (ie: without size-cache) decodes 4-instructions per clock tick, right? That's in parallel, as currently implemented. Intel just seems to think the size-cache is a potential solution for going faster. I've given it some thought and it seems like it could very well be worth the 4-bits (or so) per byte it'd cost. ---------- A parallel size-calculator would also be O(n) work and O(log(n)) depth, by using a parallel regex/finite automata on calculating the sizes for arbitrary lengths upwards.
  - Veliladon 5y ago
    That's only second stage decoding. In the fetch/pre-decode stage there is a specific piece of hardware that partially decodes 16 byte chunks of instruction streams before inserting instructions into the instruction queue for the decode from macro-op to uop. It can only handle 6 instructions per clock and 16 bytes per clock. If you have 7 instructions in a 16 byte block it takes two cycles to process that block. If you have only 2 instructions in that 16 byte block you only get those two instructions. It also only looks for instruction length and branching to feed the branch predictor, spitting the same instructions back out albeit fused and tagged with index numbers for insertion into the instruction queue ready for the second stage decoders. This is the length that Intel has to go to in order to keep the EUs fed. Apple/ARM? Every 4 bytes there's an instruction.
    - dragontamer 5y ago
      I'm talking 1st stage decoding actually. I'm ignoring the uOp cache. The 2nd stage uop can go 6-per or 7-per clock tick. But 1st stage (which executes in practice when the uop cache is thrashing) would still go 4-instructions per clock tick just fine. > This is the length that Intel has to go to in order to keep the EUs fed. Yeah. And the task described is O(n) total work and O(log(n)) depth. So... not a big difference? I'd have my doubts that the instruction-length portion of the decoder was taking up a significant amount of power.