Microprocessor and Computer Architecture

Instruction pipeline. An instruction pipeline overlaps the execution of several instructions by dividing instruction processing into segments that work concurrently. While one instruction is being executed, the next is being decoded and the one after is being fetched. This increases throughput, although each instruction still takes the same time.

Four-segment instruction pipeline

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

Example (space-time diagram). Four instructions I1-I4 go through the pipeline:

Without pipelining, 4 instructions need $4\times4=16$ clocks; with the pipeline they need $4+3=7$ clocks. In general, $n$ instructions on a $k$-segment pipeline take $k+n-1$ clock cycles. Branch instructions and data or resource conflicts can stall the pipeline.

Pipeline: Pipelining is a technique in which a task (such as instruction execution) is divided into sub-tasks called segments or stages. Each stage works on a different instruction at the same time, so several instructions are in different stages of completion simultaneously. This raises throughput; ideally one instruction completes per clock cycle.

Four-segment instruction pipeline

The instruction cycle is divided into four segments:

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

Space-time diagram (instructions 1 to 4):

For $k$ segments and $n$ instructions the pipeline needs $k + (n-1)$ clock cycles, against $n \times k$ without pipelining. Here, 4 instructions need $4 + 3 = 7$ cycles instead of 16. Delays occur on branch instructions, data dependency and resource conflicts.

Four-segment instruction pipeline

In a four-segment instruction pipeline, instruction processing is divided into four stages that work in parallel on four different instructions.

1. FI (Fetch Instruction): the instruction is fetched from memory.
2. DA (Decode and calculate effective Address): the instruction is decoded and the effective address of the operand is computed.
3. FO (Fetch Operand): the operand is fetched from memory.
4. EX (Execute): the operation is executed and the result stored.

Flow diagram (a branch empties the pipeline):

 Segment 1:  Fetch instruction from memory
      |
 Segment 2:  Decode instruction, calculate effective address
      |            \-- Branch? yes -> Update PC, Empty pipe
      |no
 Segment 3:  Fetch operand from memory
      |
 Segment 4:  Execute instruction
      |            \-- Interrupt? yes -> Interrupt handling, Update PC, Empty pipe

Space-time diagram:

Once the pipeline is full, one instruction is completed every clock. For $n$ instructions and $k = 4$ segments the time is $(k + n - 1)$ cycles, so the speed-up approaches $k$ for large $n$:

$S = \frac{n k}{k + n - 1}$

Pipeline performance falls because of branch instructions, data dependency and memory (resource) conflicts.

In a microprogrammed control unit the control signals for each instruction are stored as a sequence of microinstructions (a microprogram) in a special memory, the control memory, instead of being generated by hard-wired logic.

Main components

• Control memory (ROM): holds the microprograms. Each word is a microinstruction.
• Control address register (CAR): holds the address of the next microinstruction to read.
• Control data register (CDR) / pipeline register: holds the microinstruction just read; its bits form the control word.
• Sequencer (next-address generator): computes the next CAR value: increment, branch (jump), mapping from the opcode, or a return address for a subroutine.
• Mapping logic: converts the opcode of the instruction register into the starting address of its microprogram.
• Decoders: decode the microinstruction fields to produce the control signals sent to the datapath.

Operation: The instruction opcode is mapped to a starting address in control memory and loaded into the CAR. The microinstruction at that address is read into the CDR, and its fields drive the control signals for one micro-operation. The sequencer then sets the CAR to the next address (increment, or branch on a condition). This repeats until the microprogram ends and control returns to the instruction fetch routine.

Microprogrammed control is flexible and easy to modify, though slower than hard-wired control.

The 8085 communicates with memory and I/O devices through three groups of lines called buses.

1. Address bus (16 lines, unidirectional). Carries the address from the CPU to memory or I/O. The high-order byte is on A15-A8 (dedicated lines). The low-order byte is on AD7-AD0, which are time-multiplexed with data. A 16-bit address bus can address $2^{16}=64$ KB of memory.

2. Data bus (8 lines, bidirectional). AD7-AD0 carry data between the CPU, memory and I/O. During T1 of a machine cycle these lines carry the low-order address; the external latch (74LS373) captures it when ALE goes high. In later T-states they carry data.

3. Control bus. Carries timing and control signals:

• ALE (Address Latch Enable) to demultiplex AD7-AD0.
• $\overline{RD}$ and $\overline{WR}$ for read and write.
• IO/$\overline M$ to select I/O or memory.
• S0, S1 status signals, plus HOLD, HLDA, READY, INTR, INTA and others.

Demultiplexing the low-order address with ALE and a latch gives the 16-bit address on the separate address lines and the 8-bit data bus on AD7-AD0.

MVI A, 32H is a 2-byte instruction (opcode 3EH, then data 32H) that takes 2 machine cycles and 7 T-states: an opcode fetch cycle (4 T-states) followed by a memory read cycle (3 T-states) for the data byte.

Opcode fetch machine cycle (T1-T4)

• T1: The PC contents are placed on the address bus. A15-A8 hold the high byte, and AD7-AD0 hold the low byte. ALE goes high so the latch captures the low byte. IO/$\overline M$ = 0, S1 = S0 = 1 (opcode fetch status). The PC is incremented.
• T2: ALE goes low. $\overline{RD}$ goes low and the memory places the opcode 3EH on the data bus.
• T3: The opcode is read into the instruction register (IR) and $\overline{RD}$ goes high.
• T4: The opcode is decoded. The decoder finds that one more byte is needed, so a memory read cycle follows.

Timing diagram (summary)

In the following memory read cycle (3 T-states, S1 = 1, S0 = 0) the address in PC is output again and 32H is read into register A.

The way an instruction specifies its operand is its addressing mode. The 8085 has five modes.

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

Memory hierarchy arranges the storage of a computer in levels. Faster memory is smaller, costlier per bit and closer to the CPU, so the system gets the speed of fast memory and the capacity and low cost of slow memory.

        CPU Registers          (fastest, smallest, costliest)
              |
         Cache memory
              |
     Main memory (RAM/ROM)
              |
   Secondary storage (hard disk, SSD)
              |
   Tertiary/backup (optical disc, tape)  (slowest, largest, cheapest)

Moving down the hierarchy, access time and cost per bit fall while capacity rises. The hierarchy works because of the principle of locality: programs tend to reuse recently used data (temporal locality) and data near it (spatial locality), so most accesses are served by the fast upper levels.

Control word. A control word is a binary word whose bits (or bit fields) specify the control signals that select the micro-operation to be performed in one clock cycle, such as register selection, ALU function and data transfer. Each bit or field activates a particular control line of the datapath.

Procedure for generating a control word for an operation

1. Identify the micro-operation, for example $R1\leftarrow R2+R3$.
2. List the fields of the control word, for example source A select, source B select, destination select and ALU operation select.
3. Find the binary code for each field from the selector and function tables: R2 selects the source A input, R3 the source B input, R1 the destination and ADD the ALU function.
4. Concatenate the codes in order to form the control word.

Example (a 14-bit control word with fields SELA (3 bits), SELB (3), SELD (3), OPR (5)): for $R1\leftarrow R2+R3$ the fields are SELA = R2 = 010, SELB = R3 = 011, SELD = R1 = 001 and OPR = ADD = 00010.

Control word: 010 011 001 00010

Applying this word to the control inputs makes the ALU add R2 and R3 and store the result in R1 in one clock pulse.

The 8085 is an 8-bit microprocessor with a 16-bit address bus. Its functional blocks are as follows.

1. Arithmetic Logic Unit (ALU). Performs arithmetic (add, subtract, increment, decrement) and logic (AND, OR, XOR, compare, rotate, complement) operations. Its two inputs are the accumulator and a temporary register.

2. Accumulator (A) and temporary register. The accumulator is an 8-bit register that holds one operand and receives the result. The temporary register holds the second operand during the operation and is not accessible to the programmer.

3. Flag register. Five flags: Sign (S), Zero (Z), Auxiliary Carry (AC), Parity (P) and Carry (CY). They show the status of the last arithmetic or logical operation.

