Instruction Format of Basic Computer and FETCH Routine

Part 1: Instruction Format of Basic Computer

The basic computer has three instruction code formats, each consisting of a total of 16 bits.

General Structure of a 16-bit Instruction

Bit:  15    14  13  12    11  10  9  8  7  6  5  4  3  2  1  0
      [I]  [  Opcode  ]  [          Address / Operand           ]
       1       3 bits                   12 bits

The Three Instruction Formats

Format 1: Memory-Reference Instruction

Bit 15    Bits 14-12    Bits 11-0
  [I]    [ Opcode  ]   [  Address  ]
   1        3 bits        12 bits

• I = 0: Direct addressing (the 12-bit field is the actual memory address)
• I = 1: Indirect addressing (the 12-bit field points to the address that holds the actual address)
• The 3-bit opcode (bits 12-14) is decoded using a 3x8 decoder producing outputs D0 to D7
• D0 to D6 represent memory-reference instructions (e.g., AND, ADD, LDA, STA, BUN, BSA, ISZ)
• Example: AND, ADD, LDA, STA, BUN, BSA, ISZ

Format 2: Register-Reference Instruction

Bit 15    Bits 14-12    Bits 11-0
  [0]    [  1  1  1 ]  [ Operation bits ]
   0        D7=1           12 bits

• I = 0 and Opcode = 111 (i.e., D7 = 1, I = 0)
• The 12-bit field (bits 0-11) specifies the register operation to be performed
• These instructions operate on the Accumulator (AC) or other registers
• Examples: CLA (Clear AC), CLE (Clear E), CMA (Complement AC), CME, CIR, CIL, INC, SPA, SNA, SZA, SZE, HLT

Format 3: Input-Output (I/O) Instruction

Bit 15    Bits 14-12    Bits 11-0
  [1]    [  1  1  1 ]  [ I/O Operation bits ]
   1        D7=1            12 bits

• I = 1 and Opcode = 111 (i.e., D7 = 1, I = 1)
• The 12-bit field specifies the I/O operation
• Examples: INP (Input character to AC), OUT (Output character from AC), SKI, SKO, ION, IOF

Summary of Instruction Type Determination

Decode IR(12-14) --> D7?
        |
        |-- D7 = 0 --> Memory-Reference Instruction
        |              (check I bit for direct/indirect)
        |
        |-- D7 = 1 --> Check I bit (bit 15)
                        |
                        |-- I = 0 --> Register-Reference Instruction
                        |
                        |-- I = 1 --> Input-Output Instruction

Part 2: Symbolic Representation of the FETCH Routine

The FETCH routine retrieves an instruction from memory and places it in the Instruction Register (IR). It also decodes the instruction and prepares the Address Register (AR) for further use.

The FETCH routine uses a Sequence Counter (SC) that starts at 0 and increments with each timing signal (T0, T1, T2).

Symbolic Representation

Timing Signal T0:

T0:   AR <-- PC

At time T0, the content of the Program Counter (PC) is transferred to the Address Register (AR) so that the memory can be addressed.

Timing Signal T1:

T1:   IR <-- M[AR],   PC <-- PC + 1

At time T1, two microoperations occur simultaneously:

• The instruction stored at memory location pointed by AR is loaded into the Instruction Register (IR)
• The Program Counter (PC) is incremented by 1 to point to the next instruction

Timing Signal T2:

T2:   D0, D1, D2, D3, D4, D5, D6, D7 <-- Decode IR(12-14)
      AR <-- IR(0-11)
      I  <-- IR(15)

At time T2:

• The opcode in bits 12-14 of IR is decoded using a 3x8 decoder to produce signals D0 through D7
• The address field (bits 0-11) of IR is transferred to AR for possible use in memory-reference instructions
• The mode bit (bit 15) is transferred to flip-flop I to determine addressing mode

Complete FETCH Routine Table

After T2, control passes to the appropriate EXECUTE routine based on the decoded opcode and mode bit.

Direct Memory Access (DMA)

Definition

Direct Memory Access (DMA) is a process for data transfer between memory and I/O devices, controlled by an external circuit called the DMA controller, without the involvement of the CPU. Most data that is input or output from a computer is processed by the CPU, but some data does not require CPU processing or can be processed by another device. In these situations, DMA saves processing time and is a more efficient way to move data from the computer's memory to other devices.

Example: A PCI controller and a hard drive controller each have their own set of DMA channels.

