Processors, parallel processing, virtual machines and Boolean algebra

RISC and CISC: two ways to design an instruction set

Every processor understands a fixed list of instructions, its instruction set, and the size and style of that set is the main thing that separates a CISC (Complex Instruction Set Computer) from a RISC (Reduced Instruction Set Computer). The two names describe a design choice, not a quality ranking: both designs are used in real machines today, and which one is chosen depends on what the processor has to do and how much power it may use.

A CISC processor has a large instruction set, often several hundred instructions, and the instructions are variable in length. Many are genuinely complex: one instruction can fetch a value from memory, add it to a register and store the result back, and it may take several clock cycles to finish. CISC offers many addressing modes, so an instruction can reach its operand in several different ways, and because each instruction does more work the finished program is shorter. The cost is a complicated control unit, usually microprogrammed, in which each machine instruction is broken into a sequence of simpler micro-instructions held in a control store. That takes transistors, design effort and power, but it keeps a compiler's job easier and keeps decades of old software running, which is why the x86 family in most desktop PCs and servers is CISC.

A RISC processor goes the other way. It has a small instruction set of simple instructions, all of the same fixed length, and nearly every one completes in a single clock cycle. It uses a load/store architecture: only LOAD and STORE instructions touch memory, and every arithmetic or logic instruction works on values already sitting in registers. There are few addressing modes and many general-purpose registers (32 or more is typical), and the control unit is hardwired instead of microprogrammed, which is simpler and faster. The price is that the same job needs more instructions, so the program is larger and the compiler has more work to do; the gain is that each instruction is quick and predictable, which makes the processor cheap to build, low on power and very easy to pipeline.

The comparison you must be able to write is a set of paired statements. 'RISC has fewer instructions' on its own scores nothing, while 'RISC instructions are a fixed length, so the decode stage always takes the same time, whereas CISC instructions vary in length and may take several cycles' scores and is the kind of sentence the mark scheme is built from.

• Fixed length: RISC instructions are all one word; on a CISC they can be one byte or ten, which makes decoding harder.
• Cycles per instruction: most RISC instructions complete in one clock cycle; a complex CISC instruction may need many.
• Memory access: only LOAD and STORE reach memory on a RISC; most CISC instructions can take an operand straight from memory.
• Registers: a RISC has many general-purpose registers; a CISC has fewer, so intermediate values go back to memory more often.
• Code size: the CISC program is shorter; the RISC program has more instructions but each one is simpler.
• Where each is used: CISC for general-purpose desktops and servers that must run existing software; RISC (for example ARM) in phones, tablets and embedded systems where power and heat matter.

Interrupts: how a processor responds, and why RISC responds faster

An interrupt is a signal, sent by hardware or generated by software, telling the processor that something needs attention now. It might be a device that has finished a transfer, a timer tick reminding the operating system to switch between processes, a hardware fault such as a power failure, or a program error such as division by zero. Interrupts exist so that the processor does not have to keep stopping to check every device in turn: the device announces itself when it is ready.

The processor does not respond in the middle of an instruction. It checks for pending interrupts at the end of each fetch-decode-execute cycle, and if one is waiting it works through a fixed sequence: finish the instruction it is on; save the processor state (the program counter and the contents of the registers, together called the context), on most designs by pushing them onto a stack in memory; load the address of the correct interrupt service routine (ISR) from the interrupt vector table into the program counter; run the ISR, which services the device; restore the saved state; and resume the interrupted program at exactly the point it had reached. Interrupts carry priorities, so a high-priority interrupt can itself interrupt a low-priority ISR, and interrupts can be masked so that a critical section of code cannot be broken into.

On a CISC processor this sequence is slower and harder to predict. Because the instructions are complex and take several clock cycles, the processor cannot be interrupted halfway through one without preserving a great deal of internal state, so it must run to the end of the instruction; a long instruction means a longer and less predictable wait before the interrupt is serviced, which is the processor's interrupt latency. CISC designs often include dedicated instructions for handling interrupts, which helps the programmer, but because a CISC has relatively few registers, more of the context has to be written out to the stack - several extra memory writes before the ISR can even begin.

A RISC processor handles the same interrupt quickly and predictably. Every instruction is the same length and takes one cycle, so there is never a long instruction left to finish and the processor reaches a safe point almost at once. Because a RISC has many registers, more of the context can be saved into registers instead of memory, and many RISC designs provide register banks or shadow registers so that a whole bank can be swapped in a single step. The load/store design also means that a long operation is already a chain of short instructions, each of which is a safe place to stop. That is why RISC dominates in embedded and real-time systems, where interrupts arrive constantly and must be answered within a guaranteed time.