4. General purpose registers. B, C, D, E, H and L (8-bit each) can be used singly or as the pairs BC, DE and HL. HL also acts as a memory pointer (M).

5. Special purpose registers.

• Program Counter (PC, 16-bit): address of the next instruction.
• Stack Pointer (SP, 16-bit): address of the top of the stack.
• Instruction register and decoder: hold and decode the opcode being executed.

6. Timing and control unit. Generates timing and control signals (ALE, $\overline{RD}$, $\overline{WR}$, IO/$\overline M$, S0, S1, CLK OUT) that synchronize the operation of the CPU and peripherals.

7. Interrupt control. Handles TRAP, RST 7.5, 6.5, 5.5 and INTR, with INTA for acknowledgment.

8. Serial I/O control. SID and SOD pins for serial data transfer.

9. Address buffer, address/data buffer and incrementer/decrementer. The address buffer drives A15-A8; the address/data buffer drives the multiplexed AD7-AD0. The incrementer/decrementer address latch raises or lowers the PC or SP.

All these blocks are connected by the internal 8-bit data bus.

The accumulator is a register that holds one operand of an operation and receives the result. Its design is a register with an adder/logic unit and the control logic that selects its operation.

Design. An accumulator is a register $AC$ together with a combinational circuit (the ALU) whose output is loaded back into $AC$. In each stage $i$ of an $n$-bit accumulator there are:

• a flip-flop $AC_i$, which stores the bit;
• an ALU stage that combines $AC_i$ with the input bit $DR_i$ (data register) to give the sum, AND, OR, XOR and other functions;
• a multiplexer or gates that select the result of the chosen operation, such as shift, complement or clear.

Control logic. Control signals decide what is loaded into $AC$ on the next clock pulse:

The register's load input is $LD=\text{ADD}+\text{AND}+\text{DR}+\text{COM}+\text{SHR}+\text{SHL}+\text{INR}+\text{CLR}$ (OR of all signals), so that $AC$ changes only when one of the operations is selected. The input to each flip-flop is chosen with a multiplexer driven by these control signals, and the transfer occurs at the clock pulse. Control signals come from the control unit timing and the decoded instruction.

Data transfer instructions copy data between registers, memory and I/O. They do not change the flags (except POP PSW).

Data manipulation instructions

1. Arithmetic:
   • ADD B, ADI 05H, SUB C, SUI 02H, ADC, SBB: addition and subtraction (with carry or borrow).
   • INR R, DCR R, INX Rp, DCX Rp: increment and decrement.
   • DAD Rp: 16-bit add to HL.
2. Logical:
   • ANA, ANI, ORA, ORI, XRA, XRI: AND, OR, XOR.
   • CMP, CPI: compare.
   • CMA: complement the accumulator.
3. Rotate: RLC, RRC, RAL, RAR rotate the accumulator.
4. Branch / machine control: JMP, JZ, JNZ, CALL, RET, HLT, NOP.

Example program adding two numbers:

LDA 2050H   ; A <- [2050H]
MOV B, A    ; B <- A
LDA 2051H   ; A <- [2051H]
ADD B       ; A <- A + B
STA 2052H   ; store the result
HLT

CPU (Central Processing Unit). The CPU is the main processing part of a computer. It fetches instructions from memory, decodes them and executes them. It consists of the ALU, the control unit and registers.

Microprocessor vs microcontroller

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

Opcode fetch machine cycle for MOV A, B (78H)

MOV A, B is a one-byte instruction, so it needs only one machine cycle (M1, opcode fetch) of 4 T-states.

        T1     T2     T3     T4
CLK   _|‾|_|‾|_|‾|_|‾|_
ALE    ___|‾‾‾|___________
A15-A8 [ PC high  (20H) ]-----------
AD7-0  [PC low]  [ 78H  ]--[ idle ]
RD     ‾‾‾‾‾‾‾‾|_______|‾‾‾‾‾‾
IO/M   ______________________  (low = memory)

Total time = 4 T-states (one machine cycle).

Idea: a number is odd if bit D0 is 1 and even if D0 is 0. Mask all bits except D0 with ANI 01H and test the zero flag. The result is stored at 8081H (00H for even, 01H for odd).

        LDA  8080H      ; A <- number
        ANI  01H        ; keep only D0
        JZ   EVEN       ; Z = 1 -> D0 = 0 -> even
        MVI  A, 01H     ; odd
        STA  8081H
        HLT
EVEN:   MVI  A, 00H
        STA  8081H
        HLT

Example: if (8080H) = 37H, then 37H AND 01H = 01H, Z = 0, so the number is odd and 01H is stored at 8081H.

Cache memory: Cache is a small, very fast memory placed between the CPU and main memory. It holds copies of the most recently or frequently used instructions and data so that the average memory access time is reduced. It works on the principle of locality of reference. When the CPU finds the required word in cache it is a hit; otherwise it is a miss and the block is brought from main memory.

Elements of cache design

1. Cache size: small enough to keep cost per bit low, large enough to give a high hit ratio.
2. Mapping function: decides where a main-memory block may be placed in the cache.
   • Direct mapping: each block maps to exactly one line (line = block number mod number of lines). Simple but may cause conflict misses.
   • Associative mapping: a block can go in any line; flexible but needs expensive parallel tag comparison.
   • Set-associative mapping: the cache is divided into sets; a block maps to one set and can go to any line in it. A compromise between the two.
3. Replacement algorithm: chooses which block to remove on a miss when the cache is full, for example LRU, FIFO, LFU or random.
4. Write policy: write-through (main memory is updated on every write) or write-back (memory is updated only when the block is replaced, using a dirty bit).
5. Block (line) size: larger blocks exploit spatial locality but too large a block reduces the number of blocks and raises the miss penalty.
6. Number of caches: single or multilevel (L1, L2, L3), and unified or split (separate instruction and data caches).

(a) Accumulator

The accumulator (register A) is an 8-bit register that is the main working register of the 8085. One operand of most arithmetic and logic operations is taken from it, and the result is stored back in it. It is also used for data transfer with I/O ports (IN, OUT) and memory (LDA, STA). Example: ADD B performs A ← A + B. The accumulator together with the flag register forms the Program Status Word (PSW).

(b) 8085 Interrupts

An interrupt is a signal that makes the processor suspend its current program, run a service routine and then resume. The 8085 has five interrupt pins:

Maskable interrupts are enabled with EI, disabled with DI, and selectively masked with SIM. The INTA signal acknowledges INTR.

Instruction set: The instruction set of a microprocessor is the complete collection of instructions (machine operations) that the processor can recognise and execute. The 8085 has 74 instructions (246 opcodes), each one to three bytes long.

Classification of 8085 instructions

1. Data transfer instructions: copy data between registers, memory and I/O without changing the source. They do not affect flags.

• MOV A, B (register to register), MVI B, 32H (immediate), LDA 2050H (memory to A), STA 2060H, LXI H, 2050H, LHLD, SHLD, LDAX B, STAX D, XCHG.

2. Arithmetic instructions: addition, subtraction, increment and decrement.

• ADD B, ADI 05H, ADC C, SUB B, SBI 02H, INR A, DCR B, INX H, DCX D, DAD B, DAA.

3. Logical instructions: AND, OR, XOR, compare, rotate and complement.

• ANA B, ANI 0FH, ORA C, XRA A, CMP B, CPI 40H, RLC, RRC, RAL, RAR, CMA, CMC, STC.

4. Branching instructions: change the sequence of program execution.

• Unconditional: JMP 2050H, CALL 3000H, RET.
• Conditional: JZ, JNZ, JC, JNC, JP, JM, JPE, JPO, and conditional CALL and RET (CZ, RNZ, and so on).
• PCHL, RST n.

5. Stack, I/O and machine control instructions:

• Stack: PUSH B, POP D, XTHL, SPHL.
• I/O: IN 40H, OUT 41H.
• Machine control: HLT, NOP, EI, DI, RIM, SIM.

