3 ms·

I don't understand why they don't use simply a prefix-free code, for example the Huffman code. You can have arbitrary length instructions at entropy-optimal eff

I don't understand why they don't use simply a prefix-free code, for example the Huffman code. You can have arbitrary length instructions at entropy-optimal efficiencies that way, and decoding in binary-tree fashion should be linear and very fast in hardware.

infogulch 11y ago
Could a prefix-free code work with all the instruction arguments like arbitrary 64 bit immediates? Perhaps you could have a separate argument stream but you still need to parse all the prior instructions to get the offset.
- darkmighty 11y ago
  Not my area of expertise, but in principle any set of instructions can be encoded into a prefix-free code (e.g. a binary argument just expands the set of instructions by a factor of 2). If both arguments have equal probabilities this simplifies to simply appending the argument as a prefix. If the probabilities are unequal, you can save bits (entropy) by bundling frequently occurring arguments together in the Huffman scheme, at the cost of increased decoding complexity. I heard bandwidth/cache sizes is a much greater problem than circuit area though. You are right that you need to parse all previous instructions to get an offset. Again, this is far from my area of expertise (first time I read about CPU design), but it seems this problem could easily be alleviated by slight modifications to Huffman codes, for example by setting "blocks" of instructions of certain sizes and assigning a prefix to each block containing the number of instructions in each -- you then can get offsets very quickly.
  - JoeAltmaier 11y ago
    Anything is possible. But consider: Intel length-encoded opcodes for the 8086. Decades later, turns out they made bad choices. The shortest instructions (xchg r1, r2) are NEVER used. Compilers have changed; nobody codes much ASM any more. Its a crap-shoot.
Veedrac 11y ago
Linear decoding is too slow. The talk is about efficient parallel decoding, which requires having decoders at every potential alignment and discarding the improperly aligned outputs after-the-fact.
- darkmighty 11y ago
  I don't get what you mean by "linear is too slow" -- if you want to decode n bits you need at least O(n) time. Decoding every potential alignment seems equally silly since even in parallel processing each branch will have to performing at least one decoding task, so what exactly are the gains?
  - Veedrac 11y ago
    > if you want to decode n bits you need at least O(n) time This is hardware. There aren't branches, there are wires. Decoding those n bits can be constant time at the cost of quadratic "space" usage.
    - 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.

infogulch 11y ago

Could a prefix-free code work with all the instruction arguments like arbitrary 64 bit immediates? Perhaps you could have a separate argument stream but you still need to parse all the prior instructions to get the offset.

darkmighty 11y ago
Not my area of expertise, but in principle any set of instructions can be encoded into a prefix-free code (e.g. a binary argument just expands the set of instructions by a factor of 2). If both arguments have equal probabilities this simplifies to simply appending the argument as a prefix. If the probabilities are unequal, you can save bits (entropy) by bundling frequently occurring arguments together in the Huffman scheme, at the cost of increased decoding complexity. I heard bandwidth/cache sizes is a much greater problem than circuit area though. You are right that you need to parse all previous instructions to get an offset. Again, this is far from my area of expertise (first time I read about CPU design), but it seems this problem could easily be alleviated by slight modifications to Huffman codes, for example by setting "blocks" of instructions of certain sizes and assigning a prefix to each block containing the number of instructions in each -- you then can get offsets very quickly.
- JoeAltmaier 11y ago
  Anything is possible. But consider: Intel length-encoded opcodes for the 8086. Decades later, turns out they made bad choices. The shortest instructions (xchg r1, r2) are NEVER used. Compilers have changed; nobody codes much ASM any more. Its a crap-shoot.

Veedrac 11y ago

Linear decoding is too slow. The talk is about efficient parallel decoding, which requires having decoders at every potential alignment and discarding the improperly aligned outputs after-the-fact.

darkmighty 11y ago
I don't get what you mean by "linear is too slow" -- if you want to decode n bits you need at least O(n) time. Decoding every potential alignment seems equally silly since even in parallel processing each branch will have to performing at least one decoding task, so what exactly are the gains?
- Veedrac 11y ago
  > if you want to decode n bits you need at least O(n) time This is hardware. There aren't branches, there are wires. Decoding those n bits can be constant time at the cost of quadratic "space" usage.
  - 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.