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

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.

• "Most computers today I think use the x86 architecture": depends what you mean by computer. There are far more embedded devices using ARM or other RISC instruction sets such as Atmel's AVR than there are desktop and laptop PCs. Feb 11 '19 at 10:54
• "I'm not sure if this means you can implement a computer with just these two instructions": typical CPUs are implemented with NANDs in silicon. Feb 11 '19 at 10:59
• @PeterTaylor please explain more that's so interesting, maybe where I can find a resource to see the implementation of some/all of the different CPU pieces with NANDs. (electronics.stackexchange.com/questions/280855/…) Feb 11 '19 at 19:21
• electronics.stackexchange.com/questions/203605/… Feb 11 '19 at 19:26

1 Answer

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.

• It's also worth pointing out that one motivation behind SIMD vector instructions is that it's a way of designing an ISA to keep functional units as busy as possible with less pressure on instruction issue. That's another kind of "optimal". Feb 11 '19 at 0:06
• The complexity of translation is not always trivial (for some values of trivial). E.g., instruction fusion is typically limited to two adjacent instructions (similarly POWER8 dynamic hammock predication only handles single instruction branches). VAX's POLY instruction was probably not a good idea even at the time, so including every even remotely plausible opcode probably does negatively correlate with optimizing a computer design. Preserving many obsolete opcodes (like multiply step) to provide compatibility is not free. Feb 11 '19 at 0:09