By size, instructions are also grouped as one-byte (MOV A, B), two-byte (MVI A, 32H) and three-byte (LDA 2050H).

Addressing mode: The addressing mode is the method by which an instruction specifies the location of its operand (data). The 8085 supports five addressing modes.

1. Immediate addressing: The operand is part of the instruction itself.

• MVI A, 32H loads 32H into A.
• LXI H, 2050H loads the 16-bit value 2050H into HL.

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

• MOV A, B copies the content of B to 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 stores A at 3000H.
• IN 40H and OUT 41H use direct I/O port addresses.

4. Register indirect addressing: A register pair 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 stores A at the address in DE.

5. Implicit (implied) addressing: The operand is implied by the opcode; no operand is specified.

• CMA complements the accumulator.
• RAL rotates the accumulator left.
• STC, XCHG and HLT.

Micro-program: A micro-program is a sequence of microinstructions stored in the control memory (ROM) of a microprogrammed control unit. Each microinstruction specifies the control signals (micro-operations) to be activated in one clock period; the set of microinstructions for a machine instruction forms its micro-routine.

Symbolic microprogram for the instruction FETCH routine

The fetch routine is stored at control-memory addresses 64 to 66 (the first three words of the micro-program). In symbolic form each line has fields: label, micro-operations (F1, F2, F3), condition (CD), branch (BR) and address (AD).

• Step 1: the address register receives the program counter.
• Step 2: the instruction is read into the data register and PC is incremented.
• Step 3: the address part of the instruction is moved to AR and the MAP branch transfers control to the micro-routine of the decoded opcode.

U means unconditional; MAP means map the opcode bits to a control-memory address.

Organization of the micro-program sequencer

The sequencer computes the next address of the control memory. Its main parts are:

 Instruction opcode -> [Mapping logic] ----+
 External input ---> [Input logic / MUX2 test] -+
                                         v     |
 Branch address (from microinstruction) -> [MUX1] -> [Control Address Register (CAR)] -> Control memory (ROM) -> Microinstruction
        ^                                          |   ^ 
        +-------- [Incrementer (CAR+1)] <----------+   |
        +-------- [Subroutine register SBR] <-----------+

1. Multiplexer MUX1 selects the next address from: CAR + 1 (incrementer), the branch address field, the mapping logic output, or the subroutine register (return address).
2. Multiplexer MUX2 selects one of the status bits (test condition) according to the CD field; its output decides whether the branch is taken.
3. Input logic takes the BR field and the selected status bit and generates the select signals S1 and S0 for MUX1 and the load signal for SBR.
4. Control Address Register (CAR) holds the address of the microinstruction being fetched.
5. Subroutine register (SBR) saves the return address for CALL and restores it for RET.
6. Control memory gives the microinstruction, whose fields supply the control signals to the datapath, and the CD, BR and AD fields back to the sequencer.

The addressing mode is the way an instruction specifies where its operand is. The 8085 has five modes.

1. Immediate: the data is in the instruction. Example: MVI A, 35H (A ← 35H); LXI H, 3000H.
2. Register: the operand is in a register. Example: MOV A, B (A ← B); ADD C.
3. Direct: the 16-bit address of the operand is given. Example: LDA 2050H (A ← content of 2050H); STA 3000H; IN 40H.
4. Register indirect: a register pair holds the address of the operand. Example: MOV A, M (A ← memory addressed by HL); LDAX B.
5. Implicit: the operand is implied by the opcode. Example: CMA (complement A); RAL; XCHG.

MVI A, 35H is a two-byte instruction (opcode 3EH, data 35H). It takes two machine cycles: opcode fetch (4 T-states) and memory read (3 T-states), total 7 T-states.

        |<------- M1: Opcode fetch ------>|<---- M2: Memory read ---->|
        T1    T2    T3    T4              T1    T2    T3
ALE     _|‾‾|______________                _|‾‾|__________
A15-A8  [ PC high ]-----------             [ PC+1 high ]---
AD7-0   [PC low][ 3EH ]---[idle]           [PC+1 low][ 35H ]
RD      ‾‾‾‾‾|_____|‾‾‾‾‾‾‾‾‾‾            ‾‾‾‾‾‾|_____|‾‾‾
IO/M    ______________________              ______________
S1,S0   1,1  (opcode fetch)                 0,1 (memory read)

M1 (opcode fetch):

• T1: PC (say 2000H) is placed on the address bus and ALE latches the low address byte.
• T2: RD goes low and the opcode 3EH is read from memory; PC becomes 2001H.
• T3: the opcode is stored in the instruction register.
• T4: the opcode is decoded; the processor finds that one more byte is needed.

M2 (memory read):

• T1: address 2001H is placed on the bus (ALE high).
• T2: RD goes low and the data byte 35H is read from memory; PC becomes 2002H.
• T3: the data 35H is loaded into the accumulator and RD goes high.

Instruction (opcode) mapping: In a microprogrammed control unit, mapping is the process of converting the operation-code bits of a machine instruction into the starting address of its micro-routine in the control memory. It is done by the mapping logic after the instruction is fetched, so the sequencer can jump to the right micro-routine.

Converting an instruction code to a microinstruction address

Take an 11-bit instruction with a 4-bit opcode, and a control memory of 128 words (7-bit address). The mapping puts the opcode in bits 4 to 1 of the control address and fills the other bits with fixed values:

$\text{Opcode } = \; 0\,\mathrm{o_3 o_2 o_1 o_0}\;\;\Rightarrow\;\; \text{Address} = 0\;\mathrm{o_3 o_2 o_1 o_0}\; 0\; 0$

Steps:

1. Bit 6 of the address is 0.
2. The four opcode bits fill bits 5 to 2.
3. Bits 1 and 0 are set to 0.

Example: opcode 0010 maps to address 0 0010 00 = 0001000 (decimal 8). This gives each routine a block of 4 words; if a routine is longer, it branches elsewhere. A ROM or PLA can also perform the mapping. The mapping uses little hardware and lets the micro-routines be placed anywhere, with each opcode giving its own address.

Stack: A stack is a last-in first-out (LIFO) storage structure: the last item pushed on is the first one popped off. Only the top is accessible. It is used for subroutine calls, interrupts, expression evaluation and recursion.

Stack organization

1. Register stack: a finite number of registers act as the stack. A stack pointer (SP) holds the address of the top. Push: SP ← SP + 1; stack[SP] ← data. Pop: data ← stack[SP]; SP ← SP − 1. Flags FULL and EMPTY show the state.
2. Memory stack: a portion of RAM is reserved for the stack, and the SP register holds the address of the top item. In the 8085 the stack grows downward:
   • PUSH B: SP ← SP − 1; M[SP] ← B; SP ← SP − 1; M[SP] ← C.
   • POP B: C ← M[SP]; SP ← SP + 1; B ← M[SP]; SP ← SP + 1.

Example: if SP = 3FFFH, PUSH B stores B at 3FFEH and C at 3FFDH, and SP becomes 3FFDH.

The return address of CALL and the PSW of an interrupt are saved on the stack automatically.

Arithmetic pipeline: An arithmetic pipeline divides an arithmetic operation, such as floating-point addition or multiplication, into segments, each doing part of the operation, so a stream of operations can be processed at overlapping times. It is used in high-speed computers for vector and floating-point calculations.

Example: floating-point addition/subtraction pipeline of $X = A \times 2^a$ and $Y = B \times 2^b$ has four segments:

1. Compare exponents (subtract $a - b$).
2. Align mantissas (shift the mantissa of the number with the smaller exponent right by the difference).
3. Add or subtract mantissas.
4. Normalize the result (shift the mantissa and adjust the exponent).

Registers between segments hold the intermediate results so that while one pair of numbers is in segment 3, the next pair is in segment 2, and so on.

Numerical example: $X = 0.9504 \times 10^3$ and $Y = 0.8200 \times 10^2$.

• Exponent difference = 1; align: $Y = 0.0820 \times 10^3$.
• Add: $0.9504 + 0.0820 = 1.0324 \times 10^3$.
• Normalize: $0.10324 \times 10^4$.

