Computer Architecture

Common bus system. In the basic computer, the registers and memory are connected through a single common bus of 16 lines, so that any register can send data to any other by using one shared set of wires. Only one source can drive the bus at any time. The source is chosen by a bus selector built from 16 multiplexers (4-to-1 style, 8 inputs), controlled by the select lines $S_2S_1S_0$.

Diagram:

        +------------- 16-bit common bus --------------+
        |    |     |     |     |     |     |      |    |
       MEM   AR    PC    DR    AC    IR    TR   INPR  OUTR
      (111) (001) (010) (011) (100) (101) (110)
        ^ select by S2 S1 S0 (bus selector / multiplexers)

Operation:

• The bus selector places the contents of the selected register on the bus.
• A destination register receives the data when its LD (load) control is $1$ at the clock edge. Registers also have INR (increment) and CLR (clear) inputs.
• The 12-bit registers AR and PC use the lower 12 bits of the bus; the memory address is always taken from AR.
• Memory read: $DR\leftarrow M[AR]$ puts memory on the bus ($S_2S_1S_0=111$) and loads DR. Memory write: $M[AR]\leftarrow DR$ with DR on the bus.
• Example $AR\leftarrow PC$: $S_2S_1S_0=010$ and LD of AR $=1$.
• The adder and logic unit takes AC and DR as inputs and its output goes to AC; the output of AC is also an input to the bus.

Advantage: fewer connections than separate paths between every pair of registers. Disadvantage: one transfer at a time over the bus.

Statement: $X=(A\cdot B+C-D)/(E+F\cdot G)$

(a) Three-address instructions (OP dest, src1, src2):

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

(b) Single-address (accumulator) instructions (AC is the implied operand):

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

(c) Zero-address (stack) instructions (operands are on the stack, the operation uses the top elements):

PUSH A
PUSH B
MUL               ; A*B
PUSH C
ADD               ; A*B + C
PUSH D
SUB               ; A*B + C - D
PUSH E
PUSH F
PUSH G
MUL               ; F*G
ADD               ; E + F*G
DIV               ; (A*B+C-D) / (E+F*G)
POP  X

This is the evaluation of the reverse Polish form $AB*C+D-EFG*+/$.

Evaluate $X = \dfrac{A + B \times C - D}{E \times F + G}$. The numerator is $A + (B \times C) - D$ and the denominator is $(E \times F) + G$.

(a) Three-address instructions (each instruction OP dest, src1, src2). Temporary registers R1 and R2 are used.

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

(b) Single-address (accumulator) instructions. One operand is in memory, the other is the accumulator AC. T is a temporary memory location.

LOAD  B        ; AC = B
MUL   C        ; AC = B*C
ADD   A        ; AC = A + B*C
SUB   D        ; AC = A + B*C - D
STORE T        ; T = numerator
LOAD  E        ; AC = E
MUL   F        ; AC = E*F
ADD   G        ; AC = E*F + G
STORE U        ; U = denominator
LOAD  T        ; AC = numerator
DIV   U        ; AC = numerator / denominator
STORE X        ; X = AC

(c) Zero-address (stack) instructions. Operations take their operands from the top of the stack. The expression is converted to reverse Polish notation: $A\,B\,C\,*\,+\,D\,-\,E\,F\,*\,G\,+\,/$.

PUSH A
PUSH B
PUSH C
MUL          ; B*C
ADD          ; A + B*C
PUSH D
SUB          ; A + B*C - D
PUSH E
PUSH F
MUL          ; E*F
PUSH G
ADD          ; E*F + G
DIV          ; (A+B*C-D) / (E*F+G)
POP X

The three-address program is shortest (6 instructions) but each instruction is long; the stack program has the shortest instructions but needs the most (14).

Common bus system. The basic computer has registers (AR, PC, DR, AC, IR, TR), a memory unit with 4096 words of 16 bits, and the INPR/OUTR registers. For data to move between them, instead of a dedicated path for each pair, a single shared common bus is used. The bus is 16 bits wide, and only one register or memory output can place data on it at one time.

Selection of the source. Three select lines $S_2S_1S_0$ drive a multiplexer (or three-state buffers) that picks the source:

Diagram (description).

              +------------------------------+
   S2 S1 S0 ->|  16-bit common bus (mux)     |
              +--^---^---^---^---^---^---^---+
                 |   |   |   |   |   |   |
              Memory AR  PC  DR  AC  IR  TR
              (111) (001)(010)(011)(100)(101)(110)
   Each register has LD (load), INR (increment), CLR (clear).
   AR, PC and the memory address use the 12 low-order bits; 
   AC <-> ALU <-> DR; INPR -> ALU; AC -> OUTR.

Operation.

• The source register is selected by $S_2S_1S_0$; its contents go on the bus.
• The destination register has its LD (load) input enabled and takes the bus contents at the next clock pulse. Several registers may load the same bus value at once.
• The address register AR (12 bits) supplies the memory address; the memory read/write is controlled by Read/Write signals, and data passes through the bus.
• PC and DR may be incremented (INR) or cleared (CLR); AC takes input from the adder/logic circuit (ALU) which combines AC and DR, as well as INPR.
• The 12-bit contents of AR and PC are placed in the low-order 12 bits of the bus (the top four bits are 0), and IR sends the 12-bit address field to the bus.

Example: $AR \leftarrow PC$ sets $S_2S_1S_0 = 010$ and enables LD of AR. The memory read $DR \leftarrow M[AR]$ sets $S_2S_1S_0 = 111$ and enables LD of DR.

Benefits: fewer connections and lower cost. Drawback: only one transfer can happen per clock cycle.

Overlapping register windows. In a RISC processor (e.g. Berkeley RISC, SPARC) a large bank of registers is divided into small windows, one per procedure. Procedure calls are very frequent in high-level programs, and saving and restoring registers to memory on every call/return is slow. With register windows, a call simply switches to a new window instead of pushing registers on the stack. The windows are overlapped: the registers at the end of one window are physically the same registers as those at the start of the next window, so parameters can be passed without copying.