Pipelining and registers in RISC processors

The fetch-decode-execute cycle is usually drawn as three steps one after another, but the three steps use different hardware inside the processor. Pipelining exploits that: instead of waiting for one instruction to finish before starting the next, the processor overlaps the stages, so while instruction 1 is being executed instruction 2 is being decoded and instruction 3 is being fetched. A typical five-stage pipeline is fetch, decode, execute, memory access and write back.

After the pipeline has filled - which takes as many clock cycles as there are stages - one instruction completes in every clock cycle. A five-stage pipeline therefore gives close to five times the throughput of the same processor without pipelining. It does not make any single instruction finish sooner: the time from fetch to write back for one instruction is unchanged, and may even rise slightly because a register sits between each pair of stages.

RISC suits pipelining almost perfectly, and this is the link the syllabus wants. Fixed-length instructions mean every stage has the same amount of work and can complete in one cycle, so no stage waits for a long instruction to finish. Simple addressing means an effective address can be worked out inside the decode stage. The load/store design means only two instructions use the memory stage, so the stages stay balanced. And having many registers means most operands are already inside the processor, so the pipeline rarely has to stop and wait for memory.

Pipelines are held up by hazards. A data hazard happens when an instruction needs a result that the instruction in front of it has not yet written back; the pipeline must stall (insert a bubble) or the hardware must forward the result straight across. A control hazard happens at a branch, because the processor does not know which instruction to fetch next until the branch is resolved; it either flushes the wrongly fetched instructions or uses branch prediction and speculates. A structural hazard happens when two instructions in the pipeline want the same hardware in the same cycle.

Registers are the small, extremely fast storage locations inside the processor, built from flip-flops, and they exist because main memory is far too slow to feed a one-cycle pipeline. The program counter holds the address of the next instruction to fetch. The memory address register and memory data register hold the address and the data passing to and from memory. The current instruction register holds the instruction being decoded, the accumulator holds the result of the arithmetic being done, the status register holds the condition flags, and the stack pointer holds the top of the stack used for subroutine calls and interrupts. The general-purpose registers hold the operands and results of the program itself, and a RISC has many of them so that a calculation can be done without repeatedly going back to memory.

The four basic computer architectures: SISD, SIMD, MISD, MIMD

The four Flynn classifications describe a computer by asking two questions: how many instruction streams can it work on at once, and how many data streams can it work on at once? A stream is a sequence - one instruction stream means one sequence of instructions being executed, and one data stream means one sequence of operands being worked through.

SISD - single instruction, single data - is the ordinary one-processor computer. One instruction is fetched and executed at a time, on one item of data, exactly as the fetch-decode-execute cycle describes. A single-core desktop processor is SISD, even though it pipelines internally, because pipelining overlaps the stages of different instructions rather than executing several instructions in parallel.

SIMD - single instruction, multiple data - applies one instruction to many data items at the same time. Vector and array processors work this way, and so do the thousands of cores in a GPU: one instruction tells every core to add its own pair of pixel values, so a whole image is processed in the time one pixel would have taken. SIMD is ideal when the same operation is repeated over a large regular set of numbers - image and video processing, matrix arithmetic, physics simulations and the arithmetic inside neural networks.

MISD - multiple instruction streams working on a single data stream - is the odd one out. Several processors each apply a different operation to the same data. True MISD machines are rare because most problems do not have that shape; the usual illustration is a fault-tolerant system in which several processors run the same input through different implementations and a voter compares the results, or a systolic array in which data is passed through a chain of processing elements. You are expected to describe it, not to name one on your desk.

MIMD - multiple instruction, multiple data - gives every processor its own instruction stream and its own data. Multicore processors, multi-processor servers, clusters of machines and supercomputers are all MIMD. It is the most flexible arrangement and the one that handles general parallel programs, because different processors can be doing genuinely different jobs; it is also the hardest to program, because the processors must be kept supplied with work and their results must be coordinated through shared memory or messages.

Massively parallel computers

A massively parallel computer is a machine built from a very large number of processors - thousands, or tens of thousands - that work on one problem at the same time. Each processor normally has its own local memory and its own copy of the program, so the machine is MIMD in Flynn's terms, and the processors are joined by a very fast internal network over which they pass messages.