(a) LDA 7050H: Load Accumulator Direct. A three-byte instruction (3AH, 50H, 70H). The content of memory location 7050H is copied into the accumulator. Flags are not affected. Example: if (7050H) = 4CH, then A = 4CH after execution. Addressing mode: direct. It needs 4 machine cycles (13 T-states).

(b) CPI 35H: Compare Immediate. A two-byte instruction (FEH, 35H). The data 35H is subtracted from the accumulator internally and the result is discarded; only the flags are set. If A < 35H then CY = 1; if A = 35H then Z = 1; if A > 35H then CY = 0 and Z = 0. The accumulator is unchanged.

(c) PUSH B: Push register pair BC on the stack. A one-byte instruction (C5H). SP is decremented and B is stored at the address in SP; SP is decremented again and C is stored there:

• SP ← SP − 1; M[SP] ← B
• SP ← SP − 1; M[SP] ← C

Flags are not affected. It takes 3 machine cycles (12 T-states).

CISC (Complex Instruction Set Computer) architecture has a large and powerful instruction set. Typical characteristics:

1. Large number of instructions: typically 100 to 250, including special-purpose instructions.
2. Many addressing modes: 5 to 20 modes, such as immediate, direct, indirect, indexed, relative.
3. Variable-length instruction formats: instructions differ in length and execution time.
4. Complex, powerful instructions: a single instruction can do work that needs several simple instructions (for example string moves, memory-to-memory operations).
5. Microprogrammed control unit: most instructions are decoded by microcode stored in ROM, which makes it easy to add new instructions.
6. Memory-to-memory operations: operands can be taken directly from memory.
7. Few general-purpose registers.
8. Smaller programs but slower instructions: code density is high and the compiler is simpler, but many instructions need multiple clock cycles and pipelining is hard.

Examples: Intel x86, VAX, Motorola 68000.

Mnemonics: A mnemonic is a short symbolic name (abbreviation) for a machine instruction, such as MOV, ADD, JMP, LDA, that is easy for humans to remember. An assembler converts mnemonics into binary opcodes.

Instruction cycle: The total time needed to fetch an instruction from memory and execute it. It consists of one or more machine cycles.

Machine cycle: The time required to perform one basic operation, such as an opcode fetch, memory read or write, or I/O read or write. Each machine cycle consists of 3 to 6 T-states (clock periods).

Program: Tables at 3000H and 3020H (20 = 14H entries each) are added element by element. Sums are stored from 3040H and carries from 3060H. E is the index (00H to 13H), C is the counter.

        MVI  E, 00H      ; index
        MVI  C, 14H      ; 20 elements
LOOP:   MVI  H, 30H
        MOV  L, E
        MOV  B, M        ; B <- table 1 element (3000H + E)
        MOV  A, E
        ADI  20H
        MOV  L, A        ; HL = 3020H + E
        MOV  A, M        ; A <- table 2 element
        ADD  B           ; A <- sum, CY set on carry
        MOV  D, A        ; save sum (MOV keeps flags)
        MVI  A, 00H      ; MVI keeps flags
        ACI  00H         ; A <- carry (0 or 1)
        MOV  B, A        ; B <- carry
        MOV  A, E
        ADI  40H
        MOV  L, A        ; HL = 3040H + E
        MOV  M, D        ; store sum
        MOV  A, E
        ADI  60H
        MOV  L, A        ; HL = 3060H + E
        MOV  M, B        ; store carry
        INR  E
        DCR  C
        JNZ  LOOP
        HLT

Expression: $Y = (A + B) \times (C + D)$

Three-address instructions (operation, destination, source1, source2):

ADD  R1, A, B      ; R1 <- A + B
ADD  R2, C, D      ; R2 <- C + D
MUL  Y, R1, R2     ; Y  <- R1 * R2

Two-address instructions (destination also acts as the first source):

MOV  R1, A         ; R1 <- A
ADD  R1, B         ; R1 <- A + B
MOV  R2, C         ; R2 <- C
ADD  R2, D         ; R2 <- C + D
MUL  R1, R2        ; R1 <- (A+B) * (C+D)
MOV  Y, R1         ; Y  <- R1

One-address instructions (the accumulator AC is implied):

LOAD  A            ; AC <- A
ADD   B            ; AC <- A + B
STORE T            ; T  <- AC
LOAD  C            ; AC <- C
ADD   D            ; AC <- C + D
MUL   T            ; AC <- (C+D) * T
STORE Y            ; Y  <- AC

Parallel processing: Parallel processing is a method of carrying out two or more computations or data-processing tasks at the same time, using multiple functional units, processors or pipelines, instead of one after another. Its purpose is to increase computing speed and throughput.

Benefits

1. Higher speed and throughput, because many operations are done simultaneously.
2. Large problems (weather forecasting, simulation, image processing) can be solved in a reasonable time.
3. Better utilisation of hardware resources, since functional units do not sit idle.
4. Better reliability and fault tolerance: other processors can continue if one fails.
5. Scalability: more processors can be added to raise performance.

Flynn's classification (by the number of instruction streams and data streams):

1. SISD (Single Instruction, Single Data): one control unit, one processing unit, one data stream. A conventional uniprocessor (possibly pipelined). Example: a classic PC with one core.
2. SIMD (Single Instruction, Multiple Data): one control unit issues the same instruction to many processing elements, each working on its own data. Used for array and vector processors. Example: vector/GPU operations on arrays.
3. MISD (Multiple Instruction, Single Data): several processing units execute different instructions on the same data stream. It is rarely built; some fault-tolerant and systolic designs are quoted as examples.
4. MIMD (Multiple Instruction, Multiple Data): many processors execute different instructions on different data at the same time. Used in multiprocessors and multicomputers (shared or distributed memory). Example: multicore computers and clusters.

Use of flags: Flags are single-bit flip-flops, held in the flag register, that record the status of the result of the last arithmetic or logic operation. Conditional instructions (JZ, JC, CNZ, and so on) test them to make decisions and change the program flow.

The five flags of the 8085 (flag register: S Z X AC X P X CY):

