Microprocessor and Computer Architecture

Memory hierarchy organises storage into levels to balance speed, capacity and cost.

• The upper levels are fast, small and expensive; the lower levels are slow, large and cheap.
• Data moves between levels in blocks: cache to main memory by cache mapping, and main memory to disk by paging (virtual memory).
• It works because of locality of reference: temporal (recently used items are used again) and spatial (nearby addresses are used soon). So most accesses hit the fast levels, and the average access time approaches that of cache while the capacity and cost are that of disk.
• Effective access time $= h\,t_c + (1-h)\,t_m$, where $h$ is the hit ratio.

Memory hierarchy arranges storage in levels so that the system gets high speed, large capacity and low cost together. Going down the hierarchy, access time and cost per bit increase in speed, but capacity grows.

1. CPU registers: fastest, smallest (bytes), inside the processor.
2. Cache memory: small, very fast SRAM between CPU and main memory; holds frequently used data and instructions.
3. Main memory (RAM): medium speed DRAM that holds running programs and data.
4. Secondary storage: magnetic disks/SSDs, large and non-volatile, slower.
5. Tertiary/backup storage: magnetic tapes, optical disks, used for archives.

As we move from registers to tape: speed decreases, cost per bit decreases, capacity increases.

The hierarchy works because of the principle of locality (temporal and spatial): programs reuse recent data and access nearby addresses. Hence most accesses are satisfied by the fast upper levels. Main memory and cache interact via mapping (direct, associative, set-associative), and main memory and disk via virtual memory (paging).

Micro-program: a sequence of microinstructions stored in the control memory (a ROM) that together implement one machine instruction. Each microinstruction specifies the control signals (micro-operations) to be activated in one clock period and the address of the next microinstruction. A microprogrammed control unit executes the microprogram of each machine instruction to control the hardware.

Symbolic microprogram for FETCH

The fetch routine is stored at control memory address 64 (ORG 64):

         ORG 64
FETCH:   PCTAR            U   JMP   NEXT
         READ, INCPC      U   JMP   NEXT
         DRTAR            U   MAP

Each line has fields: label, micro-operations (F1, F2, F3), condition (CD), branch (BR) and address (AD).

• PCTAR: $AR \leftarrow PC$
• READ, INCPC: $DR \leftarrow M[AR]$ and $PC \leftarrow PC + 1$ together (they are in different microoperation fields)
• DRTAR: $AR \leftarrow DR(0\text{-}10)$
• U JMP NEXT: unconditional jump to the next microinstruction
• U MAP: unconditional mapping of the opcode (DR bits 11-14) to the starting address of the routine for that instruction: $CAR(2\text{-}5) \leftarrow DR(11\text{-}14)$, $CAR(0,1,6) \leftarrow 0$.

Difference

Isolated I/O

• Advantages: the whole memory space is available for memory; I/O instructions make programs easy to read; the address decoding for ports is simple (8-bit).
• Disadvantages: only IN/OUT with the accumulator can be used (no arithmetic or logic directly on port data); special instructions and control signals are needed.

Memory-mapped I/O

• Advantages: all memory instructions (MOV, ADD, ANA, etc.) can be applied to I/O data; any register may be used; no special I/O instructions or signals.
• Disadvantages: part of the memory address space is lost to I/O; full 16-bit address decoding is needed; programs are harder to read because I/O accesses look like memory accesses.

Pipelining is a technique that decomposes a process into sub-operations executed in dedicated segments that operate concurrently on different data, so that the overall throughput is higher.

Instruction pipeline: an instruction pipeline overlaps the phases of different instructions, so while one instruction is being executed the next is being decoded and the one after that fetched. Its speedup comes from the overlapping of the fetch, decode and execute phases.

Four-segment instruction pipeline

1. FI (Fetch instruction): fetch the instruction from memory.
2. DA (Decode and calculate effective address): decode the instruction and compute the effective address of the operand.
3. FO (Fetch operand): fetch the operand from memory.
4. EX (Execute): execute the instruction and store the result.

Space-time diagram (instructions 1 to 4)

Four instructions complete in 7 cycles instead of 16, and in steady state one instruction completes per cycle.

Difficulties: resource conflicts (memory access by FI and FO at once), data dependency (an instruction needs a result not yet produced), and branch difficulties (a branch makes the prefetched instructions useless). They are handled with separate instruction and data memory, operand forwarding, delayed load, delayed branch, branch prediction and a branch target buffer.

Difference

Isolated I/O

• Advantages: the whole memory space is available for memory; I/O instructions make programs easy to read; the address decoding for ports is simple (8-bit).
• Disadvantages: only IN/OUT with the accumulator can be used (no arithmetic or logic directly on port data); special instructions and control signals are needed.

Memory-mapped I/O

• Advantages: all memory instructions (MOV, ADD, ANA, etc.) can be applied to I/O data; any register may be used; no special I/O instructions or signals.
• Disadvantages: part of the memory address space is lost to I/O; full 16-bit address decoding is needed; programs are harder to read because I/O accesses look like memory accesses.

Pipelining is a technique that decomposes a task into sequential sub-operations (segments), each executed in a dedicated stage, so that several tasks overlap in execution. Like an assembly line, a new task enters the pipeline every clock cycle, which increases throughput.

Four-segment instruction pipeline:

1. FI (Fetch Instruction): fetch the instruction from memory.
2. DA (Decode and calculate Address): decode the instruction and compute the effective address.
3. FO (Fetch Operand): read the operand from memory.
4. EX (Execute): execute the instruction and store the result.

Timing for instructions I1 to I4:

For $n$ instructions and $k$ segments, the pipeline needs $k + (n-1)$ cycles, versus $nk$ without pipelining. Speedup is $\dfrac{nk}{k+n-1}$, approaching $k$ for large $n$. Branches, data dependencies and resource conflicts can stall the pipeline.

Micro-operations are elementary operations performed on data stored in registers.

Arithmetic micro-operations

They are implemented with a binary adder and a multiplexer-based arithmetic circuit that selects $B$, $\bar{B}$, 0 or 1s and a carry-in.

Binary (logic) micro-operations work bit-wise on register contents:

• AND ($\wedge$): $R1 \leftarrow R1 \wedge R2$ (masking)
• OR ($\vee$): $R1 \leftarrow R1 \vee R2$ (selective set)
• XOR ($\oplus$): selective complement
• NOT: $R1 \leftarrow \overline{R1}$

For $A = 1010$, $B = 0110$: AND $= 0010$, OR $= 1110$, XOR $= 1100$, NOT $A = 0101$.

Arithmetic micro-operations perform arithmetic on numbers stored in registers.

They are built from a binary adder (full adders in cascade) and a binary adder-subtractor: with mode input $M$, each $B_i$ is XORed with $M$ and $M$ is the input carry; $M = 0$ gives $A + B$ and $M = 1$ gives $A - B$. A binary incrementer uses half adders. The arithmetic circuit uses a 4-to-1 multiplexer to choose $B$, $\bar{B}$, 0 or all 1s with carry-in 0 or 1, producing add, subtract, increment, decrement and transfer from one circuit.

SAP-1 (Simple-As-Possible-1) is a very small 8-bit teaching computer with a 4-bit address (16 bytes of memory), a single 8-bit bus (the W bus) and only five instructions.

Components

• Program Counter (PC): 4-bit counter holding the address of the next instruction. It is reset to 0000 and incremented after each fetch.
• Memory Address Register (MAR): 4-bit register that latches the address sent to RAM.
• RAM: 16 x 8 memory holding both program and data.
• Instruction Register (IR): 8-bit register. The upper nibble is the opcode (sent to the controller); the lower nibble is the operand address (sent back to the bus).
• Controller-Sequencer: a ring counter (T1-T6) plus decoding logic that generates the 12-bit control word (Ep, Cp, Lm, CE, Li, Ei, La, Ea, Su, Eu, Lb, Lo) and the CLR/HLT signals.
• Accumulator (A): 8-bit register holding intermediate results; feeds the adder/subtractor.
• Adder/Subtractor: 8-bit ALU computing A+B or A-B (Su selects subtraction); its output is placed on the bus by Eu.
• B register: 8-bit register holding the second operand.
• Output register and binary display: hold and show the result of the OUT instruction.
• W bus and clock: a common 8-bit bus connects all units; the clock synchronizes all registers.

