Microprocessor and Computer Architecture

The instruction cycle is the sequence of steps a CPU repeats to execute each instruction: fetch the instruction from memory, decode it, fetch the operand (if any, using the effective address), execute it, and then store the result and go on to the next instruction.

The address bus is a unidirectional bus on which the CPU sends the address of the memory location or I/O port to be accessed; its width ($n$ lines) decides the addressable memory of $2^n$ locations. The data bus is a bidirectional bus that carries the actual data between the CPU, memory and I/O devices; its width decides how many bits are transferred at once.

DMA (Direct Memory Access) is a technique in which an I/O device transfers a block of data directly to or from main memory under the control of a DMA controller, without passing it through the CPU. The CPU only starts the transfer and is interrupted when it ends, so the transfer is fast and the CPU is free for other work.

SAP-2 (Simple-As-Possible 2) is the second stage of the SAP teaching computer. It extends SAP-1 with a 16-bit address (64 KB memory), registers A, B and C, input and output ports, a bidirectional register, flags (sign and zero), and jump, call and return instructions. Its instruction set includes MOV, MVI, ADD, SUB, ANA, ORA, XRA, INR, DCR, JMP, JM, JZ, CALL, RET, IN, OUT and HLT, and the instructions are one to three bytes long. It is close to the Intel 8085 and is used to understand microprocessor operation.

The operation code (opcode) is the part of a machine instruction that specifies the operation to be performed, such as add, load, store or jump. The control unit decodes it to produce the control signals; the remaining bits of the instruction are the operand address or data.

An instruction format is the layout of the bits of an instruction, divided into fields. It normally contains an opcode field, one or more address (operand) fields and a mode field that tells how the operand address is found. Depending on the number of address fields, formats are three-address, two-address, one-address and zero-address.

Shift microoperations move the bits of a register left or right, and are used for serial transfer and for arithmetic. The three types are:

• Logical shift: zero is shifted in at the vacant end (shl, shr).
• Circular shift (rotate): the bit shifted out is fed back into the other end (cil, cir).
• Arithmetic shift: the sign bit is kept; shifting left multiplies by 2 and shifting right divides by 2 (ashl, ashr).

Example: $R \leftarrow \text{shl } R$.

CISC (Complex Instruction Set Computer) is a processor architecture with a large set of powerful instructions, many addressing modes, variable-length instructions and microprogrammed control. A single instruction can do a multi-step task, which makes programs short but needs several clock cycles per instruction. Examples are the Intel x86 family and the VAX.

Memory hierarchy is the arrangement of the different memories of a computer in levels according to speed, cost and size: registers, cache memory, main memory, secondary storage (disk) and tertiary storage. Going down the hierarchy, capacity increases and cost per bit falls, but access time rises. The hierarchy gives the CPU an effective speed close to the fastest memory at a cost close to the cheapest, because of the locality of reference.

Data dependency (data hazard) occurs in a pipeline when an instruction needs the result of an earlier instruction that has not yet been produced. For example, in ADD R1,R2,R3 followed by SUB R4,R1,R5, the second instruction needs R1 before the first has written it. The pipeline must stall or use operand forwarding. Types are RAW, WAR and WAW.

The Intel 8085 is an 8-bit microprocessor with about 74 instructions (246 opcodes), which are grouped as:

1. Data transfer: MOV, MVI, LDA, STA, LXI, LDAX, XCHG.
2. Arithmetic: ADD, ADI, SUB, SUI, INR, DCR, INX, DAA.
3. Logical: ANA, ORA, XRA, CMP, RAL, RAR, CMA.
4. Branching: JMP, JZ, JNZ, JC, CALL, RET.
5. Machine control: HLT, NOP, EI, DI, IN, OUT.

By size, instructions are one, two or three bytes long. Example: MVI A, 05H loads 05H into the accumulator.

Arithmetic microoperations perform arithmetic on data stored in registers:

A single binary adder with a selection circuit (the arithmetic circuit) implements all of them. Subtraction is done by adding the 2's complement of the subtrahend.

Symbolic microinstructions are microinstructions written in assembly-like symbolic form, which an microprogram assembler translates into the binary microinstruction format. Each line has fields:

1. Label: optional, ends with a colon, marks the microinstruction address.
2. Microoperations: up to three fields F1, F2, F3, each naming a microoperation (e.g. ADD, DRTAC, READ), or NOP.
3. CD (condition): U (unconditional), I (indirect bit), S (sign bit), Z (zero).
4. BR (branch): JMP, CALL, RET or MAP.
5. AD (address): a symbolic address or label (or NEXT).

Example: ORG 64 followed by ADD: NOP I CALL INDRCT and READ U JMP NEXT.

The control unit of the basic computer is hardwired. It generates the control signals that direct the register transfers of each instruction cycle.

Main components

• Instruction register (IR): 16 bits. Bits 12-14 are the opcode, bit 15 is the mode bit $I$, bits 0-11 are the address.
• 3x8 decoder: decodes the opcode into $D_0$ to $D_7$.
• 4-bit sequence counter (SC) and 4x16 decoder: produces the timing signals $T_0$ to $T_{15}$. SC is incremented, or cleared by a control signal at the end of an instruction.
• Control logic gates: combine $D_i$, $T_i$, $I$ and flags to produce control signals for registers, memory and the bus.

Operation