1. Sign (S): set to 1 if bit D7 of the result is 1 (negative in 2's complement). Example: 40H − 50H = F0H, S = 1.
2. Zero (Z): set to 1 if the result is zero. Example: 25H − 25H = 00H, Z = 1.
3. Auxiliary Carry (AC): set when there is a carry out of bit D3 into D4. Used by DAA. Example: 0FH + 01H = 10H, AC = 1.
4. Parity (P): set to 1 if the result has an even number of 1s. Example: result 03H (0000 0011) has two 1s, P = 1.
5. Carry (CY): set when an addition produces a carry out of D7, or a subtraction needs a borrow. Example: F0H + 20H = 110H, CY = 1.

Example: A = 37H, ADI 57H gives 8EH, so S = 1, Z = 0, AC = 0, P = 1, CY = 0.

LXI H, 5070H is a three-byte instruction (opcode 21H, low byte 70H, high byte 50H). It needs three machine cycles: opcode fetch (4 T), memory read (3 T), memory read (3 T), total 10 T-states.

      M1: Opcode fetch        M2: Memory read        M3: Memory read
      T1  T2  T3  T4          T1  T2  T3             T1  T2  T3
ALE   |‾|_________           |‾|_______             |‾|_______
A15-8 [PC high]---           [(PC+1) high]--         [(PC+2) high]--
AD7-0 [PC low][21H]--        [(PC+1)low][70H]        [(PC+2)low][50H]
RD    ‾‾‾|___|‾‾‾‾‾‾         ‾‾‾‾|___|‾‾‾            ‾‾‾‾|___|‾‾‾
IO/M  low (memory) throughout
S1S0  1 1                    0 1                      0 1

• M1: the opcode 21H is fetched from address PC (say 2000H) and decoded in T4. PC becomes 2001H.
• M2: the byte at 2001H, 70H, is read and stored in register L. PC becomes 2002H.
• M3: the byte at 2002H, 50H, is read and stored in register H. PC becomes 2003H.

After execution HL = 5070H.

The control unit finds the type of an instruction from its opcode field, after the instruction has been fetched into the instruction register (IR).

Steps:

1. Fetch: the address in the program counter is sent to memory; the instruction word is read and placed in the IR; PC is incremented.
2. Decode: the opcode bits in the IR are sent to the instruction decoder. The decoder activates exactly one output line for each opcode, which identifies the instruction.
3. Determine the type: the mode bit and opcode tell whether it is a memory-reference, register-reference or I/O instruction. For example, in the basic computer, the opcode (bits 12-14) and mode bit I (bit 15) are tested: opcode 111 with I = 0 means register-reference; opcode 111 with I = 1 means input/output; opcode other than 111 means memory-reference, and I = 1 means indirect addressing.
4. Generate control signals: the decoder output and the timing signals from the sequence counter are combined to give the control signals for the micro-operations that execute the instruction. In a microprogrammed unit, the opcode is mapped to the start address of a micro-routine in control memory.

Microprogram sequencer: A microprogram sequencer is the circuit of a microprogrammed control unit that determines the address of the next microinstruction to be read from control memory. It contains the control address register (CAR), an incrementer, multiplexers, the mapping logic, a subroutine register and branch (condition) logic. It chooses among: CAR + 1, a branch address, the mapped opcode address, or a return address.

Hardwired vs microprogrammed control unit

Pipeline hazards: A hazard is a situation that prevents the next instruction in the pipeline from executing in its clock cycle, and so stalls the pipeline or causes wrong results. There are three types.

1. Structural (resource) hazard: two instructions need the same hardware resource at the same time, for example both need memory (one to fetch an instruction, the other to read data). Solved by duplicating resources (separate instruction and data memories or caches) or stalling.
2. Data hazard: an instruction depends on the result of a previous instruction that has not yet completed. For example, ADD R1, R2, R3 followed by SUB R4, R1, R5 needs R1 before it is written. Types are RAW, WAR and WAW. Solved by operand forwarding (bypassing), compiler instruction reordering, delayed load or inserting stalls (NOPs).
3. Control (branch) hazard: a branch or jump changes the PC, so the instructions already fetched after it may be wrong. Solved by prefetching both paths, a branch target buffer, branch prediction, delayed branch, or flushing the pipeline.

(a) Addressing modes of 8085

The addressing mode is how an instruction locates its operand. The 8085 has five modes:

1. Immediate: the data is in the instruction, e.g. MVI A, 35H.
2. Register: the operand is in a register, e.g. MOV A, B.
3. Direct: the instruction gives the 16-bit address of the data, e.g. LDA 2050H.
4. Register indirect: a register pair holds the address, e.g. MOV A, M; LDAX B.
5. Implicit: the operand is implied by the opcode, e.g. CMA, RAL.

(b) Vector Processing

Vector processing is the processing of vectors (one-dimensional arrays of data) by a single instruction, instead of looping over each element. A vector processor has vector registers, pipelined functional units and a special vector instruction set. A vector instruction contains the operation code, base addresses of the source and destination vectors, and the vector length. For example, C(1:100) = A(1:100) + B(1:100) is one instruction instead of a 100-iteration loop.

Advantages: it removes loop overhead and instruction-fetch time, avoids data hazards inside the vector because the elements are independent, and gives high speed for scientific work such as weather forecasting, matrix operations and image processing. Examples: Cray-1, and vector extensions in modern CPUs.

Symbolic microprogram: A symbolic microprogram is the microprogram written in a symbolic (assembly-like) language with labels and mnemonic fields for micro-operations, condition, branch and address, in place of binary microinstructions. An assembler translates it into the binary microprogram placed in control memory. Example: FETCH: AR ← PC U JMP NEXT.

Program: the array begins at 8050H and ends with 00H. D holds the running sum and B counts the carries.

        MVI  D, 00H      ; sum = 0
        MVI  B, 00H      ; carry count = 0
        LXI  H, 8050H    ; pointer to the array
LOOP:   MOV  A, M        ; get next byte
        CPI  00H         ; end of array?
        JZ   DONE
        ADD  D           ; A <- byte + sum
        MOV  D, A
        JNC  NEXT
        INR  B           ; count carry
NEXT:   INX  H
        JMP  LOOP
DONE:   MOV  A, D
        STA  9050H       ; store sum
        MOV  A, B
        STA  9051H       ; store total carry
        HLT

Expression: $X = A - B + \dfrac{C \times (D \times E + F)}{C} + H \times K$

(a) General register computer, two-address instructions

MOV  R1, D         ; R1 <- D
MUL  R1, E         ; R1 <- D*E
ADD  R1, F         ; R1 <- D*E + F
MUL  R1, C         ; R1 <- C*(D*E+F)
DIV  R1, C         ; R1 <- C*(D*E+F)/C
MOV  R2, H         ; R2 <- H
MUL  R2, K         ; R2 <- H*K
MOV  R3, A         ; R3 <- A
SUB  R3, B         ; R3 <- A - B
ADD  R3, R1        ; R3 <- A - B + C*(D*E+F)/C
ADD  R3, R2        ; R3 <- ... + H*K
MOV  X, R3         ; X <- R3

(b) Accumulator computer, one-address instructions

LOAD  D            ; AC <- D
MUL   E            ; AC <- D*E
ADD   F            ; AC <- D*E + F
MUL   C            ; AC <- C*(D*E+F)
DIV   C            ; AC <- C*(D*E+F)/C
STORE T            ; T  <- AC
LOAD  H            ; AC <- H
MUL   K            ; AC <- H*K
ADD   T            ; AC <- H*K + T
STORE T
LOAD  A            ; AC <- A
SUB   B            ; AC <- A - B
ADD   T            ; AC <- A - B + T
STORE X            ; X  <- AC

(c) Stack computer, zero-address instructions (reverse Polish form: $D\,E\,*\,F\,+\,C\,*\,C\,/\,A\,B\,-\,+\,H\,K\,*\,+$)

PUSH D
PUSH E
MUL                ; D*E
PUSH F
ADD                ; D*E + F
PUSH C
MUL                ; C*(D*E+F)
PUSH C
DIV                ; C*(D*E+F)/C
PUSH A
PUSH B
SUB                ; A - B
ADD                ; (A-B) + C*(D*E+F)/C
PUSH H
PUSH K
MUL                ; H*K
ADD                ; final result
POP  X             ; X <- top of stack

Control word: A control word is a string of bits in which each bit (or group of bits) represents a control signal or micro-operation to be activated in a given clock period. It selects registers, ALU function, bus paths, memory read/write and so on. In a microprogrammed unit, each microinstruction is a control word stored in control memory.

For example, in a datapath with fields for selecting source A (SELA), source B (SELB), destination (SELD) and ALU operation (OPR), the control word is the concatenation SELA | SELB | SELD | OPR. The 14-bit word 010 011 010 01010 would give R2 ← R2 + R3 style operations, depending on the codes used.

Structure of the control unit

The control unit has the following main parts.

1. Instruction register (IR): holds the current instruction; its opcode is decoded.
2. Instruction decoder: converts the opcode into one active line per instruction.
3. Sequence (timing) counter and clock: produces timing signals T0, T1, T2, ... that order the micro-operations.
4. Control logic gates (hardwired) or control memory with micro-program sequencer (microprogrammed): combine decoder outputs, timing signals and status flags to produce control signals.
5. Status flags and condition inputs: results of previous operations used for conditional execution.
6. Control signal outputs: go to the ALU, registers, buses and memory.

Control memory-based structure: the opcode is mapped to a starting address; the control address register (CAR) fetches the microinstruction into the control data register, which supplies the control word; the sequencer then computes the next address.

Basic requirements of a control unit

1. Fetch instructions from memory in correct order (sequencing).
2. Decode each instruction to identify the operation.
3. Generate the correct control signals in the correct time order for each micro-operation (execution).
4. Respond to status flags and external signals such as interrupts, reset and wait.
5. Control the data movement between CPU, memory and I/O.
6. Be fast, and flexible enough to add or change instructions.

Addressing mode: The addressing mode is the method an instruction uses to specify the location of its operand, such as immediate, register, direct, register indirect and implicit (the five 8085 modes).

Flags after ADD B with A = 37H and B = 57H:

$37\text{H} + 57\text{H} = 8E\text{H} = 1000\;1110_2$

• Sign (S): D7 = 1, so S = 1.
• Zero (Z): the result is not zero, so Z = 0.
• Auxiliary carry (AC): low nibbles 7H + 7H = EH, no carry out of D3, so AC = 0.
• Parity (P): 8EH has four 1s (even), so P = 1.
• Carry (CY): no carry out of D7, so CY = 0.

Flag register (S Z X AC X P X CY) = 1 0 X 0 X 1 X 0, which is 84H when the undefined bits are 0.

Common bus system: In a basic computer, many registers must exchange data with each other and with memory. Connecting every pair of registers with its own lines would need a huge number of wires. A common bus is a single set of shared lines to which all registers are connected, so that any register can transfer data to any other register through it.

Requirements

1. Reduced wiring and cost: one shared path replaces many point-to-point links.
2. Selection of the source: only one register may place data on the bus at a time, so a multiplexer (or tri-state buffers) selects the source register using select lines S2 S1 S0.
3. Destination control: a load (LD) input on each register decides which register accepts the bus data on the clock edge.
4. Increment/clear control: registers such as PC and AR need INR and CLR inputs.
5. Memory and ALU connection: memory read/write, the ALU (via AC and DR) are linked to the bus.

  Memory (4096x16) <---> |        |
  AR  ------------------>|        |
  PC  <----------------->|  COMMON|---> select S2 S1 S0 -> MUX
  DR  <----------------->|   BUS  |
  AC  <----> ALU <------>|        |
  IR  <------------------|        |
  TR  <----------------->|        |
  OUTR <-----------------|        |

For example, the transfer AR ← PC is done by S2S1S0 = 010 (select PC) and enabling LD of AR.

Symbolic microinstruction: A symbolic microinstruction is the human-readable form of a microinstruction, written in assembly-like symbols so that micro-programs are easy to write. It is translated by a micro-assembler into binary code. Format of one line: Label: micro-operations; CD; BR; AD. Example: FETCH: AR ← PC U JMP NEXT.

Microinstruction format

A microinstruction word has these fields:

• F1, F2, F3 (micro-operation fields): each field selects one micro-operation (up to 7 per field, 000 means no operation), so up to three micro-operations execute at one time. Example: F1 = 001 means AC ← AC + DR.
• CD (condition field): selects the status bit to test: 00 = always 1 (unconditional, U), 01 = DR(15) (I), 10 = AC(15) (S), 11 = AC = 0 (Z).
• BR (branch field): with AD, selects the next-address action: JMP (jump if the condition is 1), CALL (jump and save the return address), RET (return), MAP (map the opcode to an address).
• AD (address field): the branch address, 7 bits for a 128-word control memory.

Total word length is 20 bits.

Stack: A stack is a LIFO (last-in first-out) storage in which items are inserted (pushed) and removed (popped) only at the top. The stack pointer (SP) always holds the address of the top item.

Organization of a register stack

A register stack is made of a finite number of registers (for example 64 words, C0 to C63) forming the stack, with the following elements:

• Stack pointer SP: a 6-bit register that gives the address of the top item. Initially SP = 0.
• FULL flip-flop: set to 1 when the stack is full (SP = 63).
• EMPTY flip-flop: set to 1 when the stack is empty (SP = 0).
• DR (data register): holds the data to be pushed or popped.

 Address
   63 |   |
   ...|   |
    4 | C |
    3 | B |
    2 | A |  <- top when SP = 3? (SP -> top)
    1 |   |
    0 |   |
          DR <-> stack

PUSH operation: $SP \leftarrow SP + 1;\quad M[SP] \leftarrow DR;$ If SP = 0 after incrementing, the stack is full: FULL ← 1; EMPTY ← 0.

POP operation: $DR \leftarrow M[SP];\quad SP \leftarrow SP - 1;$ If SP = 0 after decrementing, EMPTY ← 1; FULL ← 0.

The SP is 6 bits, so it wraps from 63 to 0 when the stack becomes full.

Pipeline conflict (hazard): A pipeline conflict is a condition in which the next instruction cannot enter the pipeline in the following clock cycle because of resource sharing, data dependency or branching. The main kinds are resource (structural) conflicts, data dependency conflicts and branch difficulties.

Data dependency: It occurs when an instruction needs data that a previous instruction has not yet produced. Example: ADD R1, R2, R3 followed by SUB R4, R1, R5; SUB needs R1 before ADD has written it. Solutions:

• Hardware interlock: a circuit detects the conflict and delays the dependent instruction by inserting stall cycles.
• Operand forwarding (bypassing): the result is passed directly from the ALU output to the next instruction's input without waiting for the register write.
• Delayed load: the compiler rearranges instructions or inserts NOPs to give the needed time.

Handling of branch instructions: A branch changes the PC, so instructions already fetched may be wrong. Methods:

• Prefetch target instruction: fetch both the branch target and the next sequential instruction; keep the right one.
• Branch target buffer (BTB): an associative memory holding the target instructions of recently used branches.
• Loop buffer: a small fast buffer that holds a whole loop.
• Branch prediction: guess the branch outcome (static or dynamic) and fetch accordingly.
• Delayed branch: the compiler places useful instructions after the branch or inserts NOPs so that the pipeline is not stalled.

Working principle of the control unit

The control unit directs the operation of the whole processor. For every instruction it repeats the cycle fetch, decode, execute, using timing signals to order the micro-operations. A hardwired control unit has these parts: instruction register (IR), 3-to-8 opcode decoder, a 4-bit sequence counter (SC) with a 4-to-16 timing decoder (T0 to T15), control logic gates, and the flags.

1. The sequence counter is cleared at the start; it is incremented on each clock pulse, and the timing decoder activates T0, T1, T2, ... one at a time.
2. Fetch:
   • T0: AR ← PC
   • T1: IR ← M[AR], PC ← PC + 1
   • T2: decode the opcode in IR(12-14), AR ← IR(0-11), I ← IR(15)
3. After T2 the opcode decoder output (D0 to D7) and the mode bit I decide the type of instruction. The control gates combine D, I and T signals to produce the control signals for the execution micro-operations in T3, T4, ... For example, ADD: D1T4: DR ← M[AR]; D1T5: AC ← AC + DR, SC ← 0.
4. At the end of execution, SC is cleared and a new instruction cycle starts.

Timing diagram:

CLK   |‾|_|‾|_|‾|_|‾|_|‾|_|‾|_
T0    ‾‾‾|_________________
T1    ____|‾‾‾|____________
T2    ________|‾‾‾|________
T3    ____________|‾‾‾|____
D1    ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾ (after decode)
Control signal = D1 . T4 (one clock wide)

(a) LHLD 5050H: Load H and L Direct. A three-byte instruction (2AH, 50H, 50H). The content of memory location 5050H is loaded into register L, and the content of the next location 5051H is loaded into register H:

• L ← M[5050H]
• H ← M[5051H]

Flags are not affected. Addressing mode: direct. It takes 5 machine cycles (16 T-states). Example: if (5050H) = 34H and (5051H) = 12H, then HL = 1234H.

(b) CPI 34H: Compare Immediate with the accumulator. A two-byte instruction (FEH, 34H). The data 34H is subtracted from A internally and only the flags are changed; A keeps its value. If A < 34H, CY = 1; if A = 34H, Z = 1; if A > 34H, CY = 0 and Z = 0. Addressing mode: immediate.

(c) JNZ 6080H: Jump on No Zero. A three-byte instruction (C2H, 80H, 60H). If the zero flag is 0 (the last result was not zero), the program counter is loaded with 6080H and execution continues from there; if Z = 1 the next sequential instruction is executed. Flags are not affected. Example: used to close a loop after DCR C.

Timing diagram for MOV B, C (opcode 41H, one byte): the instruction needs only one machine cycle, the opcode fetch, with 4 T-states.

        T1     T2     T3     T4
ALE    _|‾‾‾|_______________
A15-8  [ PC high ]-----------------
AD7-0  [PC low][ 41H ]--[ idle ]
RD     ‾‾‾‾‾‾|_______|‾‾‾‾‾‾
IO/M   __________________________ (low: memory)

• T1: PC is put on the address bus; ALE high latches the low byte.
• T2: RD goes low; the opcode 41H is read from memory; PC is incremented.
• T3: the opcode is moved to the instruction register.
• T4: it is decoded and executed: B ← C.

Program to sort 10 bytes from 7050H in ascending order (bubble sort). B holds the number of passes (9), C the comparisons per pass (9).

        MVI  B, 09H      ; passes
OUTER:  LXI  H, 7050H    ; start of the array
        MVI  C, 09H      ; comparisons per pass
INNER:  MOV  A, M        ; A <- first element
        INX  H
        CMP  M           ; compare with next element
        JC   NOSWAP      ; first < next -> in order
        MOV  D, M        ; swap the two elements
        MOV  M, A
        DCX  H
        MOV  M, D
        INX  H
NOSWAP: DCR  C
        JNZ  INNER
        DCR  B
        JNZ  OUTER
        HLT

After execution the smallest number is at 7050H and the largest at 7059H.

Address sequencing: Address sequencing is the way the microprogram control unit determines the address of the next microinstruction in the control memory. The control memory holds the micro-routines for all instructions, so the address sequence must handle ordinary execution, branching, subroutines and the mapping from opcode.

Steps of address sequencing

1. Initial address: when power is on or reset, the control address register (CAR) is loaded with the address of the first microinstruction, which starts the instruction FETCH routine.
2. Fetch routine: microinstructions in sequence (CAR ← CAR + 1) fetch the instruction from main memory into the instruction register.
3. Mapping: at the end of the fetch routine, the opcode of the instruction register is mapped to the starting address of the corresponding micro-routine (the MAP branch).
4. Execution of the micro-routine: the microinstructions are executed in sequence by incrementing CAR.
5. Branching: conditional or unconditional branching loads CAR with the branch address (AD field) when the tested status bit satisfies the condition; otherwise CAR is incremented.
6. Subroutine call and return: a CALL stores the return address CAR + 1 in the subroutine register (SBR) and branches; RET loads CAR from SBR. This lets common micro-routines (e.g. effective address calculation) be shared.
7. Return to fetch: after the last microinstruction of the routine, control returns to the first address of the fetch routine (usually by an unconditional jump), and the next instruction cycle begins.

Selection of address for control memory

          +--------------------+
 CAR+1 -->|0                   |
 Branch  >|1       MUX 1       |--> Control Address Register (CAR) --> Control memory
 address  |   (4 x 1 select)   |
 Mapping >|2                   |
 SBR     >|3                   |
          +--^------^----------+
             S1     S0
          +--+------+----------+
 CD field>|     MUX 2           |-> test bit
 status  >|  (status bit select)|        Input logic -> S1, S0, load SBR
 bits     +---------------------+       (from BR field and test bit)

• MUX 1 selects the next address: S1S0 = 00 gives CAR + 1 (incrementer), 01 the branch address (AD), 10 the mapping logic output, 11 the subroutine register.
• MUX 2 selects one of the status bits chosen by the CD field and passes it to the input logic.
• The input logic uses the BR field and the selected bit: for JMP it takes the branch address if the bit is 1 (otherwise increments), for CALL it also loads SBR, for RET it selects SBR, and for MAP it selects the mapping output.

Comparison of 8085 and 8086

Flags for SUB B

Taking the 8-bit values A = 45H and B = 67H:

$45\text{H} - 67\text{H}: \quad 45\text{H} + (\text{2's complement of }67\text{H} = 99\text{H}) = DE\text{H}$

with no carry out, so a borrow occurred. Result $DE\text{H} = 1101\;1110_2$.

• S = 1 (D7 = 1)
• Z = 0
• AC = 0 (low nibble 5 + 9 = E, no carry out of D3)
• P = 1 (six 1s, even)
• CY = 1 (borrow)

Flag register = 1 0 X 0 X 1 X 1 = 85H.

MVI B, 35H is a two-byte instruction (opcode 06H followed by the data byte 35H). It needs two machine cycles: opcode fetch (4 T-states) and memory read (3 T-states), total 7 T-states.

        |<------ M1: Opcode fetch ------>|<---- M2: Memory read ---->|
        T1    T2    T3    T4              T1    T2    T3
ALE     _|‾‾|______________                _|‾‾|__________
A15-A8  [ PC high ]-----------             [ PC+1 high ]---
AD7-0   [PC low][ 06H ]--[idle]            [PC+1 low][ 35H ]
RD      ‾‾‾‾‾|_____|‾‾‾‾‾‾‾‾‾‾            ‾‾‾‾‾‾|_____|‾‾‾
IO/M    ___________________________        ___________________
S1,S0   1,1 (opcode fetch)                 0,1 (memory read)

M1 (opcode fetch):

• T1: the address in PC (say 2000H) is put on the address bus; ALE is high to latch the low byte; IO/M = 0.
• T2: RD goes low; the opcode 06H is read from memory; PC becomes 2001H.
• T3: the opcode is placed in the instruction register; RD goes high.
• T4: the opcode is decoded; the processor sees that a data byte is needed.

M2 (memory read):

• T1: address 2001H is placed on the bus.
• T2: RD goes low; the data byte 35H is read; PC becomes 2002H.
• T3: 35H is stored in register B.

Data transfer instructions move data from one place to another (register to register, memory to register, register to memory, I/O to register) without changing the data. The source content is unchanged (copied), and flags are normally not affected.

Examples: MOV (move), LOAD/LDA, STORE/STA, PUSH, POP, XCHG, IN, OUT. For example, MOV A,B copies register B into A, and LDA 2050H loads the accumulator from memory location 2050H.

Arithmetic instructions perform arithmetic operations on data and update status flags (carry, zero, sign, parity, overflow).

Data transfer instructions bring operands into registers, arithmetic instructions process them, and the result is moved back to memory by data transfer instructions.

Evaluate $X = (A+B-C)\times(D+E\times F)$.

Three-address instructions (operation, destination, source1, source2):

ADD  R1, A, B      ; R1 = A + B
SUB  R1, R1, C     ; R1 = A + B - C
MUL  R2, E, F      ; R2 = E * F
ADD  R2, D, R2     ; R2 = D + E*F
MUL  X, R1, R2     ; X = R1 * R2

One-address instructions (accumulator AC and temporary memory T):

LOAD  E
MUL   F            ; AC = E*F
ADD   D            ; AC = D + E*F
STORE T
LOAD  A
ADD   B
SUB   C            ; AC = A + B - C
MUL   T            ; AC = (A+B-C)*(D+E*F)
STORE X

Zero-address instructions (stack machine, postfix form $A\,B\,+\,C\,-\,D\,E\,F\,*\,+\,*$):

PUSH A
PUSH B
ADD
PUSH C
SUB
PUSH D
PUSH E
PUSH F
MUL
ADD
MUL
POP  X

An arithmetic pipeline divides an arithmetic operation into sub-operations executed in separate pipeline segments, each separated by registers, so several operations are in different stages at the same time. It is used for fixed-point multiplication and floating-point operations on vectors.

Example: floating-point addition/subtraction pipeline for $X = A\times 2^a + B\times 2^b$:

 Inputs: exponents a, b ; mantissas A, B
   |
 [ Segment 1: Compare exponents by subtraction ]
   |            (R)
 [ Segment 2: Align mantissas (shift smaller one right) ]
   |            (R)
 [ Segment 3: Add / subtract mantissas ]
   |            (R)
 [ Segment 4: Normalize result, adjust exponent ]
   |
 Output

Working:

1. Segment 1 subtracts the exponents; the difference gives the shift amount.
2. Segment 2 shifts the mantissa of the number with the smaller exponent so exponents are equal.
3. Segment 3 adds or subtracts the aligned mantissas.
4. Segment 4 normalizes the result (shift mantissa, adjust exponent) and handles overflow/underflow.

Registers between segments hold intermediate results, so while one pair of operands is being added, the next is being aligned and the one after is compared. After the pipe fills, one result is produced every clock cycle, giving speedup close to the number of segments $k$: for $n$ tasks, time is $(k+n-1)t_p$ instead of $nkt_p$.

Vector processing is the processing of vectors (one-dimensional arrays of data) by a single vector instruction that operates on all elements, using pipelined or parallel arithmetic units. It removes the loop overhead of scalar processing, for example $C(i) = A(i) + B(i),\ i=1..n$ is done by one instruction ADD C, A, B with vector length $n$. It is used in weather forecasting, seismic analysis, image processing and scientific simulation.

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

1. SISD (Single Instruction, Single Data): one control unit, one processor, one data stream. Conventional serial uniprocessor computers. No parallelism in instruction or data.
2. SIMD (Single Instruction, Multiple Data): one control unit broadcasts the same instruction to many processing elements, each working on a different data item. Examples: array processors, vector processors, GPUs.
3. MISD (Multiple Instruction, Single Data): many processors perform different instructions on the same data stream. Rarely practical; used in some fault-tolerant or systolic systems.
4. MIMD (Multiple Instruction, Multiple Data): many processors each execute their own instructions on their own data, working independently. Examples: multiprocessors, multicore CPUs, clusters, distributed systems.

a) DAA (Decimal Adjust Accumulator): 8085 instruction, 1 byte, that converts the binary result in the accumulator after adding two BCD numbers into a valid BCD result.

• If the lower nibble of A is greater than 9 or the AC flag is set, 06H is added to A.
• If the upper nibble is then greater than 9 or the CY flag is set, 60H is added to the upper nibble.

Example: A = 38H (BCD 38) is added to 49H, giving 81H. DAA adds 06H since the lower nibble 1 with AC set, giving 87H, which is BCD 87.

b) RLC (Rotate Accumulator Left): each bit of A moves one position left, bit D7 goes to bit D0 and also to the carry flag CY. Only CY is affected. Example: A = 1011 0001, then after RLC, A = 0110 0011, CY = 1.

c) INX B (Increment register pair BC): increments the 16-bit content of the BC register pair by 1. No flags are affected. Example: BC = 25FFH, then after INX B, BC = 2600H.