Organisation of each window. Every window consists of:

• Local registers: used only by that procedure for its local variables and temporaries.
• High (input) registers: shared with the calling procedure; they receive the parameters passed by the caller and hold values returned to it.
• Low (output) registers: shared with the called procedure; the procedure puts parameters for the next call here.
• A few global registers, visible to all procedures.

Relationship among windows. For procedures A, B and C where A calls B and B calls C:

• The low (output) registers of A's window are the same physical registers as the high (input) registers of B's window.
• The low registers of B are the high registers of C.
• Local registers of each window are private and never shared.

Example (Berkeley RISC, 74 registers): 10 global registers R0-R9; 64 registers in windows. Each window has 10 local registers, 6 high (input), 6 low (output), so a window has 22 registers visible, and 16 physical registers are shared between adjacent windows. With 4 windows, the total is $4\times(10+6)=64$ window registers (the windows form a circular buffer, so the last window overlaps the first).

 window A:  [ high_A | local_A | low_A ]
                                  ||  (same physical registers)
 window B:                 [ high_B | local_B | low_B ]
                                                 ||
 window C:                                [ high_C | local_C | low_C ]

Operation. On a call, the current window pointer (CWP) moves to the next window, so the caller's low registers instantly become the callee's high registers. On return, CWP moves back and the results left in the callee's high registers are seen by the caller as its low registers. If the nesting depth exceeds the number of windows, the oldest window is saved to memory (window overflow) and brought back on underflow. Advantages: fast procedure call/return, no parameter copying, fewer memory references.

Flynn's classification. Michael Flynn (1966) classified computer architectures by the number of instruction streams and data streams that are processed simultaneously, giving four classes.

1. SISD (Single Instruction, Single Data). A conventional uniprocessor. One control unit fetches one instruction at a time and one processing unit operates on one data item at a time. Example: classic von Neumann machines, older PCs. Pipelining or a superscalar design may overlap instructions but the model is still SISD.

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

2. SIMD (Single Instruction, Multiple Data). One control unit broadcasts the same instruction to many processing elements, each working on its own data in lock-step. Suited to regular data-parallel work such as vector/matrix operations and image processing. Examples: array processors, vector processors, GPUs, MMX/SSE extensions.

                  +--> PU1 <--> Memory 1
 CU --- IS ------>+--> PU2 <--> Memory 2
                  +--> PUn <--> Memory n

3. MISD (Multiple Instruction, Single Data). Several processing units each execute a different instruction on the same data stream. It is rarely built in practice; examples are fault-tolerant systems executing different programs on the same input for redundancy (space-shuttle flight computers) and sometimes systolic arrays/pipelines.

 CU1 --IS1--> PU1 \
 CU2 --IS2--> PU2  >--- single data stream <--- Memory
 CUn --ISn--> PUn /

4. MIMD (Multiple Instruction, Multiple Data). Multiple processors, each with its own control unit, execute different instructions on different data at the same time. This is the most general and most common parallel model. Examples: multicore processors, multiprocessor servers, clusters and distributed systems. It has two forms:

• Shared-memory (tightly coupled) multiprocessors, all CPUs access a common memory.
• Distributed-memory (loosely coupled) multicomputers, each CPU has local memory and communicates by message passing.

 CU1 -IS1-> PU1 <-DS1-> Memory 1 \
 CU2 -IS2-> PU2 <-DS2-> Memory 2  >-- interconnection network
 CUn -ISn-> PUn <-DSn-> Memory n /

Pipeline hazards. A hazard is a situation that prevents the next instruction in the pipeline from executing in its designated clock cycle, causing a stall (bubble) and reducing throughput. There are three types.

1. Structural hazards. Two instructions need the same hardware resource at the same time, and the resource cannot serve both.

Example: with a single memory shared for instructions and data, a LOAD instruction in its memory-access (MEM) stage conflicts with the instruction fetch (IF) of a later instruction in the same cycle. One must wait a cycle.

Remedy: separate instruction and data memories (caches), duplicate or pipeline the functional units, or stall.

2. Data hazards. An instruction depends on the result of a previous instruction that is not yet complete. Types:

• RAW (read after write, true dependence): I2 reads a register before I1 has written it.

ADD R1, R2, R3     ; writes R1 in WB (cycle 5)
SUB R4, R1, R5     ; reads R1 in ID (cycle 3): stale value

• WAR (write after read, anti-dependence): a later instruction writes a register before an earlier instruction has read it (occurs when instructions are reordered).
• WAW (write after write, output dependence): two instructions write the same register and the writes complete in the wrong order.

Remedies: operand forwarding (bypassing) passes the ALU result straight to the next instruction's input; stalling/inserting NOPs (pipeline interlock); compiler instruction scheduling; register renaming (for WAR/WAW).

3. Control (branch) hazards. A branch or jump changes the program counter, so the instructions fetched after the branch may be the wrong ones, and the target is not known until the branch is decoded or executed.

Example:

      BEQ R1, R2, LABEL    ; outcome known in EX/MEM stage
      ADD R3, R4, R5       ; fetched, but may need to be discarded
      ...
LABEL: SUB R6, R7, R8

If the branch is taken, the instructions already fetched behind it must be flushed, costing 1-3 cycles.

Remedies: branch prediction (static or dynamic with a branch history table), delayed branch (the compiler fills the delay slot with a useful instruction), branch target buffer, early branch resolution in the decode stage, and prefetching both paths.

Summary: structural hazards come from resource conflicts, data hazards from dependences between instructions, and control hazards from changes in the instruction flow.

A computer system consists of hardware components that work together under a program. The basic components are as follows.

1. Central Processing Unit (CPU). It fetches, decodes and executes instructions. It contains:

• Arithmetic Logic Unit (ALU): performs arithmetic (add, subtract) and logical (AND, OR, compare, shift) operations.
• Control Unit (CU): generates timing and control signals that direct the other components and sequence the instruction cycle.
• Registers: small, very fast storage inside the CPU, such as the program counter (PC), instruction register (IR), memory address register (MAR), memory buffer register (MBR) and accumulator.

2. Main memory. Stores the programs and data currently in use. It is divided into addressable locations. RAM is volatile and read/write; ROM holds permanent start-up code. The CPU transfers data using MAR and MBR.

3. Input/Output (I/O) devices and modules. Input devices (keyboard, mouse, scanner) bring data in; output devices (monitor, printer) deliver results. I/O modules interface the devices to the system, handling speed and format differences, using programmed I/O, interrupts or DMA.

4. Secondary storage. Hard disk, SSD and optical media provide large, permanent (non-volatile) storage at lower speed.

5. System bus (interconnection). The shared pathways that carry information between components: the data bus (data transfer), address bus (location of memory/I/O) and control bus (read/write, interrupt, clock signals).

       +-----------------+
       |  CPU (ALU, CU,  |
       |   registers)    |
       +--------+--------+
                | system bus (data, address, control)
     +----------+-----------+
     |                      |
 Main memory           I/O modules ---> devices

Stored-program concept. The idea, proposed by John von Neumann (and used in the IAS machine), is that the instructions of a program and its data are stored together in the same main memory in binary form. The CPU reads instructions from memory one after another, and decodes and executes them. Earlier machines (such as ENIAC) were programmed by rewiring or setting switches, which was slow and error-prone; with a stored program the machine is reprogrammed simply by loading different contents into memory.

Key features

• A single read/write memory holds both instructions and data, addressed by location.
• Instructions are executed sequentially unless a branch changes the flow; the program counter (PC) holds the address of the next instruction.
• Instructions can be treated as data, so a program can be loaded, modified or generated by another program (compilers, loaders, operating systems).
• The processor repeatedly performs the fetch-decode-execute cycle.

Example. Computing $C=A+B$, with $A$ at address 100, $B$ at 101 and $C$ at 102, program stored at addresses 0-3:

Execution: PC=0, the CPU fetches LOAD 100 into IR via MAR/MBR, increments PC, decodes, and loads 5 into the accumulator. Next it fetches ADD 101, giving AC = 12. Then STORE 102 writes 12 into location 102. Finally HALT stops the machine. The instructions and the data lie in the same memory.

The shared path between CPU and memory limits speed (the von Neumann bottleneck).

CISC (Complex Instruction Set Computer) and RISC (Reduced Instruction Set Computer) are two design philosophies for the instruction set of a processor.

In short, CISC tries to reduce the number of instructions per program, while RISC reduces the number of cycles per instruction.

Pipelining divides a task into sub-tasks handled by separate segments that work in parallel on different tasks. The two main types are the instruction pipeline and the arithmetic pipeline.

Example (arithmetic pipeline). Floating-point addition of $X=A\times 2^{a}$ and $Y=B\times 2^{b}$ is split into four segments: (1) compare exponents, (2) align mantissa of the smaller number, (3) add mantissas, (4) normalise the result. While one pair is being normalised, the next pair is already in the addition stage.

Example (instruction pipeline). While instruction $I_1$ is being executed, $I_2$ is being decoded and $I_3$ is being fetched.

Non-restoring division. The dividend is $Q=10=1010_2$, the divisor is $M=4=0100_2$, the accumulator is $A=0000$ and the count is $n=4$ bits.

Rule for each cycle:

• If $A\ge 0$: shift $AQ$ left one bit, then $A\leftarrow A-M$.
• If $A<0$: shift $AQ$ left one bit, then $A\leftarrow A+M$.
• If the new $A\ge 0$ set $q_0=1$, otherwise set $q_0=0$.

After $n$ cycles, if $A<0$ perform a final correction $A\leftarrow A+M$.

Result: Quotient $=Q=0010_2=2$ and remainder $=A=0010_2=2$.

Check: $4\times2+2=10$.

Associative memory (content addressable memory, CAM) is a memory in which a word is located by its content rather than by its address. A search key is given and the memory compares it with all stored words simultaneously; the words that match are flagged. It is much faster than address-based search because all comparisons happen in parallel in hardware.

Block diagram and working.

            Argument register (A)  ----> n bits
            Key register (K)  --------> mask (which bits to compare)
                    |
                    v
   +-----------------------------------------+      Match register (M)
   |  Associative memory array               |      +----+
   |  m words x n bits                       |----->| M1 |  word 1 matches?
   |  (each cell has compare logic)          |----->| M2 |
   |                                         |----->| .. |
   +-----------------------------------------+      | Mm |
        ^                    |                      +----+
   Input (write)        Output (read)

Components:

• Argument register A holds the word to be searched.
• Key register K masks the argument. Only bit positions where $K=1$ take part in the comparison; where $K=0$ the bit is ignored.
• Associative memory array of $m$ words, each $n$ bits, where every cell has comparison logic.
• Match register M has one bit per word. $M_i=1$ if word $i$ matches the unmasked part of A.

Operation. The argument is placed in A and the mask in K. Every word is compared with A in parallel, the match bits are set in M, and the words with $M_i=1$ are read out (or written for a write operation). For a single bit of cell $j$ in word $i$ the match is $x_j=A_jF_{ij}+A_j'F_{ij}'$ and the word matches if

