I sure hope not, otherwise they would probably not let me teach this stuff...
I will give a few pointers below.
What I don't understand is why asymptotic complexity is even remotely relevant for this discussion. Decoding a stream of instructions or in fact scanning any kind of sequence is always going to be O(n) at best — simply because you have to examine every element of the sequence regardless of what you do.
Thats just wrong - of course it depends what you understand under "scanning". In a general computation model you calculate your output from the input - there is no notion of scanning. First of all, a parallel machine model or uniform circuit has essentially parallel access to the input - there is no notion of going sequentially through your input. Of course the algorithm (or function) itself might have dependencies, which might force you to sequentialize some computations - and that is precisely what we are talking about here.
Coming back to what you trying to say above, there are some theorems about lower limits if we remove the notion of scanning. One of them states that a function, which needs all inputs to calculate the output cannot be in NC^0 and must be at least in NC^1. (informally NC^x = O(log^x n) depth on a circuit with bounded fan-in using standard gates). As lecture i suggest to read up on the classes NC, AC, TC - but i guess Nicks Class (NC) is the most relevant for the discussion.
What we are discussing instead is how to reduce the constant factor. Processing multiple bytes simultaneously is an obvious approach. It won't change the asymptotic complexity, but it will improve the performance by a factor of X.
Of course it is harder to speed up parsing a variable-length code by parallelization, but it's not impossible. There is this popular view that since x86 ISA is variable-length, the decoder has to process each instruction on bey one (mind, I am not implying that you subscribe to this view).
You should convince yourself, that when talking about NC, we are already talking about the best case parallel implementation - indeed i am not subscribing to such mundane arguments
🙂
A block of k bytes can be preprocessed in constant time to detect the offsets of each individual instruction, and each of these instructions can be decoded in parallel by a separate decoder. This will obviously add some latency and considerable hardware complexity to the implementation, and it won't reduce the asymptotic complexity, but it will improve the decoding performance.
As you noted correctly the O(n) nature is something you cannot escape by any clever implementation - and i am sure the current 4-wide decode in x86 is already extremely clever and it gets increasingly harder to "hide" the O(n) nature of the problem as you go wider. This is opposed to ARM (or any other fixed length ISA), where the nature of the problem is O(1).
Backends seem rather similar to me (although Apple does have more integer ports and it is also possible that their EUs are in general more capable)
Cortex X1:
https://fuse.wikichip.org/news/3543/arm-cortex-x1-the-first-from-the-cortex-x-custom-program/
A14/M1:
https://www.anandtech.com/show/16226/apple-silicon-m1-a14-deep-dive/2
The argument would be that building wide cores is difficult because ILP in real world code is inherently limited by dependencies, control flow and things like that. When you look at modern high performance computing, be it Zen or Intel cores, or X1, they seem to converge at roughly comparable backend sizes. It's quite possible that going wider would be subject to diminishing returns. But Apple can go wider and also maintain very high retire rate. Maybe their branch predictor is just that good?
But anyway, I am just grasping at straws here. I don't really insist that this argument has much merit. I'm just curious about these things.
Right, ILP is limited but on the other hand it is very application dependent. But we should separate concerns here. So even if you predict branches 100% correctly you still have the same ILP limit.
Outside of the theoretical ILP limit, you have just limits on how the ISA allows you to present the parallelism. All the parallelism a backend based on dynamic scheduling (aka OOE) architecture is able to extract is based on observing register dependencies. Therefore register-renaming plays a huge role, as it removes anti-dependencies between instructions. Anyway, size of your architectural register file also limits how parallelism can be presented. If the compiler ever comes into a situation, where it needs to emit spilling code because running out of architectural registers - register renaming does not help you anymore - the potential parallelism is gone. The conclusion here would be, that with ARM you can potentially extract more ILP due to the larger GP register file compared to x64. And while you can never pass the inherent ILP limit - there still is an ISA dependency here - namely architectures with larger GP register files do have an advantage.
That having said, i truly believe, if ARM decides to make the cores the same size as Firestorm, they would achieve very similar IPC - contrary to the x64 competition. In some cases ARM is very explicit, they say, when we would have increased feature xyz by this amount, they would have gained uvw amount of performance - so "we are not doing this". The X1 is the first ARM core, where ARM is somewhat deviating from these considerations.[/quote]
