5 ms·
That doesn't seem too hard to me frankly. Intel has shown that you can just store the sizes of instructions in a new cache (in their new architecture) for exam
by dragontamer 5y ago
That doesn't seem too hard to me frankly.
Intel has shown that you can just store the sizes of instructions in a new cache (in their new architecture) for example.
But even then: it shouldn't be much more than O(n) work / O(log(n)) depth to determine the length of an instruction. Once lengths are known, you can perform parallel instruction decoding rather easily.
Ex: given "Instruction at X, X+1, X+5, and X+10", decode the instructions. Well, simple. Just shove a decoder at X, X+1, X+5, and X+10. 4 instructions, decoded in parallel.
Even with "Dynamic" length (ex: X, X+4, X+6, and X+7 afterwards), its clear how to process these 4 instructions in parallel. Really not a problem IMO.
--------
So solving the length thing is a bit harder to see, but clearly could be implemented as a parallel-regex (which is O(n) work and O(log(n)) depth).
I seriously doubt that decoding is really a problem. I'd expect that Apple just has made many small efficiency gains across the chip, especially the uncore.
I'm personally looking at the L1 / L2 cache hierarchies more so than anything on this Apple chip.
- api 5y agoThe words "just" and "cache" should never appear in the same sentence.
- dragontamer 5y agoWhy not? L1 $I cache is already read-only / Harvard architecture. There's only two states here: size == unknown, and size == known. This is a simple size = 0 (default), and size=X (where X is the known size of the instruction) situation. x86 architecture states that if you write to those instructions, you need to flush L1 cache (ex: JIT Java) before the state is updated. L1 instructions are non-cohesive, so it isn't very hard. Upon the flush, set sizes back to 0 and you're done.
- Veliladon 5y agoThe problem is how do you know if your just decoded instruction isn't just the operands for another legal instruction?
- dragontamer 5y agoWhen 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 agoThe 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.
- codedokode 5y agoThis complicated decoding makes a pipeline longer. This means that in case of branch misprediction there would be a large penalty.
- dragontamer 5y ago> This complicated decoding makes a pipeline longer. This means that in case of branch misprediction there would be a large penalty. PDEP / PEXT are single-clock tick instructions and are far more complex than what I'm proposing here. As is AESRound. I think you're underestimating the number of gates you can put in parallel and execute in a single stage of the pipeline. 64-bit PDEP / PEXT are more complicated than say... a 64-byte parallel adder in terms of depth. (PDEP / PEXT need both a butterfly circuit forward + inverse butterfly back + a decoder in parallel. 64-byte prefix sum is just one butterfly forward).
- rbanffy 5y ago> That doesn't seem too hard to me frankly. Consider Intel has a more or less infinite amount of money and they don't seem to be able to do that. And they have tried (I even had an Atom-based Android phone for a while). If you want an easy way to build a reorder buffer, you'll need to push every instruction in a structure that fits, IIRC, 15 bytes, which is the longest x86 instruction possible (for now - mwahahaha). This alone will make it twice as large as a similar arm64 one. Now factor in that the dependencies between instructions are defined in bits that can pretty much be all over the place in those 15 bytes and you end up with a nightmare most engineers would consider suicide before having to work on it.
- dragontamer 5y agoOr maybe, the problem isn't as hard as you think it is. Look, I started programming in GPUs a year or two ago. I've begun to "think in parallel", and now I'm beginning to see all sorts of efficient patterns all over the place. The actual CPU-architects have known about kogge-stone carry-lookahead longer than I have. I'm still a newbie to this mindset of parallel computations... but I enjoy reading the papers on PDEP / PEXT / other parallel structures these CPU designers are doing (and these structures have gross implications to how GPU code should be structured). But I've had enough practice with Kogge-stone / Carry-lookahead / Prefix-sum / scan pattern (yeah, its __all__ the same parallelism), and this pattern has been well published since the 1970s. I have to assume that engineers know about this stuff. Instruction length decoding is very clearly a kogge-stone pattern / prefix sum / scan problem to me. Now, I'm not a chip architect and maybe there's some weird fanout / chip level thing going on that my ignorance is keeping me out of... but... based on my understanding of parallel systems + very, very common patterns well known to that community, I'd expect that chip-designers would just Kogge-stone their way out of this decoding problem. ------- Like, I'm coming in from the reverse here. I suddenly realized that chip-designers have incredibly active minds about the layout and structure of parallel computing mechanisms, and have now taken an interest in studying some CPU-level parallelism techniques to apply to my GPU code. The CPU-designers are way ahead of us in "parallel thinking". I'm a visitor to their subject, they do this stuff for breakfast every day. They have to see the Kogge-stone solution to the decoding problem. If not, they've thought of something better.