Micro-operation: an elementary operation performed on data stored in registers in one clock pulse, such as a register transfer, shift or increment, for example $R1 \leftarrow R2$ or $PC \leftarrow PC + 1$. A machine instruction is carried out by a sequence of micro-operations.

Micro-instruction: a control word stored in control memory that specifies the set of micro-operations (control signals) to be executed in one clock period, along with the next-address information (condition, branch address).

Micro-program: a sequence of micro-instructions stored in control memory that implements one machine instruction or the instruction cycle (fetch, decode, execute). The set of microprograms forms the firmware of a microprogrammed control unit.

Program (8085) to find the smallest element, length at 2310H, block starting at 2050H, result stored at 2311H:

        LDA  2310H      ; A = length of block
        MOV  C, A       ; C = counter
        LXI  H, 2050H   ; HL points to the first element
        MOV  A, M       ; assume first element is smallest
        DCR  C          ; remaining elements
        JZ   DONE       ; block of one element
LOOP:   INX  H          ; next element
        CMP  M          ; compare A - M
        JC   SKIP       ; if A < M, A remains smallest
        MOV  A, M       ; else M is smaller; load into A
SKIP:   DCR  C
        JNZ  LOOP
DONE:   STA  2311H      ; store the smallest
        HLT

CMP M sets carry when A < M, so A holds the smallest value found so far at each step.

