4 ms·

I remember reading (in 2012 maybe) that ISA doesn't really matter and decoders don't really matter for performance. The decoder is such a small part of the powe

by mastax 5y ago

I remember reading (in 2012 maybe) that ISA doesn't really matter and decoders don't really matter for performance. The decoder is such a small part of the power and area compared to the rest of the chip. I had a hypothesis that as we reach the tail end of microarchitectural performance the ISA will start to matter a lot more, since there are fewer and fewer places left to optimize. Well now in 2021 cores are getting wider and wider to have any throughput improvement and power is a bigger concern than ever. Apple M1 has an 8-wide decoder feeding the rest of the extremely wide core. For comparison, Zen 3 has a 4-wide decoder and Ice Lake has 5-wide. We'll see in 3 years if Intel and AMD were just being economical or unimaginative or if they really can't go wider due to the x86 decode complexity. I suppose we'll never really know if they cover for a power hungry decoder with secret sauce elsewhere in the design.

dragontamer 5y ago
The state-machine that can determine the start-of-instructions can be run in parallel. In fact, any RegEx / state machine / can be run in parallel on every byte with Kogge-stone / parallel prefix, because the state-machine itself is an associative (but not communitive) operation. As such, I believe that decoders (even complicated ones like x86) scale at O(n) total work (aka power used) and O(log(n)) for depth (aka: clock cycles of latency). ------- Obviously, a simpler ISA would allow for simpler decoding. But I don't think that decoders would scale poorly, even if you had to build a complicated parallel-execution engine to discover the start-of-instruction information.
- klelatti 5y ago
  Maybe but O(n) on a complex decoder could be a material penalty vs a much simpler design.
  - dragontamer 5y ago
    Sure, but only within a constant factor. My point is that the ARM's ISA vs x86 ISA is not any kind of asymptotic difference in efficiency that grossly prevents scaling. Even the simplest decoder on a exactly 32-bit ISA (like POWER9) with no frills would need O(n) scaling. If you do 16-instructions per clock tick, you need 16x individual decoders on every 4-bytes. Sure, that delivers the results in O(1) instead of O(log(n)) like a Kogge-stone FSM would do, but ARM64 isn't exactly cake to decode either. There's microop / macro-op fusion going on in ARM64 (ex: AESE + AESMC are fused on ARM64 and executed as one uop).