$M_i=\prod_{j=1}^{n}\left(x_j+K_j'\right)$

Uses: cache memory tags, virtual-memory page tables (TLB), and database or routing-table lookup.

Drawback: every cell needs comparison logic, so it is expensive compared to ordinary RAM.

The control unit generates the control signals that drive the data path. It can be built in two ways.

Direct Memory Access (DMA) lets an I/O device transfer a block of data directly to or from main memory without passing every word through the CPU. The transfer is managed by a DMA controller.

Structure of the DMA controller. It contains an address register (starting memory address), a word count register (number of words left), a control register (read/write, mode), a data buffer, and request/acknowledge lines (DREQ, DACK, and the bus-request/bus-grant lines BR and BG to the CPU).

Working.

1. The CPU initialises the DMA controller by writing the memory start address, the word count and the direction (read or write), and then continues with other work.
2. When the device is ready it raises DREQ. The DMA controller sends a bus request (BR/HOLD) to the CPU.
3. The CPU finishes its current bus cycle, floats its address, data and control buses and replies with bus grant (BG/HLDA). The DMA controller now controls the bus.
4. The controller places the address on the address bus, issues the read or write signal, and moves one word between the device and memory. It then increments the address register and decrements the word count.
5. Steps 3 and 4 repeat until the count reaches zero (burst mode) or one word at a time with the bus returned in between (cycle stealing).
6. When the count is zero, the controller releases the bus and sends an interrupt to the CPU to say that the transfer is complete.

Example. Reading a 512-byte disk sector into memory starting at address $2000_H$: the CPU loads address register $=2000_H$, word count $=512$ and direction = write to memory. The disk controller then fills memory by DMA, using cycle stealing, while the CPU runs another program. At the end, the DMA controller interrupts the CPU. The CPU is involved only at the start and at the end, so the transfer is much faster than programmed or interrupt I/O.

Interconnection network. In a multiprocessor or multicomputer system, an interconnection network is the hardware path that connects processors to memory modules or to other processors so that they can communicate and share data. Its design decides the bandwidth, latency, cost and scalability of the system.

Common types.

• Time-shared common bus: all units share one bus; cheap but only one transfer at a time.
• Multiport memory: each memory module has several ports, one per processor; fast but needs many connections.
• Crossbar switch: a switch at every processor-memory crosspoint; all non-conflicting transfers go in parallel, but cost grows as $n^2$.
• Multistage switching network (omega network): stages of $2\times2$ switches; uses $\tfrac{n}{2}\log_2 n$ switches, cheaper than a crossbar but may block.
• Hypercube: $2^n$ nodes, each connected to $n$ neighbours.
• Mesh, ring, tree: other static topologies for direct processor-to-processor links.

Uses.

1. Connecting many processors to shared memory in multiprocessors.
2. Message passing between nodes in clusters and parallel computers.
3. Allowing parallel communication and so improving speed.
4. Providing alternative paths, which gives fault tolerance.
5. Inside chips as network-on-chip, and in data-centre switches and routers.

Pipeline. Pipelining is a technique in which a task is divided into a sequence of sub-tasks, each executed in its own segment (stage), and the segments work simultaneously on different tasks. Each segment output is held in a register that feeds the next segment, and all segments operate under a common clock. It increases throughput; the time for one task is not reduced, but a new task can finish every clock cycle once the pipe is full.

Space-time diagram for $k=6$ segments and $n=8$ tasks.

The first task needs $k$ cycles to leave the pipeline and each following task finishes one cycle later, so the total number of clock cycles is

$k+(n-1)=6+(8-1)=13$

Task T1 completes at clock 6, T2 at 7, and so on until T8 completes at clock 13. So the pipeline needs 13 clock cycles for 8 tasks.

Comparison with a non-pipelined unit. A non-pipelined unit with the same total delay needs $n\cdot k=8\times6=48$ cycles, so

$\text{Speedup}=\frac{n k}{k+n-1}=\frac{48}{13}\approx3.69$

As $n\to\infty$ the speedup approaches $k=6$.

Booth's multiplication algorithm multiplies two signed numbers in 2's complement form directly. It treats a string of 1s in the multiplier as $2^{j+1}-2^{i}$, so a run of 1s needs only one subtraction at its start and one addition after its end, and it handles signs automatically.

Hardware. The registers are:

• BR holds the multiplicand $M$.
• AC (initially 0) and QR (multiplier) form a combined register that shifts right.
• $Q_{-1}$ is a one-bit flip-flop to the right of QR (initially 0).
• SC is a sequence counter set to $n$, the number of bits.
• A parallel adder/subtractor combines AC and BR.

  BR (multiplicand) --> [ Parallel adder / subtractor ] <-- AC
                                      |
                       AC -> QR -> Q(-1)   (arithmetic shift right)
                       Control logic examines Q0 and Q(-1), counter SC

Algorithm.

1. Initialise AC $=0$, $Q_{-1}=0$, BR $=$ multiplicand, QR $=$ multiplier, SC $=n$.
2. Examine $Q_0Q_{-1}$:
   • $10$: AC $\leftarrow$ AC $-$ BR
   • $01$: AC $\leftarrow$ AC $+$ BR
   • $00$ or $11$: no operation
3. Arithmetic shift right the combined AC, QR, $Q_{-1}$ (the sign bit of AC is kept).
4. Decrement SC. If SC $\ne0$ go to step 2, otherwise stop. The product is in AC:QR.

Example $(-4)\times(-3)$ using 4 bits. $M=-4=1100$, $-M=0100$, multiplier $Q=-3=1101$.

Product $=$ AC:QR $=0000\,1100_2=+12$.

Check: $(-4)\times(-3)=12$.

I/O interface. An I/O interface is the hardware (and its control logic) that sits between the CPU/system bus and a peripheral device. It resolves the differences in speed, data format, voltage levels and timing between them. Its functions are: address decoding to select the device, buffering of data, status and control signals, converting data between serial and parallel form, and interrupt/DMA handling.

Comparison of the three data transfer techniques.

Instruction cycle. The CPU executes a program by repeating the instruction cycle for each instruction. With interrupts, the cycle is extended so that interrupt requests can be checked and serviced after each instruction.

State diagram.

 +--> (1) Instruction address calc. --> (2) Instruction fetch --> (3) Instruction decode
 |                                                                      |
 |                                                                      v
 |   +--> (4) Operand address calc. --> (5) Operand fetch --> (6) Data operation
 |   |                                                              |
 |   +------------------ more operands ----------------------------+
 |                                                                  v
 |                       (7) Operand address calc. --> (8) Operand store
 |                                                                  |
 |   +---------------- more results <------------------------------+
 |                                                                  v
 |                                                       Interrupt check
 |                                                       /            \
 |                                              no interrupt        interrupt
 |                                                     |                |
 +-----------------------------------------------------+      (9) Interrupt: save PC,
 +----------------------------------------------------------- load ISR address ---+

Explanation of the states.

1. Instruction address calculation: determine the address of the next instruction (usually PC + length).
2. Instruction fetch: read the instruction from memory into the instruction register.
3. Instruction operation decoding: decode the opcode to find the operation and the number and type of operands.
4. Operand address calculation: find the effective address of each source operand if it is in memory.
5. Operand fetch: read the operand from memory or register.
6. Data operation: perform the arithmetic or logical operation in the ALU.
7. Operand address calculation (result): find the destination address.
8. Operand store: write the result to memory or register.

States 4 to 8 may repeat for instructions with multiple operands or results.

Interrupt handling. At the end of each instruction execution the CPU checks the interrupt line. If no interrupt is pending (or interrupts are disabled), it fetches the next instruction. If an interrupt is pending, the CPU saves the current PC (and status) on the stack, loads the PC with the address of the interrupt service routine, executes it, and then restores the saved PC and resumes the interrupted program.

Register Transfer Language (RTL). A symbolic notation used to describe the micro-operations of a digital system in terms of the transfer of data between registers and the operations performed on that data. A micro-operation is an elementary operation performed on data stored in registers, such as shift, load, clear, increment, add.

Notation.

• Registers are named by capital letters: $R1$, $MAR$, $PC$, $IR$. Bits are shown in brackets, e.g. $R1(7:0)$.
• Replacement (transfer) is written with an arrow: $R2\leftarrow R1$ copies the contents of $R1$ into $R2$; the source is not changed.
• A condition is written before a comma: $P: R2\leftarrow R1$ means the transfer happens only if control signal $P=1$.
• Simultaneous operations are separated by commas: $R2\leftarrow R1,\ R1\leftarrow R2$ (swap).
• Memory is shown as $M[AR]$, a read is $DR\leftarrow M[AR]$ and a write is $M[AR]\leftarrow R1$.

Types of micro-operations with examples.

Example (hardware). For $T_1: R2\leftarrow R1$, the output of $R1$ is connected to the input of $R2$, and the load input of $R2$ is enabled by the control signal $T_1$ at the clock edge. For the bus-based transfer, a common bus built with multiplexers or tri-state buffers selects the source register and the destination loads it.

Instruction fetch in RTL: $T_0: AR\leftarrow PC$ $T_1: IR\leftarrow M[AR],\ PC\leftarrow PC+1$

The expression is $X=\frac{A}{B}+\frac{C\times D}{C}$ evaluated as $(A/B)+((C\times D)/C)$.

(a) Three-address instructions (OP dest, src1, src2):

DIV  R1, A, B      ; R1 = A / B
MUL  R2, C, D      ; R2 = C * D
DIV  R2, R2, C     ; R2 = (C * D) / C
ADD  X, R1, R2     ; X = R1 + R2

(b) Two-address instructions (OP dest, src; the destination is also the first operand):

MOV  R1, A         ; R1 = A
DIV  R1, B         ; R1 = A / B
MOV  R2, C         ; R2 = C
MUL  R2, D         ; R2 = C * D
DIV  R2, C         ; R2 = (C * D) / C
ADD  R1, R2        ; R1 = A/B + C*D/C
MOV  X, R1         ; X = R1

(c) One-address instructions (all operations use the accumulator AC):

LOAD  C            ; AC = C
MUL   D            ; AC = C * D
DIV   C            ; AC = (C * D) / C
STORE T            ; T = AC (temporary)
LOAD  A            ; AC = A
DIV   B            ; AC = A / B
ADD   T            ; AC = A/B + C*D/C
STORE X            ; X = AC

Counts: 4 instructions for 3-address, 7 for 2-address and 8 for 1-address. As the number of addresses per instruction decreases, the program becomes longer but each instruction is shorter.

The addressing mode is the rule used to find the operand (effective address, EA) from the address field of an instruction. Modes give flexibility to handle pointers, arrays, loops and relocation.

Example. Let the instruction be LOAD 500 with R1 $=400$, memory $M[500]=800$, $M[800]=300$, $M[900]=700$.

• Immediate: AC $\leftarrow500$.
• Direct: AC $\leftarrow M[500]=800$.
• Indirect: AC $\leftarrow M[M[500]]=M[800]=300$.
• Register indirect (R1 $=900$): AC $\leftarrow M[900]=700$.
• Indexed (X $=400$): EA $=500+400=900$, AC $\leftarrow M[900]=700$.

How pipelining improves performance. In a non-pipelined processor one instruction must finish before the next starts. In a pipelined processor the instruction is divided into stages (for example fetch, decode, execute) and a new instruction enters the pipeline every clock cycle, so several instructions are in progress at once. The execution time of one instruction does not decrease, but the throughput (instructions completed per unit time) increases and the CPI approaches 1.

For $k$ stages, $n$ tasks and clock period $t_p$ (non-pipelined time per task $t_n=k\,t_p$):

$\text{Speedup}=\frac{n\,t_n}{(k+n-1)\,t_p}=\frac{nk}{k+n-1}\to k \quad (n\to\infty)$

Practical example (washing clothes / assembly line). Washing, drying and ironing each take 30 minutes. For 4 loads without overlap, the total time is $4\times90=360$ min. With a pipeline, the washer starts the next load as soon as the first moves to the dryer, so the total is $(3+4-1)\times30=180$ min, a speedup of 2.

Example with instructions. Take a 3-stage pipeline (fetch, decode, execute) with 10 instructions and a clock of 1 ns.

• Non-pipelined: $10\times3=30$ ns.
• Pipelined: $(3+10-1)\times1=12$ ns.
• Speedup $=30/12=2.5$.

Real speedup is lower than ideal because of hazards (data, control, structural) and unequal stage delays, which are reduced by forwarding, branch prediction and stalls.

Both algorithms divide unsigned integers using shift and subtract, for a dividend in $Q$, divisor $M$ and partial remainder $A$.

Why non-restoring works. Restoring then shifting gives $2(A+M)-M=2A+M$. Non-restoring skips the restore and simply adds $M$ in the next cycle, so the result is the same with one fewer operation.

In associative (fully associative) mapping a main-memory block can be placed in any cache line, and the tag of every line is compared in parallel with the requested block address.

A replacement algorithm is required because:

1. There is no fixed line for a block. When a miss occurs and the cache is full, the hardware must choose which of the existing blocks to remove. In direct mapping this is not needed because each block has exactly one possible line.
2. The cache is much smaller than main memory, so the number of blocks that can compete for space is much larger than the number of lines.
3. The choice affects the hit ratio. Removing a block that will be used again soon causes another miss, while removing a block that will not be needed keeps performance high.
4. It must be done in hardware for speed, since the cache is accessed at CPU speed.

Common algorithms: Least Recently Used (LRU), First-In First-Out (FIFO), Least Frequently Used (LFU) and Random replacement. LRU is the most popular because of temporal locality of reference.

Hardwired versus microprogrammed control unit.

Microprogram sequencer. In a microprogrammed control unit, each machine instruction is carried out by a sequence of microinstructions in the control memory. The microprogram sequencer (next-address generator) decides the address of the next microinstruction.

Components:

• Multiplexer (MUX) selects the source of the next address.
• Branch logic tests the status bits and selects the branch condition.
• Incrementer adds 1 to the control address register (CAR) for sequential execution.
• Subroutine register (SBR) stores the return address for micro-subroutines.
• Mapping logic converts the opcode of the instruction into the starting address of its microroutine.
• Control address register (CAR) holds the current address, and the control memory with its microinstruction register supplies the control word.

 Instruction opcode --> [Mapping logic] ---+
 CAR --> [Incrementer] --------------------+
 SBR (return address) ---------------------+--> [MUX] --> CAR --> [Control memory] --> Microinstruction
 Branch address field ---------------------+        ^
 External address ---------------------+            |
 Status bits --> [Branch/condition logic]-----select-+

Example (instruction fetch/execute sequence). The next address is selected as:

1. Sequential: $CAR\leftarrow CAR+1$.
2. Unconditional branch: $CAR\leftarrow$ address field.
3. Conditional branch: if the condition (e.g. Z flag) is true $CAR\leftarrow$ address field, else $CAR\leftarrow CAR+1$.
4. Call: $SBR\leftarrow CAR+1$, $CAR\leftarrow$ address field.
5. Return: $CAR\leftarrow SBR$.
6. Map: $CAR\leftarrow$ mapping of the opcode (at the end of the fetch routine, to jump to the routine for the decoded instruction).

For example, the fetch routine at addresses $64$ to $66$ ends with a MAP microinstruction which loads CAR with the start address of the ADD routine, e.g. $80$. The ADD microprogram executes sequentially and finishes with a branch back to the fetch routine at $64$.

The addressing mode specifies how the effective address (EA) of the operand is found from the address field of the instruction.

Types, algorithm (EA calculation), advantages and disadvantages.

Example. For LOAD 500 with $M[500]=800$, $M[800]=300$, $R=900$, index $X=400$ and $PC=200$:

• Immediate: operand $=500$.
• Direct: operand $=M[500]=800$, EA $=500$.
• Indirect: EA $=800$, operand $=300$.
• Register indirect: EA $=900$.
• Indexed: EA $=500+400=900$.
• Relative: EA $=200+500=700$.

Comparison summary. Speed (fastest to slowest): immediate, register, register indirect, direct, indexed/relative/base, indirect. Flexibility (least to most): immediate and direct, then register indirect, then indexed, base and indirect. Modes with a computed address give flexibility at the price of more memory references or additions.

Non-restoring division. It divides without restoring the accumulator after a negative result.

Hardware. Registers:

• A (accumulator, $n+1$ bits) holds the partial remainder, initially 0.
• Q ($n$ bits) holds the dividend and ends with the quotient.
• M ($n+1$ bits) holds the divisor.
• An adder/subtractor combines A and M, and a counter holds $n$.
• The sign bit of A controls whether to add or subtract.

   M (divisor) ---> [ Adder / Subtractor ] <--- A (partial remainder)
                               |
              A:Q shifted left as one register, q0 gets quotient bit
              Control logic uses sign of A, counter n

Flow chart (algorithm).

1. Start: $A\leftarrow0$, $Q\leftarrow$ dividend, $M\leftarrow$ divisor, $count\leftarrow n$.
2. If $A\ge0$ (sign bit 0): shift $A:Q$ left, then $A\leftarrow A-M$. Otherwise ($A<0$): shift $A:Q$ left, then $A\leftarrow A+M$.
3. If now $A\ge0$ then $q_0\leftarrow1$, else $q_0\leftarrow0$.
4. $count\leftarrow count-1$. If $count\ne0$ go to step 2.
5. If $A<0$ then $A\leftarrow A+M$ (final correction).
6. Stop: $Q$ is the quotient and $A$ is the remainder.

Divide $10\div3$ using restoring division (as asked). $Q=1010$, $M=0011$, $A=0000$, $n=4$. Each cycle: shift left, $A\leftarrow A-M$; if $A<0$, restore ($A\leftarrow A+M$) and $q_0=0$; else $q_0=1$.

Result: Quotient $=0011_2=3$, remainder $=0001_2=1$.

Check: $3\times3+1=10$.

Bus interconnection. A bus is a shared communication path of lines that connects the CPU, memory and I/O modules, so that they can exchange data. Only one device can transmit at a time, while all others can listen.

Bus structure.

   +-----+     +--------+     +-------+     +-------+
   | CPU |     | Memory |     | I/O 1 |     | I/O 2 |
   +--+--+     +----+---+     +---+---+     +---+---+
      |             |             |             |
 =====+=============+=============+=============+===== Address bus
 =====+=============+=============+=============+===== Data bus
 =====+=============+=============+=============+===== Control bus

Three groups of lines.

• Address bus: carries the address of the memory location or I/O port; unidirectional from the CPU. Its width fixes the maximum memory ($2^n$ locations for $n$ lines).
• Data bus: carries data and instructions; bidirectional. Its width (8, 16, 32, 64 bits) gives the amount of data moved at once.
• Control bus: carries timing and control signals such as memory read/write, I/O read/write, interrupt request/acknowledge, bus request/grant, clock and reset.

Operation. To write to memory: the CPU requests the bus, places the address on the address bus and the data on the data bus, and asserts memory-write on the control bus. The addressed device is selected by decoding the address and takes the data.

Multiple bus hierarchy. A single bus becomes a bottleneck when many devices are attached, so systems use a hierarchy: a local bus (CPU to cache), a system bus (to main memory), and expansion buses (PCI, USB) connected through bridges, which gives higher performance.

Bus arbitration is needed when more than one device may be bus master: centralised (daisy chaining, polling, independent request) or distributed.

Instruction format. An instruction format defines the layout of the bits of an instruction, divided into fields. It tells the control unit how to interpret the instruction. The main fields are:

• Opcode: specifies the operation (add, load, jump).
• Address / operand fields: specify the operand or its location (register or memory address).
• Mode field: specifies the addressing mode used to find the operand.

 | Opcode | Mode | Operand 1 / Address | Operand 2 / Address |

Types by number of address fields.

• Three-address: ADD R1, R2, R3 means $R1\leftarrow R2+R3$.
• Two-address: ADD R1, R2 means $R1\leftarrow R1+R2$.
• One-address: ADD X means $AC\leftarrow AC+M[X]$.
• Zero-address (stack): ADD pops two items from the stack and pushes the sum.

Example. A 16-bit instruction with a 4-bit opcode, 3-bit mode and 9-bit address:

The 4-bit opcode gives $2^4=16$ operations, and the 9-bit address field can address $2^9=512$ words. This instruction could mean ADD using direct addressing with the operand at address 5.

Fixed versus variable length. Fixed-length formats (RISC) are easy to decode; variable-length formats (CISC) save space but are harder to decode.

Data transfer instructions copy data from one place to another (register, memory, I/O or stack) without changing its value, and normally do not alter the flags. The source is not modified.

Example program. To copy the value in memory location 500 to location 600:

LD  R1, 500     ; R1 = M[500]
ST  R1, 600     ; M[600] = R1

To swap R1 and R2 using the stack:

PUSH R1
PUSH R2
POP  R1
POP  R2

Symbolic microinstruction. In a microprogrammed control unit each microinstruction is stored in control memory as a binary word. When writing a microprogram, a symbolic microinstruction is the human-readable form of that word. An assembler converts the symbols into the binary microinstruction.

Fields of a symbolic microinstruction (as in the basic computer microprogram with a 20-bit word):

A symbolic line is written as: LABEL: F1, F2, F3, CD, BR, AD. A field that is not used is written NOP. A label ends with a colon, and the assembler assigns it a control-memory address.

Example: fetch routine.

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

• PCTAR (F1) means $AR\leftarrow PC$.
• READ (F2) means $DR\leftarrow M[AR]$ and INCPC (F3) means $PC\leftarrow PC+1$.
• DRTAR means $AR\leftarrow DR(0\text{-}10)$.
• U JMP NEXT means jump unconditionally to the label NEXT.
• MAP loads the control address register from the opcode, so execution moves to the microroutine of the instruction.

The assembler gives each line a binary word. For example, PCTAR corresponds to F1 $=110$, so the first word has F1 $=110$, F2 $=000$, F3 $=000$, CD $=00$ (U), BR $=00$ (JMP) and AD $=$ address of NEXT.

Advantage. Symbols make the microprogram easy to write, read and debug compared with raw binary.

Instruction pipeline. Pipelining divides instruction processing into several stages, each handled by a separate segment. While one instruction is in a later stage, the next instructions occupy the earlier stages. Several instructions are therefore in progress at the same time, which raises throughput.

Four-segment instruction pipeline:

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

Space-time diagram for three instructions $I_1, I_2, I_3$:

Speed-up. For $n$ instructions and $k$ stages with clock period $t_p$:

• Pipelined time $=(k+n-1)\,t_p$.
• Non-pipelined time $=n\,k\,t_p$.

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

Example: with $k=4$ and $n=100$, $S=\dfrac{400}{103}\approx 3.88$, which approaches $k=4$ for large $n$.

Problems (hazards). Resource conflicts (structural), data dependency between instructions (data hazard), and branch instructions (control hazard) can stall the pipeline. They are handled by operand forwarding, delayed load, branch prediction and delayed branch.

Booth multiplication algorithm. Booth's algorithm multiplies two signed numbers in 2's complement form. A string of 1s in the multiplier is treated as $2^{k+1}-2^{m}$, so only the two ends of a string of 1s need an operation (subtract at the start, add at the end).

Registers: $BR$ = multiplicand, $QR$ = multiplier, $AC=0$, $Q_{n+1}=0$ (an extra flip-flop), $SC=n$ (number of bits).

Steps. Examine $Q_n Q_{n+1}$ (the last bit of $QR$ and $Q_{n+1}$):

• $10$ (beginning of a string of 1s): $AC\leftarrow AC+\overline{BR}+1$ (subtract).
• $01$ (end of a string of 1s): $AC\leftarrow AC+BR$.
• $00$ or $11$: no operation.
• Arithmetic shift right $AC, QR, Q_{n+1}$ (sign bit of $AC$ is kept), then $SC\leftarrow SC-1$.
• Repeat until $SC=0$. The product is in $AC\,QR$.

Example: $(-3)\times(+3)$ with 4 bits. $BR=1101$ ($-3$), $QR=0011$ ($+3$), $-BR=0011$.

The product is $AC\,QR=1111\ 0111_2$, which is $-9$ in 2's complement. This agrees with $-3\times 3=-9$.

Direct mapping. Each main-memory block can go to only one cache line, given by $i=j \bmod m$ ($j$ = block number, $m$ = number of cache lines). The address is split into tag, line and word fields.

Associative mapping. Any main-memory block can be placed in any cache line. The address is split into a tag and a word field; the tag is compared with the tags of all lines in parallel.

IOP versus DMA.

In short, a DMA controller is a simple data mover, while an IOP is a special-purpose processor that takes over the full I/O workload from the CPU.

Hypercube (n-cube) interconnection. A hypercube is a multiprocessor interconnection structure with $2^n$ nodes (processors), each node connected to $n$ neighbours. A 3-dimensional hypercube has $2^3=8$ nodes, each with 3 links, and $8\times 3/2=12$ links in all.

Each node is given a binary address of $n=3$ bits. Two nodes are directly connected if their addresses differ in exactly one bit.

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

Edges: $000$-$001$, $010$-$011$, $100$-$101$, $110$-$111$ (differ in bit 0); $000$-$010$, $001$-$011$, $100$-$110$, $101$-$111$ (bit 1); $000$-$100$, $001$-$101$, $010$-$110$, $011$-$111$ (bit 2).

Example of routing. To send a message from node $001$ to node $110$, XOR the addresses: $001\oplus 110=111$. The number of 1s is 3, so the distance is 3 hops. The message corrects one differing bit per hop, for example $001\to 000\to 010\to 110$. The maximum distance (diameter) in an $n$-cube is $n=3$.

Properties. Short diameter ($\log_2 N$), several alternative paths between nodes, good fault tolerance, and the number of links per node grows only as $\log_2 N$.

Cache memory. 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 most memory accesses are served at cache speed. It works because of the locality of reference (temporal and spatial). If the CPU finds the word in the cache it is a hit, otherwise a miss and the block is loaded from main memory.

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

Mapping process. The transformation of main-memory blocks into cache lines is called mapping. Main memory is divided into blocks of $K$ words and the cache into lines of the same size. There are three techniques.

1. Direct mapping. Block $j$ goes to line $i=j \bmod m$ ($m$ = number of lines). The address has three fields: Tag | Line | Word. The line field selects one cache line, and the tag stored there is compared with the tag of the address. If equal it is a hit.

2. Associative mapping. A block can be placed in any line. The address has Tag | Word. The tag is compared with all line tags simultaneously.

3. Set-associative mapping. The cache is divided into $v$ sets of $k$ lines. Block $j$ goes to set $j \bmod v$ and to any line in that set. The address has Tag | Set | Word. It is a compromise of the other two.

Example. Main memory $64$ K words ($16$-bit address), cache $1$ K words, block size $16$ words. Then word field $=4$ bits, cache lines $=1024/16=64$, so the line field $=6$ bits and the tag $=16-6-4=6$ bits for direct mapping. For associative mapping the tag is $12$ bits.

Difference between direct and associative mapping.

Micro-programmed control unit. A control unit whose control signals are generated by a stored program called a microprogram, kept in a control memory (ROM). Each machine instruction is executed by a sequence of microinstructions, each of which produces the control word for one clock period.

Organisation:

• Control memory stores the microprograms.
• Control address register (CAR) holds the address of the next microinstruction.
• Control data register / microinstruction register holds the microinstruction being executed.
• Next-address generator (sequencer) decides the next CAR value: increment, branch, call, return or map from the opcode.
• Control signals go to the datapath; the status bits go back to the sequencer.

Working. The opcode of the instruction is mapped to the starting address of its microroutine and loaded into CAR. The microinstruction is read, its fields drive the control lines, and the sequencer computes the next address. The routine ends by returning to the fetch routine.

Advantages: flexible and easily modified, systematic design. Disadvantage: slower than a hardwired unit.

Addressing modes. The addressing mode tells how the operand (or its effective address, EA) is found from the address field of the instruction. Assume $R1=300$, $PC=200$, index register $XR=100$, and the address field $=500$, with $M[500]=800$, $M[600]=700$, $M[800]=900$.

Fixed-point versus floating-point representation.

Restoring division of $23$ by $9$. Dividend $Q=23=10111_2$, divisor $M=9=01001_2$, $A=00000$, count $=5$.

Each step: shift left $A\,Q$, then $A\leftarrow A-M$. If $A<0$ set $Q_0=0$ and restore $A$ (add $M$ back); else set $Q_0=1$.

Result: quotient $Q=00010_2=2$ and remainder $A=00101_2=5$.

Check: $9\times 2+5=23$.

Methods of representing signed numbers. The leftmost bit is the sign bit ($0$ = positive, $1$ = negative). Three methods are used:

1. Signed magnitude: the sign bit followed by the magnitude in binary.
2. Signed 1's complement: a negative number is the 1's complement (every bit inverted) of the positive number.
3. Signed 2's complement: a negative number is the 1's complement plus 1.

Representation of $-71$ in 8 bits.

$71=64+4+2+1=01000111_2$.

Check of 2's complement: $10111001_2=-128+32+16+8+1=-71$.