Block Diagram of DMA Controller

         +------------------+
         |       CPU        |
         |  (HOLD)  (HLDA)  |
         +--------+---------+
                  |
         +--------+---------+
         |   System Buses   |
         | (Address / Data) |
         +--+----------+----+
            |          |
   +--------+--+    +--+--------+
   |   Memory  |    |    DMA    |
   |   (RAM)   |    | Controller|
   +--------+--+    +--+---+----+
                       |   |
                    BR/BG  RS/DS
                       |   |
                  +----+---+----+
                  |  I/O Device |
                  | (Peripheral)|
                  +-------------+

Internal Structure of DMA Controller

+-----------------------------------------------+
|              DMA Controller                   |
|                                               |
|  +------------------+  +------------------+  |
|  | Address Register |  |  Word Count Reg  |  |
|  +------------------+  +------------------+  |
|                                               |
|  +------------------+  +------------------+  |
|  |  Data Register   |  |  Control/Status  |  |
|  +------------------+  |    Register      |  |
|                         +------------------+  |
|                                               |
|   Control Lines: BR, BG, RD, WR, RS, DS      |
+-----------------------------------------------+

Key Registers in DMA Controller

Control Signals Used in DMA Operation

The CPU has two special pins used for DMA operation:

1. Bus Request (BR)

• Used by the DMA controller to request the CPU to release the buses.
• When BR is active, the CPU:
  • Terminates execution of the current instruction
  • Places the address bus, data bus, and read/write lines into high impedance state

2. Bus Grant (BG)

• CPU activates the BG output to inform the DMA that buses are now available.
• DMA takes control and conducts memory transfers without CPU involvement.
• When DMA finishes the transfer:
  • It disables the BR line
  • CPU disables BG and returns to normal operation

Sequence of Events During DMA Operation

Step 1: I/O device sends DMA Request to DMA Controller
         |
Step 2: DMA Controller activates BR line --> CPU
         |
Step 3: CPU completes current instruction, releases buses
         CPU activates BG line --> DMA
         |
Step 4: DMA puts address register value onto Address Bus
        DMA initiates RD and WR signals
        DMA sends DMA Acknowledge to I/O device
         |
Step 5: Data transfer takes place between Memory and I/O
        (without CPU involvement)
         |
Step 6: DMA disables BR line after transfer completes
        CPU disables BG and resumes normal operation

How DMA Interacts with I/O Devices

The interaction between DMA and I/O devices follows the steps below (based on the DMA transfer mechanism):

Step-by-Step Interaction

1. CPU Initiates the Setup:

   • The CPU communicates with the DMA controller through the address and data buses.
   • The DMA has its own address, which activates the RS (Register Select) and DS (DMA Select) lines.
   • CPU loads the DMA controller with:
     • Starting memory address
     • Word count (number of words to transfer)
     • Direction of transfer (read/write)

2. I/O Device Sends DMA Request:

   • When a peripheral device is ready for data transfer, it sends a DMA Request signal to the DMA controller.

3. DMA Requests the Bus:

   • The DMA controller activates the BR (Bus Request) line, informing the CPU to release the buses.

4. CPU Grants the Bus:

   • The CPU responds by activating BG1 (Bus Grant) line.
   • When BG1 = 0: RD and WR signals allow the CPU to communicate with internal DMA registers.
   • When BG1 = 1: DMA communicates with RAM through RD and WR lines directly.

5. DMA Performs the Transfer:

   • DMA puts the current value of its address register onto the address bus.
   • Initiates RD and WR signals as required.
   • Sends a DMA Acknowledge to the peripheral device.
   • Data is transferred directly between I/O device and Memory.

6. Transfer Completion:

   • After all words are transferred (word count reaches zero), DMA disables the BR line.
   • CPU regains control of the buses and resumes normal operation.

Types of DMA Transfer

Summary

DMA is an efficient I/O technique that lets a peripheral device transfer data directly to and from memory without CPU intervention on every word, using the DMA controller as a temporary bus master to drive the address and control lines. This significantly speeds up bulk data transfers compared to programmed I/O, since the CPU is freed to execute other instructions while the transfer proceeds in the background and is only notified (typically by an interrupt) once the transfer is complete.

Error Correction Codes

Definition

An error correction code is a binary code that not only detects errors that occur during data transmission but also corrects those errors automatically without requiring retransmission. Unlike error detection codes (such as parity bits) which can only indicate the presence of an error, error correction codes can identify the exact location of the erroneous bit and fix it.

Hamming Code (Error Correction Technique)

