3 ms·
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
by 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 agoYou'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.
- dragontamer 5y ago> In fixed width ISAs, you have N decoders and all their work is useful. ARM isn't fixed width anymore. AESE + AESMC macro-op fuse into a singular opcode, for example. IIRC, high performance ARM cores are macro-op fusing and/or splitting up opcodes into micro-ops. Its not necessarily a 1-to-1 translation from instructions to opcodes anymore for ARM. But yes, a simpler ISA will have a simpler decoder. But a lot of people seem to think its a huge, possibly asymptoticly huge, advantage. ----------------- > The only way out I can see is if determining instruction length is extremely cheap. That doesn't really describe x86 though. I just described a O(n) work / O(log(n)) latency way of determining instruction length. Proposal: 1. have a "instruction length decoder" on every byte coming in. Because this ONLY determines instruction length and is decidedly not a full decoder, its much cheaper than a real decoder. 2. Once the "instruction length decoders" determine the start-of-instructions, have 4 to 8 complete decoders read instructions starting "magically" in the right spots. That's the key for my proposal. Sure, the Kogge-stone part is a bit more costly, but focus purely on instruction length and you're pretty much set to have a cheap and simple "full decoder" down the line.