If there is any sense of an optimal set of instructions in an ISA

Question

So there are One Instruction Set Computers, having only one (complicated) instruction like addleq, "add and branch if less than or equal to zero". And then there are extremely complicated Instruction Set Architectures (ISAs) with 100's of instructions like x86.

Most computers today I think use the x86 architecture, though ARM architectures seem like they are gaining some attention. I think x86 is popular (for one reason or another) because they have created these many instructions to handle specific use-cases, and so can be performance-optimized for specific common instruction scenarios.

However, I am interested in the fact that all logic can be boiled down to AND + NOT or OR + NOT. I'm not sure if this means you can implement a computer with just these two instructions, or if it's not possible to model things like ALUs using them. But it's interesting.

What I'm wondering though is if there is any notion of "optimal" in the architecture of an ISA. For example, it's a lot easier to represent things you can do in a computer with the let's say 20 or 30 or so regular operators like + and >= and =, etc. LLVM also shows you can have a pretty small instruction set, not taking into account the instructions with multiple different variations based on the datatype (int32 vs. int64, etc.). But either way, from a practical perspective I suspect most people don't use the 100's of x86 instructions, and instead use a standard small subset. Compiler architects probably do because they have the time and resources to do all the micro optimizations perhaps.

But then there are the optimizations in terms of processor speed. Implementing custom instructions like x86 does probably allows you to take advantage of hardware accelerations. So there is a balance.

My question is if there are any resources/papers/topics on "optimal" and "minimal" ISAs. Maybe they have like 10 or 20 instructions or something like that. Some minimal but not too minimal as in OISCs.

Answer 1

The paper you are asking for is:

Patterson, David A; Ditzel; David R: The case for the Reduced Instruction Set Computer, Computer Architecture News, 8(6):25-33, Oct 1980. (non-paywalled copy).

Beware that it may be the paper you are asking for, but may not be the paper you want. Almost everything it says is false, or has been debunked. It is more of a humanities paper than a computer science paper.

There are ways of reducing the number of instruction bits that are fetched from DRAM (using more-or-less traditional compression techniques like Huffman encoding). (And these kinds of concerns about minimizing instruction bits are evident in most "CISC" designs, as I described in a different question.) There are ways of minimizing the decode logic of a state machine (see for example the work of Villa, Kam, Brayton and Sangiovanni-Vincentelli, especially their 1997 book). There are ways of minimizing the amount of power consumed by an instruction (for example, by increasing the number of different things that the instruction does, thereby better amortizing the power costs of fetching and decoding the instruction).

Finally, when there are ways of better representing instructions internally (for example to reduce decode power) it is trivial to do the translation from the "bad" instruction set to the "good" instruction set and cache the result. (Something x86 processors and many others have been doing since the late '80's (I can't find the academic references for this idea right now)).

What is rarely the case is that minimizing the number of instruction opcodes, or minimizing the number of addressing modes, is correlated with optimizing anything else about a computer design.