Instruction Set Architecture
This page is intended to provide an explanation of the various instruction set architecture principles such as Complex Instruction Set, Reduced Instruction Set, Writable Instruction Set, Single Instruction Set, etc. The instruction sets are named beginning with the simplest toward the most complex set.
See also Historical Notes on CISC and RISC.
Church-Turing Thesis
For the beginning of theoretical informatics Alan Turing(1912-1954) was maybe the most important person. The Church-Turing thesis states that any algorithm computable by humans (without time and memory limitations and of course failure free) is computable by an Church-Turing powerful machine.
To be Church-Turing mighty, it is sufficient to be able to load data, change it in any possible way and store it afterwards. Saving and Storing a value is self explanatory, the interesting part is the processing.
Common algorithms:
- Logic functions: One might not notice, but e.g. brains use in daily challenges for decisions simple state machines and every state machine can be expressed by logic functions.
- Comparisons: Is this red brighter than this? Answer: Yes or No. See example above. This is implemented by an addition or rather a subtraction. Can be implemented by logical functions.
- Multiplications/divisions: Used f.e. in case of applying weights. Can be implemented by addition and subtraction, and addition can be implemented by logic functions, so ...
- Integration/differentiation: Any physic law may be implemented by using integration and differentiation. Can be implemented by multiplication or rather division, and this can be implemented by arithmetic and logic functions.
As you might have noticed everything can be implemented by logic functions. This is important: To be able to do any logic function means to be Church-Turing mighty.
To be exact only a single logic function, such as NAND, with two inputs and one output is needed. Other sets of "complete" logic functions can be found, but NAND is the most common.
Any Instruction Set Architecture (ISA) is Church-Turing mighty.
Flynn's Bottleneck and Fisher's Optimism
M. J. Flynn (*1934) found 1970 a very interesting fact: If one fetches (loads) only one instruction per cycle, one will never get more than one executed instruction per cycle. (This is valid for each physical ALU.)
J. A. Fisher (*1946) argued 1984 an array (packed) data structure could achieve more executed instructions per cycle than one.
This will become important speaking about RISC/CISC dis-/advantages.
One Instruction Set
The so called Ultimate Reduced Instruction Set Computer (URISC) or One Instruction Set Computer (OISC) is programmed by only one instruction. This instruction must be possible however to decide, to move data, to jump to different targets in the instruction stream and to calculate. This is only possible with a complex instruction.
Applications for a computer programmed by this ISA have a huge-sized code, so that this ISA is only of theoretical interest. For further information refer to One instruction set computer on Wikipedia.
Minimal Instruction Set
It is defined by less than 32 instructions (one can't really distinguish between MISC and RISC). Mostly MISCs are Stack machines. Owing to missing security features and the huge code size this ISA is not used anymore, but its instructions are included in more sophisticated ISAs. For further information refer to Minimal instruction set computer. This type of instruction set has been used on some early computers such as ENIAC.
Reduced Instruction Set
A RISC provides fast and simple basic instructions, e.g. conditional jumps, logic functions, addition/subtraction, multiplication/division, etc. It's execution environment is simple, because RISC must not provide complex instructions. This might cause security issues. Often Flynn's bottleneck applies, because data can't be processed in advanced structures, as the ISA must be simple by definition. Examples of RISC ISAs include previous ARM and MIPS generations.
Complex Instruction Set
A CISC instantiates simple and additional complex instructions. It comes mostly with different execution environments and security features. Especially streaming extensions like SSE must be named. They are the reason why RISC-only processors almost disappeared nowadays. Flynn's bottleneck applies, but by using streaming extensions the chance to reduce its influence and switch to Fisher's optimism grows fast. Other advanced features may reduce memory accesses and therefore idle times of the CPU. Clearly the advantage of the CISC architectures are their capabilities, but that complexity is a disadvantage as well and can result in serious security issues that it needs to handle. CISC architectures such as M68K or 6502 were common in the early days of computing, when optimising compiler technology was less advanced. A CISC architecture still in use is x86 (including x86_64).
Hybrid Instruction Set
Modern CPUs are built upon a hybrid RISC-CISC architecture. RISC processors can be built more easily and clocked faster, but lack the advanced instructions of a CISC. To get the best of both worlds, a hybrid is built. A RISC is used as the ALU, and is wrapped by a CISC environment. Any instruction is interpreted by this CISC and is split into one or more sub-instructions, called "micro-opcodes", for the RISC. Additionally, the CISC-wrapping provides security, along with operating system stability and control. Nowadays, only microcontrollers use pure RISC; any other CPU is more or less a hybrid RISC-CISC CPU.