- Someone 5y ago
  x86 instructions can straddle MMU pages and even cache lines. I guess that will affect the constant factor in that O(n) (assuming that’s true. I wouldn’t even dare say I believe that or its converse)
  - dragontamer 5y ago
    > x86 instructions can straddle MMU pages and even cache lines. That doesn't change the size or power-requirements of the decoder however. The die-size is related to the total-work done (aka: O(n) die area). And O(n) also describes the power requirements. If the core is stalled on MMU pages / cache line stalls, then the core idles and uses less power. The die-area used doesn't change (because once fabricated in lithography, the hardware can't change) > (assuming that’s true. I wouldn’t even dare say I believe that or its converse) Kogge-stone (https://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder https://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder) can take *any* associative operation and parallelize it into O(n) work / O(log(n)) depth. The original application was the Kogge-stone carry-lookahead adders. How do you calculate the "carry bit" in O(log(n)) time, where n is the number of bits? It is clear that a carry bit depends on all 32-bits + 32-bits (!!!), so it almost defies logic to think that you can figure it out in O(log(n)) depth. You need to think about it a bit, but it definitely works, and is a thing taught in computer architecture classes for computer engineers. -------- Anyway, if you understand how Kogge-Stone carry lookahead works, then you understand that any associative operation (of which "Carry-bit" calculations is associative). The next step is realizing that "stepping a state machine" is associative. This is trickier to prove, so I'll just defer to the 1986 article "Data Parallel Algorithms" (http://uenics.evansville.edu/~mr56/ece757/DataParallelAlgorithms.pdf http://uenics.evansville.edu/~mr56/ece757/DataParallelAlgori...), page 6 in the PDF / page 1175 in the lower corner. There, Hillis / Steel prove that FSM / regex parsing is an associative operation, and therefore can be implemented in the Kogge-stone adder (called a "prefix-sum" or "Scan" operation in that paper).
    - atq2119 5y ago
      You're right about the implications of Kogge-Stone, but constant factors matter a lot. In fixed width ISAs, you have N decoders and all their work is useful. In byte granularity dynamic width ISAs, you have one (partial) decoder per byte of your instruction window. All but N of their decode results are effectively thrown away. That's very wasteful. The only way out I can see is if determining instruction length is extremely cheap. That doesn't really describe x86 though. The other aspect is that if you want to keep things cheap, all this logic is bound to add at least one pipeline stage (because you keep it cheap by splitting instruction decode into a first partial decode that determines instruction length followed by a full decode in the next stage). Making your pipeline ~10% longer is a big drag on performance.
- mhh__ 5y ago
  >because the state-machine itself is an associative (but not communitive) operation. Proof? > But I don't think that decoders would scale poorly, even if you had to build a complicated parallel-execution engine to discover the start-of-instruction information. Surely we have empirical proof of that in that Apple's first iteration of a PC chip is noticeably wider than AMD's top of the line offering. On top of this we know that to make X86 run fast you have to include an entirely new layer of cache just to help the decoders out. We've had this exact discussion on this site before, so I won't start it up again but even if you are right that you can decode in this manner I think empirically we know that the coefficient is not pretty.
  - dragontamer 5y ago
    I'm not a chip designer. I don't know the best decoding algorithms in the field. What I can say is, I've come up with a decoding algorithm that's clearly O(n) total work and O(log(n)) depth. From there, additional work would be done to discover faster methodologies. The importance of proving O(n) total work is not in "X should be done in this manner". Its in that "X has asymptotic complexity of at worst case, this value". I presume that the actual chip designers making decoders are working on something better than what I came up with. > Proof? Its not an easy proof. But I think I've given enough information in sibling posts that you can figure it out yourself over the next hour if you really cared. The Hillis / Steele paper is considered to be a good survey of parallel computing methodologies in the 1980s, and is a good read anyway. One key idea that helped me figure it out, is that you can run FSM's "backwards". Consider a FSM where "abcd" is being matched. (No match == state 1. State 2 == a was matched. State 3 == a and b was matched. State 4 == abc was matched, State5 == abcd was matched). You can see rather easily that FSM(a)(b)(c)(d), applied from left-to-right is the normal way FSMs work. Reverse-FSM(d) == 4 if-and-only if the 4th character is d. Reverse-FSM(other-characters) == initial state in all other cases. Reverse-FSM(d)(c) == 3. In contrast, we can also run the FSM in the standard forward approach. FSM(a)(b) == 3 Because FSM(a)(b) == 3, and Reverse-FSM(d)(c) == 3, the two states match up and we know that the final state was 5. As such, we can run the FSM-backwards. By carefully crafting "reverse-FSM" and "forward-FSM" operations, we can run the finite-state-machine in any order. Does that help understand the concept? The "later" FSM operations being applied on the later-characters are "backwards" operations (figuring out the transition from transitioning from state4 to state 3). While "earlier" FSM operations on the first characters are the traditional forward-stepping of the FSM. When the FSM operations meet in the middle (aka: FSM(a)(b) meets with reverse-FSM(c)), all you do is compare states: reverse-FSM(c) declares a match if-and-only-if the state was 3. FSM(a)(b) clearly is in state 3, so you can combine the two values together and say that the final state was in fact 4. ----- Last step: now that you think of forward and reverse FSMs, the "middle" FSMs are also similar. Consider FSM2(b), which processes the 2nd-character: the output is basically 1->3 if-and-only-if the 2nd character is b. FSM(a) == 1 and ReverseFSM(d)(c) == 3, and we have the middle FSM2 returning (1->3). So we know that the two sides match up. So we can see that all bytes: the first bytes, the last bytes, and even the middle bytes, can be processed in parallel. For example, lets take FSM2(b)(c), and process the two middle bytes before we process the beginning or end. We see that the 2nd byte is (b), which means that FSM2(b)(c) creates a 2->4 link (if the state entering FSM2(b)(c) is 2, then the last state is 4). Now we do FSM(a), and see that we are in state 2. FSM(a) puts us in state 2, and since FSM2(b)(c) has been preprocessed to be 2->4, that puts us at state 4. So we can really process the FSM in any order. Kogge-Stone gives us a O(n) work + O(log(n)) parallel methodology. Done.
- adrian_b 5y ago
  I am not sure what you mean by running in parallel. On x86, to be able to determine whether a given byte is the start of an instruction, the start of the part of an instruction following the variable-number of prefix bytes or another kind of byte, requires information from the decoding of the previous bytes. So you may have as many pre-decoders as the fetched bytes, all starting decoding in parallel, but they are not independent and the later pre-decoders need the propagation of signals from the first pre-decoders, so the delay required for determining the initial instruction bytes grows with the number of bytes fetched and examined simultaneously (16 bytes for most x86 CPUs, which on average may contain 4 or 5 instructions). We do not know for sure where the exact limitation is, but despite the vague and inconsistent information from the vendor documentation, which in a few cases seems to imply better capabilities, until now no Intel or AMD CPU has been shown to be able to decode more than 4 instructions simultaneously (the only exception is that some pairs of instruction are fused, e.g. some combinations of compare-and-branch, and those count as a single instruction for decoding, increasing the apparent number of simultaneously decoded instructions when those pairs occur in the program).
  - dragontamer 5y ago
    > I am not sure what you mean by running in parallel. I literally mean in parallel. Computing a FSM from "backwards" and "forwards" simultaneously, as well as "from the middle outward". From all bits, simultaneously, in parallel. As I stated earlier: Kogge-Stone carry save adder is the first step to understanding this. Lets take 32-bits of two numbers: A[0:31] and B[0:31]. C [0:32] = A + B. Simple, yes? Lets focus on purely a singular bit: C[32], the so called "carry bit". It is easy to see that the carry bit (the 33rd bit of the addition operation) depends on all 32-bits of A, as well as all 32-bits of B. Nonetheless, the carry bit can be computed in parallel with Kogge-Stone (as well as other parallel carry-lookahead adders). I've explained this process in multiple sibling posts at this point. Please give them a look first, and ask questions after you've read them. I understand that I've written quickly, verbosely, and perhaps inaccurately, but hopefully there's enough there to get started.
Symmetry 5y ago
You're right in a sense, in that even really hairy decode problems like x86 only add 15% or so to a core's overall power usage. But on the other hand verification is a big NRE cost for chips and proving that that second ISA works correctly in all cases is a pretty substantial engineering cost even if the resulting chip is much the same.
- ants_a 5y ago
  It likely wouldn't be 15% with an 8-wide x86 decoder if such a thing would even be possible within any reasonable clock budget. So in that sense a fixed width ISA does buy something. Also, given that chips today are mostly power limited, 15% power usage is 15% that could be used to increase performance in other ways.

by mastax 5y ago

dragontamer 5y ago

The state-machine that can determine the start-of-instructions can be run in parallel. In fact, any RegEx / state machine / can be run in parallel on every byte with Kogge-stone / parallel prefix, because the state-machine itself is an associative (but not communitive) operation. As such, I believe that decoders (even complicated ones like x86) scale at O(n) total work (aka power used) and O(log(n)) for depth (aka: clock cycles of latency). ------- Obviously, a simpler ISA would allow for simpler decoding. But I don't think that decoders would scale poorly, even if you had to build a complicated parallel-execution engine to discover the start-of-instruction information.

klelatti 5y ago
Maybe but O(n) on a complex decoder could be a material penalty vs a much simpler design.
- dragontamer 5y ago
  Sure, but only within a constant factor. My point is that the ARM's ISA vs x86 ISA is not any kind of asymptotic difference in efficiency that grossly prevents scaling. Even the simplest decoder on a exactly 32-bit ISA (like POWER9) with no frills would need O(n) scaling. If you do 16-instructions per clock tick, you need 16x individual decoders on every 4-bytes. Sure, that delivers the results in O(1) instead of O(log(n)) like a Kogge-stone FSM would do, but ARM64 isn't exactly cake to decode either. There's microop / macro-op fusion going on in ARM64 (ex: AESE + AESMC are fused on ARM64 and executed as one uop).
Someone 5y ago
x86 instructions can straddle MMU pages and even cache lines. I guess that will affect the constant factor in that O(n) (assuming that’s true. I wouldn’t even dare say I believe that or its converse)
- dragontamer 5y ago
  > x86 instructions can straddle MMU pages and even cache lines. That doesn't change the size or power-requirements of the decoder however. The die-size is related to the total-work done (aka: O(n) die area). And O(n) also describes the power requirements. If the core is stalled on MMU pages / cache line stalls, then the core idles and uses less power. The die-area used doesn't change (because once fabricated in lithography, the hardware can't change) > (assuming that’s true. I wouldn’t even dare say I believe that or its converse) Kogge-stone (https://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder https://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder) can take *any* associative operation and parallelize it into O(n) work / O(log(n)) depth. The original application was the Kogge-stone carry-lookahead adders. How do you calculate the "carry bit" in O(log(n)) time, where n is the number of bits? It is clear that a carry bit depends on all 32-bits + 32-bits (!!!), so it almost defies logic to think that you can figure it out in O(log(n)) depth. You need to think about it a bit, but it definitely works, and is a thing taught in computer architecture classes for computer engineers. -------- Anyway, if you understand how Kogge-Stone carry lookahead works, then you understand that any associative operation (of which "Carry-bit" calculations is associative). The next step is realizing that "stepping a state machine" is associative. This is trickier to prove, so I'll just defer to the 1986 article "Data Parallel Algorithms" (http://uenics.evansville.edu/~mr56/ece757/DataParallelAlgorithms.pdf http://uenics.evansville.edu/~mr56/ece757/DataParallelAlgori...), page 6 in the PDF / page 1175 in the lower corner. There, Hillis / Steel prove that FSM / regex parsing is an associative operation, and therefore can be implemented in the Kogge-stone adder (called a "prefix-sum" or "Scan" operation in that paper).
  - atq2119 5y ago
    You're right about the implications of Kogge-Stone, but constant factors matter a lot. In fixed width ISAs, you have N decoders and all their work is useful. In byte granularity dynamic width ISAs, you have one (partial) decoder per byte of your instruction window. All but N of their decode results are effectively thrown away. That's very wasteful. The only way out I can see is if determining instruction length is extremely cheap. That doesn't really describe x86 though. The other aspect is that if you want to keep things cheap, all this logic is bound to add at least one pipeline stage (because you keep it cheap by splitting instruction decode into a first partial decode that determines instruction length followed by a full decode in the next stage). Making your pipeline ~10% longer is a big drag on performance.
mhh__ 5y ago
>because the state-machine itself is an associative (but not communitive) operation. Proof? > But I don't think that decoders would scale poorly, even if you had to build a complicated parallel-execution engine to discover the start-of-instruction information. Surely we have empirical proof of that in that Apple's first iteration of a PC chip is noticeably wider than AMD's top of the line offering. On top of this we know that to make X86 run fast you have to include an entirely new layer of cache just to help the decoders out. We've had this exact discussion on this site before, so I won't start it up again but even if you are right that you can decode in this manner I think empirically we know that the coefficient is not pretty.
- dragontamer 5y ago
  I'm not a chip designer. I don't know the best decoding algorithms in the field. What I can say is, I've come up with a decoding algorithm that's clearly O(n) total work and O(log(n)) depth. From there, additional work would be done to discover faster methodologies. The importance of proving O(n) total work is not in "X should be done in this manner". Its in that "X has asymptotic complexity of at worst case, this value". I presume that the actual chip designers making decoders are working on something better than what I came up with. > Proof? Its not an easy proof. But I think I've given enough information in sibling posts that you can figure it out yourself over the next hour if you really cared. The Hillis / Steele paper is considered to be a good survey of parallel computing methodologies in the 1980s, and is a good read anyway. One key idea that helped me figure it out, is that you can run FSM's "backwards". Consider a FSM where "abcd" is being matched. (No match == state 1. State 2 == a was matched. State 3 == a and b was matched. State 4 == abc was matched, State5 == abcd was matched). You can see rather easily that FSM(a)(b)(c)(d), applied from left-to-right is the normal way FSMs work. Reverse-FSM(d) == 4 if-and-only if the 4th character is d. Reverse-FSM(other-characters) == initial state in all other cases. Reverse-FSM(d)(c) == 3. In contrast, we can also run the FSM in the standard forward approach. FSM(a)(b) == 3 Because FSM(a)(b) == 3, and Reverse-FSM(d)(c) == 3, the two states match up and we know that the final state was 5. As such, we can run the FSM-backwards. By carefully crafting "reverse-FSM" and "forward-FSM" operations, we can run the finite-state-machine in any order. Does that help understand the concept? The "later" FSM operations being applied on the later-characters are "backwards" operations (figuring out the transition from transitioning from state4 to state 3). While "earlier" FSM operations on the first characters are the traditional forward-stepping of the FSM. When the FSM operations meet in the middle (aka: FSM(a)(b) meets with reverse-FSM(c)), all you do is compare states: reverse-FSM(c) declares a match if-and-only-if the state was 3. FSM(a)(b) clearly is in state 3, so you can combine the two values together and say that the final state was in fact 4. ----- Last step: now that you think of forward and reverse FSMs, the "middle" FSMs are also similar. Consider FSM2(b), which processes the 2nd-character: the output is basically 1->3 if-and-only-if the 2nd character is b. FSM(a) == 1 and ReverseFSM(d)(c) == 3, and we have the middle FSM2 returning (1->3). So we know that the two sides match up. So we can see that all bytes: the first bytes, the last bytes, and even the middle bytes, can be processed in parallel. For example, lets take FSM2(b)(c), and process the two middle bytes before we process the beginning or end. We see that the 2nd byte is (b), which means that FSM2(b)(c) creates a 2->4 link (if the state entering FSM2(b)(c) is 2, then the last state is 4). Now we do FSM(a), and see that we are in state 2. FSM(a) puts us in state 2, and since FSM2(b)(c) has been preprocessed to be 2->4, that puts us at state 4. So we can really process the FSM in any order. Kogge-Stone gives us a O(n) work + O(log(n)) parallel methodology. Done.
adrian_b 5y ago
I am not sure what you mean by running in parallel. On x86, to be able to determine whether a given byte is the start of an instruction, the start of the part of an instruction following the variable-number of prefix bytes or another kind of byte, requires information from the decoding of the previous bytes. So you may have as many pre-decoders as the fetched bytes, all starting decoding in parallel, but they are not independent and the later pre-decoders need the propagation of signals from the first pre-decoders, so the delay required for determining the initial instruction bytes grows with the number of bytes fetched and examined simultaneously (16 bytes for most x86 CPUs, which on average may contain 4 or 5 instructions). We do not know for sure where the exact limitation is, but despite the vague and inconsistent information from the vendor documentation, which in a few cases seems to imply better capabilities, until now no Intel or AMD CPU has been shown to be able to decode more than 4 instructions simultaneously (the only exception is that some pairs of instruction are fused, e.g. some combinations of compare-and-branch, and those count as a single instruction for decoding, increasing the apparent number of simultaneously decoded instructions when those pairs occur in the program).
- dragontamer 5y ago
  > I am not sure what you mean by running in parallel. I literally mean in parallel. Computing a FSM from "backwards" and "forwards" simultaneously, as well as "from the middle outward". From all bits, simultaneously, in parallel. As I stated earlier: Kogge-Stone carry save adder is the first step to understanding this. Lets take 32-bits of two numbers: A[0:31] and B[0:31]. C [0:32] = A + B. Simple, yes? Lets focus on purely a singular bit: C[32], the so called "carry bit". It is easy to see that the carry bit (the 33rd bit of the addition operation) depends on all 32-bits of A, as well as all 32-bits of B. Nonetheless, the carry bit can be computed in parallel with Kogge-Stone (as well as other parallel carry-lookahead adders). I've explained this process in multiple sibling posts at this point. Please give them a look first, and ask questions after you've read them. I understand that I've written quickly, verbosely, and perhaps inaccurately, but hopefully there's enough there to get started.

Symmetry 5y ago

You're right in a sense, in that even really hairy decode problems like x86 only add 15% or so to a core's overall power usage. But on the other hand verification is a big NRE cost for chips and proving that that second ISA works correctly in all cases is a pretty substantial engineering cost even if the resulting chip is much the same.

ants_a 5y ago
It likely wouldn't be 15% with an 8-wide x86 decoder if such a thing would even be possible within any reasonable clock budget. So in that sense a fixed width ISA does buy something. Also, given that chips today are mostly power limited, 15% power usage is 15% that could be used to increase performance in other ways.