Hardware and Virtual Machines

This chapter extends chapters 3 and 4 for Paper 3. The first half is about how processors are designed and combined; the second half moves from logic gates to circuits that calculate and remember, and the algebra for simplifying them.

15.1 Processors, parallel processing and virtual machines

RISC and CISC

Pipelining

Pipelining lets the processor work on several instructions at the same time, each at a different stage of the fetch-decode-execute cycle, like an assembly line. While one instruction is being executed, the next is being decoded and the one after that is being fetched.

Without pipelining, three instructions would take 9 cycles; with it, 5 (and one new instruction finishes every cycle after the pipeline is full). This increases throughput. Pipelining is easier with RISC, because every instruction needs the same time and has a simple format, and many registers keep the data close so the pipeline does not wait for memory.

Tap to enlarge

Two timing grids for three instructions each needing fetch, decode and execute: without pipelining they take nine clock cycles one after another, and with pipelining the stages overlap so all three finish in five cycles

Close

Problems (hazards): a branch or jump means the instructions already fetched may be the wrong ones, so the pipeline has to be flushed and refilled, wasting cycles; and an instruction may need the result of one still in the pipeline, so it must wait (a data dependency). These are reduced by branch prediction and by re-ordering instructions.

Interrupts on RISC and CISC processors

Both types check for an interrupt at the end of an instruction and then save the state, run the interrupt service routine and restore the state (chapter 4). CISC: instructions are long and take several cycles, so the processor finishes the current instruction before it can respond, which makes the response slower; the registers are usually saved to the stack in memory. RISC: instructions are short and take one cycle, so the response is quicker and the pipeline can be flushed and refilled quickly; the many registers mean the interrupt routine can use spare ones (some designs have separate register banks) instead of saving every register to memory.

