Instruction Set Architecture
This page is intended to provide an explanation of some of the various types of instruction sets. The instruction sets are listed starting with the simplest and ending with the most complex instruction set.
See also Historical Notes on CISC and RISC.
Church-Turing Thesis
Alan Turing (1912-1954) was highly influential during the early days of computer science. The Church-Turing thesis states that any algorithm computable by humans (without time and memory limitations and without failures) is computable by a Turing machine.
To be Turing complete, a machine must be able to load data, change it according to a set of rules, and store it afterwards. Loading and storing values 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, in 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 in 1984 that an array (packed) data structure could achieve more executed instructions per cycle than one.
This will become important speaking when 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 make it possible to decide, to move data, to calculate, and to jump to different targets in the instruction stream. This is only possible with a complex instruction.
Applications for a computer programmed by this ISA have huge programs, so 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 program 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 may cause security issues. Oftentimes, 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 access, and will therefore induce idle times in 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.
Very Long Instruction Word
VLIW processors are defined by large instruction bundles that are split up into several smaller independent instructions, these independent instructions often map to specific execution units within the processor. Some prominent CPU VLIW architectures include: Itanium, and Elbrus 2000. Although not often used in CPUs, VLIW designs have been quite common in GPUs with architectures such as AMD's Terascale systems.