A microprogram sequencer generates the address of the next micro-instruction for the control memory. It decides whether the next address is the next sequential one, a branch address, a subroutine return, or a mapped address from an instruction opcode.

Block diagram

 Instruction code (opcode)
        |
   [ Mapping logic ] ---------------------+
                                           |
 Branch address (from microinstruction) -->|
                                           v
 External       +-----------+       [ MUX 1 ]  <---- Return address
 Input -------> |  Input    | S1 S0   |             (from SBR)
 (condition,    |  logic    |-------> | select             ^
  status bits)  +-----------+          v                   |
                                [ CAR: control address      |
                                       register ]           |
                                   |        |               |
                                   |   [ Incrementer ] +1   |
                                   |        |               |
                                   |   (to MUX 1, next seq.)|
                                   |        +--> [ SBR: subroutine register ]
                                   v
                           [ Control memory ]
                                   |
                           Microinstruction (to pipeline register / control signals)

Components and working

1. Control address register (CAR): holds the address of the micro-instruction to be read from control memory.
2. Incrementer: increments CAR by 1 to give the next sequential address.
3. Multiplexer (MUX): selects the next address from four sources: the incremented CAR (sequential), the branch address field of the current micro-instruction, the mapped address from the opcode (mapping logic), or the return address held in the subroutine register (SBR).
4. Mapping logic: converts the opcode bits of the machine instruction into the starting address of its microprogram in control memory.
5. Subroutine register (SBR): saves the return address when a microprogram subroutine is called, and restores it on return.
6. Input (condition) logic: tests the status bit chosen by the microinstruction together with its branch field, and generates select signals S1 S0 for the multiplexer. If the condition is true, branch or call is taken; otherwise the next sequential address is used.