Hamming Code is the most widely used error correction technique, developed by R.W. Hamming. It adds redundant bits (called parity bits) at specific positions to detect and correct single-bit errors.

Key Rules for Hamming Code

• Parity bits are placed at positions that are powers of 2: position 1, 2, 4, 8, 16, ...
• Each parity bit checks specific bit positions in the codeword.
• Data bits occupy the remaining positions.

Formula for Number of Parity Bits

If the data has m bits, the number of parity bits r must satisfy:

2^r >= m + r + 1

Worked Example

Encode the data bits: 1011

Step 1: Determine number of parity bits

• m = 4 (data bits)
• Try r = 3: 2^3 = 8 >= 4 + 3 + 1 = 8 ✓
• So we need 3 parity bits

Step 2: Total bits = m + r = 4 + 3 = 7 bits

Step 3: Assign positions

Data bits 1, 0, 1, 1 are placed at positions 3, 5, 6, 7 respectively.

Step 4: Calculate parity bits (using even parity)

• P1 (position 1): checks positions 1, 3, 5, 7

  • Bits: P1, 1, 0, 1 → count of 1s = 2 (even) → P1 = 0

• P2 (position 2): checks positions 2, 3, 6, 7

  • Bits: P2, 1, 1, 1 → count of 1s = 3 (odd) → P2 = 1

• P3 (position 4): checks positions 4, 5, 6, 7

  • Bits: P3, 0, 1, 1 → count of 1s = 2 (even) → P3 = 0

Step 5: Final Hamming Codeword

Transmitted codeword: 0110011

Error Detection and Correction

At the receiver, parity checks are recalculated. If an error occurs (say bit 5 flips from 0 to 1):

• The parity checks that fail are noted.
• Their position numbers are added to give the position of the erroneous bit.
• That bit is then flipped to correct the error.

Advantages of Hamming Code

• Corrects all single-bit errors
• Detects double-bit errors (with extended Hamming code)
• Efficient and widely used in memory systems (ECC RAM)

Micro Operation and Arithmetic Micro Operations

What is Micro Operation? (1 mark)

Micro operation is an elementary operation performed on data stored in registers. It is the basic operation executed on the data held in one or more registers during a single clock pulse.

Example: add, subtract, load, store, clear, shift, etc.

In Register Transfer Language (RTL), a micro operation is expressed as:

R1 ← R1 + R3

This means the contents of R1 and R3 are added and the result is stored back in R1.

Arithmetic Micro Operations (4 marks)

Arithmetic micro operations perform basic arithmetic operations on numeric data stored in registers. The common arithmetic micro operations are:

1. Addition

The contents of two registers are added and the result is stored in a destination register.

RTL notation:

R3 ← R1 + R2

Example:

R1 = 1010
R2 = 0101
R3 = 1111

2. Subtraction

The contents of one register are subtracted from another. This is typically implemented using 2's complement addition.

RTL notation:

R3 ← R1 - R2

Which is equivalent to:

