3 ms·
By quadratic you mean O(2^(2n)) physical space, right? By a naive approach (making decoding like a ROM memory), I still can't see how it's not at least linear o
by darkmighty 11y ago
By quadratic you mean O(2^(2n)) physical space, right? By a naive approach (making decoding like a ROM memory), I still can't see how it's not at least linear on the number of bits even assuming simplifying things for circuit sizes.
- Veedrac 11y ago> By quadratic you mean O(2^(2n)) Quadratic is O(n^2), not O(4^n). n is the number of bits. The bits are decoded in parallel, ergo. in constant time. There may be a linear step afterwards (eg. numbering each instruction result) but the actual decode happens in parallel. I'm a bit confused about why you think it's linear time. (I suppose technically it even has to be constant time, since the number of bits is capped at a low constant, but I suppose that's also besides the point.) It's not actually quite that simple, since it's actually a 3-phase decode and there is some interdependence. However, the point remains that shifting the read along one instruction at a time would be too slow and parallel decode is key to fixing that. I suppose you might instead be asking why it's not linear hardware space complexity (rather than quadratic); the answer to that is a little more subtle.