Block diagram (data path)

        +---------------- W bus (8-bit) ----------------+
        |     |       |        |       |       |         |
       PC -> MAR -> RAM(16x8)  IR     A  <->  Adder/Sub  B   Output -> Display
                                |      ^
                                +--> Controller-Sequencer --> control word
                                          ^ clock, clear

Instruction set: LDA addr, ADD addr, SUB addr, OUT, HLT.

SAP-1 vs SAP-2

SAP-2 therefore resembles a simplified 8080/8085, while SAP-1 only shows the basic fetch-execute idea.

Types of instructions in the 8085 (about 74 instructions, grouped by function):

1. Data transfer: copy data between registers, memory and I/O without changing flags, e.g. MOV, MVI, LXI, LDA, STA, LDAX, XCHG, IN, OUT.
2. Arithmetic: ADD, ADC, SUB, SBB, INR, DCR, INX, DCX, DAD, DAA.
3. Logical: ANA, ORA, XRA, CMP, CMA, RLC, RRC, RAL, RAR, and the immediate forms.
4. Branching: unconditional (JMP, CALL, RET) and conditional (JC, JNC, JZ, JNZ, JP, JM, JPE, JPO, CC, RZ and so on).
5. Machine control and stack: PUSH, POP, XTHL, SPHL, EI, DI, RIM, SIM, NOP, HLT.

Program: smallest element of an array

Assume the array length is stored at 2050H, the elements (unsigned 8-bit) start at 2051H, and the result goes to 2100H.

        LXI  H, 2050H    ; HL points to the length
        MOV  C, M        ; C = number of elements
        INX  H           ; HL -> first element
        MOV  A, M        ; assume first element is the smallest
        DCR  C
        JZ   STORE       ; only one element
LOOP:   INX  H           ; next element
        CMP  M           ; compare A with M (A - M)
        JC   SKIP        ; if A < M, A is still smallest
        MOV  A, M        ; else new smallest
SKIP:   DCR  C
        JNZ  LOOP
STORE:  STA  2100H       ; store smallest
        HLT

Instruction format of the basic computer

The basic computer has 16-bit instructions and three formats, distinguished by the opcode bits and the mode bit I.

1. Memory-reference instruction: bit 15 is the mode bit I (0 = direct, 1 = indirect), bits 14-12 are the opcode (000 to 110) and bits 11-0 are the 12-bit address.

 15  14 12 11            0
| I | opcode |  address  |

2. Register-reference instruction: bits 15-12 are 0111; each of bits 11-0 selects one register operation (CLA, CLE, CMA, CIR, CIL, INC, SPA, SNA, SZA, SZE, HLT).
3. Input-output instruction: bits 15-12 are 1111; bits 11-0 select an I/O operation (INP, OUT, SKI, SKO, ION, IOF).

RISC vs CISC

Arithmetic micro-operations perform arithmetic on data held in registers. The basic ones are:

Example: let R1 = 0110 (6) and R2 = 0011 (3).

• Add: $R3 = 0110 + 0011 = 1001$ (9).
• Subtract: $R3 = 0110 + 1100 + 1 = 1\,0011$; discarding the carry gives 0011 (3).
• Increment R1: 0110 becomes 0111.

Addition and subtraction are done in hardware by a binary adder built from full adders. A binary adder-subtractor adds a mode input M that XORs each bit of B, with M also fed as the input carry. M = 0 gives $A+B$ and M = 1 gives $A + \overline{B} + 1 = A - B$. Increment and decrement are done by an up/down counter or an adder with a constant input.

In signed-magnitude representation a number is a sign bit plus a magnitude. Addition and subtraction depend on the signs of the operands and the operation requested.

Algorithm (A = augend/minuend, B = addend/subtrahend, As and Bs their signs)

1. If the signs call for adding: $A \leftarrow A + B$, the sign of the result is As, and the carry E is the overflow (AVF = E).
2. If the signs call for subtracting: $A \leftarrow A + \overline{B} + 1$ (E is the end carry).
   • If E = 1 then $A \ge B$; the result is correct and the sign is As.
   • If E = 0 then $A < B$; the result is negative of the true value, so take $A \leftarrow \overline{A} + 1$ and $As \leftarrow \overline{As}$.
3. If the final magnitude is zero, set $As \leftarrow 0$ so that zero is positive.

Hardware

 Bs --XOR-- M     As         B register          A register (accumulator)
       |            |         | (via complementer, controlled by M)   |
       +-> sign logic         v                                       |
                         Parallel adder  ---> A register  <-----------+
                           |  Cin = M (E)
                         E flip-flop (end carry) -> AVF (overflow)

• Register A (with sign flip-flop As) and register B (with Bs).
• A parallel adder fed from A and from B through a complementer (XOR gates controlled by the mode M).
• E flip-flop for the carry, AVF for overflow.
• Control logic compares signs ($As \oplus Bs \oplus M$) and chooses add or subtract, and the complement circuit on A in the case E = 0.

The memory hierarchy arranges storage in levels so that the system gets the speed of the fastest memory and the capacity and cost per bit of the cheapest. Going down the hierarchy, access time increases while cost per bit falls and capacity grows.

• Main memory communicates directly with the CPU; auxiliary memory supplies programs and data that are not currently needed.
• Cache holds the most active portions of programs and data and cuts the average access time.
• The hierarchy works because of the principle of locality (temporal and spatial) of references: most accesses hit the faster levels.
• Average access time: $t_{avg} = h\,t_c + (1-h)\,t_m$ where $h$ is the hit ratio.
• Virtual memory manages the movement between main and secondary memory.

A microprocessor-based system is built around a microprocessor (the CPU on one chip) connected to memory and I/O devices by buses.

Main blocks

1. Microprocessor (CPU): contains the ALU, registers and control unit. It fetches, decodes and executes instructions and supervises the whole system.
2. Memory: ROM stores the permanent program (boot or monitor program) and RAM stores user programs and data.
3. Input/output: input devices (keyboard, switches) and output devices (display, printer) connected through interface chips (ports).
4. System bus:
   • Address bus is unidirectional and carries the address from the CPU; $n$ lines address $2^n$ locations (16 lines give 64 KB).
   • Data bus is bidirectional and carries data (8 bits for the 8085).
   • Control bus carries signals such as RD, WR, IO/M, ALE, READY and INTR.

          +-----------+     Address bus      +-----+  +-----+  +------------+
          |   CPU     |=====================>| ROM |  | RAM |  | I/O ports  |
          | (ALU, Reg,|<====================>|     |  |     |  |            |
          |  Control) |     Data bus         +-----+  +-----+  +------------+
          |           |-------------------- Control bus ---------------------
          +-----------+

The CPU puts an address on the address bus, issues a read or write command on the control bus and moves data over the data bus.

A flag is a 1-bit flip-flop that records a condition resulting from the execution of an arithmetic or logical instruction. Flags are used by conditional jump, call and return instructions to make decisions.

The 8085 has five flags in an 8-bit flag register (the other three bits are unused):

 D7  D6  D5  D4  D3  D2  D1  D0
  S   Z   X  AC   X   P   X  CY