R3 ← R1 + (2's complement of R2)
     = R1 + R2' + 1

Example:

R1 = 1010  (10)
R2 = 0011  (3)
R3 = 0111  (7)

3. Increment

The content of a register is increased by 1.

RTL notation:

R1 ← R1 + 1

Example:

R1 = 1010  →  R1 = 1011

4. Decrement

The content of a register is decreased by 1.

RTL notation:

R1 ← R1 - 1

Example:

R1 = 1010  →  R1 = 1001

5. Multiplication

The contents of two registers are multiplied and the result is stored in a destination register.

RTL notation:

R3 ← R1 * R2

6. Division

The content of one register is divided by another.

RTL notation:

R3 ← R1 / R2

7. Negation (2's Complement)

The value in a register is negated (sign is changed) using 2's complement.

RTL notation:

R1 ← R1' + 1

Example:

R1 = 0101 (5)  →  R1 = 1011 (-5 in 2's complement)

Summary Table

Note: The arithmetic circuit for these operations is implemented using full adders, where the output is computed as: D = A + Y + Cin, and the function is selected by control inputs.

Pipelining Concept and Pipeline Hazards

Pipelining Concept

Pipelining is a technique used in computer architecture to improve CPU performance by overlapping the execution of multiple instructions. Instead of completing one instruction fully before starting the next, the processor divides instruction execution into several stages, and different instructions occupy different stages simultaneously.

For example, a typical 4-stage pipeline:

Example of pipeline operation:

Time:    T1   T2   T3   T4   T5   T6
I1:      IF   ID   EX   WB
I2:           IF   ID   EX   WB
I3:                IF   ID   EX   WB

This overlap increases throughput (instructions completed per unit time) without reducing the time for a single instruction.

Pipeline Hazards (Pipelining Conflicts)

As stated in the notes: "There are three major difficulties that cause the instruction pipeline to deviate from its normal operation."

These three hazards are:

1. Structural Hazards (Resource Conflicts)

Definition: Occur when two or more instructions in the pipeline require the same hardware resource at the same time.

Example: Two instructions both needing memory access simultaneously.

Solutions:

• Resource duplication: Provide separate instruction memory and data memory (Harvard Architecture).
• Stalling the pipeline: Insert a pipeline bubble (NOP) to delay one instruction until the resource is free.

2. Data Hazards (Data Conflicts)

Definition: Occur when an instruction depends on the result of a previous instruction that has not yet completed its execution.

Example:

I1: ADD R1, R2, R3    ; R1 = R2 + R3
I2: SUB R4, R1, R5    ; R4 = R1 - R5  (needs R1 from I1)

I2 tries to read R1 before I1 has written it.

Types:

• RAW (Read After Write): Most common; instruction reads before previous writes.
• WAR (Write After Read): Instruction writes before previous reads.
• WAW (Write After Write): Two instructions write to the same location out of order.

Solutions:

• Forwarding (Data Bypassing): The result is forwarded directly from the output of one stage to the input of another without waiting for write-back.
• Pipeline Stalling (Interlocking): The pipeline is stalled (bubbles inserted) until the required data is available.
• Compiler-based instruction reordering: The compiler reorders instructions to place independent instructions between dependent ones.

3. Control Hazards (Branch Conflicts)

Definition: As stated in the notes, "These difficulties arise from branch and other instructions that change the value of PC." When a branch instruction is encountered, the pipeline may have already fetched the wrong instructions.

Example:

I1: BEQ R1, R2, LABEL   ; branch if R1 == R2
I2: ADD ...              ; fetched but may not be needed
I3: SUB ...              ; fetched but may not be needed

Solutions:

• Pipeline Flushing: Discard (flush) the incorrectly fetched instructions when a branch is detected.
• Branch Prediction:
  • Static prediction: Always predict branch taken or not taken.
  • Dynamic prediction: Use a branch history table to predict based on past behavior.
• Delayed Branching: The compiler fills the delay slot after a branch with a useful instruction that executes regardless of the branch outcome.
• Branch Target Buffer (BTB): A cache that stores the target address of recent branches for faster resolution.

Summary Table

Pipelining significantly improves CPU performance, but these hazards must be carefully managed to ensure correct and efficient execution.

X = (A + BC - D) / (EF + G)

Using Three-Address, One-Address (Accumulator), and Zero-Address (Stack) instructions.

Given Data

• Expression: $X = \dfrac{A + B \cdot C - D}{E \cdot F + G}$
• Operands: $A, B, C, D, E, F, G$
• Operations: multiply, add, subtract, divide

Three-Address Instructions

Format: OP dest, src1, src2 meaning dest = src1 OP src2

MUL  T1, B, C      ; T1 = B * C
ADD  T2, A, T1     ; T2 = A + B*C
SUB  T3, T2, D     ; T3 = A + B*C - D    (numerator)
MUL  T4, E, F      ; T4 = E * F
ADD  T5, T4, G     ; T5 = E*F + G        (denominator)
DIV  X,  T3, T5    ; X  = T3 / T5

Total: 6 instructions

One-Address Instructions (Accumulator based)

Format: OP M meaning AC = AC OP M

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

Total: 12 instructions

Zero-Address Instructions (Stack based)

Format: PUSH/POP M for memory access; arithmetic ops act on top two stack elements.

PUSH  A            ; [A]
PUSH  B            ; [A, B]
PUSH  C            ; [A, B, C]
MUL                ; [A, B*C]
ADD                ; [A+B*C]
PUSH  D            ; [A+B*C, D]
SUB                ; [A+B*C-D]              (numerator)
PUSH  E            ; [num, E]
PUSH  F            ; [num, E, F]
MUL                ; [num, E*F]
PUSH  G            ; [num, E*F, G]
ADD                ; [num, E*F+G]           (denominator)
DIV                ; [num/den]
POP   X            ; X = result

Total: 14 instructions

Summary

As the number of addresses per instruction decreases, more instructions are required, but each instruction becomes simpler and shorter.

All three programs evaluate the expression correctly while respecting operator precedence (multiplication before addition and subtraction, numerator and denominator computed before division).