The four basic computer architectures (Flynn's taxonomy)

Computers can be classed by the number of instruction streams and data streams they handle at once.

Massively parallel computers

A massively parallel computer has thousands of processors (each with its own memory), connected by a very fast network, that work on different parts of one problem at the same time. The problem is divided up (decomposition), the parts are processed in parallel, and the results are combined. It is much faster than a single processor for suitable problems.

Characteristics: very large number of processors (or cores); the work must be split so the processors work at the same time; fast communication between them; needs specially written software; problems with a lot of independent calculations benefit most. Uses: weather forecasting, climate and scientific modelling, simulating nuclear reactions, analysing genetic data, large-scale machine learning, and graphics. The drawbacks are the cost, the power use and cooling needed, the difficulty of programming, and that tasks which depend on previous results cannot be done in parallel.

Virtual machines

A virtual machine (VM) is a software emulation of a computer that runs on a host computer. It behaves like a separate physical machine, with its own (virtual) processor, memory, storage and operating system.

Uses:

• Running a different operating system on the same computer (for example Linux on a Windows PC).
• Testing software, or running untrusted programs, safely: the VM is isolated, so a fault or virus does not affect the host.
• Running old software that needs an old operating system.
• Server consolidation: several virtual servers on one physical machine.
• Java Virtual Machine (JVM): Java is compiled to bytecode that the JVM interprets, so the same program runs on any hardware with a JVM (chapter 5).

Benefits: cheaper than having many real machines; isolation and security; easy to copy, back up and restore; the hardware is used more fully. Drawbacks: the VM runs slower than a real machine, since it shares the host's resources and has the extra layer of emulation, and the host needs enough memory and processing power.

15.2 Boolean algebra and logic circuits

Half adder and full adder

A computer adds binary numbers using logic circuits.

A half adder adds two bits, A and B, and gives a sum (S) and a carry (C):

$S = A \text{ XOR } B$ and $C = A \text{ AND } B$. It is built from one XOR gate and one AND gate. It cannot add a carry in from a previous column.

A full adder adds three bits: A, B and a carry in ($C_{in}$), and gives a sum and carry out ($C_{out}$):

$S = (A \text{ XOR } B) \text{ XOR } C_{in}$ and $C_{out} = (A \text{ AND } B) \text{ OR } (C_{in} \text{ AND } (A \text{ XOR } B))$. A full adder can be built from two half adders and an OR gate. Linking full adders (the carry out of one is the carry in of the next) makes a ripple-carry adder that adds binary numbers of any number of bits.

Tap to enlarge

A half adder built from an XOR gate giving the sum and an AND gate giving the carry, a full adder built from two half adders and an OR gate adding A, B and a carry in, and the full adder truth table

Close

Flip-flops

A flip-flop is a circuit that can store one bit and keeps its value until it is changed, so it is the basis of memory and registers (SRAM is built from flip-flops). It has two stable states.

SR flip-flop (set-reset), built from two NOR (or NAND) gates with the outputs fed back to the inputs:

Tap to enlarge

An SR flip-flop drawn as two NOR gates with each output fed back to the other gate's input, with inputs S for set and R for reset, outputs Q and not Q, and a table showing that S and R both 0 keeps the value, S 1 sets Q to 1, R 1 resets it to 0, and both 1 is not allowed

Close

JK flip-flop: like the SR, but it has a clock input, and it removes the invalid state: when J = 1 and K = 1, the output toggles (changes to the opposite of Q) at each clock pulse.

Flip-flops are used to build registers, counters, memory cells (SRAM) and sequential (clocked) circuits.

Boolean algebra

Boolean algebra is the algebra of TRUE/FALSE (1/0) values. It is used to simplify logic expressions, which gives a circuit with fewer gates (cheaper, faster, smaller). Notation: $A \cdot B$ (AND), $A + B$ (OR), $\bar{A}$ (NOT), $A \oplus B$ (XOR).

Worked example: simplify $X = A \cdot B + A \cdot \bar{B}$.

$X = A \cdot (B + \bar{B}) = A \cdot 1 = A$ (distributive, then inverse, then identity).

Another: $X = \overline{A \cdot B} \cdot (A + B)$. By De Morgan, $\overline{A \cdot B} = \bar A + \bar B$, so $X = (\bar A + \bar B)(A + B) = \bar A B + A \bar B$ (the other terms $\bar A A$ and $\bar B B$ are 0), which is the XOR function.

Karnaugh maps (K-maps)

A Karnaugh map is a grid used to simplify a Boolean expression without using the laws. Each cell is one row of the truth table. The row and column labels use Gray code (only one bit changes between neighbouring cells: 00, 01, 11, 10), so cells that are adjacent differ by one variable. For two variables there are 4 cells, for three variables 8, for four variables 16.

Benefits of K-maps. They give a visual, step-by-step way to simplify an expression with less algebra, they make it easier to spot the groups, and they reduce the chance of mistakes compared with applying the Boolean laws one at a time. They are practical up to about four variables.

Method:

1. Draw the grid and fill it with the output values (1s and 0s) from the truth table.
2. Group the 1s into rectangles of size 1, 2, 4, 8 or 16 (a power of 2). Groups must contain only 1s, be as large as possible, and can wrap around the edges (the left edge is next to the right edge, and the top edge is next to the bottom edge). Groups may overlap. Every 1 must be in at least one group.
3. For each group, write the term made of the variables that do not change within the group (a variable that is 1 throughout the group appears as itself; one that is 0 throughout appears NOT-ed; a variable that changes is left out).
4. OR the terms together to get the simplified sum-of-products expression.

Tap to enlarge

Two three-variable Karnaugh maps: in the first the four 1s in the columns 00 and 01 form one group where only B stays at 0, giving NOT B; in the second the 1s in the left and right edge columns wrap round to form one group where only C stays at 0, giving NOT C

Close

Example (3 variables A, B, C). Output X is 1 for ABC = 000, 001, 100, 101 (a 2×2 block when plotted with A as the row and BC as the column in Gray code order 00, 01, 11, 10):

The four 1s form one group of 4. Over the group A changes (0 to 1) and C changes (0 to 1), but B is always 0. So $X = \bar{B}$, a single NOT gate instead of four AND terms.