Microprocessor and Computer Architecture

Microprocessor. A microprocessor is a single-chip CPU containing an ALU, a register array and a control unit, which fetches, decodes and executes instructions. It has no memory or I/O inside, so RAM, ROM and I/O interface chips must be added externally to build a computer. Examples are the Intel 8085, 8086 and Pentium.

Microcontroller. A microcontroller is a single-chip computer that has the CPU, RAM, ROM/flash, I/O ports, timers/counters and often a serial port and ADC on the same chip. It is designed for specific control tasks. Examples are the Intel 8051 and the PIC and AVR families.

The 8086 is a 16-bit microprocessor with a 20-bit address bus (1 MB memory) and a 16-bit data bus. Its internal architecture is divided into two independent units that work in parallel (pipelining): the Bus Interface Unit (BIU) and the Execution Unit (EU).

Diagram

                 +---------------------- BIU ----------------------+
                 |  CS  DS  SS  ES   (segment registers)           |
                 |  IP  (instruction pointer)                       |
 Address/Data    |  Internal communication registers                |
 bus  <--------> |  Address summing block (adder, 20 bit)           |
 (20 / 16 bit)   |  Bus control logic                               |
                 |  6-byte instruction queue  [B1][B2][B3][B4][B5][B6]
                 +--------------------------+----------------------+
                                            | (instruction bytes)
                 +--------------------------v----------------------+
                 |                      EU                          |
                 |  Control circuitry / instruction decoder         |
                 |  General registers: AX(AH,AL) BX(BH,BL)          |
                 |                     CX(CH,CL) DX(DH,DL)         |
                 |  Pointer & index:   SP  BP  SI  DI              |
                 |  ALU (16 bit)      Flag register                 |
                 |  Operand register                                |
                 +--------------------------------------------------+

1. Bus Interface Unit (BIU)

It handles all the external bus operations: fetching instructions, reading and writing memory and I/O ports.