1. Sign (S): set if bit D7 of the result is 1 (result negative in 2's complement).
2. Zero (Z): set if the result is zero.
3. Auxiliary Carry (AC): set if there is a carry out of bit D3 into D4; used by DAA for BCD arithmetic.
4. Parity (P): set if the result has an even number of 1s (even parity).
5. Carry (CY): set if an arithmetic operation produces a carry out of D7 (or a borrow in subtraction); also affected by rotate and compare instructions.

An arithmetic pipeline divides an arithmetic operation into sub-operations that are executed in separate segments, so that several operations are in progress at the same time. It is used for floating-point addition and subtraction, multiplication and fixed-point operations on vectors.

Floating-point addition/subtraction pipeline (four segments, with registers between them):

1. Compare the exponents.
2. Align the mantissas (shift the one with the smaller exponent right).
3. Add or subtract the mantissas.
4. Normalize the result (adjust the exponent).

 X, Y --> [Compare exponents] --> [Align mantissas] --> [Add/Sub mantissas] --> [Normalize] --> result
             R                         R                      R                    R

Example: $X = 0.9504 \times 10^3$, $Y = 0.8200 \times 10^2$.

• Segment 1: exponents are 3 and 2, difference 1.
• Segment 2: $Y = 0.0820 \times 10^3$.
• Segment 3: $0.9504 + 0.0820 = 1.0324$, so the sum is $1.0324 \times 10^3$.
• Segment 4: normalize to $0.1032 \times 10^4$.

While one pair of numbers is being added in segment 3, the next pair can already be in segment 2 and so on, so after the pipeline is full one result is produced every clock cycle.

Function of an I/O interface: it connects peripherals to the CPU and resolves the differences between them. Its functions are:

• Providing a path for data transfer between CPU/memory and the device, and converting data formats (serial to parallel and vice versa).
• Matching the speed of the CPU to the slower device through buffering and status/handshaking signals.
• Decoding the device address and the commands (read, write, status, control) sent by the CPU.
• Level conversion (electrical signals), synchronization and interrupt generation.

Isolated I/O vs memory-mapped I/O

(a) Control ROM

The control ROM (control memory) is the read-only memory of a microprogrammed control unit. It stores the microprograms: each word is a microinstruction with micro-operation fields and next-address information. It is addressed by the control address register (CAR), and its output goes to the control data register (pipeline register) and then to the data path. Because the content is fixed, changing the instruction set needs only a change of the ROM contents, not of the hardware.

(b) Magnetic Disk

A magnetic disk is a secondary storage device made of one or more rotating platters coated with magnetic material. Data is stored in concentric tracks divided into sectors, and read/written by heads that move over the surface. Access time = seek time + rotational latency + transfer time. It is non-volatile, has large capacity and low cost per bit, and gives random (direct) access, but is much slower than main memory.

(c) Flynn's Classification

Flynn classifies computers by the number of instruction streams and data streams:

• SISD: single instruction, single data (a conventional uniprocessor).
• SIMD: single instruction, multiple data (array and vector processors).
• MISD: multiple instruction, single data (rarely built; some pipelines or fault-tolerant systems).
• MIMD: multiple instruction, multiple data (multiprocessors and multicomputers).

The 8085 is an 8-bit, general-purpose microprocessor from Intel, fabricated in NMOS on a single 40-pin chip. It works on a single +5 V supply, has a 16-bit address bus (64 KB of memory), multiplexed address/data lines AD0-AD7, an on-chip clock generator (3 MHz typical), five hardware interrupts and serial I/O lines (SID, SOD).

Functional units

1. Arithmetic Logic Unit (ALU): performs arithmetic (add, subtract, increment, decrement) and logic (AND, OR, XOR, compare, rotate) operations; the accumulator and temporary register are its operands.
2. Register array:
   • General purpose 8-bit registers B, C, D, E, H, L (can be paired BC, DE, HL) and the accumulator A.
   • 16-bit Program Counter (PC) and Stack Pointer (SP).
   • Temporary registers W and Z (not user accessible).
3. Flag register: five flags S, Z, AC, P, CY.
4. Instruction register and decoder: the opcode is fetched into the instruction register and decoded.
5. Timing and control unit: generates timing and control signals (RD, WR, ALE, IO/M, S0, S1) for the CPU and the other devices.
6. Interrupt control: handles TRAP, RST 7.5, 6.5, 5.5 and INTR, with the interrupt mask.
7. Serial I/O control: serial input and output through SID and SOD.
8. Address buffer and address/data buffer: drive the high-order address lines A8-A15 and the multiplexed lines AD0-AD7.

In a hardwired control unit the control signals are generated by fixed logic circuits (gates, decoders, counters). It is fast but difficult to modify.

Block diagram (Mano's basic computer)

 Instruction register IR (15-0)
   bits 14-12 --> [3x8 decoder] --> D0 ... D7
   bit 15 ---------> I
   bits 11-0 ------> (register/I-O decode B0-B11)
                                   \
 Sequence Counter SC (4-bit) --> [4x16 decoder] --> T0 ... T15
        ^ INC / CLR                       \
                                           v
 Flip-flops (E, FGI, FGO, IEN, R ...) --> [ Control logic gates ] --> control signals
 AC = 0, DR = 0, AC(15)  ---------------^        (LD, INR, CLR of registers,
                                                   bus selects S2 S1 S0, memory read/write,
                                                   ALU controls)

Functional units

• Instruction register (IR): holds the fetched instruction; its opcode bits (14-12) go to the decoder and the mode bit (15) to the control logic.
• 3 x 8 decoder: decodes the opcode into the eight outputs D0 to D7, one per memory-reference or register/I-O group instruction.
• Sequence counter (SC) and 4 x 16 decoder: SC is a 4-bit counter that is incremented every clock pulse; the decoder gives timing signals T0 to T15. SC is cleared (CLR) at the end of an instruction so that the next instruction starts again at T0.
• Control logic gates: combinational circuits whose inputs are D0-D7, T0-T15, I, the flip-flops and register status (AC, DR, E). Its outputs are the control functions: register loads and increments, bus selection, memory read/write and ALU operations. For example, $R'T_0$ gives $AR \leftarrow PC$.
• Status flip-flops and register conditions: supply the conditions (e.g. AC = 0) for conditional operations.

Restoring division algorithm (dividend in AQ, divisor in B, $n$ = number of quotient bits; A initially holds the high half of the dividend)

1. Initialize: A = high part of dividend, Q = low part, B = divisor, count = $n$.
2. Shift AQ left by one bit.
3. Subtract: $A \leftarrow A - B$.
4. If A is non-negative (no borrow), set $q_0 = 1$. If A is negative, set $q_0 = 0$ and restore $A \leftarrow A + B$.
5. Decrement the count; if not zero, go to step 2.
6. At the end Q is the quotient and A the remainder.

Division: 448 / 17

Dividend 0111000000 gives A = 01110 (14), Q = 00000; B = 10001 (17); $n = 5$. A 6-bit subtraction is used to detect the sign.

Result: quotient Q = 11010 = 26, remainder A = 00110 = 6.

Check: $17 \times 26 + 6 = 442 + 6 = 448$.

SAP-1 is the simplest model that shows the fetch-execute cycle; SAP-2 adds the features of a real microprocessor (jumps, subroutines, I/O ports, flags).

Instruction cycle: the time taken by the processor to fetch an instruction from memory, decode it and execute it. It is made of one or more machine cycles (opcode fetch, memory read/write, I/O read/write), and each machine cycle is made of 3 to 6 T-states (clock periods).

MVI A, 08H is a 2-byte instruction with two machine cycles:

• Opcode fetch: 4 T-states.
• Memory read (to get the operand 08H): 3 T-states.

Total = 7 T-states.

Clock period:

$T = \frac{1}{5\ \text{MHz}} = 0.2\ \mu s$

Execution time:

$7 \times 0.2\ \mu s = 1.4\ \mu s$

A microoperation is an elementary operation performed on data stored in registers during one clock pulse. Instructions are executed as sequences of microoperations.

• $AR \leftarrow PC$: transfers the contents of the program counter (address of the next instruction) into the address register, so the instruction can be read from memory.
• $DR \leftarrow M[AR],\ PC \leftarrow PC + 1$: reads the memory word whose address is in AR into the data register (the instruction), and in the same clock pulse increments PC to point to the next instruction.
• $AR \leftarrow DR(0\text{-}10)$: loads AR with the 11-bit address field (bits 0 to 10) of the instruction in DR, giving the operand address.
• $CAR(2\text{-}5) \leftarrow DR(11\text{-}14)$: places the 4-bit opcode (bits 11 to 14 of DR) into bits 2 to 5 of the control address register. This is the mapping of the opcode to the starting address (0 xxxx 00) of the microprogram routine for that instruction in the control memory.

Instruction format: an instruction word of the basic computer has a mode (indirect) bit I, an operation code field and an address field. The mode bit tells whether the address is direct or indirect; the opcode specifies the operation; the address specifies the operand location.

Calculation

Memory = 256K words = $2^{18}$ words, so the address field needs 18 bits. The instruction is 32 bits long and includes 1 mode bit, so the remaining opcode field is

$32 - 1 - 18 = 13\ \text{bits}$

(this allows up to $2^{13} = 8192$ operations).

 31   30        18 17              0
| I |  Opcode   |    Address      |
  1     13 bits       18 bits

Mode bit I = 1 bit, opcode = 13 bits, address = 18 bits, total 32 bits.

Division by repeated subtraction: subtract the divisor from the dividend as long as the dividend is greater than or equal to the divisor, counting the subtractions. The count is the quotient and what remains is the remainder.

Assume the dividend is at 2000H, the divisor at 2001H, the quotient is stored at 2002H and the remainder at 2003H.

        LDA  2001H       ; divisor
        MOV  B, A        ; B = divisor
        ORA  A
        JZ   END         ; divisor 0: stop (no division)
        LDA  2000H       ; A = dividend
        MVI  C, 00H      ; C = quotient = 0
LOOP:   CMP  B           ; compare A with B
        JC   DONE        ; A < B: finished
        SUB  B           ; A = A - B
        INR  C           ; quotient + 1
        JMP  LOOP
DONE:   STA  2003H       ; remainder
        MOV  A, C
        STA  2002H       ; quotient
END:    HLT

Example: 17 / 5: 17, 12, 7, 2 gives quotient 3 (three subtractions) and remainder 2.

A mapping table converts one kind of address or code into another.

1. In a microprogrammed control unit: the mapping converts the opcode of the machine instruction into the starting address of its microprogram routine in the control memory. A mapping ROM (table) is addressed by the opcode and gives the control memory address. In the basic computer the 4-bit opcode is placed in bits 2 to 5 of the CAR with zeros elsewhere ($0\,xxxx\,00$), so each routine begins at a spaced address (4 microinstructions per routine). This lets different instructions have routines in different places and allows the control address register to be loaded in a single step (the MAP field of the microinstruction).

2. In virtual memory: a memory (page) table maps the virtual address generated by the program to the physical address in main memory. The page number indexes the table, which gives the block (frame) number, with a presence bit showing whether the page is in memory; the line number (offset) is copied unchanged. Because of this table programs can use addresses larger than the physical memory, and a page can be placed in any frame.

Pipelining is a technique in which a task is divided into sub-tasks, each carried out in its own segment, and the segments work concurrently on different tasks. The output of each segment is passed to the next segment, with registers between segments, like an assembly line.

Clock:      1    2    3    4    5    6
Task 1:    S1   S2   S3   S4
Task 2:         S1   S2   S3   S4
Task 3:              S1   S2   S3   S4

Role in computing

• Increases throughput: after the pipe is filled, one task completes each clock cycle, although each task still takes $k$ cycles.
• Speedup for $n$ tasks in a $k$-segment pipeline: $S = \frac{n\,k\,t_n}{(k+n-1)\,t_p} \to k \ \text{when}\ n \to \infty$
• It uses the hardware efficiently and allows a faster effective clock, without needing extra copies of the hardware.
• It is applied as an instruction pipeline (fetch, decode, operand fetch, execute) and as an arithmetic pipeline (floating-point operations), and in vector processing.
• Limitations: data hazards, control hazards (branches) and structural hazards cause stalls.

(a) Multiplexed Address

In the 8085, the lower 8 address lines and the 8 data lines share the same pins, AD0-AD7. During the first clock cycle (T1) of a machine cycle these pins carry the low-order address A0-A7, and in later cycles they carry data. The ALE (Address Latch Enable) signal goes high in T1 to tell an external latch (such as the 74LS373) to capture and hold the low-order address, while the high-order address A8-A15 is always on separate pins. Multiplexing saves pins on the 40-pin chip but needs the external latch.

(b) Memory Hierarchy

The memory hierarchy arranges storage in levels (registers, cache, main memory, magnetic disk, tape or optical) so that speed decreases and capacity increases while cost per bit decreases as we move away from the CPU. Cache holds the active parts of programs to reduce average access time, main memory holds running programs, and auxiliary memory holds everything else. It works because of the locality of reference. The average access time is $t_{avg} = h\,t_c + (1-h)\,t_m$ with hit ratio $h$.

Addressing mode: the way in which the operand of an instruction is specified, i.e. how the effective address of the data is determined.

Addressing modes of the 8085

1. Immediate: the operand is part of the instruction. Example: MVI B, 32H (B gets 32H); LXI H, 2050H.
2. Register: the operand is in a register. Example: MOV A, B; ADD C.
3. Direct: the instruction gives the 16-bit memory address of the operand. Example: LDA 2050H; STA 3000H.
4. Register indirect: a register pair holds the address of the operand. Example: MOV A, M (address in HL); LDAX B.
5. Implied (implicit): the operand is implied by the opcode. Example: CMA (complement A); RAL; STC.

General addressing modes (for a general computer): indirect (address field points to the word that holds the operand's address), relative (EA = PC + address), indexed (EA = index register + address), base-register (EA = base register + address) and auto-increment/decrement (register indirect with the register updated).

STA 4000H

• It is a 3-byte instruction: opcode 32H, followed by the low byte 00H and the high byte 40H of the address.
• Function: stores the contents of the accumulator at memory location 4000H, i.e. $M[4000H] \leftarrow A$. No flags are affected.
• Addressing mode: direct addressing, because the 16-bit address of the destination operand is given directly in the instruction.

The control unit of a microprocessor is the part that directs the operation of the processor: it fetches instructions, decodes them and generates the timing and control signals that make the ALU, registers, memory and I/O carry out the instruction.

In a hardwired control unit these signals are generated by fixed logic circuits (gates, decoders, counters).

Block diagram

 IR bits 14-12 --> [3x8 decoder] --> D0..D7 ----+
 IR bit 15 (I) -------------------------------->|
                                                v
 Sequence counter SC --> [4x16 decoder] --> T0..T15 --> [ Control logic gates ] --> control outputs
      ^  (INC / CLR)                                      ^
      |                                                   |
      +------- clear at end of instruction     Flip-flops / register conditions (E, FGI, AC=0 ...)

Functions of the units

• Instruction register: holds the current instruction; its opcode bits are decoded and the I bit is passed to the control logic.
• 3 x 8 opcode decoder: produces one of the lines D0-D7 for the instruction type.
• Sequence counter and 4 x 16 timing decoder: produce the timing signals T0 to T15 which sequence the microoperations; the counter is cleared at the end of each instruction.
• Control logic gates: combine D, T, I and status conditions to produce the control signals (register loads, increments, clears, bus select, memory read/write, ALU function).
• Status flip-flops: supply condition information for conditional operations.

It is fast, but changes need redesign of the hardware, unlike microprogrammed control.

A microprocessor is a programmable, clock-driven, register-based electronic device that is fabricated on a single semiconductor chip (VLSI) and contains the ALU, registers and control unit of a CPU. It reads binary instructions from memory, processes data according to them and gives the results.

Three general categories of its functions

1. Microprocessor-initiated (communication) operations: the MPU communicates with memory and I/O devices: memory read, memory write, I/O read and I/O write. It places the address on the address bus, sends control signals and transfers data over the data bus.
2. Internal operations: the MPU performs the operations inside itself, such as storing data in registers, performing arithmetic and logic operations in the ALU, testing the data for conditions, and sequencing the program through the PC. Decoding and executing instructions is part of this.
3. Peripheral (externally) initiated operations: operations started by external signals: reset, interrupt requests (INTR, TRAP, RST), ready/wait and hold (DMA). The MPU responds to these by suspending or changing normal execution.

        LDA  2030H       ; A = first number
        MOV  B, A        ; B = first number
        LDA  2040H       ; A = second number
        ADD  B           ; A = A + B
        STA  2050H       ; store the sum at 2050H
        HLT

Explanation: the first number is loaded into the accumulator and moved to B, the second number is loaded into A, ADD B forms the sum in the accumulator (carry, if any, is in the CY flag), and STA stores the sum at 2050H.

Design idea: $A - 1$ is the same as $A + (-1)$, and in 2's complement $-1 = 1111$. So a decrementer is a 4-bit binary adder (four full adders) with one input A and the other input fixed to 1111.

$A - 1 = A + 1111$

Circuit

        A3    A2    A1    A0
        |     |     |     |
      +-FA3--+-FA2--+-FA1--+-FA0-+
 B3=1 -|     B2=1 - | B1=1 -|  B0=1 -|
        |     |     |     |
       S3    S2    S1    S0      (Cin of FA0 = 0)

• Each full adder $FAi$ has inputs $A_i$, $B_i = 1$ and the carry from the previous stage; the carry-in of FA0 is 0.
• The carries ripple from FA0 to FA3 and the final carry-out is ignored.
• Outputs $S_3S_2S_1S_0$ are $A-1$.

Example: A = 0101 (5): $0101 + 1111 = 1\,0100$; ignoring the carry gives 0100 (4). For A = 0000: $0000 + 1111 = 1111$ (-1 in 2's complement).

With $B_i = 1$ the equations simplify to $S_0 = \overline{A_0}$, $C_1 = A_0$, $S_1 = A_1 \oplus \overline{A_0}$ and so on, but the adder form with four full adders meets the requirement.

Selective set is a logic micro-operation that sets to 1 those bits of register A which are 1 in register B (the mask); the other bits of A are unchanged. It is the bitwise OR operation:

$A \leftarrow A \lor B$

Example

• A (before) = 1010
• B (mask) = 1100
• A (after) = 1110

Bits of A in positions where B has a 1 are forced to 1, other bits stay as they were.

Hardware circuit

One 2-input OR gate per bit:

 A3 ---\                A2 ---\               A1 ---\              A0 ---\
        OR --> A3'             OR --> A2'            OR --> A1'           OR --> A0'
 B3 ---/                B2 ---/               B1 ---/              B0 ---/
        (outputs are loaded back into register A on the clock pulse)

For an $n$-bit register, $n$ OR gates are used, with inputs $A_i$ and $B_i$ and output $A_i'$ that is loaded into register A.

Given: AQ = 10100011, B = 1011, so A = 1010 (10) and Q = 0011 (3); the dividend is 163 and the divisor is 11. Four quotient bits, so 4 steps. A is kept with a 5th bit to detect negative results.

Result: quotient Q = 1110 = 14 and remainder A = 1001 = 9.

Check: $11 \times 14 + 9 = 154 + 9 = 163$.

For 194 / 10 (A = 00000000, Q = 11000010, B = 00001010) the same procedure with 8 steps gives quotient 00010011 = 19 and remainder 00000100 = 4, since $10 \times 19 + 4 = 194$.

Virtual memory is a technique that lets programs use a much larger address space than the available main memory. The programmer writes programs using virtual (logical) addresses, while the system keeps only the needed parts in main memory and the rest on the disk. The hardware and the operating system automatically translate virtual addresses to physical addresses.

Working

• The virtual address space is divided into fixed-size pages, and main memory into blocks (frames) of the same size.
• A page table maps each page to a frame, with a presence bit.
• If the referenced page is in memory, its physical address is formed from the frame number and the offset.
• If it is not, a page fault occurs; the OS brings the page from disk, replacing another page if memory is full (FIFO, LRU, optimal).

Advantages: programs larger than main memory can run; memory is used efficiently, multiprogramming is easier, and the programmer need not manage overlays.

Address mapping may also be done using segmentation or paged segmentation. A TLB (associative memory) caches recent translations to reduce the access time.

In a microprogrammed control computer, the control signals are not generated by fixed logic gates; instead they are stored as microinstructions in a control memory. The control unit reads these microinstructions in sequence, and each one specifies the microoperations to be performed in a clock period. Changing the instruction set only requires changing the stored microprogram.

Main memory: stores the machine-language programs and data (instructions and operands), is read/write (RAM) and is addressed by the address register AR. The CPU fetches each machine instruction from main memory and then executes it by running the corresponding microprogram.

Control memory: a read-only memory (ROM) inside the control unit that stores the microprograms. Each machine instruction has a routine of microinstructions in it (including the common fetch routine). It is addressed by the control address register (CAR), whose value is set by incrementing, branching or mapping from the opcode. The word read is held in the control data register (pipeline register) and its fields are decoded to produce the control signals. Since the microprogram is permanent, a ROM is used, and it is not part of the user-accessible address space.

 Opcode --> [Mapping logic] --> CAR --> [Control memory ROM] --> Control data register --> control signals
                              ^   |  (increment / branch / subroutine)
                              +---+

(a) Performance of a pipelined processor

For a $k$-segment pipeline with clock period $t_p$ executing $n$ tasks, the time is $(k + n - 1)\,t_p$, because the first task needs $k$ cycles and each later task finishes one cycle after the previous. A non-pipelined unit needs $n\,t_n$, with $t_n = k\,t_p$ if the same work is done. The speedup is

$S = \frac{n\,t_n}{(k+n-1)\,t_p} = \frac{n\,k}{k+n-1}$

and it approaches $k$ as $n \to \infty$. Example: $k = 4$, $n = 100$ gives $S = 400/103 \approx 3.88$. The ideal throughput of one result per cycle is reduced by hazards (data, control, structural), unequal segment delays and register overhead, which cause stalls.

(b) Page Replacement

When a page fault occurs and main memory has no free frame, the OS must choose a page to replace. Algorithms:

• FIFO: replace the oldest page in memory; simple but may remove heavily used pages and can show Belady's anomaly.
• LRU (least recently used): replace the page unused for the longest time; good performance, costlier to implement.
• Optimal: replace the page that will not be used for the longest time in future; the lowest fault rate, but not implementable, used as a benchmark.

A microprocessor is a programmable, multipurpose, clock-driven, register-based integrated circuit on a single chip which reads binary instructions from memory, accepts binary data as input, processes them as per the instructions, and gives the results as output. It contains the ALU, registers and control unit of a CPU.

Block diagram of the 8085

                +--------------------- Internal data bus (8-bit) ---------------------+
                |        |            |            |             |                    |
          +---------+ +------+  +-----------+  +--------+  +------------+   +----------------+
 Accumulator| Temp reg| | Flag |  | Instruction|  | Instr. |  | Reg array  |   | Interrupt ctrl |
    (A)  -> |  ALU    |<-| reg  |  |  register  |->|decoder |  | B C D E H L|   | TRAP RST7.5-5.5|
          +---------+ +------+  +-----------+  | W Z SP PC |   | INTR INTA      |
                                           |      +------------+   +----------------+
                                    Timing and control        Address buffer   Address/data buffer
                                    (CLK gen, ALE, RD, WR,       A15-A8           AD7-AD0
                                     IO/M, S0, S1, READY...)   Serial I/O control (SID, SOD)

Components

• ALU: performs arithmetic and logic operations on the accumulator and a temporary register.
• Accumulator and general registers: A, B, C, D, E, H, L (8-bit; BC, DE, HL as 16-bit pairs); W and Z are temporary.
• Flag register: S, Z, AC, P, CY.
• Program Counter (16-bit): address of the next instruction; Stack Pointer (16-bit): top of stack.
• Instruction register and decoder: hold and decode the opcode.
• Timing and control unit: generates timing and control signals (ALE, RD, WR, IO/M, S0, S1) and has the clock generator.
• Interrupt control: TRAP, RST 7.5, RST 6.5, RST 5.5, INTR and INTA.
• Serial I/O control: SID and SOD lines.
• Address buffer and address/data buffer: A8-A15 are output only; AD0-AD7 are multiplexed address/data lines.

Instructions of SAP-1

Each instruction is one byte: upper nibble opcode, lower nibble address. Each instruction takes 6 T-states (T1-T6): 3 for fetch and 3 for execution.

Fetch cycle (common to all instructions)

• T1 (address state): $MAR \leftarrow PC$. Control signals Ep (PC on bus) and Lm (load MAR).
• T2 (increment state): $PC \leftarrow PC + 1$. Signal Cp.
• T3 (memory state): $IR \leftarrow M[MAR]$. Signals CE (RAM output enable) and Li (load IR).

Execution of LDA addr

• T4: $MAR \leftarrow IR(\text{operand})$. Signals Ei (IR address on bus) and Lm.
• T5: $A \leftarrow M[MAR]$. Signals CE and La (load accumulator).
• T6: no operation (idle).

Timing diagram

 Clock   _|-|_|-|_|-|_|-|_|-|_|-|_
 Ring    T1   T2   T3   T4   T5   T6
 Active  Ep   Cp   CE   Ei   CE   -
 signals Lm        Li   Lm   La
 Action  MAR<-PC  PC+1  IR<-RAM  MAR<-addr  A<-RAM  nop

Control word during T1 is 5E3H, T2 is 3E3H, T3 is BE3H, T4 is 1A3H and T5 is 2C3H (T6 = 3E3H).

Micro-instruction: a control word stored in the control memory that specifies one or more microoperations to be executed in one clock period, along with the condition and the address of the next microinstruction. Its fields are the microoperation fields (F1, F2, F3), the condition field CD, the branch field BR and the address field AD.

Micro-program: a sequence of microinstructions, stored in the control memory, that implements one machine instruction (or a routine such as FETCH). The set of all microprograms constitutes the control program of a microprogrammed computer.

Symbolic microprogram for the FETCH routine

The routine occupies control memory addresses 64 to 66 (ORG 64):

         ORG 64
FETCH:   PCTAR           U   JMP   NEXT
         READ, INCPC     U   JMP   NEXT
         DRTAR           U   MAP

Here U means unconditional (no condition test), JMP NEXT means go to CAR + 1, and MAP loads CAR with the mapped address.

Dividend at 8050H, divisor at 8051H; quotient to 8052H and remainder to 8053H. The division uses repeated subtraction.

        LXI  H, 8050H    ; HL -> dividend
        MOV  A, M        ; A = dividend
        INX  H
        MOV  B, M        ; B = divisor
        MOV  D, A        ; D = dividend (save)
        MOV  A, B
        ORA  A
        JZ   END         ; divisor = 0: stop
        MOV  A, D        ; A = dividend
        MVI  C, 00H      ; C = quotient
LOOP:   CMP  B           ; A - B
        JC   DONE        ; A < B: done
        SUB  B           ; A = A - B
        INR  C           ; quotient + 1
        JMP  LOOP
DONE:   STA  8053H       ; remainder
        MOV  A, C
        STA  8052H       ; quotient
END:    HLT

Example: dividend 19H (25) and divisor 07H: 25, 18, 11, 4 gives quotient 3 and remainder 4, so 8052H = 03H and 8053H = 04H.

Logical micro-operations perform bit-by-bit operations on the binary data stored in registers. Each bit of a register is treated as a separate variable, and the operation is applied to corresponding bits of the operands.

Let $A = 1100$ and $B = 1010$.

There are 16 possible logical functions of two variables; the above are the common ones.

Selective operations built from them:

• Selective-set (OR): sets bits of $A$ where $B$ has 1. $1100 \vee 1010 = 1110$.
• Selective-complement (XOR): complements bits of $A$ where $B$ has 1. $1100 \oplus 1010 = 0110$.
• Selective-clear: $A \leftarrow A \wedge \bar{B}$ clears bits of $A$ where $B$ has 1. $1100 \wedge 0101 = 0100$.
• Mask (AND): clears bits of $A$ where $B$ has 0. $1100 \wedge 1010 = 1000$.
• Insert: mask the field first, then OR in the new value.
• Clear: $A \leftarrow A \oplus B$ gives all 0s if $A = B$.

In hardware, a 4-to-1 multiplexer per bit chooses AND, OR, XOR or NOT using two select lines.

The basic computer (Mano) has a small set of registers used for instruction execution and data handling.

Memory is $4096 \times 16$. All registers are connected through a common bus, with the bus selected by three select lines $S_2S_1S_0$ (memory = 7, AR = 1, PC = 2, DR = 3, AC = 4, IR = 5, TR = 6). Register control uses LD (load), INR (increment) and CLR (clear) signals. The memory read/write and the adder-logic circuit feed AC, whose output goes back to the bus. Flip-flops include I (indirect), S (start/stop), E (extended carry), R (interrupt), IEN, FGI and FGO.

DMA (Direct Memory Access) is a technique in which an I/O device transfers a block of data directly to or from main memory without involving the CPU in each word transfer. It is used for fast devices such as disks.

Role of the DMA controller:

1. The CPU initialises the DMA controller by sending the starting memory address (address register), the word count (word-count register) and the direction of transfer (control register).
2. The device raises a DMA request; the controller sends a HOLD/BR (bus request) signal to the CPU.
3. The CPU finishes its current bus cycle, floats its buses, and replies with HLDA/BG (bus grant).
4. The controller takes control of the address and data buses, places the memory address on the address bus, and issues read/write signals, transferring each word directly between device and memory.
5. After each word, the address register is incremented and the word count is decremented.
6. When the count reaches zero, the controller releases the bus and sends an interrupt to the CPU to signal completion.

Transfer modes are burst (block at once), cycle stealing (one word per stolen bus cycle) and transparent. DMA relieves the CPU of overhead, so the CPU can do other work during the transfer.

Use 5 bits plus sign handling, so the product has 10 bits.

• Multiplicand $M = 15 = 01111$, so $-M = 10001$.
• Multiplier $Q = -13$. $13 = 01101$, so $-13 = 10011$.
• Initial: $A = 00000$, $Q_{-1} = 0$, SC = 5.

Booth rule on $(Q_0, Q_{-1})$: $10 \Rightarrow A = A - M$; $01 \Rightarrow A = A + M$; $00$ or $11 \Rightarrow$ no operation. Then arithmetic shift right of $A, Q, Q_{-1}$.

Product $= A\,Q = 1100111101$.

It is negative (MSB = 1). Its 2's complement is $0011000011 = 195$. So the product is $-195$.

Check: $15 \times (-13) = -195$.

Addressing mode is the method by which an instruction specifies the location of its operand (data). It tells the processor how to find the data to be operated on.

The 8085 has five addressing modes:

1. Immediate: the operand is part of the instruction. Example: MVI A, 32H (load 32H into A); LXI H, 2050H.
2. Register: the operand is in a register; the instruction names it. Example: MOV A, B (copy B into A); ADD C.
3. Direct: the instruction contains the 16-bit memory address of the operand. Example: LDA 2050H (load A from 2050H); STA 3000H.
4. Register indirect: a register pair (usually HL) holds the memory address of the operand. Example: MOV A, M (A = content of memory addressed by HL); LDAX B.
5. Implied (implicit): the operand is implied by the instruction itself. Example: CMA (complement A), RAL, STC.

(a) RISC (Reduced Instruction Set Computer)

RISC is a processor design that uses a small, simple set of instructions, each executed in one clock cycle.

• Fixed-length instructions, few addressing modes.
• Load/store architecture: only LOAD and STORE access memory; all other operations use registers.
• Large register file and hardwired control (no microcode).
• Heavy use of pipelining and compiler optimisation.
• Examples: ARM, MIPS, SPARC.

(b) Page Fault

In virtual memory with paging, a page fault occurs when a program references a page that is not currently in main memory. The hardware traps to the operating system, which:

1. locates the page on disk,
2. finds a free frame (or selects a victim page using a replacement algorithm such as FIFO or LRU, writing it back if modified),
3. loads the required page into the frame and updates the page table,
4. restarts the interrupted instruction.

Page faults are costly because of disk access time, so a low page-fault rate is important.

The 8085 is an 8-bit microprocessor with a 16-bit address bus (64 KB memory), operating at +5 V with a single-phase clock.

Block diagram (main parts):

        +-------------------------------------------------+
 Timing |  Accumulator   Temp reg   Flag flip-flops        |
 & Ctrl |      \            |          /                  |
        |        +--------- ALU --------+                  |
        |  B  C   D  E   H  L  W  Z  SP  PC               |
        |  Instruction register -> Decoder -> Control      |
        |  Interrupt control    Serial I/O control         |
        +-------------------------------------------------+
         Address bus A15-A8 | AD7-AD0 multiplexed addr/data

Components:

1. ALU: performs arithmetic (add, subtract, increment, decrement) and logical (AND, OR, XOR, compare, rotate) operations.
2. Accumulator (A): 8-bit register that holds one operand and receives the result.
3. Temporary register: holds the second operand during ALU operation; not accessible to programmers.
4. Flag register: 5 flags: Sign (S), Zero (Z), Auxiliary carry (AC), Parity (P), Carry (CY).
5. General-purpose registers: B, C, D, E, H, L (8-bit), usable as pairs BC, DE, HL; HL pair is used as memory pointer M. W and Z are temporary registers for the processor.
6. Program Counter (PC): 16-bit, holds the address of the next instruction.
7. Stack Pointer (SP): 16-bit, points to the top of the stack in memory.
8. Instruction register and decoder: hold the fetched opcode and decode it.
9. Timing and control unit: generates timing and control signals (ALE, RD, WR, IO/M, S0, S1).
10. Interrupt control: handles TRAP, RST 7.5, 6.5, 5.5 and INTR with INTA.
11. Serial I/O control: SID and SOD pins for serial data.
12. Address/data buffers: the lower address byte is multiplexed with data on AD0-AD7 and latched using ALE; A8-A15 are the high-order address lines.

SAP-1 vs SAP-2 architecture

Addressing modes of 8085

1. Immediate: operand is in the instruction. MVI B, 05H, LXI SP, 2FFFH.
2. Register: operand in a register. MOV C, D copies D into C; ADD B.
3. Direct: instruction gives the memory address. LDA 8000H loads A from 8000H; SHLD 9000H.
4. Register indirect: register pair holds the address. MOV A, M with HL = 8000H reads memory 8000H; STAX D.
5. Implied: operand is implicit. CMA complements A; RAR; HLT.

RISC vs CISC

Representation of $(88)_{10}$

$88 = 64 + 16 + 8 = 1011000_2$. In 8 bits, $88 = 01011000$.

For a positive number all three forms are the same.

Algorithm: load the first byte into A and save it in B, load the second byte, store it at 8000H, then store the saved byte at 9000H.

        LDA 8000H      ; A = content of 8000H
        MOV B, A       ; save it in B
        LDA 9000H      ; A = content of 9000H
        STA 8000H      ; store it in 8000H
        MOV A, B       ; get the original 8000H content
        STA 9000H      ; store it in 9000H
        HLT

Example: if (8000H) = 25H and (9000H) = 4AH, after execution (8000H) = 4AH and (9000H) = 25H.

Control unit is the part of the CPU that generates the timing and control signals needed to fetch, decode and execute instructions and to direct the data flow among registers, ALU, memory and I/O.

Hardwired vs microprogrammed control unit

Pipelining is a technique of dividing an operation into sequential segments, each handled by separate hardware, so that multiple operations overlap in time. Throughput increases because a new task enters the pipeline every clock cycle.

Four-segment instruction pipeline:

1. FI: fetch the instruction from memory.
2. DA: decode the instruction and calculate the effective address.
3. FO: fetch the operand from memory.
4. EX: execute the instruction and store the result.

For $n$ instructions through $k$ segments, time is $(k + n - 1)$ cycles instead of $nk$; the speedup is $\frac{nk}{k+n-1}$. Delays occur from data dependency, branch instructions (the pipeline is flushed when a branch is taken), and resource conflicts (memory access by FI and FO at the same time).

Booth's algorithm multiplies two signed binary numbers in 2's complement form. It treats a string of 1s in the multiplier as $2^{k+1} - 2^{m}$, so only the start and end of each block of 1s needs an operation.

Registers: BR = multiplicand, QR = multiplier, AC = 0, a 1-bit register $Q_{n+1}$ (called $Q_{-1}$) = 0, and sequence counter SC = number of bits $n$.

Procedure:

1. Examine the pair $Q_n Q_{n+1}$ (the last bit of QR and $Q_{n+1}$).
   • $10$: beginning of a block of 1s, so $AC \leftarrow AC + \overline{BR} + 1$ (subtract multiplicand).
   • $01$: end of a block of 1s, so $AC \leftarrow AC + BR$ (add multiplicand).
   • $00$ or $11$: no operation.
2. Arithmetic shift right the combined AC, QR, $Q_{n+1}$ (sign bit of AC is preserved).
3. Decrement SC.
4. If SC $\ne 0$, repeat from step 1; otherwise stop.

The product is in AC and QR ($2n$ bits). It works directly for positive and negative operands with no correction needed.

Example: $9 \times 7$ in 5 bits yields $0000111111 = 63$.

(a) DMA

Direct Memory Access lets an I/O device transfer a block of data directly to or from memory without CPU involvement for each word. The CPU programs the DMA controller with the start address, word count and direction. The controller requests the bus (HOLD), the CPU grants it (HLDA), the controller performs the transfers, and interrupts the CPU when the count reaches zero. Modes: burst, cycle stealing and transparent. It speeds up transfer for fast devices such as disks and frees the CPU.

(b) Flags in 8085

The flag register has five flags set after arithmetic/logic operations:

• Sign (S): 1 if result bit D7 = 1 (negative).
• Zero (Z): 1 if the result is zero.
• Auxiliary Carry (AC): 1 if a carry occurs from bit 3 to bit 4 (used in BCD).
• Parity (P): 1 if the result has an even number of 1s.
• Carry (CY): 1 if there is a carry out of bit 7 (or a borrow in subtraction).

Order in the flag register: D7 D6 D5 D4 D3 D2 D1 D0 = S Z X AC X P X CY.

(c) Instruction set

The instruction set is the collection of all instructions a processor understands. The 8085 has 74 instruction types (246 opcodes) in groups: data transfer (MOV, MVI, LDA), arithmetic (ADD, SUB, INR), logical (ANA, ORA, CMP, RAL), branching (JMP, JNZ, CALL, RET) and machine control (HLT, NOP).

RISC vs CISC

$9 \times 7$ using Booth's algorithm (5 bits)

$M = 9 = 01001$, $-M = 10111$, $Q = 7 = 00111$, $A = 00000$, $Q_{-1} = 0$.

Product $= A\,Q = 0000111111_2 = 63$.

Check: $9 \times 7 = 63$.

SAP-2 (Simple As Possible-2) computer is an improved 8-bit teaching computer, closer to a real microprocessor (like the 8085).

Features:

• 8-bit data bus, 16-bit address bus, so up to 64 KB memory.
• 16-bit program counter and MAR; memory data is accessed through a MDR/memory.
• Registers: accumulator A, B, C, temporary register TMP, instruction register IR; flag flip-flops (sign, zero).
• Input ports (1, 2) and output ports (3, 4), accessed by IN/OUT.
• Instructions of 1, 2 or 3 bytes; many instructions such as MOV, MVI, ADD, SUB, ANA, ORA, XRA, INR, DCR, CMA, LDA, STA, JMP, JM, JZ, JNZ, CALL, RET, HLT.
• Jump and subroutine (CALL/RET) support with a stack; conditional jumps use the flags.
• Hardwired/microprogrammed controller with a ring counter giving timing states, with variable-length machine cycles (fetch, then 1 to 3 byte reads/executes).

Block diagram:

 PC(16) --\                 /-- Input ports 1,2
 MAR(16) --\               /
 Memory(64KB)--- W BUS (8/16) --- A reg <-> ALU <-> B,C,TMP
 MDR ------/               \        |          (flags S,Z)
 IR -> Controller-Sequencer \-- Output ports 3,4

The PC, MAR, memory, MDR, IR, registers and ports all connect to the common W bus. The controller-sequencer decodes IR and issues control signals (LD, ENABLE, ALU operation lines).

Difference from SAP-1: SAP-1 has 4-bit addresses (16 bytes), only five instructions (LDA, ADD, SUB, OUT, HLT), one-byte instructions, no jumps, no flags, and a single output port. SAP-2 has 16-bit addresses, many more instructions of varying length, jumps, subroutines, flags, extra registers and I/O ports.

Addressing modes in 8085

1. Immediate: the data is in the instruction. MVI A, 45H; LXI H, 2000H.
2. Register: the data is in a register. MOV A, B; ADD C.
3. Direct: the instruction holds the address of the data. LDA 2050H; STA 3000H; IN 01H.
4. Register indirect: a register pair holds the address of the data. MOV A, M (HL points to memory); LDAX D.
5. Implied: the data is implicit in the opcode. CMA, RAL, STC.

Five arithmetic instructions

1. ADD R/M: add register or memory to A. ADD B: if A = 25H, B = 12H then A = 37H.
2. ADI data: add immediate. ADI 05H: A = 10H becomes 15H.
3. SUB R/M: subtract from A. SUB C: if A = 50H, C = 20H then A = 30H.
4. INR R/M: increment by 1. INR D: D = 0FH becomes 10H (flags affected except CY).
5. DCR R/M: decrement by 1. DCR B: B = 01H becomes 00H (Z flag set).

Others: ADC, SBB, DAD (16-bit add to HL), DAA.

Multiplication is performed by repeated addition: add 09H eight times (08H is the counter). The carry from any addition is accumulated in register C.

        MVI D, 08H     ; counter = multiplier 08H
        MVI B, 09H     ; B = multiplicand 09H
        MVI C, 00H     ; C = carry count
        MVI A, 00H     ; A = product (low byte)
LOOP:   ADD B          ; A = A + B
        JNC NEXT       ; if no carry skip
        INR C          ; count carry
NEXT:   DCR D          ; decrement counter
        JNZ LOOP       ; repeat until D = 0
        STA 8050H      ; store product
        MOV A, C
        STA 8051H      ; store carry
        HLT

Result: $8 \times 9 = 72 = 48H$, so (8050H) = 48H and (8051H) = 00H, as no carry is generated.

We compute $1197 - 1234$, which should be $-37$.

9's complement method

9's complement of $1234$ is $9999 - 1234 = 8765$.

$1197 + 8765 = 9962$

There is no end-around carry, so the result is negative and equals the 9's complement of the sum: $9999 - 9962 = 0037$.

Result: $-37$.

10's complement method

10's complement of $1234$ is $10000 - 1234 = 8766$.

$1197 + 8766 = 9963$

There is no carry out, so the result is negative: take the 10's complement of the sum, $10000 - 9963 = 37$.

Result: $-37$.

In the microprogrammed control of the basic computer, the fetch routine occupies the first addresses of control memory (ORG 64 in the text). The symbolic microprogram is:

        ORG 64
FETCH:  PCTAR              U JMP NEXT
        READ, INCPC        U JMP NEXT
        DRTAR              U JMP DECODE

Meaning of each microinstruction:

1. PCTAR: $AR \leftarrow PC$. The address of the next instruction is placed in the address register.
2. READ, INCPC: $DR \leftarrow M[AR]$, $PC \leftarrow PC + 1$. The instruction is read from memory and the PC is incremented.
3. DRTAR: $AR \leftarrow DR(0\text{-}10)$, transferring the address part of the fetched instruction to AR. The condition U JMP DECODE then branches (via the mapping ROM, using the opcode bits of DR) to the routine for the particular instruction.

Each line is a microinstruction with fields F1, F2, F3 (micro-operations), CD (condition), BR (branch type: JMP, CALL, RET, MAP) and AD (address). U means unconditional, NEXT the next address in control memory, and DECODE is a mapping (MAP) of the opcode to the routine's starting address.

Pipeline hazards are situations that prevent the next instruction from executing in its designated clock cycle, causing stalls.

1. Structural (resource) hazards: two instructions need the same hardware at the same time (e.g. one memory used for instruction fetch and operand fetch). Solution: duplicate resources (separate instruction and data memory or caches), or add more pipelined units, or stall.

2. Data hazards: an instruction depends on the result of a previous one that is not yet available (RAW, WAR, WAW). Example: ADD R1,R2,R3 followed by SUB R4,R1,R5. Solutions: operand forwarding (bypassing), inserting NOPs/stalls (pipeline interlocks), compiler instruction scheduling (reordering), and delayed load.

3. Control (branch) hazards: a branch changes the PC, so the instructions already fetched after it may be wrong. Solutions: pipeline flushing, branch prediction (static/dynamic), branch target buffer, delayed branch (compiler fills the delay slot), and prefetching both paths.

The 8085 has a flag register with five flip-flops that indicate the status of the result of an arithmetic or logical operation. The format is:

1. Sign flag (S): set (1) if bit D7 of the result is 1, meaning a negative number in 2's complement; otherwise 0.
2. Zero flag (Z): set if the result is zero; reset if non-zero.
3. Auxiliary carry flag (AC): set if there is a carry from bit D3 to D4; used for BCD arithmetic (DAA).
4. Parity flag (P): set if the result has an even number of 1s (even parity); reset for odd parity.
5. Carry flag (CY): set if an addition produces a carry out of D7, or a subtraction needs a borrow. It can be set by STC and complemented by CMC.

The X bits are unused. Conditional jump, call and return instructions test these flags.

The DMA controller (e.g. Intel 8257/8237) manages data transfer between an I/O device and memory without CPU intervention.

Main components: address register (holds the current memory address), word-count register (number of words left), control register (direction and mode), data buffers, and DMA request/acknowledge logic.

Role in a DMA operation:

1. The CPU loads the starting address, word count and transfer direction into the controller (initialisation), then continues with other work.
2. When the device is ready, it sends a DMA request (DREQ) to the controller.
3. The controller sends a bus request (HOLD) to the CPU.
4. The CPU completes the current bus cycle, releases the address, data and control buses (tri-state) and sends the bus grant (HLDA).
5. The controller sends DMA acknowledge (DACK) to the device and takes control of the buses. It places the address on the address bus and generates memory read/write and I/O read/write signals, so the word moves directly between device and memory.
6. After each transfer the address register is incremented and the word count is decremented.
7. When the count reaches zero, the controller releases the bus (HOLD removed) and issues an interrupt to the CPU to report completion.

(a) Microprogrammed Control Unit

In a microprogrammed control unit, the control signals for each instruction are generated by a sequence of microinstructions (a microprogram) stored in a control memory (ROM). Each machine instruction is executed by a micro-routine.

Main parts:

• Control memory: holds the microprogram.
• Control address register (CAR): holds the address of the next microinstruction.
• Control data register (pipeline register): holds the microinstruction being executed.
• Next-address (sequencing) logic: increments CAR, branches, or loads the address from the mapping logic (opcode to routine address), or from the subroutine register.

Advantages: flexible, easy to modify and implement complex instruction sets. Disadvantage: slower than hardwired control.

(b) Virtual Memory

Virtual memory is a technique that lets programs use a logical address space larger than the physical main memory. The programs are stored in secondary memory, and only the needed parts are loaded into main memory. The memory management unit translates virtual (logical) addresses to physical addresses through a page table (paging) or segment table.

• Pages of fixed size are brought in on demand; a page fault occurs if the page is absent, and replacement algorithms (FIFO, LRU) decide which page to remove.
• A TLB (translation lookaside buffer) speeds up address translation.
• Benefits: large programs can run, more programs can share memory, and the programmer need not manage memory.