$T_0:\ AR \leftarrow PC$ $T_1:\ IR \leftarrow M[AR],\ PC \leftarrow PC+1$ $T_2:\ D_0,\dots,D_7 \leftarrow \text{decode } IR(12\text{-}14),\ AR \leftarrow IR(0\text{-}11),\ I \leftarrow IR(15)$

From $T_3$ the execute microoperations of the decoded instruction follow, and at the end $SC \leftarrow 0$.

An I/O processor (IOP), or channel, is a processor with its own instruction set that is dedicated to input-output. It communicates with the devices and with memory by DMA, so the CPU is relieved of I/O work.

Working

1. The CPU checks the IOP status and starts it by sending a command (device address, memory area, count).
2. The IOP fetches its I/O program from memory and carries out the transfers between the devices and memory.
3. When it has finished, the IOP interrupts the CPU, which examines the status.

The CPU executes other programs in the meantime, so CPU and I/O overlap. The IOP handles many devices at the same time.

Example: IBM mainframe channels (selector and multiplexer channels), and the Intel 8089 I/O processor used with the 8086, which controls a keyboard, printer or disk without the CPU's involvement.

Memory (cache) mapping is the method by which blocks of main memory are placed in cache lines. Let main memory be 64K words, cache 1K words and block size 16 words.

1. Direct mapping

A memory block can go to only one cache line: $i = j \bmod m$, where $m$ is the number of lines. The address is split into tag, line and word fields. With 64 lines and 16 words per block, the 16-bit address is tag 6 bits, line 6 bits, word 4 bits. It is simple and cheap, but two blocks that share the same line will keep replacing each other (thrashing).

2. Associative mapping

Any block can go to any line. The address is tag (12 bits) plus word (4 bits), and all tags are compared in parallel. It is flexible and has the highest hit ratio, but needs costly associative hardware.

3. Set-associative mapping

The cache is divided into sets of $k$ lines (k-way). A block maps to a fixed set but may use any line within it. With 2-way, 64 lines make 32 sets, so the address is tag 7 bits, set 5 bits, word 4 bits. It is a compromise between the two.

Example: For direct mapping, block 70 goes to line $70 \bmod 64 = 6$; for 2-way mapping it goes to set $70 \bmod 32 = 6$ in either line of the set.

Take multiplicand $M = 8 = 01000$ (so $-M = 11000$) and multiplier $Q = -7 = 11001$ (5-bit 2's complement). Registers: $AC = 00000$, $Q_{-1}=0$, sequence counter $= 5$.

The product is $AC\,Q = 1111001000_2$. Since the sign bit is 1, it is in 2's complement: its magnitude is $0000111000_2 = 56$, so the product is $-56$.

$-7 \times 8 = -56$

An arithmetic pipeline divides an arithmetic operation into sub-operations that are done in successive stages, each with its own hardware, so that several operations are in different stages at the same time. It is used for floating-point addition, subtraction and multiplication.

Example: floating-point addition of $X = A \times 2^a$ and $Y = B \times 2^b$

Stages (with registers between them):

1. Compare the exponents by subtraction.
2. Align the mantissas: shift the mantissa of the smaller exponent right by the difference.
3. Add or subtract the mantissas.
4. Normalise the result and adjust the exponent.

Numerical example: $X = 0.9504 \times 10^3$ and $Y = 0.8200 \times 10^2$. Exponent difference is 1; $Y$ becomes $0.0820 \times 10^3$; sum of mantissas is $1.0324$; normalised result is $0.10324 \times 10^4$.

While one pair is being normalised, the next pair is added and a third is aligned. For $n$ operations and $k$ stages the time is $(k + n - 1)$ clock cycles instead of $nk$, so the speed-up is $\frac{nk}{k+n-1}$, which approaches $k$ for large $n$.

Data transfer instructions copy data from one place to another (register, memory, I/O port or stack) without changing the data's value. The source is left unchanged, and the flags are usually not affected.

In general form, LOAD copies from memory to a register ($AC \leftarrow M[addr]$) and STORE copies from a register to memory ($M[addr] \leftarrow AC$).

Purpose of addressing modes

An addressing mode is the rule by which the operand address (effective address) is obtained from the address field of an instruction. They are used to:

• give programming flexibility, for pointers, arrays, loop counters and indexing;
• reduce the number of bits in the address field of the instruction;
• allow relocation of programs, and access to large memory with a short field;
• let data and addresses be handled easily in loops and subroutines.

Types of addressing modes

1. Implied: operand is implicit in the opcode (CMA, accumulator).
2. Immediate: the operand is in the instruction (MVI A, 05H).
3. Register: the operand is in a register (MOV A, B).
4. Register indirect: the register holds the address of the operand (MOV A, M).
5. Direct: the address field gives the operand address: $EA = A$ (LDA 2050H).
6. Indirect: the address field points to a location that holds the address: $EA = M[A]$.
7. Autoincrement/autodecrement: the register is changed after or before use.
8. Relative: $EA = PC + A$ (used in branches).
9. Indexed: $EA = XR + A$ (arrays).
10. Base register: $EA = BR + A$ (relocation).

Comparison

Difference

Divide 7 by 3 (non-restoring)

$Q = 0111$ (dividend), $M = 00011$, $A = 00000$, $n = 4$.

Quotient $= 0010_2 = 2$ and remainder $= 00001_2 = 1$, which is correct since $7 = 3\times 2 + 1$.