• Segment registers: CS (code), DS (data), SS (stack) and ES (extra), each 16 bits, hold the starting addresses of four 64 KB segments.
• Instruction pointer (IP): 16-bit register holding the offset of the next instruction within the code segment.
• Address summing block (adder): forms the 20-bit physical address: $\text{Physical address} = \text{Segment} \times 10H + \text{Offset}$
• Instruction queue: a 6-byte FIFO. While the EU executes an instruction, the BIU prefetches the next instruction bytes into the queue. This overlap of fetch and execute (pipelining) increases speed. The queue is flushed when a jump or call is taken.
• Bus control logic: generates the control signals (ALE, RD', WR', DEN', DT/R', M/IO').

2. Execution Unit (EU)

It decodes and executes the instructions supplied by the queue. It has no direct connection to the system bus.

• Control circuitry and instruction decoder: takes the opcode from the queue, decodes it and generates the internal control signals.
• ALU: 16-bit unit performing arithmetic (add, subtract, ...) and logic (AND, OR, XOR, NOT, shift) operations.
• General purpose registers: AX (accumulator), BX (base), CX (count), DX (data); each can be used as two 8-bit registers (AH/AL etc.).
• Pointer and index registers: SP (stack pointer), BP (base pointer), SI (source index), DI (destination index), used in addressing modes and string operations.
• Flag register: 16 bits, of which 9 are used. Six status flags (CF, PF, AF, ZF, SF, OF) show the result of operations, and three control flags (TF, IF, DF) control the processor.

Working: the BIU fills the queue with instruction bytes; the EU takes bytes from the queue, executes them, and requests the BIU whenever it needs to read or write data in memory or I/O. Because both units operate at the same time, the total execution time is reduced.

The 8085 is an 8-bit microprocessor with a 16-bit address bus (64 KB memory), an 8-bit data bus, a single +5 V supply and an on-chip clock generator.

Architecture.

  +-----------------------------------------------------------+
  |  Interrupt control         Serial I/O control             |
  |  (INTR, TRAP, RST7.5-5.5)  (SID, SOD)                     |
  |                                                           |
  |  Accumulator   Temp reg     B   C                         |
  |      |            |         D   E                         |
  |      +---- ALU ---+         H   L                         |
  |           |                 W   Z (temporary)             |
  |        Flags                Stack pointer (16)            |
  |                             Program counter (16)          |
  |                             Incrementer/decrementer       |
  |  Instruction register -> Instruction decoder              |
  |  Timing and control -> ALE, RD', WR', IO/M', S0, S1, ...  |
  |  Address buffer (A15-A8)    Address/data buffer (AD7-0)   |
  +-----------------------------------------------------------+

Parts.

1. ALU. Performs arithmetic and logic operations on 8-bit data: ADD, SUB, INR, DCR, AND, OR, XOR, CMP, rotate, complement. Inputs are the accumulator and the temporary register.
2. Accumulator. An 8-bit register that holds an operand and the result of the operation. Data I/O (IN/OUT) is also done through it.
3. Temporary register. Holds the second operand of the ALU; it is not accessible to the user.
4. Flag register. Holds S, Z, AC, P and CY flags that reflect the result of the last operation.
5. General purpose registers. B, C, D, E, H, L (8-bit) can be used singly or as pairs BC, DE, HL (16-bit). HL is the memory pointer M. The W and Z registers are internal temporaries, not user accessible.
6. Program counter (16-bit). Holds the address of the next instruction and is incremented as each byte is fetched.
7. Stack pointer (16-bit). Holds the address of the top of the stack in RAM, used by PUSH, POP, CALL and RET.
8. Incrementer/decrementer address latch. Increments or decrements PC, SP and register pairs.
9. Instruction register and decoder. The opcode is held in the instruction register, and the decoder finds the operation.
10. Timing and control unit. Generates the control signals ($\overline{RD}$, $\overline{WR}$, ALE, $IO/\overline{M}$, S0, S1) and timing.
11. Interrupt control. Handles five interrupts: TRAP, RST 7.5, RST 6.5, RST 5.5 and INTR (with INTA).
12. Serial I/O control. SID (input) and SOD (output) allow serial data transfer using the RIM and SIM instructions.
13. Address buffer and address/data buffer. The address buffer drives A15-A8; the multiplexed AD7-AD0 carry the low address first (latched by ALE) and then data.

Flags in 8085. Flags are single-bit flip-flops in the flag register that record the status of the result of the most recent arithmetic or logical operation. The 8085 has five flags (the other three bits of the 8-bit register are unused):

• Sign (S): set if bit D7 of the result is 1 (negative in 2's complement).
• Zero (Z): set if the result is zero.
• Auxiliary Carry (AC): set if there is a carry from bit D3 to D4; used in BCD arithmetic (DAA).
• Parity (P): set if the result has an even number of 1s.
• Carry (CY): set if an addition produces a carry out of D7, or a subtraction needs a borrow.

Conditional jump, call and return instructions test these flags.

Addressing modes of 8085. An addressing mode is the way the operand of an instruction is specified.

1. Immediate addressing: the operand (data) is part of the instruction itself.
   • MVI A, 32H loads 32H into A; LXI H, 2050H loads a 16-bit value.
2. Register addressing: the operand is in a register, and the instruction names the register(s).
   • MOV A, B copies B into A; ADD C adds C to A.
3. Direct addressing: the instruction contains the 16-bit memory address of the operand.
   • LDA 2050H loads A from location 2050H; STA 3000H; IN 80H (port address, 8-bit).
4. Register indirect addressing: a register pair (HL, BC or DE) holds the memory address of the operand.
   • MOV A, M loads A from the address in HL; LDAX B loads A from the address in BC; STAX D.
5. Implicit (implied) addressing: the operand is implied by the opcode; no operand is written.
   • CMA complements the accumulator; RAL, STC, RET, HLT.

Example: MVI A,05H (immediate), MOV B,A (register), STA 2000H (direct), MOV M,B (register indirect), CMA (implicit).

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 passing through the CPU. A special hardware unit called the DMA controller (DMAC) takes over the system buses from the CPU for the transfer. This avoids the slow byte-by-byte program-controlled or interrupt-driven I/O, so the CPU is free for other work.

        +-----+  HOLD ->  +---------+   Address bus   +--------+
        | CPU |<- HLDA -- |   DMA   |================>| Memory |
        +--+--+           |Controller|<===============>|        |
           |  Data/Addr   | (8257)  |   Data bus       +--------+
           +====bus======>|         |
                          +--+---+--+
                  DREQ --> |   |  --> DACK
                          I/O device

The DMAC contains an address register (starting memory address), a word/byte count register, a control/status register and the bus-control logic with DREQ and DACK lines.

Steps of a DMA transfer

1. The CPU initialises the DMAC by writing the starting memory address, the number of bytes to transfer, the direction (read/write) and the mode.
2. The I/O device raises DMA request (DREQ) when it is ready for transfer.
3. The DMAC sends a HOLD request to the CPU.
4. The CPU completes the current machine cycle, floats its buses, and replies with hold acknowledge (HLDA).
5. The DMAC sends DMA acknowledge (DACK) to the device, puts the memory address on the address bus, and generates the read/write control signals. Data moves directly between the device and memory.
6. After each transfer the address register is incremented and the count register decremented.
7. When the count reaches zero (terminal count), the DMAC releases HOLD, the CPU regains the buses, and it may be informed by an interrupt.

Modes of DMA transfer

• Burst (block) mode: the whole block is transferred while the DMAC holds the bus; fastest, but the CPU is blocked.
• Cycle stealing: the DMAC takes the bus for one cycle per word and returns it, so the CPU slows slightly but is not stopped.
• Transparent mode: the DMAC uses the bus only when the CPU is not using it.

Advantages: high-speed data transfer and low CPU overhead. Disadvantage: extra hardware and bus contention.

Unsigned notation

All $n$ bits of the number represent its magnitude; there is no sign. An $n$-bit unsigned number can represent values from $0$ to $2^n - 1$. For $n = 8$ the range is $0$ to $255$; for example $11111111_2 = 255$. Unsigned numbers are used for addresses, counters and sizes, where negative values do not occur.

Signed notation

One bit (the most significant bit, MSB) is used as the sign: 0 means positive and 1 means negative. The common representations are:

1. Sign-magnitude: MSB is the sign and the remaining $n-1$ bits give the magnitude. Range $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$. It has two zeros ($+0$ and $-0$), and the arithmetic circuits are complex.
2. 1's complement: a negative number is formed by complementing every bit of its positive form. Range is the same as sign-magnitude, and there are still two zeros.
3. 2's complement: a negative number is formed by adding 1 to its 1's complement. Range is $-2^{n-1}$ to $+2^{n-1}-1$. There is a single zero and addition/subtraction use the same hardware, so it is the form used in almost all computers.

Example (8 bits): $+5 = 00000101$.

• Sign-magnitude of $-5$ = 10000101
• 1's complement of $-5$ = 11111010
• 2's complement of $-5$ = 11111011

Comparison for 8 bits

The same bit pattern can mean different values: 11111011 is 251 as unsigned but $-5$ as signed 2's complement. Hence the programmer or the processor must know which interpretation is used. Overflow is detected by the carry flag for unsigned numbers and by the overflow flag for signed numbers.

Interfacing. Interfacing is the process of connecting a microprocessor to memory or to peripheral devices such as keyboards, displays and printers, using extra hardware so that the speed, voltage levels and data formats are compatible. The interface circuits include buffers, latches, decoders and programmable chips like the 8255A.

8255A PPI (Programmable Peripheral Interface). It is a 40-pin chip that provides 24 programmable I/O lines, in three 8-bit ports (A, B and C), and connects the 8085 to the outside world.

Block diagram.

D7-D0 <-> [Data bus buffer] <-> internal data bus
                                  |
RD'  --\                  +-------+---------+
WR'  ---->[Read/Write     |                 |
A0   ---->  control  ]----+-> Group A control -> Port A (PA7-PA0)
A1   --/  [  logic   ]    |                 |-> Port C upper (PC7-PC4)
CS'  --/                  +-> Group B control -> Port C lower (PC3-PC0)
RESET -->                                    -> Port B (PB7-PB0)

Sections.

1. Data bus buffer. An 8-bit bidirectional buffer that connects the 8255A to the system data bus. Data and control words pass through it.
2. Read/write control logic. It receives $\overline{RD}$, $\overline{WR}$, $\overline{CS}$, A0, A1 and RESET. It controls the data direction and selects the port or control register.

3. Group A and Group B controls. Group A controls Port A and the upper half of Port C (PC7-PC4). Group B controls Port B and the lower half of Port C (PC3-PC0). They receive the control word from the CPU and set the mode of the ports.
4. Port A. An 8-bit latched output buffer and input latch. It can be used in modes 0, 1 and 2.
5. Port B. An 8-bit I/O port, usable in modes 0 and 1.
6. Port C. Two 4-bit ports, used for I/O in mode 0 or for control and status signals (handshaking) in modes 1 and 2. Individual bits can be set or reset by the BSR mode.

The 8255A is programmed by writing a control word into the control register.

LDA 2000H loads the accumulator with the content of memory location 2000H. It is a 3-byte instruction: opcode 3AH, then the low-order address byte 00H, then the high-order address byte 20H. It needs four machine cycles and 13 T states.

Total = $4 + 3 + 3 + 3 = 13$ T states. At 3 MHz this is $13 \times 0.333 = 4.33\ \mu s$.

Timing diagram (instruction stored at 1000H as an example).

        |<--- M1 (OF) --->|<-- M2 (MR) -->|<-- M3 (MR) -->|<-- M4 (MR) -->|
        | T1 T2 T3 T4     | T1  T2  T3    | T1  T2  T3    | T1  T2  T3    |
A15-A8  | 10H (PC)        | 10H           | 10H           | 20H           |
AD7-AD0 | 00H -> 3AH      | 01H -> 00H    | 02H -> 20H    | 00H -> data   |
ALE     | |-|             | |-|           | |-|           | |-|           |
RD'     |    low in T2,T3 |   low T2-T3   |   low T2-T3   |   low T2-T3   |

Fetch cycle.

• M1 (opcode fetch): the PC places the address on the bus, ALE latches the low byte, $\overline{RD}$ goes low, and the opcode 3AH is read into the instruction register and decoded in T4.

Execute cycles.

• M2: the low-order address byte 00H is read from PC + 1 into register Z.
• M3: the high-order address byte 20H is read from PC + 2 into register W. WZ now holds 2000H.
• M4: the address 2000H is output from WZ, $\overline{RD}$ goes low, and the data byte is read from memory location 2000H into the accumulator.

Take LDA addr (opcode 3AH), a 3-byte instruction that loads the accumulator with the content of a 16-bit address. It takes 4 machine cycles and 13 T-states: the first three cycles are the fetch phase and the last one is the execution phase.

Machine cycles

Timing details

• T1: the address goes out on A15-A8 and AD7-AD0, ALE goes high to latch the low address byte, and the status signals are put on IO/M', S1 and S0.
• T2: the multiplexed lines AD7-AD0 become the data bus, and RD' goes low.
• T3: the data is read from the bus and RD' goes high.
• T4 (M1 only): the opcode is decoded in the instruction decoder, and the bus is idle.

So the diagram has four consecutive cycles: M1 (4 T) + M2 (3 T) + M3 (3 T) + M4 (3 T) = 13 T-states.

Microprocessor. A microprocessor is a programmable, multipurpose integrated circuit (a single VLSI chip) that works as the central processing unit of a computer. It fetches instructions from memory, decodes them, performs the arithmetic and logical operations, and controls the other parts of the system, all driven by a clock. Examples are the Intel 8085, 8086 and Pentium.

Basic components. A microprocessor is built from three main units connected by internal buses.

        +---------------------------------------------+
        |                MICROPROCESSOR               |
        |  +---------+   +---------+   +-----------+  |
        |  |   ALU   |<->| Register|<->|  Control  |  |
        |  |         |   |  Array  |   |   Unit    |  |
        |  +---------+   +---------+   +-----------+  |
        +------^--------------^--------------^--------+
               |  Data bus    | Address bus  | Control bus

1. Arithmetic and Logic Unit (ALU). It performs arithmetic operations (add, subtract, increment, decrement) and logic operations (AND, OR, XOR, NOT, compare, shift/rotate). One operand usually comes from the accumulator and the result goes back to it. The result affects the flag register.

2. Register array. Registers are fast on-chip storage.

• General purpose registers (B, C, D, E, H, L in the 8085) hold data and addresses temporarily.
• Accumulator holds one operand and the result of the ALU.
• Program Counter (PC) holds the address of the next instruction.
• Stack Pointer (SP) points to the top of the stack in memory.
• Instruction Register (IR) holds the opcode being decoded.
• Flag register records the status of the last operation (Sign, Zero, Auxiliary Carry, Parity, Carry).

3. Control unit. It decodes the instruction in the IR and generates timing and control signals (such as $\overline{RD}$, $\overline{WR}$, ALE, $IO/\overline{M}$) that coordinate the ALU, registers, memory and I/O devices in the correct sequence.

Buses.

• Address bus: unidirectional; carries the address (16 lines in the 8085, so $2^{16}=64$ KB memory).
• Data bus: bidirectional; carries data (8 lines in the 8085).
• Control bus: carries control and timing signals.

Together these components let the microprocessor perform the instruction cycle of fetch, decode and execute.

Idea. The byte is placed in the accumulator and rotated right 8 times. After each rotation the bit that moved out is in the carry flag. If carry is set, a counter is incremented. $AB_H = 1010\ 1011_2$ contains five 1s, so the expected result is $05_H$.

        MVI A, ABH      ; A = data byte
        MVI B, 08H      ; B = bit counter (8 bits)
        MVI C, 00H      ; C = count of 1s
LOOP:   RRC             ; rotate right, D0 -> CY
        JNC SKIP        ; if CY = 0, do not count
        INR C           ; CY = 1, increment count
SKIP:   DCR B           ; one bit processed
        JNZ LOOP        ; repeat until B = 0
        MOV A, C        ; A = number of 1s
        STA C000H       ; store result at C000H
        HLT

Trace. The bits of ABH from D0 upward are 1,1,0,1,0,1,0,1. Carry is set five times, so C goes $0\to1\to2\to3\to4\to5$. After 8 iterations B reaches 0 and the loop ends.

Result: $[C000_H] = 05_H$.

Machine cycle. A machine cycle is the time needed by the microprocessor to complete one basic operation such as an opcode fetch, memory read, memory write, I/O read or I/O write. It consists of 3 to 6 clock periods (T-states). One or more machine cycles form an instruction cycle.

MOV M, A. The instruction copies the accumulator into the memory location whose address is in the HL pair. It has one byte and needs 2 machine cycles and 7 T-states:

1. Opcode fetch (M1), 4 T-states. PC is placed on the address bus, ALE goes high to latch the low address, $IO/\overline M=0$, $S_1S_0=11$; $\overline{RD}$ goes low in T2 to read the opcode (77H); the opcode is decoded in T4.
2. Memory write (M2), 3 T-states. The content of HL is placed on the address bus (ALE high in T1, $IO/\overline M=0$, $S_1S_0=01$); the data from A is placed on AD7-AD0 in T2 and $\overline{WR}$ goes low during T2-T3 to write it.

        |  M1: Opcode fetch   |   M2: Memory write  |
        | T1 | T2 | T3 | T4   | T1 | T2 | T3        |
CLK     |_|-|_|-|_|-|_|-|_|-|_|-|_|-|_|-|_|-|_|-|
ALE     __|--|_______________|--|________________
A15-A8  [   PC high         ][   H (HL high)    ]
AD7-AD0 [PCL][ opcode 77H   ][L ][ data from A   ]
IO/M    ___________________________________(low)
RD      ----------|_____|---------------------------
WR      ---------------------------------|______|--
S1S0       1 1 (fetch)       0 1 (write)

Execution time. Total T-states $= 4 + 3 = 7$. With a clock frequency of 10 kHz:

$T = \frac{1}{f} = \frac{1}{10\times10^{3}} = 0.1\ \text{ms}$

$\text{Execution time} = 7\times 0.1\ \text{ms} = 0.7\ \text{ms} = 700\ \mu\text{s}$

The 8086 is internally divided into two independent units, the Bus Interface Unit (BIU) and the Execution Unit (EU), which work in parallel. This overlapping of fetch and execute is called pipelining, and it speeds up processing.

          +---------------------- 8086 ----------------------+
          |  BIU                          EU                 |
          |  CS DS SS ES  (segment regs)  AX BX CX DX        |
          |  IP                           SP BP SI DI        |
          |  Adder (20-bit address)       ALU   Flags        |
          |  6-byte instruction queue --> Control unit/decoder|
          |  Bus control logic                               |
          +----------^----------------------------^----------+
                20-bit address bus          16-bit data bus

Bus Interface Unit (BIU). It handles all communication with memory and I/O.

• Fetches instructions from memory and stores them in a 6-byte instruction queue (FIFO), so the next instructions are ready before the EU asks.
• Reads operands and writes results to memory or ports for the EU.
• Generates the 20-bit physical address in its address adder: physical address $=$ segment $\times 10_H +$ offset, so 1 MB can be addressed.
• Contains the segment registers CS, DS, SS, ES, the instruction pointer IP, the instruction queue and the bus control logic.

Execution Unit (EU). It executes instructions taken from the queue.

• Control unit/decoder decodes the instructions and generates control signals.
• ALU (16-bit) does arithmetic and logic operations.
• General registers AX, BX, CX, DX (also usable as 8-bit halves AH/AL etc.), pointer and index registers SP, BP, SI, DI, and the flag register (9 flags: CF, PF, AF, ZF, SF, OF, TF, IF, DF).
• It has no direct connection to the system bus; when it needs data from memory it passes the offset to the BIU.

Working. While the EU is busy executing an instruction, the BIU fetches the next instruction bytes into the queue. When a jump instruction is executed the queue is flushed and refilled. This parallel operation reduces the idle time of the buses and increases throughput.

Generic CPU design. A CPU has a datapath (registers, ALU and internal buses that process data) and a control unit (which sequences the datapath). It is connected to memory and I/O through the system bus.

                 +--------------------- CPU ---------------------+
 System bus      |  +---------+      +------------------------+   |
 Address <-------|--|   MAR   |      |        Control Unit    |   |
 Data   <------->|--|   MBR   |      |  IR -> Decoder -> CW   |   |
 Control<------->|  |   PC    |      +-----------+------------+   |
                 |  +----+----+      control signals            |
                 |       |                      |                |
                 |  ===== Internal data bus ====+=====           |
                 |   |       |        |                          |
                 | +-----+ +-----+ +-------+                     |
                 | | GPR | | ACC | |  ALU  |<-- Flags            |
                 | +-----+ +-----+ +-------+                     |
                 +-----------------------------------------------+

Register organization. Registers are grouped as:

1. User-visible registers: general purpose registers (data and address), the accumulator, and the stack pointer/index registers for addressing.
2. Control and status registers:
   • Program Counter (PC): address of the next instruction.
   • Instruction Register (IR): holds the fetched instruction.
   • Memory Address Register (MAR): address sent to the address bus.
   • Memory Buffer/Data Register (MBR/MDR): data read from or to be written to memory.
   • Status/flag register (PSW): zero, sign, carry, overflow, etc.

Data path. The data path is the route over which data flows between registers, ALU and memory. Using a single internal bus, a register's output is gated onto the bus by a control signal and loaded into the destination register by another. For example, an instruction fetch is the sequence:

$MAR\leftarrow PC;\quad MBR\leftarrow M[MAR];\quad PC\leftarrow PC+1;\quad IR\leftarrow MBR$

For ADD R1, the operands are placed in the ALU input registers (one is the accumulator, the other comes from R1 over the bus), the ALU adds them, and the result is written back to the accumulator and the flags are updated. Each step is carried out in one clock period by control signals from the control unit. In a multiple-bus data path two operands can be moved simultaneously, which reduces the number of clock cycles.

Factors favouring a micro-programmed control unit over a hardwired one

So a micro-programmed unit is chosen when the instruction set is large or complex, when flexibility, easy modification and low design cost matter more than the raw speed.

Hardwired control unit. In this design the control signals are generated by a fixed combinational logic circuit (gates, decoders, counters) rather than by a stored program.

   IR (opcode) --> [ Instruction decoder ] --+
   Flags / condition codes ------------------+--> [ Control logic   ] --> Control
   Clock --> [ Timing generator: ring/       |     (AND-OR gates)         signals
              counter + step decoder T1..Tn ]+

Components:

• Instruction register and decoder: the opcode bits in the IR are decoded into one line per instruction (e.g. ADD, LOAD, JMP).
• Timing (step) generator: a clock-driven counter or ring counter and decoder produce the timing signals $T_1, T_2,\dots,T_n$ for each step of the instruction cycle.
• Control logic network: gates combine the instruction lines, timing signals and flags to produce each control signal, e.g.

$C_{\text{PC}_{\text{out}}} = T_1 + T_4\cdot \text{BRANCH}\cdot \text{Z}$

• Control signals: drive the registers, ALU, buses and memory.

Operation: the clock advances the step counter; for the current opcode and step, the logic network activates exactly the required control signals, so each micro-operation (e.g. $MAR\leftarrow PC$, $PC\leftarrow PC+1$) occurs in the proper time slot.

Advantages: very fast (only gate delays), suited to RISC. Disadvantages: inflexible, costly and error prone for complex instruction sets, and difficult to modify.

Microinstruction sequencing is the way the control unit of a micro-programmed CPU decides which microinstruction in the control memory to execute next. Each machine instruction is carried out by a microroutine, and the sequencing logic must (1) start the proper microroutine from the opcode, (2) step through its microinstructions, (3) branch on conditions, and (4) return to the fetch routine when the instruction ends.

 IR (opcode) --> Mapping logic --+
 Next-address field -------------+--> [ MUX ] --> CAR --> Control memory --> CW / microinstruction
 Condition flags --> Branch logic+       ^  
 CAR + 1 (incrementer) -----------------+
 Subroutine register SBR (return) ------+

CAR is the control address register that holds the address of the current microinstruction.

Techniques / sequencing modes

1. Incrementing: CAR is incremented to give the next sequential microinstruction. Example: a fetch microroutine $MAR\leftarrow PC$ at address 0, $MBR\leftarrow M$ at 1, $IR\leftarrow MBR$ at 2.
2. Unconditional branch: the address field of the microinstruction is loaded into CAR. Example: JMP 20 jumps to address 20.
3. Conditional branch: CAR is loaded with the address field if a flag/condition (Z, C, S) is true; otherwise CAR is incremented. Example: BRZ 30 branches to 30 if Z = 1.
4. Mapping from opcode: after the fetch routine, the opcode in IR is mapped to the starting address of its microroutine, typically by appending bits to the opcode, e.g. address $= 0\,\text{opcode}\,00$ (4 microinstructions per routine). So ADD (opcode 0001) maps to 0 0001 00 $= 4_{10}$.
5. Subroutine call and return: a microroutine shared by several instructions (such as an effective-address computation) is called by saving CAR+1 in the subroutine register SBR; a return loads CAR from SBR.

Design for the next address field

• Two address fields: the microinstruction holds two next addresses (true/false); a MUX picks one using the condition. Fast but wide.
• One address field: a single address plus condition; if false, CAR is incremented. Compact, the most common.
• Variable format: a bit decides whether the word is an operation microinstruction or a branch microinstruction.

Example. Instruction ADD R1 completes as: fetch routine (addresses 0-2) $\to$ mapping to ADD routine at 4 $\to$ microinstructions at 4, 5 (sequentially incrementing) $\to$ unconditional branch back to address 0 to fetch the next instruction.

Setup. Multiplicand $M = X = 1001_2\ (9)$ and multiplier $Q = Y = 0101_2\ (5)$. The accumulator $A=0000$ and the carry $C=0$. For each of the 4 bits of $Q$: if $Q_0=1$ then $A\leftarrow A+M$; then shift $C\,A\,Q$ right by one bit. After 4 cycles the product is in $A\,Q$ (8 bits).

Product $= A\,Q = 0010\ 1101_2$.

Verification.

$0010\,1101_2 = 32 + 8 + 4 + 1 = 45$

and $9\times5 = 45$. It also matches the partial-product method: $1001 + 100100 = 101101_2 = 45$ (the multiplier 0101 has 1s in positions 0 and 2).

Result: $1001\times0101 = 00101101_2 = 45_{10}$.

Cache memory. Cache is a small, very fast memory placed between the CPU and the main memory. It keeps copies of the most recently or frequently used blocks of main memory, so that most CPU accesses are served at cache speed. It works because of the principle of locality (temporal and spatial). When the required word is found in the cache it is a hit; otherwise it is a miss and the block is brought from main memory.

$\text{Hit ratio } h=\frac{\text{hits}}{\text{total accesses}},\qquad T_{avg}=h\,T_c+(1-h)\,T_m$

Direct mapping. In direct mapping each block of main memory can be placed in exactly one cache line, given by

$\text{line number} = (\text{block number}) \bmod (\text{number of cache lines})$

The main memory address is divided into three fields:

 | Tag (t bits) | Line / index (l bits) | Word offset (w bits) |

• Word offset selects the word in a block ($2^w$ words per block).
• Line field selects the cache line ($2^l$ lines).
• Tag identifies which of the memory blocks that share the line is currently stored.

Operation. The line field of the CPU address selects a cache line. The stored tag is compared with the tag field of the address. If they match and the valid bit is set, it is a hit and the word is read using the offset. Otherwise it is a miss: the whole block is fetched from main memory, placed in that line (replacing the existing block) and the tag is updated.

Example. Main memory of 64 KB (16-bit address), cache of 1 KB, block size 16 words. Offset $= 4$ bits; lines $= 1024/16 = 64 \Rightarrow$ index $= 6$ bits; tag $= 16-6-4=6$ bits. Blocks 5, 69, 133,... all map to line 5.

Advantages: simple, cheap hardware, no replacement algorithm needed, fast lookup. Disadvantages: if two frequently used blocks map to the same line they keep replacing each other (conflict misses, thrashing), so the hit ratio can be low.

Address calculation. A 4K EPROM has $4096 = 2^{12}$ locations, so it needs 12 address lines A0-A11 and 8 data lines D0-D7. Starting at 2000H its range is 2000H-2FFFH:

The lines A11-A0 go directly to the chip; the upper lines A15-A12 = 0010 must select it.

Decoder connection (74LS138, 3-to-8). Inputs: C = A14, B = A13, A = A12. For A14 A13 A12 = 0 1 0 the output $\overline{Y_2}$ goes low. Enable inputs: $G_1 = +5$ V (high), $\overline{G_{2A}} = A_{15}$ (must be 0), $\overline{G_{2B}} = IO/\overline M$ (must be 0 for a memory access). $\overline{Y_2}$ is connected to the chip enable $\overline{CE}$ of the EPROM.

Demultiplexing. The 8085 multiplexes A0-A7 with D0-D7 on AD0-AD7. A 74LS373 octal latch, clocked by ALE, separates them: its outputs give A0-A7. A8-A15 come directly from the processor.

 8085                                   74LS373                    2732 4K EPROM
 AD7-AD0 ------+------------------------ D  Q ---- A7-A0 -------> A7-A0
               |  ALE -----------------> G                         
               |                          
 A15-A8        +-- (data lines) ---------------------------------> D7-D0
 A11-A8 -----------------------------------------------------> A11-A8
 A12 ------> A  \
 A13 ------> B   74LS138 ---- Y2 (active low) -------------------> CE
 A14 ------> C  /
 A15 ------> G2A
 IO/M -----> G2B ;  G1 = +5V
 RD ------------------------------------------------------------> OE

Working. When the 8085 outputs an address in 2000H-2FFFH, A15=0, IO/M̅=0, A14A13A12 = 010, so $\overline{Y_2}=0$ and the EPROM is enabled. The latched low address and A11-A8 select one location, $\overline{RD}$ enables the output buffer ($\overline{OE}$), and the byte appears on the data bus. For other addresses the decoder does not select this chip, so its outputs stay in high impedance.

Multicore architecture. A multicore processor is a single chip (one package) that contains two or more independent processing units (cores). Each core has its own ALU, registers, control unit and usually its own L1 cache; the cores usually share the L2/L3 cache, memory controller and system bus.

 +---------------------------------------------+
 | Core 1 (L1) | Core 2 (L1) | Core 3 | Core 4 |
 +-------------+-------------+--------+--------+
 |        Shared L2 / L3 cache                 |
 |        Memory controller / bus interface    |
 +---------------------------------------------+

Advantages: several tasks or threads run truly in parallel, so higher throughput; better performance per watt than raising the clock speed; lower heat; cores on one die communicate faster. Limitation: software must be multithreaded to benefit, and shared resources can cause contention. Examples: Intel Core i5/i7, AMD Ryzen.

RISC (Reduced Instruction Set Computer) characteristics

• Small, simple instruction set; fixed-length instructions (e.g. 32 bit) with few formats.
• Most instructions execute in one clock cycle (hardwired control, no microcode).
• Load/store architecture: only LOAD and STORE access memory; all other operations are register to register.
• Large number of general purpose registers.
• Few addressing modes.
• Heavy use of pipelining; the compiler does more work.
• Examples: ARM, MIPS, SPARC, RISC-V.

CISC (Complex Instruction Set Computer) characteristics

• Large, rich instruction set with complex instructions (e.g. string move, multiply) that do several operations.
• Variable-length instructions and many instruction formats.
• Many addressing modes; instructions can operate directly on memory operands.
• Fewer registers.
• Instructions take multiple cycles; control is micro-programmed.
• Compact programs, so less memory is needed, and simpler compilers.
• Examples: Intel x86, VAX, Motorola 68000.

Memory hierarchy is the arrangement of the different memories of a computer in levels, according to speed, cost and capacity, so that the system gets the speed of the fastest memory and the capacity of the cheapest.

            ^  faster, costlier, smaller
   Registers (in CPU)
   Cache memory (L1, L2, L3)
   Main memory (RAM)
   Secondary storage (SSD / hard disk)
   Tertiary / archival (optical disk, tape)
            v  slower, cheaper, larger

As we go down the hierarchy, cost per bit and speed decrease while capacity increases. The hierarchy works because of the principle of locality of reference: programs tend to reuse the same data and instructions (temporal locality) and nearby addresses (spatial locality). So the data currently needed is kept in the upper fast levels, and the average access time is close to that of the fastest level:

$T_{avg}=h\,T_{fast}+(1-h)\,T_{slow}$

Virtual memory extends main memory using the disk, and the cache mapping techniques manage the transfer of blocks between levels.

2's complement is the most common method of representing signed integers in computers. A positive number is written in ordinary binary with a leading 0; a negative number $-N$ is represented by the 2's complement of $N$.

To find the 2's complement: invert all bits (1's complement) and add 1.

