<p>I want to design a variable-instruction-length instruction set for an instruction set architecture I'm working on. I've heard that there are generalizable, systematic techniques for optimizing average code size of programs that will be written using it. What are they?</p>
<p>I realize there are lots of different ways to design an ISA (Ex. <a href="https://en.wikipedia.org/wiki/Byte" rel="nofollow noreferrer">bits per byte</a>), and that not all ISAs are necessarily designed to run the same kinds of programs. That's why I say &quot;<em>generalizable</em>, systematic techniques&quot;.</p>
<p>For the sake of this question, ignore non-optimal expressions of tasks as programs using the ISA encoding. Assume that the best way of expressing a task given the resulting ISA encoding will always be used.</p>

<instruction-set-encoding>
How can I optimize for average code size when designing my ISA's variable-instruction-length instruction set?
CC BY-SA 4.0
2023-08-15T21:24:30.860Z
Great question. I asked a similar question in a different context: https://cstheory.stackexchange.com/questions/46610/improving-boolean-circuits-w-r-t-a-probability-distribution I doubt what you are looking for exists, in a well-developed, mathematically clean way.
Martin Berger
CC BY-SA 4.0
2023-05-20T18:57:22.003Z
related on meta: [Are questions about the design of ISA instruction-set encodings on-topic?](https://languagedesign.meta.stackexchange.com/q/181/251)
starball
<p>This can be difficult without the feedback loop of hardware–software co-design, as each influences the other. However, you can still make some reasonable estimations.</p>
<p>If your architecture is in an existing family of architectures (RISC, CISC, VLIW) and you have a corpus of representative programs in the application area that your chip is meant for, then you can compile those programs for similar architectures, and analyse their assembly. If you have no corpus, you may need to bootstrap one, or reason from first principles based on the operations needed by your target area (e.g. vector addition, byte permutation, matrix multiplication, or memory and I/O ops).</p>
<p>Building a histogram tells you the baseline frequency of each instruction class. More sophisticated statistical models such as a <a href="https://en.wikipedia.org/wiki/Markov_model" rel="nofollow noreferrer">Markov model</a> may give you more insights. Perhaps the simplest kind of Markov model suitable for this purpose is an <a href="https://en.wikipedia.org/wiki/N-gram_language_model" rel="nofollow noreferrer"><em>n</em>-gram model</a>. This is essentially a histogram in the case that <em>n</em> = 0; but for larger <em>n</em>, it tells you the conditional probability of each instruction given <em>n</em> prior instructions. This may help you identify instructions that are commonly used together, and thus potentially worth fusing into a single [macro-]op.</p>
<p>Once you have a model, you can find an optimal encoding for it. For instance, if you use the <em>n</em>-gram model to derive an instruction set with a “flat” model of independent probabilities for each op, then <a href="https://en.wikipedia.org/wiki/Huffman_coding" rel="nofollow noreferrer">Huffman coding</a> gives an optimal method of assigning encodings to ops based on those probabilities. More probable instructions will be given shorter encodings.</p>
<p>However, this must be subject to some constraints, because optimising purely for bit size isn’t likely to produce an optimal hardware design. Typically, instruction fetching and decoding stages will have some minimal granularity determined by the bus width between those pipeline stages, like a byte or word. Complex encodings are harder for humans to read, which may be a concern for debugging—it’s desirable for opcodes to have a fixed position, and for instruction fields to be aligned along regular boundaries of 3 or 4 bits, so that the instruction is legible in octal or hex. Moreover, complex decoding logic may make it harder to fit within a small timing window; if every opcode can be identified using the same shift+mask logic, then this pipeline stage is fixed and simple; whereas a chain of tests to decompress a variable-sized op may end up crossing a timing threshold, and require adding pipeline stages with registers between them, costing area and power.</p>
<p>Any regularity in the structure of programs can also be exploited to great effect to achieve asymptotic improvements in the design of the ISA. For example, suppose certain classes of regular loops are very common, like a 2D <span class="math-container">$m \times n$</span> iteration with a stride for each dimension. Adding an encoding for this case may save a great deal of space and branching logic, compared to encoding these loops as jumps or unrolled instruction streams. You’re unlikely to identify this kind of structure with a Markov model of tractable size, but you may spot it through other methods—a cheap one that I particularly like is rendering a 2D greyscale plot of each byte of a program’s machine code XOR’d with itself; this exploits your ability to visually identify large-scale repetitive patterns.</p>

CC BY-SA 4.0
2023-05-21T17:35:09.870Z
2023-08-11T05:33:39.710Z
2023-08-11T05:33:39.710Z
Jon Purdy
# How can I optimize for average code size when designing my ISA's variable-instruction-length instruction set?
Posted by: username_0 on 2023-05-20
I want to design a variable-instruction-length instruction set for an instruction set architecture I'm working on. I've heard that there are generalizable, systematic techniques for optimizing average code size of programs that will be written using it. What are they?

I realize there are lots of different ways to design an ISA (Ex. [bits per byte](https://en.wikipedia.org/wiki/Byte)), and that not all ISAs are necessarily designed to run the same kinds of programs. That's why I say "*generalizable*, systematic techniques".

For the sake of this question, ignore non-optimal expressions of tasks as programs using the ISA encoding. Assume that the best way of expressing a task given the resulting ISA encoding will always be used.
**Tags:** instruction-set-encoding
> **Comments:**
> **username_0**: related on meta: [Are questions about the design of ISA instruction-set encodings on-topic?](https://languagedesign.meta.stackexchange.com/q/181/251)  
> **username_1**: Great question. I asked a similar question in a different context: https://cstheory.stackexchange.com/questions/46610/improving-boolean-circuits-w-r-t-a-probability-distribution I doubt what you are looking for exists, in a well-developed, mathematically clean way.  
---
## 1 answers
### Answer by username_2 on 2023-05-21. Score: 7
This can be difficult without the feedback loop of hardware–software co-design, as each influences the other. However, you can still make some reasonable estimations.

If your architecture is in an existing family of architectures (RISC, CISC, VLIW) and you have a corpus of representative programs in the application area that your chip is meant for, then you can compile those programs for similar architectures, and analyse their assembly. If you have no corpus, you may need to bootstrap one, or reason from first principles based on the operations needed by your target area (e.g. vector addition, byte permutation, matrix multiplication, or memory and I/O ops).

Building a histogram tells you the baseline frequency of each instruction class. More sophisticated statistical models such as a [Markov model](https://en.wikipedia.org/wiki/Markov_model) may give you more insights. Perhaps the simplest kind of Markov model suitable for this purpose is an [*n*-gram model](https://en.wikipedia.org/wiki/N-gram_language_model). This is essentially a histogram in the case that *n* = 0; but for larger *n*, it tells you the conditional probability of each instruction given *n* prior instructions. This may help you identify instructions that are commonly used together, and thus potentially worth fusing into a single [macro-]op.

Once you have a model, you can find an optimal encoding for it. For instance, if you use the *n*-gram model to derive an instruction set with a “flat” model of independent probabilities for each op, then [Huffman coding](https://en.wikipedia.org/wiki/Huffman_coding) gives an optimal method of assigning encodings to ops based on those probabilities. More probable instructions will be given shorter encodings.

However, this must be subject to some constraints, because optimising purely for bit size isn’t likely to produce an optimal hardware design. Typically, instruction fetching and decoding stages will have some minimal granularity determined by the bus width between those pipeline stages, like a byte or word. Complex encodings are harder for humans to read, which may be a concern for debugging—it’s desirable for opcodes to have a fixed position, and for instruction fields to be aligned along regular boundaries of 3 or 4 bits, so that the instruction is legible in octal or hex. Moreover, complex decoding logic may make it harder to fit within a small timing window; if every opcode can be identified using the same shift+mask logic, then this pipeline stage is fixed and simple; whereas a chain of tests to decompress a variable-sized op may end up crossing a timing threshold, and require adding pipeline stages with registers between them, costing area and power.

Any regularity in the structure of programs can also be exploited to great effect to achieve asymptotic improvements in the design of the ISA. For example, suppose certain classes of regular loops are very common, like a 2D $m \times n$ iteration with a stride for each dimension. Adding an encoding for this case may save a great deal of space and branching logic, compared to encoding these loops as jumps or unrolled instruction streams. You’re unlikely to identify this kind of structure with a Markov model of tractable size, but you may spot it through other methods—a cheap one that I particularly like is rendering a 2D greyscale plot of each byte of a program’s machine code XOR’d with itself; this exploits your ability to visually identify large-scale repetitive patterns.
---