Operation: the address in CAR reads a micro-instruction; its control fields drive the datapath, while its branch/condition fields drive the sequencer, which then loads CAR with the next address. This repeats until the machine instruction is complete, when CAR is loaded via mapping for the next instruction's fetch routine.

Interrupt: a signal sent to the CPU by an I/O device or program (or internal event) requesting that the CPU suspend its current program, execute a special service routine (ISR), and then resume the interrupted program. The CPU saves the return address and processor state before servicing and restores them afterwards. Interrupts avoid wasteful polling of devices.

Types of interrupt

1. Hardware interrupts: raised by external devices.
   • Maskable interrupts can be enabled or disabled by the programmer (e.g. INTR, RST 7.5, 6.5, 5.5 in the 8085).
   • Non-maskable interrupts cannot be disabled and are for critical events such as power failure (e.g. TRAP).
2. Software interrupts: generated by an instruction in a program (e.g. RST n in the 8085, INT n in the 8086), used for system calls.
3. Internal (exception) interrupts / traps: caused by errors inside the CPU such as divide-by-zero, overflow, invalid opcode or page fault.

Interrupts may also be classed as vectored (the device supplies or the CPU fixes the ISR address) and non-vectored (the ISR address is supplied by the device or found by polling).

Matrix multiplication on a vector computer

For $C = A\times B$ with $n\times n$ matrices: $C_{ij} = \sum_{k=1}^{n} A_{ik}B_{kj}$

On a scalar machine this is three nested loops with $n^3$ multiply-adds. On a vector computer the innermost loop (the sum over $k$) is replaced by vector instructions: the $i$-th row of $A$ and the $j$-th column of $B$ are loaded into vector registers and multiplied element by element by a pipelined multiplier, with products accumulated by a pipelined adder, i.e. a vector inner product:

for i = 1..n
  for j = 1..n
     V1 = A[i, 1..n]          ; vector load (row)
     V2 = B[1..n, j]          ; vector load (column, stride n)
     V3 = V1 * V2             ; vector multiply
     C[i][j] = SUM(V3)        ; vector accumulate (reduction)

Alternatively, row $i$ of $C$ can be built as a sum of scaled rows: $C_{i*} = \sum_k A_{ik}\,B_{k*}$, so the inner operations become vector multiply-add on whole rows ($n^2$ vector operations of length $n$), which avoids strided column access. Pipelining makes one product per clock cycle after start-up, greatly reducing the instruction fetch/loop overhead.