The defining characteristics follow from that structure. There are very many processors rather than a handful of cores, so the machine's throughput is enormous and grows as more processors are added. Each processor works on a small part of the problem, which means the problem itself must be divisible into many independent pieces. Processors communicate by message passing or through shared memory, and that communication is the main limit on performance: time spent sending data between processors is time not spent computing, and if the processors must constantly exchange results the gain from adding more of them shrinks. Such machines are expensive, power-hungry and need heavy cooling, they need software written specifically to be parallel, and they are poor at problems that are inherently sequential.

They are used for problems where enormous numbers of similar calculations are needed: weather and climate modelling, which divides the atmosphere into millions of cells; protein folding and drug design; computational fluid dynamics and crash simulation; astrophysics and particle physics; code-breaking; seismic imaging; and the training of large machine-learning models. The same idea at a smaller scale appears in a cluster, a group of ordinary servers linked by a fast network, which is cheaper than a purpose-built supercomputer and is how most universities do this work.

Frontier, at Oak Ridge National Laboratory in the United States, is a working example: thousands of nodes, each containing a CPU and several GPUs, joined by a high-speed network, running one simulation spread across the whole machine. Fugaku, in Japan, is built on ARM-based RISC processors and is another. You do not need their specification, only the shape of the argument: many processors, each with local memory, a fast interconnect, and a problem cut into pieces small enough to be shared out.

• Very large number of processors, each with its own local memory and its own instructions - the MIMD pattern.
• The problem must be split into many independent parts, or the processors spend their time waiting for each other.
• Processors exchange data by message passing over a fast interconnect, or through shared memory.
• Performance scales with the number of processors only until communication and synchronisation dominate.
• High cost, high power consumption and heavy cooling; needs a machine room, not a desk.
• Software must be written or rewritten for parallel execution; an ordinary sequential program gains nothing.
• Reliability can be improved by redundancy, because losing one node out of thousands need not stop the job.

Virtual machines: the concept, the roles and the trade-offs

A virtual machine (VM) is a software implementation of a computer system. It behaves like a complete computer - its own processor, memory, storage, network interfaces and operating system - but everything it appears to own is really being provided by software running on shared physical hardware. The layer of software that creates and manages the VMs is the hypervisor, and it decides which VM uses the physical processor, and when.

There are two kinds. A type 1 (bare-metal) hypervisor runs directly on the hardware with no host operating system underneath, and the guest operating systems sit on top of it; this is what data centres and cloud providers use, for example VMware ESXi or Microsoft Hyper-V. A type 2 (hosted) hypervisor is an ordinary application running on a normal operating system, with the VMs created inside it; this is what you would install on a laptop, for example VirtualBox or VMware Workstation. There is also the process virtual machine, which emulates just enough of a machine to run one program - the Java Virtual Machine is the classic case, executing compiled bytecode so that the same program runs on any hardware that has a JVM installed.

The roles are worth learning as a list, because questions often ask for examples. A VM lets one physical machine run several different operating systems at once, so a Linux server can host a Windows application. It gives a safe, isolated environment for testing software, trying a new operating system or opening a suspicious file, because damage inside the VM does not reach the host. It allows server consolidation, replacing a room of under-used physical servers with one large host running many VMs. It supports cloud computing, where a provider sells VMs rather than machines. It keeps legacy software alive by running an old operating system on modern hardware. It supports snapshots and cloning, so a system can be rolled back to a known good state in seconds, and it makes an excellent teaching and demonstration environment because a broken VM is simply reset.

Boolean algebra and De Morgan's laws