Example (8 bits): $+5 = 0000\,0101$. 1's complement $= 1111\,1010$; add 1 $\Rightarrow 1111\,1011 = -5$.

Range. For $n$ bits: $-2^{n-1}$ to $+(2^{n-1}-1)$; for 8 bits, $-128$ to $+127$. The MSB is the sign bit (0 positive, 1 negative). The value of a negative number is $-b_{n-1}2^{n-1}+\sum_{i<n-1} b_i2^i$.

Advantages

• There is only one representation of zero (sign-magnitude and 1's complement have $+0$ and $-0$).
• Subtraction becomes addition: $A-B = A + (\text{2's complement of } B)$, so the same adder serves both. Example: $7-5$: $0111 + 1011 = 1\,0010$; discard the carry out, result $0010 = 2$.
• Overflow is detected when the carries into and out of the sign bit differ.

The 8085 and 8086 use this representation for signed numbers, and the instruction CMA followed by INR A gives the 2's complement of the accumulator.

Microprocessor. A microprocessor is a programmable integrated circuit that serves as the CPU of a computer. It contains an ALU, a register array and a control unit on a single chip; it fetches, decodes and executes instructions stored in memory and communicates with memory and I/O through the address, data and control buses (e.g. Intel 8085, 8086).

Von-Neumann vs Harvard architecture

 Von Neumann:  CPU <== single bus ==> [ Memory: program + data ]

 Harvard:      CPU <== instruction bus ==> [ Program memory ]
                   <== data bus ========> [ Data memory    ]

Approach. The 11 bytes from 7070H to 707AH are read one by one. A number is odd if its bit D0 is 1, and even if D0 is 0, so ANI 01H followed by a zero-flag test classifies it. B counts even numbers and C counts odd numbers; they are stored at 8081H (even count) and 8082H (odd count). Since $707A_H-7070_H+1 = 0B_H = 11$ bytes, the counter starts at 0BH.

        LXI H, 7070H    ; HL points to the first data byte
        MVI D, 0BH      ; D = number of bytes (11)
        MVI B, 00H      ; B = count of even numbers
        MVI C, 00H      ; C = count of odd numbers
NEXT:   MOV A, M        ; get data byte
        ANI 01H         ; isolate D0
        JZ  EVEN        ; D0 = 0 -> even
        INR C           ; odd
        JMP SKIP
EVEN:   INR B           ; even
SKIP:   INX H           ; next address
        DCR D           ; one byte done
        JNZ NEXT        ; repeat until all 11 are checked
        LXI H, 8081H
        MOV M, B        ; [8081H] = even count
        INX H
        MOV M, C        ; [8082H] = odd count
        HLT

Example. If the data are 02, 03, 04, 05, 06, 07, 08, 09, 0A, 0B, 0C, then even = 6 (stored at 8081H as 06H) and odd = 5 (stored at 8082H as 05H); even + odd = 11.

Approach. The 8085 stores a 16-bit number with the low byte at the lower address. The minuend is at 2010H-2011H and the subtrahend at 2000H-2001H. The low bytes are subtracted with SUB and the high bytes with SBB (which includes the borrow from the first subtraction). The result is stored at 2020H (low byte) and 2021H (high byte).

$\text{Result} = [2010H\text{-}2011H] - [2000H\text{-}2001H]$

        LHLD 2010H      ; HL = minuend (L from 2010H, H from 2011H)
        XCHG            ; DE = minuend
        LHLD 2000H      ; HL = subtrahend
        MOV  A, E       ; A = low byte of minuend
        SUB  L          ; subtract low bytes, borrow in CY
        STA  2020H      ; store low byte of result
        MOV  A, D       ; A = high byte of minuend
        SBB  H          ; subtract high bytes with borrow
        STA  2021H      ; store high byte of result
        HLT

Example. Minuend $= 5A30_H$ and subtrahend $= 2B50_H$. Low bytes: $30-50 = E0$ with a borrow. High bytes: $5A-2B-1 = 2E$. Result $= 2EE0_H$, so 2020H $= E0_H$ and 2021H $= 2E_H$. Check: $5A30_H-2B50_H = 2EE0_H$. If the final CY is set, the result is negative (borrow out).

An Assembly Language Program (ALP) is a program written in mnemonics (such as MOV AX, BX) instead of binary machine code. A set of software tools is needed to turn the source text into a program that the 8086 can run and to find errors in it. These are the ALP development tools.

1. Editor

A text editor (EDIT, Notepad, or the editor of an IDE) is used to type the source program and save it with the extension .ASM. It produces plain ASCII text, with no formatting codes.

2. Assembler

The assembler (MASM, TASM, NASM) translates the .ASM source file into machine code.

• It converts mnemonics to opcodes, and labels and variable names to addresses.
• It processes assembler directives such as SEGMENT, ENDS, ASSUME, DB, DW, END.
• It reports syntax errors.
• It produces the object file (.OBJ) and, on request, a list file (.LST) showing the source with the generated code and addresses, and a cross-reference file (.CRF).

3. Linker

The linker (LINK, TLINK) combines one or more .OBJ files and library routines into a single executable.

• It resolves references between modules and library procedures.
• It assigns the final relative segment addresses.
• It produces the run (executable) file (.EXE) and a map file (.MAP) giving the start, stop and length of every segment.

4. Locator

For embedded systems the locator converts the relocatable .EXE into an absolute file with fixed memory addresses, so that it can be placed in the ROM/RAM of a target board. On a PC, DOS loads the program itself and no locator is needed.

5. Debugger

A debugger (DEBUG, TD, CodeView) is used to test the .EXE file. It allows:

• single stepping (trace) through the program,
• setting breakpoints and running up to them,
• viewing and modifying registers, flags and memory,
• finding logical errors that the assembler cannot detect.

6. Emulator

An emulator (e.g. EMU8086) imitates the 8086 on the host computer. It lets the program be run and observed without real hardware. In-circuit emulators are used in hardware development.

Development cycle

Editor  ->  prog.ASM  ->  Assembler  ->  prog.OBJ  ->  Linker  ->  prog.EXE  ->  Debugger / Run
   ^                                                                                   |
   +------------------------- correct errors <----------------------------------------+

Source is written once; errors found by the assembler (syntax), linker (unresolved references) or debugger (logic) send the programmer back to the editor.

LXI B, 1234H is a 3-byte instruction that loads the 16-bit data 1234H into the register pair BC, so that B = 12H and C = 34H.

The instruction takes 3 machine cycles and 10 T-states: one opcode fetch (4 T) and two memory read cycles (3 T each). Assume the instruction is stored at 2000H, 2001H and 2002H.

Timing diagram

        |<------- M1 (4T) ------>|<---- M2 (3T) --->|<---- M3 (3T) --->|
         T1   T2   T3   T4        T1   T2   T3        T1   T2   T3
CLK     _|-|_|-|_|-|_|-|_|-|_|-|_|-|_|-|_|-|_|-|_|-|_
A15-A8  [   20H   (PCH)       ][   20H (PCH)   ][   20H (PCH)   ]
AD7-AD0 [ 00H ][ 01H opcode  ][ 01H ][ 34H data ][ 02H ][ 12H data ]
          addr    in    decode  addr     in       addr     in
          (PCL)                 (PCL)             (PCL)
ALE     _|-|______  |-|_____      |-|_____
IO/M    ______________________ low (memory) ___________________
S1,S0   1  1  (fetch)             1  0  (read)      1  0  (read)
RD'     ______|-----|___ low T2-T3 ___|-----|___ low ___|-----

Explanation

M1: Opcode fetch (T1 to T4)

• T1: The program counter content 2000H is placed on the address lines. A15-A8 carry 20H and AD7-AD0 carry 00H. ALE goes high to latch the low-order address with an external latch. IO/M' = 0, S1 = S0 = 1 indicate an opcode fetch.
• T2: PC is incremented to 2001H. The RD' signal goes low and memory is enabled.
• T3: The opcode 01H is read from memory over AD7-AD0 into the instruction register, and RD' goes high.
• T4: The opcode is decoded. The decoder finds that two more bytes must be read, so two more machine cycles follow.

M2: Memory read (T1 to T3)

• The address 2001H is sent out (ALE high in T1), RD' goes low, and the byte 34H is read from memory and stored in register C. PC becomes 2002H.

M3: Memory read (T1 to T3)

• The address 2002H is sent out, RD' goes low, and the byte 12H is read and stored in register B. PC becomes 2003H, which points at the next instruction.

Totals: 4 + 3 + 3 = 10 T-states; with a 3 MHz clock this takes $10 \times 0.333\,\mu s = 3.33\,\mu s$.

The Central Processing Unit (CPU) is the part of the computer that fetches instructions from memory, decodes them and executes them. Its basic organization has three major parts: the Arithmetic Logic Unit (ALU), the register set and the control unit (CU), connected by internal buses.

Diagram

   +------------------------------- CPU --------------------------------+
   |                                                                     |
   |   +-----------+      +------------------+     +------------------+  |
   |   |  Control  |<---->|  Register set    |<--->|       ALU        |  |
   |   |   Unit    |      | PC  IR  MAR  MDR |     |  + Flags / PSW   |  |
   |   | (decoder, |      | ACC  R0..Rn  SP  |     +------------------+  |
   |   |  timing)  |      +------------------+                           |
   |   +-----+-----+                 ^                                   |
   +---------|-----------------------|-----------------------------------+
             | control signals       | internal bus
     Control bus           Address bus           Data bus
             |                     |                  |
        +----v---------------------v------------------v----+
        |   Main memory                 I/O devices        |
        +--------------------------------------------------+

Components

1. Arithmetic Logic Unit (ALU): performs arithmetic operations (add, subtract, multiply, divide) and logical operations (AND, OR, NOT, compare, shift). Its results set the status flags (zero, carry, sign, overflow).

2. Registers: fast storage inside the CPU.

   • Program counter (PC): holds the address of the next instruction.
   • Instruction register (IR): holds the instruction being executed.
   • Memory address register (MAR): holds the address to be accessed in memory.
   • Memory data register (MDR/MBR): holds the data read from or written to memory.
   • Accumulator and general purpose registers: hold operands and results.
   • Stack pointer (SP): points to the top of the stack.
   • Status/flag register: holds condition flags.

3. Control unit: it generates the timing and control signals that direct the operation of the ALU, registers, memory and I/O. It decodes the instruction in the IR. It may be hardwired or microprogrammed.

4. Internal buses: the paths for transferring data between registers and the ALU. The CPU connects to the outside through the address, data and control buses.

Instruction cycle

1. Fetch: MAR $\leftarrow$ PC; MDR $\leftarrow$ M[MAR]; IR $\leftarrow$ MDR; PC $\leftarrow$ PC + 1.
2. Decode: the control unit decodes the opcode in IR.
3. Execute: operands are fetched if necessary, the ALU or other units perform the operation, and the result is stored in a register or memory.

This cycle repeats for every instruction until the program halts.

In a microprogrammed control unit, control signals are produced by microinstructions stored in a control memory. The format of the microinstruction can be horizontal or vertical.

Example: to select one of 16 control signals, the horizontal format uses 16 bits (one bit each), whereas the vertical format uses a 4-bit field plus a $4 \times 16$ decoder, but then only one of the 16 signals can be active at a time.

Conclusion: horizontal microprogramming gives speed and parallelism at the cost of width; vertical microprogramming gives compact code at the cost of speed.

Register Transfer Language (RTL) is a symbolic notation used to describe the micro-operations (data transfers and operations among registers) of a digital system. For example, $R2 \leftarrow R1$ means the content of R1 is copied to R2, and $R3 \leftarrow R1 + R2$ means the sum of R1 and R2 is stored in R3. A control condition is written before a colon, for example $P: R2 \leftarrow R1$ (transfer only if P = 1).

RTL for the shift-add algorithm

Registers: M (multiplicand), Q (multiplier), A (accumulator, initially 0), C (carry flip-flop), SC (sequence counter = number of bits $n$).

Initialize:  A <- 0, C <- 0, M <- multiplicand, Q <- multiplier, SC <- n
Repeat n times:
    Q0 : A <- A + M, C <- Cout          (if multiplier bit Q0 = 1, add)
    Shift: C A Q <- shr (C A Q), C <- 0   (shift right C, A, Q together)
    SC <- SC - 1
    if SC != 0 repeat
Product is in A Q

Trace of 13 x 11 (4-bit numbers)

M = 13 = 1101, Q = 11 = 1011, A = 0000, C = 0, SC = 4.

After 4 steps SC = 0 and the product is AQ = 1000 1111.

Verification

$10001111_2 = 128 + 8 + 4 + 2 + 1 = 143$

$13 \times 11 = 143$

The product obtained matches the direct multiplication, so the result is correct.

RTL for Booth's algorithm

Registers: M (multiplicand), Q (multiplier), A (accumulator, initially 0), $Q_{-1}$ (extra flip-flop, initially 0), SC (counter = $n$).

Initialize: A <- 0, Q-1 <- 0, M <- multiplicand, Q <- multiplier, SC <- n
Repeat n times:
    Q0 Q-1 = 10 :  A <- A - M          (= A + M' + 1)
    Q0 Q-1 = 01 :  A <- A + M
    Q0 Q-1 = 00 or 11 : no operation
    Arithmetic shift right:  A Q Q-1 <- ashr (A Q Q-1)   (sign bit of A is kept)
    SC <- SC - 1
    if SC != 0 repeat
Product is in A Q

Multiplication of -13 and 3 (5-bit registers)

M = -13. In 5-bit two's complement: $+13 = 01101$, so $-13 = 10011$ and $-M = 01101$. Q = 3 = 00011. A = 00000, $Q_{-1}$ = 0, SC = 5.

Product AQ = 11110 11001 (10 bits).

Verification

The sign bit is 1, so the result is negative. Take the two's complement:

$1111011001 \rightarrow 0000100110 + 1 = 0000100111_2 = 32 + 4 + 2 + 1 = 39$

So the product is $-39$. Direct multiplication: $(-13) \times 3 = -39$. The results agree.

When a cache miss occurs and the cache (or the set, in a set-associative cache) is full, one existing block must be removed to make room for the new block. The rule used to choose that block is the replacement algorithm. In direct mapping there is no choice, because each block maps to exactly one line; algorithms are needed in associative and set-associative caches.

Types of replacement algorithms

1. Random: a block is chosen at random. Simple and cheap in hardware, with performance only slightly worse than the others.
2. FIFO (First In First Out): the block that has been in the cache longest is replaced. Easy to implement with a queue, but it may remove a block that is still heavily used.
3. LRU (Least Recently Used): the block that has not been used for the longest time is replaced. It relies on locality of reference and normally gives the best hit ratio, but needs a usage record (counters or a stack) per block.
4. LFU (Least Frequently Used): the block with the fewest references is replaced, using a counter for each block.
5. Optimal (Belady): replaces the block that will not be needed for the longest time in the future. It cannot be implemented in practice and is used only as a benchmark.

Cache hit and miss

• Hit: the requested block is found in the cache; the data is supplied quickly and no replacement happens (LRU just updates the usage record).
• Miss: the block is not in the cache; it is fetched from main memory. If the cache is full the replacement algorithm picks a victim, and the new block is loaded in its place.

Example: LRU with a 3-block cache

Block reference string: 2, 3, 2, 1, 5, 2, 4, 5, 3

There are 3 hits and 6 misses, so the hit ratio is $3/9 = 0.33$.

For comparison, FIFO on the same string gives only 2 hits (the third reference to 2 and the second reference to 5) and 7 misses, because it evicts block 2 when 5 arrives even though 2 was just used. LRU does better here because it exploits locality of reference.

Direct Memory Access (DMA) is a technique in which an I/O device transfers a block of data directly to or from main memory without passing through the CPU for each word. A special hardware unit, the DMA controller (DMAC), takes control of the system buses and carries out the transfer, so the CPU is freed for other work.

Block diagram

        +---------+   HOLD / HRQ     +------------------+
        |         |<-----------------|                  |
        |   CPU   |   HLDA / HACK    |  DMA controller  |
        |         |----------------->| Address register |
        +----+----+                  | Word count reg.  |
             |                       | Control register |
             |                       +---+----------+---+
             |                           |DREQ  ^   | DACK
   =======================================|======|===|=====  System bus
   Address / Data / Control              |      |   v
             |                       +---v------+--------+
        +----v-----+                 |   I/O device      |
        |  Memory  |<--------data----|  (disk, etc.)     |
        +----------+                 +-------------------+

Operation (steps)

1. The CPU programs the DMA controller: it loads the starting memory address in the address register, the number of words to transfer in the word count register, and the direction (read or write) in the control register.
2. The CPU then continues with other work.
3. When the I/O device is ready it sends a DMA request (DREQ) to the controller.
4. The controller sends a bus request (HOLD/BR) to the CPU.
5. After finishing its current bus cycle, the CPU floats the buses and replies with a bus grant (HLDA/BG).
6. The controller sends a DMA acknowledge (DACK) to the device and puts the memory address on the address bus. The data moves between the device and memory directly, with read/write signals from the controller.
7. After each word the address register is incremented and the word count is decremented.
8. When the count reaches zero, the controller releases the bus and sends an interrupt to the CPU to say that the transfer is complete.

Transfer modes

• Burst (block) mode: the whole block is transferred in one go while the CPU is held off the bus.
• Cycle stealing: the controller takes the bus for one word at a time, stealing a memory cycle from the CPU.
• Transparent mode: transfers occur only when the CPU is not using the bus.

Advantages: high data transfer rate, low CPU overhead, suitable for fast devices such as disks.

In a MIMD (Multiple Instruction, Multiple Data) system, several processors, each running its own instruction stream on its own data, are linked by an interconnection network. The choice of topology determines cost, speed, and fault tolerance. The main topologies are as follows.

1. Shared bus

All processors and memory modules are connected to one common bus.

 P1   P2   P3   P4   M
 |    |    |    |    |
=============================  common bus

• Simple and cheap and easy to expand.
• Only one transfer at a time, so the bus becomes a bottleneck when the number of processors increases.

2. Ring

Each processor is connected to exactly two neighbours, forming a closed loop.

   P1 --- P2
   |       |
   P4 --- P3

• Simple, low cost, and each node has only 2 links.
• The maximum distance is $N/2$ hops, so latency grows with $N$; the failure of one link breaks the ring unless it is bidirectional.

3. Mesh (2-D grid) and torus

Processors are arranged in a rows-and-columns grid, each linked to its 4 neighbours (a torus adds wrap-around links).

 P--P--P
 |  |  |
 P--P--P
 |  |  |
 P--P--P

• Good scalability; the diameter is about $2(\sqrt{N}-1)$.
• Messages may need many hops.

4. Hypercube

$N = 2^n$ processors, each connected to $n$ others, whose binary addresses differ in one bit.

      010 ------- 011
      /|          /|
   000 ------- 001 |
    |  110 -----|- 111
    | /         | /
   100 ------- 101

A 3-cube has 8 nodes, 3 links per node and diameter 3.

• Low diameter ($\log_2 N$) and many alternate paths; but the number of links per node grows with $\log_2 N$.

5. Crossbar switch

Every processor is connected to every memory module through a matrix of switches.

        M1   M2   M3
  P1 ---+----+----+
  P2 ---+----+----+
  P3 ---+----+----+

• Non-blocking, allowing several simultaneous transfers (very high bandwidth).
• Cost grows as $N^2$ switches, so it is expensive for large $N$.

6. Multistage interconnection network (e.g. Omega network)

Several stages of small $2\times2$ switches connect $N$ inputs to $N$ outputs using $\tfrac{N}{2}\log_2 N$ switches. It is cheaper than a crossbar but may suffer blocking.

7. Tree and fully connected networks

In a tree, nodes are arranged hierarchically (the root can become a bottleneck). In a fully connected network each processor links to all others, giving fastest communication but needing $N(N-1)/2$ links.

Microprocessor is a single-chip CPU that contains the ALU, registers and control unit, but memory and I/O devices must be added externally. Examples: 8085, 8086, Intel Core. It is used in general-purpose systems such as personal computers.

Microcontroller is a single chip that contains a CPU together with on-chip RAM, ROM/flash, timers, serial ports, I/O ports and often an ADC. Examples: 8051, PIC, AVR (Arduino). It is used in dedicated embedded systems such as washing machines and remote controls.

In short, a microprocessor is the "brain" of a general computer, while a microcontroller is a complete small computer on a chip designed for control tasks.

Flynn's taxonomy (M. J. Flynn, 1966) classifies computer architectures by the number of instruction streams and data streams that they can process at the same time.

1. SISD (Single Instruction, Single Data) A single processor executes one instruction stream on one data stream. This is the conventional von Neumann uniprocessor, for example an old PC.

2. SIMD (Single Instruction, Multiple Data) One control unit broadcasts the same instruction to many processing elements, each working on its own data. Used in array/vector processors and GPUs for image processing and matrix operations.

3. MISD (Multiple Instruction, Single Data) Several processors execute different instructions on the same data stream. It is rarely used in practice; fault-tolerant systems and systolic arrays are given as examples.

4. MIMD (Multiple Instruction, Multiple Data) Several processors independently execute different instructions on different data. Multiprocessors (shared memory) and multicomputers/clusters (distributed memory) belong to this class, as do modern multicore CPUs.

          Single Data   Multiple Data
Single Inst.   SISD          SIMD
Multiple Inst. MISD          MIMD

The classification is simple, but it does not distinguish all organisations (e.g. pipelined processors).

Microprocessor

A microprocessor is a programmable electronic device that integrates the functions of the central processing unit (CPU) of a computer on a single VLSI chip. It fetches instructions from memory, decodes and executes them, performs arithmetic and logic operations, and controls the other parts of the system. It is clocked and works on binary data. Examples are Intel 8085, 8086 and the Core series. Internally it has an ALU, a set of registers and a control unit.

Basic components of a computer system

          +-----------+     +-----------+
 Input -->|           |<--->|  Memory   |
 device   |    CPU    |     +-----------+
          | (ALU, CU, |
 Output <-|  registers)|
 device   +-----------+
        (connected by address, data, control buses)

1. Central Processing Unit (CPU): the microprocessor. It contains the arithmetic logic unit (ALU) for calculations and logic, the control unit (CU) for timing and control signals, and registers for temporary storage. It executes the program.
2. Memory:
   • Primary memory: ROM (non-volatile, holds the boot program/firmware) and RAM (volatile, holds the running programs and data).
   • Secondary memory: hard disk, SSD, etc. for permanent bulk storage.
3. Input devices: supply data and instructions to the computer, for example keyboard, mouse, scanner.
4. Output devices: present results to the user, for example monitor, printer, speaker.
5. System buses: the groups of lines linking the components: the address bus (carries the memory/I/O address, one way), the data bus (carries data, two way) and the control bus (carries signals such as RD, WR, clock, interrupt).
6. I/O interface: circuits that match the speed and format of the peripherals to the CPU.

The CPU, memory and I/O communicate over the buses; the program stored in memory is fetched and executed by the CPU, which takes data from the input devices and sends results to the output devices.

MVI r, data is a 2-byte instruction that loads an 8-bit immediate data byte into a register. For example, MVI B, 32H has the opcode 06H in the first byte and 32H in the second byte. It needs 2 machine cycles and 7 T-states: an opcode fetch cycle (4 T) and a memory read cycle (3 T). Assume it is stored at 2000H and 2001H.

Timing diagram

          |<------- M1: Opcode fetch (4T) ------>|<---- M2: Memory read (3T) --->|
           T1    T2    T3    T4                    T1    T2    T3
CLK       _|-|__|-|__|-|__|-|__|-|__|-|__|-|__
A15-A8    [          20H (PCH)             ]  [        20H (PCH)         ]
AD7-AD0   [ 00H ][  06H opcode in  ][ decode ][ 01H ][   32H data in      ]
ALE       __|---|________________________      |---|_____________________
IO/M'     __________ 0 (memory) ____________________ 0 (memory) __________
S1 S0     ___ 1 1 (opcode fetch) ___________   ___ 1 0 (memory read) ____
RD'       ________|---------------|_____      ______|---------------|____
                  (low in T2,T3)                    (low in T2,T3)

Explanation

Machine cycle M1: opcode fetch

• T1: The content of the program counter (2000H) is put on the address bus. The high byte 20H is on A15-A8 and the low byte 00H on the multiplexed AD7-AD0. ALE goes high so that the low byte can be latched. IO/M' = 0 and S1 S0 = 11 show that this is an opcode fetch from memory.
• T2: The PC is incremented to 2001H. RD' goes low, and the memory is told to place the content of 2000H on the data bus.
• T3: The opcode 06H arrives on AD7-AD0 and is placed in the instruction register. RD' goes high.
• T4: The instruction decoder decodes 06H as MVI B and finds that one more byte (the data) is needed.

Machine cycle M2: memory read

• T1: The address 2001H is placed on the address bus; ALE is high to latch 01H. S1 S0 = 10 (memory read).
• T2: RD' goes low and the memory puts the data byte 32H on the data bus. PC becomes 2002H.
• T3: The 8085 reads the data 32H and stores it in register B. RD' goes high.

Total: 4 + 3 = 7 T-states. If the clock is 3 MHz, execution time is $7 \times 0.333 = 2.33\,\mu s$.

(For MVI M, data the instruction needs an additional memory write cycle and takes 10 T-states.)

The 8085 has 74 instructions (246 opcodes). They are grouped into five functional categories. By size, instructions are 1-byte, 2-byte or 3-byte.

1. Data transfer (copy) instructions

Copy data between registers, memory and I/O without changing the source and without affecting flags.

• MOV A, B : copy register to register; MOV M, A : register to memory (address in HL).
• MVI B, 32H : load an immediate 8-bit value.
• LXI H, 2050H : load a register pair with 16-bit data.
• LDA 2000H, STA 2001H : load or store the accumulator from a direct address.
• LDAX B, STAX D, LHLD, SHLD, XCHG, IN port, OUT port, PUSH, POP.

2. Arithmetic instructions

• Addition: ADD B, ADD M, ADI 05H, ADC B, ACI, DAD H (16-bit add).
• Subtraction: SUB B, SUI, SBB, SBI.
• Increment/decrement: INR B, DCR C, INX H, DCX D.
• Decimal adjust: DAA. These affect the flags (S, Z, AC, P, CY) except INX/DCX which affect none.

3. Logical instructions

• ANA B, ANI 0FH (AND), ORA B, ORI (OR), XRA B, XRI (XOR).
• CMP B, CPI 40H : compare, setting flags without changing A.
• Rotate: RLC, RRC, RAL, RAR.
• CMA (complement accumulator), CMC (complement carry), STC (set carry).

4. Branching instructions

Change the sequence of execution.

• Unconditional: JMP addr, CALL addr, RET, PCHL.
• Conditional: JZ, JNZ, JC, JNC, JP, JM, JPE, JPO and conditional CALL/RET (CZ, RNZ, ...).
• RST n : restart (call to a fixed address).

5. Machine control instructions

• NOP : no operation, HLT : halt.
• EI, DI : enable/disable interrupts.
• RIM, SIM : read/set interrupt masks and serial I/O.

By instruction word length

• 1-byte: MOV A,B, ADD C, HLT
• 2-byte: MVI A, 05H, ADI 02H, IN 80H
• 3-byte: LXI H, 2000H, LDA 2050H, JMP 3000H

The addressing modes used are immediate, register, direct, indirect and implicit.

Problem: add 10 bytes stored in consecutive memory locations starting at 2000H and store the result in memory. Because the sum of 10 bytes can exceed 255, the carry is also counted, and the 16-bit result is stored: low byte at 3000H and high byte at 3001H.

Algorithm

1. Point HL to the first byte (2000H), set the counter C = 10, clear A (sum) and B (carry count).
2. Add the byte pointed by HL to A. If a carry results, increment B.
3. Increment HL and decrement the counter; repeat until the counter is zero.
4. Store A (low byte) at 3000H and B (high byte) at 3001H.

Program

        LXI  H, 2000H     ; HL points to the first data byte
        MVI  C, 0AH       ; counter = 10
        MVI  A, 00H       ; sum = 0
        MOV  B, A         ; B = 0 (carry count)
LOOP:   ADD  M            ; A = A + [HL]
        JNC  SKIP         ; no carry, go on
        INR  B            ; count the carry
SKIP:   INX  H            ; next memory location
        DCR  C            ; decrement counter
        JNZ  LOOP         ; repeat until C = 0
        STA  3000H        ; store low byte of sum
        MOV  A, B
        STA  3001H        ; store high byte (carries)
        HLT

Example: if all ten bytes are FFH, each addition after the first generates a carry, and the final sum is $10 \times 255 = 2550 = 09F6H$. The program stores F6H at 3000H and 09H at 3001H.

If the sum is known to fit in 8 bits, the carry handling (JNC, INR B, and the second store) can be omitted.

The 8086 is a 16-bit microprocessor with a 16-bit data bus and a 20-bit address bus (addressing 1 MB). Its functional block diagram consists of two units that operate concurrently: the Execution Unit (EU) and the Bus Interface Unit (BIU).

Block diagram

 +----------------------------- BIU -----------------------------+
 | CS | DS | SS | ES | IP     ->  Adder (segment x 16 + offset)  |
 | 6-byte instruction queue    ->  Bus control logic             |
 +---------------------------------------+-----------------------+
        ^ 20-bit address / 16-bit data     | queue output
        v system bus                       v
 +----------------------------- EU ------------------------------+
 | Control unit / decoder | ALU | Flags                          |
 | AX BX CX DX | SP BP SI DI                                     |
 +---------------------------------------------------------------+

Bus Interface Unit (BIU)

• Fetches instructions from memory and places them in the 6-byte queue (prefetching).
• Reads operands from, and writes results to, memory and I/O devices when the EU requests.
• Contains the segment registers CS, DS, SS, ES and the instruction pointer IP.
• The address adder computes the 20-bit physical address as segment $\times$ 16 + offset.
• The bus control logic generates control signals for the system bus.

Execution Unit (EU)

• Gets opcodes from the queue, decodes them and executes them.
• ALU: 16-bit arithmetic and logic operations.
• General registers: AX, BX, CX, DX (split into high and low 8-bit halves).
• Pointer and index registers: SP, BP, SI, DI.
• Flag register: status flags CF, PF, AF, ZF, SF, OF and control flags TF, IF, DF.
• Control circuitry generates timing and internal control signals.

Advantage: since the BIU fetches the next instruction while the EU executes the current one, the processor overlaps fetching and execution (pipelining), reducing idle time of the bus and increasing throughput.

Registers are small, very fast storage locations inside the microprocessor used to hold data, addresses and status information. They are much faster than main memory. Registers are classified as follows (with 8085 examples).

1. General purpose registers Hold data and intermediate results and can be used by the programmer for any purpose. The 8085 has six 8-bit registers B, C, D, E, H, L, which can work in pairs BC, DE, HL for 16-bit data. HL also holds the memory address (the memory pointer M).

2. Accumulator (A) An 8-bit register that is the main operand and result register of the ALU: for arithmetic and logic operations one operand is in A and the result is placed back in A. It is also used for I/O data transfer.

3. Program counter (PC) A 16-bit register holding the address of the next instruction to be fetched. It is automatically incremented after each fetch.

4. Stack pointer (SP) A 16-bit register pointing to the top of the stack in memory, used in PUSH, POP, CALL and RET.

5. Instruction register (IR) Holds the opcode of the instruction being executed, which is passed to the decoder. It is not accessible to the programmer.

6. Flag (status) register Holds the condition flags set by ALU operations: Sign (S), Zero (Z), Auxiliary carry (AC), Parity (P) and Carry (CY) in the 8085.

7. Temporary registers W and Z (in 8085) are used internally during instruction execution (such as CALL, XCHG); they are not available to the user.

8. Memory address register (MAR) and memory data register (MDR/MBR) MAR holds the address of the memory location to be accessed; MDR holds the data being read or written. They interface the CPU with the buses.

9. Segment, pointer and index registers (in 8086) Segment registers CS, DS, SS, ES hold the segment base addresses; pointer registers SP and BP and index registers SI and DI hold offsets for addressing and string operations; IP is the instruction pointer.

Registers can thus be user-accessible (general, accumulator, flag, SP, segment) or internal (IR, temporary, MAR, MDR).

The control unit generates the control signals that direct the operations of the processor. In a microprogrammed control unit these signals are produced not by fixed logic gates but by reading microinstructions from a special memory called the control memory. Each machine instruction is executed by a sequence of microinstructions called a microprogram (or routine).

Basic terms

• Microoperation: an elementary register-level operation, for example $MAR \leftarrow PC$.
• Microinstruction: a control word that specifies one or more microoperations and the address of the next microinstruction.
• Microprogram: a set of microinstructions that implements one machine instruction.
• Control memory (control store): ROM storing all microprograms.

Organisation

 Opcode in IR --> Mapping logic --> Control Address Register (CAR) <--+
                                           |                         |
                                           v                         |
                                   Control memory (ROM)              |
                                           |                         |
                                           v                         |
                                 Control Data Register (CDR)         |
                                    |                |               |
                                    v                v               |
                           Control signals    Next-address field --> Sequencing logic
                           (to ALU, registers, bus)                  (branch, status flags)

Working

1. The opcode of the fetched instruction (in IR) is converted by the mapping logic into the starting address of its microprogram in control memory, and loaded into the control address register (CAR).
2. The microinstruction at that address is read into the control data register (CDR).
3. Its control fields are decoded or applied directly to produce the control signals that perform the micro-operations.
4. The address field and the sequencing logic then determine the next address: the CAR is incremented, loaded with a branch address, or loaded with the starting address of the next instruction's microprogram.
5. The microprogram ends by jumping back to the fetch routine.

Microinstruction format: a typical format has fields for the control signals (micro-operations), a condition-select field, a branch/address field. It can be horizontal (wide, little encoding) or vertical (narrow, encoded).

Advantages

• Systematic and flexible; it is simple to modify or add instructions by changing the microprogram.
• Easy to design and test, and the design cost is low for complex instruction sets.
• Allows emulation of other machines.

Disadvantages

• Slower than hardwired control because of the control memory access time.
• Control memory adds cost for simple processors.

It is widely used in CISC processors, whereas RISC processors usually use hardwired control.

Microinstructions are stored in control memory, and after each one the control unit must determine the address of the next microinstruction. Microinstruction sequencing is the way this address is generated. The control address register (CAR) is loaded by the sequencing logic in the following ways.

1. Incrementing the CAR Normally microinstructions of a routine are stored in consecutive locations, so the next address is $CAR \leftarrow CAR + 1$. This is the default sequential flow.

2. Unconditional branch The microinstruction contains an address field, and the CAR is loaded with this address, $CAR \leftarrow AD$. It is used for jumps within the microprogram.

3. Conditional branch A condition (status bit such as zero, carry, sign, overflow) is tested. If the condition is true, then $CAR \leftarrow AD$; otherwise $CAR \leftarrow CAR + 1$. A condition-select field in the microinstruction chooses which status bit is tested through a multiplexer.

4. Mapping from the opcode At the end of the fetch routine, the opcode in IR is mapped to the starting address of the corresponding execution routine. For example, with a 4-bit opcode, address $= 0\,\text{opcode}\,00$ gives each instruction a 4-word routine (mapping by appending bits).

5. Subroutine call and return A common microroutine (such as the effective address calculation) can be shared. A call loads the CAR with the subroutine address and saves the return address ($CAR+1$) in a subroutine register (SBR) or stack; return loads the CAR from the SBR.

6. Return to fetch At the end of each execution routine, the CAR is loaded with the address of the instruction fetch microroutine (usually address 0).

Sequencing logic hardware

 Opcode ---> Mapping logic ---+
 Branch address (AD) --------+--> MUX --> CAR --> Control memory
 SBR (return address) -------+      ^
 CAR + 1 (incrementer) ------+      | select from
                             Condition tests + microinstruction (MUX select)

The multiplexer selects one of these sources according to the branch type and the test result. Two methods of sequencing are used: explicit (each microinstruction contains the next address) and implicit (the next address is $CAR + 1$ unless a branch is specified), the latter needing a shorter microinstruction.

Use Booth's algorithm with M = multiplicand = -9 and Q = multiplier = 6. Using 5-bit registers:

$+9 = 01001$, so $-9 = 10111$ (M), and $-M = 01001$. Q = 6 = 00110. A = 00000, $Q_{-1}$ = 0, count = 5.

The rules are: for $Q_0 Q_{-1}$ = 10, $A \leftarrow A - M$; for 01, $A \leftarrow A + M$; for 00 or 11, do nothing; then arithmetic shift right A, Q, $Q_{-1}$.

Product AQ = 11110 01010.

Verification

The sign bit is 1 so the product is negative. Two's complement of 1111001010:

$0000110101 + 1 = 0000110110_2 = 32 + 16 + 4 + 2 = 54$

Therefore the product is $-54$, and $(-9) \times 6 = -54$, which confirms the result.

Requirement: connect a 2 KB RAM and a 4 KB RAM to the 8085, which has a 16-bit address bus (A15-A0), an 8-bit data bus, and control signals $\overline{RD}$, $\overline{WR}$, IO/$\overline{M}$.

Address lines needed

• 2 KB = $2^{11}$ bytes, so the chip needs 11 address lines (A10-A0).
• 4 KB = $2^{12}$ bytes, so the chip needs 12 address lines (A11-A0).
• The remaining higher lines are used to generate the chip select signals through a decoder.

Address map chosen

Decoding logic

A 74LS138 (3-to-8) decoder is used.

• Select inputs: A = A12, B = A13, C = A14.
• Enables: G1 = $\overline{A15}$ (via a NOT gate), $\overline{G2A}$ = $\overline{G2B}$ = IO/$\overline{M}$ (so the decoder works only for memory operations, when IO/$\overline{M}$ = 0, and A15 = 0).
• Output $\overline{Y1}$ (A14 A13 A12 = 001) is active for 1000H-1FFFH, so it is connected directly to $\overline{CS}$ of the 4 KB RAM.
• Output $\overline{Y0}$ (A14 A13 A12 = 000) is active for 0000H-0FFFH. To restrict it to 2 KB, it is ORed with A11: $\overline{CS_1} = \overline{Y0} + A11$, which is low only when $\overline{Y0}$ = 0 and A11 = 0, i.e. 0000H-07FFH.

Connections

 A0-A7  --> latch (74LS373, ALE) <-- AD0-AD7 ;  A8-A15 from the 8085 directly
 A0-A10  ----------------------------> RAM1 (2KB) address pins
 A0-A11  ----------------------------> RAM2 (4KB) address pins
 D0-D7   (AD0-AD7 data) -------------> data pins of both RAMs
 RD' ---> OE' of both ;  WR' ---> WE' of both
 A12,A13,A14 --> 74LS138 A,B,C ; A15 -> NOT -> G1 ; IO/M -> G2A', G2B'
 Y0' --OR(A11)--> CS' of RAM1 ;  Y1' ---------------> CS' of RAM2

Working: when the 8085 issues a memory address in 0000H-07FFH, A15-A11 = 00000, so CS of RAM1 goes low and only RAM1 responds; for an address 1000H-1FFFH, A15-A12 = 0001 and only RAM2 is enabled. Since the two ranges do not overlap, there is no bus conflict. The $\overline{RD}$ and $\overline{WR}$ signals then perform the read and write on the selected chip.

There are three methods of transferring data between an I/O device and memory.

Programmed I/O The CPU executes a program that repeatedly tests (polls) the device status flag until the device is ready, and then transfers each word through the CPU. The CPU is kept busy in a wait loop for the entire transfer, and can do no other useful work.

Interrupt-driven I/O The CPU starts the I/O and carries on with other work. When the device is ready, it interrupts the CPU, which saves its state, runs an interrupt service routine to transfer one word through the CPU, and returns. The busy-waiting is gone, but each word still costs the overhead of the interrupt, saving and restoring registers.

DMA (Direct Memory Access) The CPU initialises the DMA controller with the memory address and word count; the controller then moves the whole block between the device and memory directly over the bus, interrupting the CPU only once at the end.

Why DMA is better

For example, to read 1000 words, interrupt-driven I/O needs 1000 interrupts and 1000 context switches, whereas DMA needs one set-up and one completion interrupt. The CPU in the meantime executes other programs, so system throughput increases. The disadvantage is the cost and complexity of the extra DMA hardware and the fact that the DMA controller steals bus cycles from the CPU.

Flynn's taxonomy, proposed by Michael J. Flynn in 1966, classifies computer organisations according to the multiplicity of instruction streams (the sequence of instructions executed) and data streams (the sequence of data operated on). Combining single/multiple for each gives four classes.

                    Data stream
                 Single      Multiple
Instruction  Single   SISD        SIMD
stream     Multiple   MISD        MIMD

1. SISD (Single Instruction stream, Single Data stream)

  CU ---IS---> PU <---DS---> Memory

• One control unit, one processing unit, one memory.
• Instructions execute sequentially, though they may be pipelined.
• This is the traditional uniprocessor (von Neumann machine), e.g. a conventional PC with one core.

2. SIMD (Single Instruction stream, Multiple Data streams)

              +--> PU1 <--> M1
  CU --IS-----+--> PU2 <--> M2
              +--> PUn <--> Mn

• A single control unit sends the same instruction to all processing units, and each operates on a different data item in lock step.
• Suited to regular data-parallel problems: vector and matrix operations, image processing, graphics.
• Examples: array processors, vector processors, GPUs, Intel SSE/AVX units.

3. MISD (Multiple Instruction streams, Single Data stream)

  CU1 --IS1--> PU1 \
  CU2 --IS2--> PU2  >--- same DS passes through
  CUn --ISn--> PUn /

• Several processing units perform different operations on the same data stream.
• Very few real machines exist; systolic arrays and some fault-tolerant designs (the same data processed by different programs for checking) are quoted as examples.

4. MIMD (Multiple Instruction streams, Multiple Data streams)

  CU1 --IS1--> PU1 <--DS1--> M1
  CU2 --IS2--> PU2 <--DS2--> M2        (connected by an
  CUn --ISn--> PUn <--DSn--> Mn         interconnection network)

• Each processor has its own control unit and runs its own program on its own data, asynchronously.
• Shared-memory (tightly coupled) multiprocessors and distributed-memory (loosely coupled) multicomputers or clusters are both MIMD.
• Examples: multicore processors, supercomputers, server clusters.

Evaluation: Flynn's classification is simple and widely used, but it is coarse: it does not separate shared and distributed memory, and pipelined/vector machines are hard to place.

A signed number needs a way to show whether it is positive or negative. In a computer the sign is stored as a bit, so a signed number in $n$ bits is stored in one of three standard forms. In each, the leftmost bit (MSB) is 0 for positive and 1 for negative.

1. Signed-magnitude. The MSB is the sign and the remaining $n-1$ bits hold the magnitude.

• $+5 = 0000\,0101$ and $-5 = 1000\,0101$ (8 bits).
• Range: $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$, so 8 bits give $-127$ to $+127$.
• Zero has two forms, $+0 = 00000000$ and $-0 = 10000000$, and the adder needs extra logic to handle signs.

2. 1's complement. A negative number is obtained by inverting every bit of the positive number.

• $+5 = 00000101$, so $-5 = 11111010$.
• Range is the same as signed-magnitude, and zero again has two forms ($00000000$ and $11111111$).
• Addition needs an end-around carry.

3. 2's complement. A negative number is the 1's complement plus 1.

• $-5 = 11111010 + 1 = 11111011$.
• Range: $-2^{n-1}$ to $+(2^{n-1}-1)$, so 8 bits give $-128$ to $+127$.
• Zero has one form only.
• Addition and subtraction use the same binary adder, and the sign bit takes part in the addition. For this reason almost all computers use 2's complement.

Example, $7 - 5$ in 8 bits: $00000111 + 11111011 = 1\,00000010$. Discarding the carry out gives $00000010 = +2$.

Overflow occurs when two numbers of the same sign give a result of the opposite sign.

Cache memory is a small, very fast memory placed between the CPU and main memory. It holds copies of the instructions and data the CPU is most likely to need next, so that most memory accesses are served at cache speed instead of the slower main-memory (DRAM) speed.

Principle: locality of reference.

• Temporal locality: an item used recently is likely to be used again soon (loops).
• Spatial locality: items near a used item are likely to be used soon (sequential code, arrays).

Operation. The CPU first looks in the cache.

• If the word is found, this is a hit and the word is delivered quickly.
• If not found, this is a miss. The whole block containing the word is fetched from main memory into the cache, and the word is passed to the CPU.

$\text{Hit ratio } h = \frac{\text{number of hits}}{\text{total references}}$

$t_{avg} = h\,t_{c} + (1-h)\,t_{m}$

For example, with $h = 0.9$, $t_c = 10$ ns and $t_m = 100$ ns, $t_{avg} = 0.9(10) + 0.1(100) = 19$ ns.

Mapping techniques.

• Direct mapping: each main-memory block maps to exactly one cache line (line = block mod number of lines). It is simple but suffers conflicts.
• Associative mapping: a block can go in any line. It is flexible but needs expensive comparison hardware.
• Set-associative mapping: the cache is divided into sets, and a block maps to one set but can use any line in it. It is a compromise.

Write policies. Write-through updates cache and memory together. Write-back updates memory only when the block is replaced.

Replacement algorithms. LRU, FIFO and random.

Levels L1, L2 and L3 are used in modern processors.

Microprocessor. A microprocessor is a programmable, clock-driven, register-based integrated circuit that acts as the CPU of a computer on a single chip. It fetches instructions from memory, decodes and executes them, and uses arithmetic and logic operations to process data. Its main parts are the ALU, register array and control unit. Examples are the Intel 8085 and 8086.

Buses. A bus is a group of parallel lines used to carry information between the microprocessor, memory and I/O devices. A microprocessor system uses three buses.

1. Address bus.

• It is unidirectional, carrying addresses from the CPU to memory and I/O devices.
• It selects the memory location or port to be accessed.
• If it has $n$ lines, it can address $2^n$ locations. The 8085 has 16 address lines, so it can address $2^{16} = 64$ KB. The 8086 has 20 lines, which gives 1 MB.

2. Data bus.

• It is bidirectional, carrying data between the CPU, memory and I/O devices in either direction.
• Its width decides the word size of the processor. The 8085 has an 8-bit data bus and the 8086 has a 16-bit data bus.
• The 8085 multiplexes the lower address lines with the data lines (AD0 to AD7). The ALE signal tells when the lines carry an address, so that an external latch can hold it.

3. Control bus.

• It carries timing and control signals that coordinate all operations.
• Signals that originate in the CPU include $\overline{RD}$, $\overline{WR}$, $IO/\overline{M}$, ALE and S0, S1.
• Signals that come into the CPU include READY, HOLD, INTR and RESET.
• It ensures that only one device places data on the bus at a given time.

Thus the address bus says where, the data bus carries what, and the control bus says when and how the transfer is done.

SAP-1 (Simple-As-Possible 1) is a simple 8-bit teaching computer with a 4-bit address and 16 bytes of memory.

Block diagram.

         +--------------------- W bus (8 bits) ----------------------+
         |      |        |        |       |        |        |        |
      +--+--+ +-+--+ +---+--+ +---+--+ +--+---+ +--+---+ +--+---+ +--+---+
      | PC  | |MAR | | RAM  | |  IR  | | ACC  | | ALU  | | B reg| |Output|
      |(4b) | |(4b)| |16x8  | |(8b)  | | (A)  | |(+/-) | |      | | reg  |
      +-----+ +----+ +------+ +--+---+ +------+ +------+ +------+ +--+---+
                                 | upper 4 bits                       |
                         +-------+--------+                      Binary display
                         | Controller-    |<-- Clock, Clear
                         | Sequencer      |--> 12-bit control word
                         +----------------+

Components.

• Program Counter (PC): a 4-bit counter holding the address of the next instruction. It is incremented after each fetch.
• MAR: holds the 4-bit address sent to RAM.
• RAM: 16 x 8 memory holding program and data.
• Instruction Register (IR): holds the fetched instruction. The upper nibble goes to the controller and the lower nibble (address) goes back to the bus.
• Accumulator (A): 8-bit register holding intermediate results.
• Adder/Subtractor (ALU): computes $A + B$ or $A - B$, using 2's complement for subtraction.
• B register: holds the second operand.
• Output register: sends the result to the binary display.
• Controller-sequencer: ring counter of six T states, producing the 12-bit control word.

Instruction set. Each instruction is 8 bits, 4 bits opcode and 4 bits address.

Every instruction is executed in 6 T states: T1 to T3 are the fetch cycle (address, increment and memory states) and T4 to T6 are the execute cycle. SAP-1 is a memory-reference machine, and OUT and HLT do not need an address.

SAP-1 can load, add, subtract, output and halt only. The values are $33 = 21H$, $42 = 2AH$ and $25 = 19H$, stored in locations BH, CH and DH. The result is also saved in EH, which needs a store (STA) instruction. SAP-1 has none, so the program uses an STA extension (opcode 0100) for that one step.

Memory map.

Execution.

• LDA BH: $A = 33$.
• SUB CH: $A = 33 - 42 = -9$, which is $11110111_2 = F7H$ in 2's complement.
• ADD DH: $A = F7H + 19H = 110H$. The carry is dropped, so $A = 10H = 16_{10}$.
• STA EH: $M[EH] = 10H$.
• OUT: the display shows $00010000 = 16$.
• HLT.

Check: $33 - 42 + 25 = 16$.

The SUB instruction has the form SUB addr, and it computes $A \leftarrow A - M[addr]$. Like all SAP-1 instructions it takes 6 T states, called the fetch cycle (T1 to T3) and the execution cycle (T4 to T6).

Fetch cycle (same for every instruction).

• T1, address state: $E_p = 1$, $L_m = 1$. The PC contents go to the MAR. Control word 5E3H.
• T2, increment state: $C_p = 1$. The PC is incremented. Control word BE3H.
• T3, memory state: $CE = 1$, $L_i = 1$. RAM output goes into the IR. Control word 263H.

Execution cycle for SUB addr.

• T4: $E_i = 1$, $L_m = 1$. The address field of the IR goes to the MAR. Control word 1A3H.
• T5: $CE = 1$, $L_b = 1$. The addressed data word goes from RAM to the B register. Control word 2E1H.
• T6: $E_u = 1$, $S_u = 1$, $L_a = 1$. The ALU computes $A + \overline{B} + 1 = A - B$ and the result is loaded into A. Control word 3CFH.

The control word format is $C_p\,E_p\,\overline{L_m}\,\overline{CE}\,\overline{L_i}\,\overline{E_i}\,\overline{L_a}\,E_a\,S_u\,E_u\,\overline{L_b}\,\overline{L_o}$.

Flow diagram.

T1: PC -> MAR          (Ep, Lm)
T2: PC <- PC + 1       (Cp)
T3: RAM -> IR          (CE, Li)
T4: IR(addr) -> MAR    (Ei, Lm)
T5: RAM -> B           (CE, Lb)
T6: A <- A - B         (Su, Eu, La)

The only difference from ADD is that $S_u = 1$ in T6, which makes the adder/subtractor take the 2's complement of B (control word 3CFH instead of 3C7H).

SAP-2 is an enlarged design of SAP-1, closer to a real microprocessor such as the 8085.

Architectural contrast.

Benefits of SAP-2.

1. It addresses 64 KB, so it can hold much larger programs and data.
2. A larger instruction set (arithmetic, logic, rotate, move, jump) makes programs shorter and more flexible.
3. Conditional jumps (JZ, JM) allow decisions and loops.
4. CALL and RET support subroutines, so code can be reused.
5. Several registers hold more data inside the CPU, so fewer memory accesses are needed.
6. Input and output ports let it connect to a keyboard, display and other devices.
7. The bidirectional register and the use of immediate operands (MVI) make data movement easier.
8. Because it is similar to the 8085, it is an easy bridge to learning real microprocessors.

MVI B,70H loads the immediate byte 70H into register B. It is a 2-byte instruction: the opcode is 06H and the second byte is the data 70H. It needs two machine cycles.

• M1: opcode fetch, 4 T states.
• M2: memory read (of the data byte), 3 T states.

Total = 7 T states. With a 3 MHz clock, $T = 0.333\ \mu s$, so the time is $7 \times 0.333 = 2.33\ \mu s$.

Timing diagram (assuming the instruction is stored at 2000H, so 06H is at 2000H and 70H at 2001H).

          |<------ M1: Opcode fetch ------>|<---- M2: Mem read ---->|
          |  T1   |  T2   |  T3   |  T4    |  T1   |  T2   |  T3    |
CLK     __|-|__|-|__|-|__|-|__|-|__|-|__|-|__|-|__|-|__|-|__|-|__|-|_
A15-A8  --<   20H (PC high)             >--<   20H (PC high)       >--
AD7-AD0 --< 00H >--<  06H (opcode) >-----<01H>-<   70H (data)  >----
ALE      _|--|_____________________________|--|_____________________
RD'      ____________|-------|_____________________|-----|__________
WR'      ----------------------------------------------------------
IO/M'    ________________________________________________________
S1,S0     1 , 1   (opcode fetch)               1 , 0   (mem read)

Explanation.

M1 (opcode fetch).

• T1: the PC content 2000H is placed on the address lines. A15-A8 carries 20H, and AD7-AD0 carries 00H, which is latched by ALE (ALE goes high in T1). $IO/\overline{M} = 0$, $S_1 = S_0 = 1$.
• T2: $\overline{RD}$ goes low and the memory puts 06H on the data bus. The PC is incremented to 2001H.
• T3: the opcode is read into the instruction register and $\overline{RD}$ goes high.
• T4: the opcode is decoded, and the CPU finds that another byte is needed.

M2 (memory read).

• T1: the address 2001H is placed on the bus, with ALE high, $IO/\overline{M} = 0$, $S_1 = 1$, $S_0 = 0$.
• T2: $\overline{RD}$ goes low, and memory places 70H on AD7-AD0.
• T3: the byte 70H is read and stored in register B. $\overline{RD}$ goes high and the instruction is complete.

The 8085 is an 8-bit microprocessor with a 16-bit address bus, running on a single +5 V supply and a clock of up to 3 MHz.

Block diagram.

 +------------------------------------------------------------------+
 |  INTR  INTA' RST7.5 RST6.5 RST5.5 TRAP                           |
 |     +--------------------------+        Serial I/O  SID  SOD     |
 |     | Interrupt control        |        +--------------------+   |
 |     +--------------------------+        | Serial I/O control |   |
 |                                         +--------------------+   |
 |  +-----+  +------+   +--------------------------------+          |
 |  | Acc |  | Temp |   | B | C | D | E | H | L | SP | PC |          |
 |  +--+--+  +--+---+   +--------------------------------+          |
 |     |     +--+-------------+  Incr/Decr address latch            |
 |  +--+--+  +--+---+    +-----------+    +------------+            |
 |  | ALU |--|Flags |    | Addr buf  |    | Addr/Data  |            |
 |  +-----+  +------+    +-----------+    | buffer     |            |
 |  Instruction register + decoder, Timing and control              |
 +------------------------------------------------------------------+
   A15-A8 (address)    AD7-AD0 (address/data)   control: ALE RD' WR' IO/M' S0 S1 READY HOLD HLDA RESET

Components.

1. ALU. It performs arithmetic (add, subtract, increment, decrement) and logic (AND, OR, XOR, compare, complement, rotate). Operand one comes from the accumulator and operand two from the temporary register.
2. Accumulator (A). An 8-bit register that holds one operand and receives the result of most ALU operations.
3. Temporary register. It holds the second operand during ALU operations. It is not accessible to the programmer.
4. Flag register. Five flags are set or reset by the ALU result: Sign (S), Zero (Z), Auxiliary carry (AC), Parity (P) and Carry (CY).
5. General purpose registers. B, C, D, E, H and L are 8-bit registers, usable as the pairs BC, DE and HL. HL commonly acts as the memory pointer (M).
6. Program counter (PC). A 16-bit register holding the address of the next instruction to be fetched.
7. Stack pointer (SP). A 16-bit register pointing to the top of the stack in memory.
8. Instruction register and decoder. The opcode is held in the instruction register and decoded to produce the sequence of operations.
9. Timing and control unit. It generates the timing and control signals (ALE, $\overline{RD}$, $\overline{WR}$, $IO/\overline{M}$, S0, S1) and synchronises all internal and external operations.
10. Interrupt control. It handles INTR, TRAP and RST 7.5, 6.5 and 5.5, with the INTA signal.
11. Serial I/O control. It provides the SID and SOD pins for serial data.
12. Address buffer and address/data buffer. They drive the high-order address lines A15-A8 and the multiplexed lines AD7-AD0.
13. Incrementer/decrementer address latch. It increments or decrements the PC, SP and register pairs.

Logic. HL points to the source (5060H), DE points to the destination (6050H), and C is a counter holding 16 = 10H. Each pass copies one byte, advances both pointers and decrements the counter until it reaches zero. The source block is 5060H to 506FH and the destination block is 6050H to 605FH, so the blocks do not overlap.

Program.

        LXI H, 5060H    ; HL = source address
        LXI D, 6050H    ; DE = destination address
        MVI C, 10H      ; C = 16 bytes counter
LOOP:   MOV A, M        ; A = byte from source
        STAX D          ; store A at destination
        INX H           ; next source address
        INX D           ; next destination address
        DCR C           ; count = count - 1
        JNZ LOOP        ; repeat until C = 0
        HLT

Working.

• LXI loads the 16-bit pointers, MVI sets the count.
• MOV A,M reads the memory byte pointed to by HL, and STAX D writes A to the address in DE.
• INX H and INX D move to the next locations. DCR C sets the zero flag when C reaches 0, which ends the loop.
• Sixteen iterations complete the transfer, so the byte at 5060H goes to 6050H, 5061H to 6051H, and the last byte 506FH goes to 605FH.

DMA (Direct Memory Access) is a method of transferring a block of data between an I/O device and memory directly, without involving the CPU in each byte transferred. It is used for fast devices such as disks, since moving each byte through the CPU with programmed or interrupt I/O is too slow. A special chip, the DMA controller (for example the Intel 8257 or 8237), takes control of the system buses for the transfer.

Components of a DMA controller.

• Address register: holds the memory address of the next byte.
• Word (byte) count register: holds the number of bytes still to be transferred.
• Control register: holds mode and direction (read or write) of transfer.
• Handshake lines to the device: DREQ (DMA request) and DACK (DMA acknowledge).
• Handshake lines to the CPU: HOLD and HLDA.

Sequence of operation (8085 with 8257).

1. The CPU programs the DMA controller with the starting address, the byte count and the direction of transfer, and then continues with other work.
2. When the I/O device is ready, it sends a DMA request (DREQ) to the controller.
3. The controller sends a HOLD request to the CPU.
4. The CPU completes its current machine cycle, floats (tri-states) its address, data and control buses, and answers with HLDA (hold acknowledge).
5. The controller sends DACK to the device, places the memory address on the address bus and issues the memory read or write signals. Data flows directly between the device and memory.
6. After each byte, the controller increments the address register and decrements the count register.
7. When the count reaches zero (terminal count), the controller removes HOLD, the CPU takes back the buses, and the controller can interrupt the CPU to report completion.

Transfer modes.

• Burst (block) mode: the whole block is transferred at once while the CPU is held.
• Cycle stealing: one byte is transferred at a time, and the CPU is held for one cycle only.
• Transparent mode: transfers occur only when the CPU is not using the buses.

Advantages. High transfer speed, and the CPU is free for other work during the transfer.

RS-232C. RS-232C is a standard defined by the EIA for serial data communication between a DTE (data terminal equipment, for example a computer) and a DCE (data communication equipment, for example a modem). It uses a 25-pin (DB-25) or 9-pin (DB-9) connector.

Electrical levels. Logic 1 (mark) is $-3$ V to $-15$ V (up to $-25$ V), and logic 0 (space) is $+3$ V to $+15$ V. Because the levels differ from TTL, level converters such as the MAX232 (or 1488 driver and 1489 receiver) are used.

Interface.

 Microprocessor -- UART/USART (8251A) -- TTL --> [MAX232 / 1488] --> RS-232C connector --> modem/device
                                         TTL <-- [MAX232 / 1489] <--

The UART converts parallel data from the CPU to serial and adds start, stop and parity bits.

Main signals (DB-25 pin numbers).

Connecting two computers without a modem (null modem). Two computers are both DTEs, so a straight cable would connect transmitter to transmitter. A null-modem cable crosses the lines, so that each computer thinks it is talking to a modem.

 Computer 1               Computer 2
 TxD  (2) ---------\  /--- (2) TxD
 RxD  (3) ---------/ \---- (3) RxD     (TxD of one goes to RxD of the other)
 RTS  (4) ---------> (5) CTS           (RTS of each is wired to the CTS of the other)
 CTS  (5) <--------- (4) RTS
 DTR (20) ---------> (6) DSR and (8) DCD
 DSR (6), DCD (8) <-- (20) DTR
 GND  (7) ------------ (7) GND

The minimal version uses only three wires: TxD to RxD, RxD to TxD, and ground to ground. Software (XON/XOFF) flow control is then used, and the handshake pins on each side are jumpered together locally.

INT 21H with AH = 02H displays the character held in DL. The program loads each character of the string in turn and calls the interrupt. The string "MICROPROCESSOR" has 14 characters.

.MODEL SMALL
.STACK 100H
.DATA
MSG   DB 'MICROPROCESSOR'      ; string of 14 characters
.CODE
MAIN  PROC
      MOV AX, @DATA            ; initialise data segment
      MOV DS, AX
      LEA SI, MSG              ; SI points to first character
      MOV CX, 14               ; CX = character count
NEXT: MOV DL, [SI]             ; DL = character to be displayed
      MOV AH, 02H              ; DOS function: display character
      INT 21H                  ; display it
      INC SI                   ; next character
      LOOP NEXT                ; CX = CX - 1, repeat until CX = 0
      MOV AH, 4CH              ; terminate program
      INT 21H
MAIN  ENDP
      END MAIN

Explanation.

• MOV AX,@DATA and MOV DS,AX load the data segment address into DS.
• LEA SI,MSG makes SI point to 'M'. CX holds the number of characters.
• In every pass, DL receives one character, AH = 02H selects "display character", and INT 21H writes it at the cursor. AH is set inside the loop because the DOS call may change AX.
• INC SI moves to the next character, and LOOP decrements CX and jumps back until CX = 0.
• AH = 4CH with INT 21H returns control to DOS.

Output: MICROPROCESSOR

The 8255A has two basic operating modes, selected by bit D7 of the control word: the I/O mode (D7 = 1) and the Bit Set/Reset (BSR) mode (D7 = 0).

1. I/O modes (D7 = 1). Control word bits: D6 D5 select the Group A mode, D4 = Port A direction (1 = input), D3 = Port C upper direction, D2 = Group B mode, D1 = Port B direction, D0 = Port C lower direction.

• Mode 0, simple (basic) I/O. Ports A, B and the two halves of C work as simple input or output ports without handshaking. Outputs are latched, inputs are not. It is used for simple devices like switches, LEDs and seven-segment displays.
• Mode 1, strobed (handshake) I/O. Ports A and B work as 8-bit I/O ports, and the lines of Port C act as handshake signals (STB, IBF, OBF, ACK, INTR). Data is transferred with synchronising signals and can be interrupt-driven. It suits devices like printers.
• Mode 2, strobed bidirectional bus. Only Port A (Group A) can work in this mode. It acts as an 8-bit bidirectional bus, with five lines of Port C used for handshaking. It suits two-way communication.

2. Bit Set/Reset (BSR) mode (D7 = 0). Individual bits of Port C can be set or reset by a single control word. D3-D1 select the bit (PC0-PC7) and D0 = 1 sets it and D0 = 0 resets it. D6-D4 are not used. This is useful for generating control signals, such as setting an interrupt enable.

Example: control word 80H (1000 0000) sets Ports A, B and C as outputs in mode 0. The BSR word 0BH (0000 1011) selects bit 5 (D3-D1 = 101) and sets it (D0 = 1), so PC5 becomes 1.

Parallel communication. All bits of a data word (for example 8 bits) are sent at the same time, each on its own line, plus ground and control lines.

• It is fast, since a whole byte goes in one clock cycle.
• It needs many wires and connectors, so cost rises with distance.
• It suffers from skew and crosstalk at higher speed and longer distances.
• It is used over short distances, such as the CPU to memory, or to a printer (Centronics), through a device like the 8255A.

Serial communication. The bits of a word are sent one after another over a single line (plus ground).

• It needs few wires, so it is cheaper and suitable for long distances.
• It is slower, since 8 clock periods are needed for each byte.
• The transmitter converts parallel to serial using a shift register, and the receiver converts it back. Chips such as the 8251A USART do this.
• It is used for modems, mice, and RS-232C links.

Types of serial transmission.

• Asynchronous: each character is framed by a start bit (0) and one or two stop bits (1), with optional parity. No common clock is needed, but the sender and receiver must use the same baud rate.
• Synchronous: a block of characters is sent with a common clock or sync characters. It has less overhead and is faster.

Modes by direction. Simplex (one way only), half duplex (both ways, one at a time), and full duplex (both ways at once).

The 8085 has a flag register of 8 bits, of which five are used. The flags are single-bit flip-flops that are set (1) or reset (0) according to the result of an arithmetic or logic operation and are used for decisions (conditional jump, call, return).

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

1. Sign flag (S). It copies the MSB (bit D7) of the result. S = 1 means the result is negative (in 2's complement), S = 0 means positive.
2. Zero flag (Z). Z = 1 if the result is zero, otherwise 0. It is also set when two numbers are equal after CMP.
3. Auxiliary carry flag (AC). AC = 1 when there is a carry from bit D3 to D4. It is used internally by the DAA instruction for BCD arithmetic.
4. Parity flag (P). P = 1 if the result has an even number of 1s, P = 0 if odd.
5. Carry flag (CY). CY = 1 if an addition produces a carry out of D7, or a subtraction needs a borrow. It is also affected by rotates and by STC and CMC.

Example: adding $A = 9AH$ and $B = 67H$ gives $101H$. The result in A is 01H, so CY = 1, Z = 0, S = 0, P = 0 (one 1-bit, odd) and AC = 1 (since $A + 7 = 17H$ carries from the low nibble).

Conditional instructions use the flags: JC/JNC (carry), JZ/JNZ (zero), JM/JP (sign), JPE/JPO (parity). The flags are saved on the stack by PUSH PSW.

The addressing mode is the way in which the operand of an instruction is specified. The 8085 has five addressing modes.

1. Immediate addressing. The operand (data) is part of the instruction itself.

• Examples: MVI B, 45H (B = 45H), LXI H, 2050H (HL = 2050H), ADI 0FH.

2. Register addressing. The operand is in a CPU register named in the instruction.

• Examples: MOV A, B (A = B), ADD C, XCHG.

3. Direct addressing. The 16-bit address of the operand is given in the instruction.

• Examples: LDA 2000H (A = content of 2000H), STA 3000H, IN 80H, OUT 81H (8-bit port address), LHLD 2050H.

4. Register indirect addressing. A register pair holds the address of the operand in memory.

• Examples: MOV A, M (the address is in HL), LDAX B (address in BC), STAX D, ADD M.

5. Implied (implicit) addressing. The operand is implied by the instruction itself and no operand is written. The accumulator is generally used.

• Examples: CMA (complement A), RAL, RAR, DAA, STC, HLT.

The numbers are $3020H$ and $5040H$. Their sum is

$3020H + 5040H = 8060H$

so H = 80H and L = 60H at the end. The 8085 DAD instruction adds a 16-bit register pair to HL, so the program is short.

Program using DAD.

        LXI H, 3020H    ; HL = 3020H (first number)
        LXI D, 5040H    ; DE = 5040H (second number)
        DAD D           ; HL = HL + DE = 8060H
        HLT

Program using 8-bit additions (equivalent).

        LXI H, 3020H    ; H = 30H, L = 20H
        LXI D, 5040H    ; D = 50H, E = 40H
        MOV A, L        ; A = 20H
        ADD E           ; A = 20H + 40H = 60H
        MOV L, A        ; L = 60H
        MOV A, H        ; A = 30H
        ADC D           ; A = 30H + 50H + carry(0) = 80H
        MOV H, A        ; H = 80H
        HLT

Check. Low bytes: $20H + 40H = 60H$ with no carry. High bytes: $30H + 50H = 80H$. Result HL = 8060H, that is H = 80H, L = 60H. If the low-byte addition produced a carry, ADC would add it into the high byte, so the program is correct for any data. The carry flag after DAD is 0, since the sum does not exceed FFFFH.

Register organization. A CPU contains a set of fast registers that hold the data and addresses it is working with. In a typical organization there are general purpose registers (R1 to R7), an accumulator, the program counter (PC), the stack pointer (SP), the instruction register (IR), the address register (AR), the data register (DR) and a status (flag) register. Registers are used for fast data access and so avoid memory references.

Registers are connected through a data path, and the paths between registers, buses and the ALU decide how data moves. Two ways of connecting them are common bus systems (a single bus with a multiplexer or tri-state buffers) and a register file with two multiplexers.

CPU data path (typical bus organization).

 Input data
     |
  +--v-------------------------------------------+
  |  R1  R2  R3  R4  R5  R6  R7  (register file)  |
  +--+------------------------------------+------+
     |  (loaded via decoder SELD)         |
   [MUX A] <-- SELA           SELB --> [MUX B]
     | A bus                           | B bus
     +--------->[   ALU   ]<-----------+
                [OPR select]-> F (flags: C, S, Z, V)
                     |
                 Output result  ---> back into register file

Operation.

1. The registers feed two multiplexers (MUX A and MUX B). Selection inputs SELA and SELB (3 bits each) choose the source registers, and these put the operands on the A and B buses.
2. The ALU performs the operation chosen by the operation select field OPR (5 bits), such as add, subtract, AND, OR, XOR or transfer, and produces output F and status bits.
3. The result goes back into the register chosen by the decoder (SELD, 3 bits), which loads it into the destination register on the next clock edge.

Control word. The 14 bits SELA (3) + SELB (3) + SELD (3) + OPR (5) form the control word.

Example: R1 $\leftarrow$ R2 + R3 uses SELA = R2, SELB = R3, SELD = R1 and OPR = ADD. All of this happens in a single clock cycle. A stack can be organised in the same way, using a register or memory with the SP.

A control unit generates the control signals that sequence the operations of the CPU. In a hardwired control unit these are produced by fixed logic circuits (gates, decoders, counters), while in a microprogrammed control unit they come from microinstructions stored in a control memory.

A microprogram sequencer decides the address of the next microinstruction to be read from the control memory. It supplies the control memory with the next address, which may come from simple incrementing, a branch, a subroutine return or a mapping of the opcode.

Block diagram.

 Instruction  --> [Mapping logic] ----------------+
 (opcode)                                         |  (3)
                   +-----------+                  v
 Branch address -->|           |-- MUX 1 (4:1) -> [CAR] -> Control memory -> Microinstruction
 (from control     |           |      ^   ^  ^        |                          |  (fields)
  memory)          |           |      |   |  +--------+ (increment)              |
 SBR (return) ---->|           |   S1 S0  |                                      |
                   +-----------+      [Input logic] <-- I1 I0 (MC field)       |
                                          ^  |  L (load)                        |
 Status bit --> [MUX 2 (test select)] ---T   +--> [SBR]  <-- CAR+1              |

Components.

• Control address register (CAR). Holds the address that is sent to the control memory.
• Incrementer. Computes CAR + 1 for sequential microinstructions.
• Subroutine register (SBR). Holds the return address when a microprogram subroutine is called.
• Multiplexer 1. Selects the next address from four sources according to S1 S0: 00 = CAR + 1, 01 = branch address, 10 = SBR (return), 11 = external mapping address.
• Multiplexer 2 (test select). Chooses one status bit (carry, zero, sign etc.) and gives the condition T.
• Branch logic (input logic). Produces S1, S0 and L from I1, I0 (the microinstruction's branch type) and T.
• Mapping logic. Converts the opcode of the machine instruction into the starting address of its microprogram, for example by adding zeros to the opcode.
• Control memory. Holds the microinstructions.

Truth table of the input logic.

Operation.

1. At the start of an instruction cycle, the opcode is mapped to the address of its microroutine and loaded into CAR.
2. The microinstruction is read from the control memory and its fields produce the control signals.
3. Meanwhile the sequencer picks the next address. For a normal microinstruction it is CAR + 1; for a conditional branch the status bit T decides between CAR + 1 and the branch address; a CALL also saves CAR + 1 in SBR; a RET restores CAR from SBR.
4. The process repeats until the end of the microroutine, which maps back to the fetch routine.

Flowchart of Booth's algorithm

START
  |
  v
AC <- 0, Q-1 <- 0, M <- multiplicand, Q <- multiplier, SC <- n
  |
  v
<--------------------------------------------+
 Look at Q0 Q-1                              |
  |-- 10 --> AC <- AC - M  --+               |
  |-- 01 --> AC <- AC + M  --+               |
  |-- 00 or 11 --------------+               |
                              v              |
          Arithmetic shift right (AC, Q, Q-1)|
                              v              |
                         SC <- SC - 1        |
                              v              |
                         SC = 0 ? --No-------+
                              |Yes
                              v
                 Product is in AC:Q  -->  END

Multiply $(-6) \times (12)$ with n = 5 bits

The multiplicand is $M = 12 = 01100$, so $-M = 10100$. The multiplier is $Q = -6 = 11010$.

The product is AC:Q $= 1110111000_2$. The sign bit is 1, so the value is negative. The 2's complement of $1110111000$ is $0001001000 = 72$.

Hence the product is $-72$, which agrees with $(-6)\times 12 = -72$.

Cache mapping is the method used to decide where a block of main memory is placed in the cache. Because the cache is much smaller than main memory, each memory block must be mapped to a cache line. There are three techniques.

1. Direct mapping

• Each main-memory block can go to exactly one cache line: $i = j \bmod m$, where $j$ is the block number and $m$ is the number of cache lines.
• The address is divided into Tag | Line | Word fields. The line field selects the cache line, and the stored tag is compared with the address tag to detect a hit.
• Advantages: simple and cheap, needs only one comparator, and no replacement algorithm is needed.
• Disadvantage: two blocks that map to the same line keep replacing each other (thrashing), so the hit ratio can be low.

2. Fully associative mapping

• A block can be placed in any cache line.
• The address is divided into Tag | Word. The tag is compared with the tags of all lines in parallel.
• Advantages: most flexible and gives the highest hit ratio.
• Disadvantages: expensive, because it needs many comparators (associative memory), and it needs a replacement algorithm such as LRU, FIFO or random.

3. Set-associative mapping

• The cache is divided into $v$ sets of $k$ lines each, and a block maps to one particular set but can occupy any line within it: $set = j \bmod v$.
• The address is divided into Tag | Set | Word. Only the $k$ tags of the selected set are compared.
• It is a compromise between the first two. It has fewer conflicts than direct mapping and lower cost than fully associative mapping. Typical values are 2-way and 4-way.

Comparison