Boolean algebra is the algebra of two values, 0 and 1, and it is how logic circuits are described and simplified. A variable such as A is a signal that is either 0 (false, low voltage) or 1 (true, high voltage). The three operations are NOT, written as a bar over the letter or as an apostrophe (A' means NOT A), AND, written with a dot or by writing the letters together (A.B or AB), and OR, written with a plus sign (A + B). Brackets are worked out first, then NOT, then AND, then OR - so A + B.C means A + (B.C), not (A + B).C.

The laws below are the whole toolkit. You are not expected to memorise a huge list, but you are expected to use each step in a simplification and to be able to say which law you used.

• De Morgan's first law: (A.B)' = A' + B'. The NOT of an AND is the OR of the NOTs.
• De Morgan's second law: (A + B)' = A'.B'. The NOT of an OR is the AND of the NOTs.
• The rule to apply it: break the bar, change the sign underneath, and invert each term. (A.B.C)' becomes A' + B' + C', and (A + B + C)' becomes A'.B'.C', for any number of terms.
• Both laws together: (A.B + C)' = (A.B)'.C' = (A' + B').C'. Work from the outside in, one bar at a time.
• Simplify before you expand: look for A + A' (= 1) and A.A' (= 0) first, because they collapse a whole expression in one line.

Logic circuits: half adders, full adders and flip-flops

A truth table lists every possible combination of inputs and the output for each. With n inputs there are 2 to the power n rows, written in binary counting order (00, 01, 10, 11) so that nothing is missed, and it helps to add intermediate columns - one for each bracket in the expression - so the final column can be checked. Gates with more than two inputs follow the same rules: a three-input AND is 1 only when all three inputs are 1, and a three-input OR is 1 when any one of them is 1, so always read the gate symbol for its number of inputs.

A half adder adds two single bits, A and B. Its Sum output is 1 when exactly one input is 1, which is the XOR function, and its Carry output is 1 only when both inputs are 1, which is AND. The truth table is short: 0+0 gives Sum 0 Carry 0; 0+1 and 1+0 both give Sum 1 Carry 0; 1+1 gives Sum 0 Carry 1, because binary 1 + 1 = 10. The limitation is in the name - it has no input for a carry arriving from a previous column, so it can only add the rightmost bits of two numbers.

A full adder adds three bits: A, B and a carry in, Cin. Its Sum is A XOR B XOR Cin, and its Carry out is A.B + Cin.(A XOR B). It can be built from two half adders and an OR gate: the first half adder adds A and B, the second adds that Sum to Cin, and the OR combines the two carries. Chaining n full adders, with each Carry out feeding the next Carry in, gives an n-bit adder - the ripple carry adder at the heart of every ALU - and the carry is what makes the delay grow with the number of bits.

• Half adder: Sum = A XOR B, Carry = A AND B. Four rows, two gates.
• Full adder: Sum = A XOR B XOR Cin, Cout = A.B + Cin.(A XOR B). Eight rows, five gates if built directly.
• SR flip-flop (NOR version): two NOR gates cross-coupled, output Q taken from one and Q' from the other. S = 1, R = 0 sets Q to 1; S = 0, R = 1 resets Q to 0; S = 0, R = 0 holds the previous value; S = 1, R = 1 is invalid, because both outputs go to 0 and Q and Q' are no longer opposites.
• SR flip-flop (NAND version): the same circuit built from NAND gates, with the inputs active low - the invalid state is S = 0, R = 0 and the hold state is S = 1, R = 1. Read the gate type before you write the table.
• JK flip-flop: J and K replace S and R and the invalid state is removed. J = 0, K = 0 holds; J = 0, K = 1 resets to 0; J = 1, K = 0 sets to 1; J = 1, K = 1 toggles, so Q becomes Q'.
• Why flip-flops matter: one flip-flop stores one bit and keeps it after the input is removed, so a row of them is a register, and registers, counters and the memory cells of SRAM are all built from them.

Karnaugh maps: simplifying without guesswork

Algebraic simplification works, but it depends on spotting the right law at the right moment. A Karnaugh map (K-map) turns the same job into a picture. The map is a grid with one cell for every row of the truth table, and the cells are arranged so that any two adjacent cells differ in exactly one variable. That is why the column and row labels are ordered 00, 01, 11, 10 - Gray code - and not 00, 01, 10, 11: in the Gray order, 01 and 11 differ only in the first bit.

To use it: write a 1 in every cell where the output is 1. Then group the 1s into rectangles containing 1, 2, 4, 8 or 16 cells - always a power of two, never three or five - and make each group as large as possible and use as few groups as possible. Groups may overlap, which is normal and often necessary, and groups may wrap around the edges of the map, because the left and right columns and the top and bottom rows are also adjacent. Each group becomes one product term: the variables that change inside the group are eliminated, and the variables that stay the same are kept, written unbarred if they are 1 and barred if they are 0.

A group of 2 cells removes one variable, a group of 4 removes two, a group of 8 removes three, and a single ungrouped cell keeps all of them. A three-variable map with 1s in cells 0, 1, 4, 5 and 7 (reading A B C) gives two groups: cells 0, 1, 4, 5 form a block of four across both A values with B = 0 throughout, so they give B'; cells 5 and 7 share A = 1 and C = 1, so they give A.C. The simplified expression is X = B' + A.C, which needs two gates instead of the five the original sum of three minterms would have taken.

The benefit is that the map is systematic and quick, it gives a minimum sum of products for up to four variables without relying on inspiration, and fewer terms mean fewer gates: a cheaper circuit, a faster one because the signal passes through fewer stages, lower power, and less chance of a wiring error. The limitations are that maps become unmanageable beyond four or five variables, they handle XOR and XNOR patterns badly, and a careless group - three cells, a diagonal, or a group that does not actually cover the 1s - gives a wrong expression that still looks tidy.