RISC vs CISC Architecture and Booth's Multiplication Algorithm

STEP 1 - EXTRACT: Given Data

• Multiply 9 × 7 using Booth's Algorithm
• Multiplicand $M = 9$
• Multiplier $Q = 7$
• Both positive, need signed 2's complement representation

Bit-width check: $9 = 1001_2$ (4 bits). To represent as signed positive, we need a leading 0, so minimum 5 bits: $9 = 01001$. Similarly $7 = 00111$. Use $n = 5$ bits.

Part 1: RISC vs CISC Architecture [4 Marks]

RISC (Reduced Instruction Set Computer) uses a small set of simple, fixed-length instructions, each executing in a single clock cycle.

CISC (Complex Instruction Set Computer) uses a large set of complex, variable-length instructions where one instruction may perform several low-level operations over multiple cycles.

Part 2: Booth's Multiplication -- 9 × 7 [6 Marks]

Booth's Rules

Setup

• $M = 01001$
• $-M = 10111$ (2's complement of $M$)
• $Q = 00111$
• $A = 00000$, $Q_{-1} = 0$, $n = 5$

Step-by-Step

Initial: $A=00000,\ Q=00111,\ Q_{-1}=0$

Cycle 1: $Q_0 Q_{-1} = 10 \Rightarrow A = A - M$ $$A = 00000 + 10111 = 10111$$ Before ASR: $A=10111,\ Q=00111,\ Q_{-1}=0$ After ASR: $A=11011,\ Q=10011,\ Q_{-1}=1$

Cycle 2: $Q_0 Q_{-1} = 11 \Rightarrow$ no op After ASR: $A=11101,\ Q=11001,\ Q_{-1}=1$

Cycle 3: $Q_0 Q_{-1} = 11 \Rightarrow$ no op After ASR: $A=11110,\ Q=11100,\ Q_{-1}=1$

Cycle 4: $Q_0 Q_{-1} = 01 \Rightarrow A = A + M$ $$A = 11110 + 01001 = 00111$$ Before ASR: $A=00111,\ Q=11100,\ Q_{-1}=1$ After ASR: $A=00011,\ Q=11110,\ Q_{-1}=0$

Cycle 5: $Q_0 Q_{-1} = 00 \Rightarrow$ no op After ASR: $A=00001,\ Q=11111,\ Q_{-1}=0$

Summary Table

Result

$$AQ = 00001,11111$$

Converting to decimal: $0000111111_2 = 63$

$$9 \times 7 = 63 \checkmark$$

Conclusion: Booth's algorithm correctly yields the product 63.

SAP-2 Computer: Features, Block Diagram, and Comparison with SAP-1

Note: The reference notes did not contain this topic. The following answer is based on standard computer architecture curriculum as taught in TU BSc CSIT (Malvino's "Digital Computer Electronics" textbook content), which is the standard source for SAP computers in this course.

SAP-2 (Simple As Possible - 2) Computer

SAP-2 is an improved version of SAP-1, designed to be more powerful and closer to a real microprocessor. It has an 8-bit architecture with enhanced instruction set, more registers, and bidirectional data bus.

Features of SAP-2 Computer

1. 8-bit Bidirectional Data Bus

• SAP-2 uses a bidirectional bus (unlike unidirectional in SAP-1), allowing data to flow in both directions between components.

2. 64 KB Memory (16-bit Address)

• SAP-2 has a 16-bit Program Counter and can address up to 65,536 (64K) memory locations, a significant improvement over SAP-1's 16-byte memory.

3. More General Purpose Registers

• SAP-2 contains:
  • Accumulator (A) - 8-bit
  • Register B - 8-bit
  • Register C - 8-bit
  • B and C can be used for temporary data storage.

4. Input/Output Ports

• SAP-2 has dedicated input ports (Port 1, Port 2) and output ports (Port 3) for I/O operations, making it capable of real I/O communication.

5. Flags Register

• SAP-2 includes a Flags register with:
  • Sign Flag (S) - set if result is negative
  • Zero Flag (Z) - set if result is zero
• These flags enable conditional jump instructions.

6. Enhanced ALU

• The ALU supports more operations:
  • Addition (ADD)
  • Subtraction (SUB)
  • Logical AND, OR, NOT (logical operations)
  • Increment / Decrement

7. Larger Instruction Set

• SAP-2 supports a much richer instruction set including:
  • Data transfer: MOV, MVI, LDA, STA
  • Arithmetic: ADD, SUB, INR, DCR
  • Logical: ANA, ORA, CMA
  • Branch: JMP, JZ, JNZ, JM
  • I/O: IN, OUT
  • Control: HLT

8. Controller/Sequencer

• Uses a more complex control unit with more control words to handle the larger instruction set and more components.

9. Stack Pointer (in some versions)

• Some implementations include a Stack Pointer for subroutine handling.

10. Instruction Register (IR)

• 8-bit IR stores the fetched instruction. The opcode is decoded by the controller.

Well-Labeled Block Diagram of SAP-2

        +------------------+
        |   INPUT PORTS    |
        |  (Port 1, Port 2)|
        +--------+---------+
                 |
+----------------+------------------------------------------+
|                    8-BIT BIDIRECTIONAL BUS (W BUS)        |
+---+----------+--------+--------+--------+--------+--------+
    |          |        |        |        |        |
+---+---+  +--+---+  +--+--+  +--+--+  +--+--+  +--+--+
|  MAR  |  |  PC  |  |  A  |  |  B  |  |  C  |  |  IR |
|(Mem   |  |(16-  |  |(Acc)|  |Reg B|  |Reg C|  |(Inst|
|Addr   |  | bit) |  |8-bit|  |8-bit|  |8-bit|  | Reg)|
|Reg)   |  +--+---+  +--+--+  +--+--+  +--+--+  +--+--+
+---+---+     |         |        |                   |
    |         |      +--+--------+--+                |
    |         |      |     ALU       |                |
+---+---+     |      | (ADD,SUB,AND, |                |
|MEMORY |     |      |  OR, NOT,INC) |                |
|(64KB) |     |      +------+--------+                |
+---+---+     |             |                         |
    |         |         +---+----+                    |
    |         |         | FLAGS  |                    |
    |         |         | (S, Z) |                    |
    |         |         +--------+                    |
    |         |                                       |
    |    +----+------------------------------------------+
    |    |        CONTROLLER / SEQUENCER                  |
    |    |   (Control Word, Ring Counter, Decoder)        |
    |    +------------------------------------------------+
    |
+---+---------+
| OUTPUT PORT |
|  (Port 3)   |
+-------------+

Simplified Clean Diagram:

 +-----------+     +-----------+     +-----------+
 |  INPUT    |     |  MEMORY   |     |  OUTPUT   |
 | PORTS 1,2 |     |  (64 KB)  |     |  PORT 3   |
 +-----+-----+     +-----+-----+     +-----+-----+
       |                 |                 |
=======+=========================================+======
              8-BIT BIDIRECTIONAL W-BUS
=======+====+====+====+====+====+====+====+======
       |    |    |    |    |    |    |    |
     +-+--+ +-+-+ +-+-+ +-+-+ +-+-+ +-+--+
     | MAR| | PC| | A | | B | | C | | IR |
     +--+-+ +---+ +-+-+ +-+-+ +---+ +--+-+
        |            |     |            |
    +---+---+     +--+-----+--+    +----+-------------+
    |MEMORY |     |    ALU    |    | CONTROLLER /     |
    |(64 KB)|     |(ADD, SUB, |    | SEQUENCER        |
    +-------+     | AND, OR,  |    | (control word,   |
                  | NOT, INC) |    |  ring counter,   |
                  +-----+-----+    |  decoder)        |
                        |          +------------------+
                  +-----+-----+
                  |  FLAGS    |
                  |  (S, Z)   |
                  +-----------+

How SAP-2 Differs from SAP-1 [2 Marks]

Conclusion

SAP-2 keeps the single 8-bit W-bus architecture of SAP-1 but grows in every dimension that matters: 64 KB of memory instead of 16 bytes, more registers, a richer ALU with flags, real input and output ports, and an instruction set large enough to support branching and subroutines. Those additions are what turn SAP-1's straight-line toy machine into something that behaves like a genuine microprocessor such as the 8085.

Assembly Language Program: Multiply 08H × 09H (8085 Microprocessor)

STEP 1 - Given Data

• Multiplicand = 08H
• Multiplier = 09H
• Product storage address = 8050H
• Carry (higher byte) storage address = 8051H

STEP 2 - Solution

Concept

The 8085 has no hardware multiply instruction, so multiplication is done by repeated addition: add the multiplicand (08H) to itself the number of times given by the multiplier (09H). Any carry beyond 8 bits is counted in a separate register.

Program

        LXI  H, 8050H   ; HL points to product location 8050H
        MVI  B, 08H     ; B = multiplicand (08H)
        MVI  C, 09H     ; C = multiplier / counter (09H)
        MVI  A, 00H     ; A = 00H (accumulate product low byte)
        MVI  D, 00H     ; D = 00H (accumulate carry / high byte)

LOOP:   ADD  B          ; A = A + B
        JNC  SKIP       ; if no carry, skip
        INR  D          ; else increment high byte
SKIP:   DCR  C          ; decrement counter
        JNZ  LOOP       ; repeat until C = 0

        MOV  M, A       ; store product low byte at 8050H
        INX  H          ; HL points to 8051H
        MOV  M, D       ; store carry / high byte at 8051H

        HLT             ; halt

Execution Trace

Verification

$$08H \times 09H = 8 \times 9 = 72_{10} = 48H$$

Since the result 72 fits in one byte (< 256), no carry is generated, so D = 00H.

Result in Memory

The final product is 48H with carry 00H.

Subtraction Using 9's and 10's Complement Methods

"Subtract $(1197){10}$ from $(1234){10}$" means the minuend is 1234 and the subtrahend is 1197, so the value wanted is $1234 - 1197$. Both numbers have four digits, so every complement below is taken to four digits.

9's complement method

The 9's complement of the subtrahend is found by subtracting each digit from 9:

$$9999 - 1197 = 8802$$

Adding this to the minuend replaces the subtraction:

$$1234 + 8802 = 10036$$

  1 2 3 4
+ 8 8 0 2
---------
1 0 0 3 6   (carry out of the most significant digit)

A carry out of the most significant digit tells us the result is positive. In the 9's complement method that carry is not simply discarded: it is added back into the least significant digit, which is why the rule is called the end around carry.

$$0036 + 1 = 0037$$

Therefore $1234 - 1197 = +37$.

10's complement method

The 10's complement is one more than the 9's complement:

$$8802 + 1 = 8803$$

$$1234 + 8803 = 10037$$

  1 2 3 4
+ 8 8 0 3
---------
1 0 0 3 7   (carry out of the most significant digit)

Here the carry is simply discarded rather than added back, because the extra 1 has already been built into the complement. What remains is the answer directly.

Therefore $1234 - 1197 = +37$, agreeing with the 9's complement method and with ordinary decimal subtraction.

Summary

Had the operands been the other way round, $1197 - 1234$, no carry would have been produced, and the rule for that case is to recomplement the sum and attach a minus sign, which gives $-37$.

Pipelining Hazards

Definition

Pipelining hazards are situations that prevent the next instruction in the instruction stream from executing during its designated clock cycle, causing the pipeline to stall.

Types of Pipelining Hazards

1. Structural Hazards

Definition: Arise when the hardware cannot support all possible combinations of instructions in simultaneous overlapped execution (resource conflict).

Example: Two instructions needing the same memory unit or ALU at the same time.

IF  ID  EX  MEM  WB
    IF  ID  EX   MEM  WB
                 ^
         Both need memory at same time --> CONFLICT

Solutions:

• Resource duplication: Use separate instruction memory and data memory (Harvard architecture).
• Pipeline stalling (bubble insertion): Insert a NOP (no-operation) cycle to delay one instruction.

2. Data Hazards

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

Types:

Example (RAW):

ADD R1, R2, R3    ; writes R1
SUB R4, R1, R5    ; reads R1 -- hazard!

Solutions:

• Forwarding (Data Bypassing): Route the result directly from the output of one stage to the input of another without waiting for WB stage.
• Pipeline Stalling / Bubbles: Insert NOP cycles (stall) until the required data is available.
• Compiler-based reordering: Reorder instructions so that independent instructions fill the delay slots.

3. Control Hazards (Branch Hazards)

Definition: Arise due to branch instructions (conditional/unconditional jumps). The pipeline fetches the next sequential instruction before knowing whether a branch is taken, causing incorrect instructions to enter the pipeline.

Example:

BEQ R1, R2, LABEL   ; branch instruction
ADD R3, R4, R5      ; fetched but may not be needed

Solutions:

• Branch Prediction: Predict whether a branch will be taken (static or dynamic) and fetch accordingly.
  • Static: Always predict taken or always predict not taken.
  • Dynamic: Use a branch history table (BHT) to predict based on past behavior.
• Delayed Branching: Execute one or more instructions after the branch (delay slot) that are independent of the branch outcome.
• Flushing the Pipeline: If a wrong instruction is fetched, flush (discard) it and fetch the correct one (costly but correct).
• Branch Target Buffer (BTB): Cache the target address of branches to reduce delay.

Summary Table

Key Point: Hazards reduce pipeline efficiency. The goal of all solutions is to minimize CPI (Cycles Per Instruction) and keep the pipeline as full as possible.

Short Notes

(a) Microprogrammed Control Unit

A Microprogrammed Control Unit is a control unit implementation where the control signals required to execute machine instructions are generated by a program stored in a special high-speed memory called the Control Memory (CM).

Key Concepts

• Proposed by Maurice Wilkes (1951).
• Each machine instruction is interpreted by a sequence of microinstructions stored in control memory.
• A microinstruction specifies the control signals to be activated during one clock cycle.
• A sequence of microinstructions for one machine instruction is called a microprogram or microcode.

Components

Working

1. Machine instruction is fetched and decoded.
2. The opcode maps to a starting address in control memory.
3. Microinstructions are fetched sequentially, generating control signals.
4. Execution continues until the microprogram for that instruction completes.

Advantages

• Easy to design and modify (change microcode instead of hardware).
• Flexible and less error-prone than hardwired control.

Disadvantage

• Slower than hardwired control due to memory access overhead.

(b) Virtual Memory

Virtual Memory is a memory management technique that allows a computer to use more memory than is physically available (RAM) by using a portion of secondary storage (hard disk) as an extension of main memory.

Key Concepts

• Programs are given the illusion of a large, contiguous address space called the virtual address space.
• Only the actively used portions of a program need to reside in physical memory at any time.
• The rest resides on disk in a swap space or page file.

How It Works

• The virtual address space is divided into fixed-size blocks called pages.
• Physical memory is divided into frames of the same size.
• A Page Table maps virtual page numbers to physical frame numbers.
• When a referenced page is not in physical memory, a page fault occurs, and the OS loads the required page from disk.

Address Translation

Virtual Address --> [Page Table] --> Physical Address
  (Page No. + Offset)               (Frame No. + Offset)

Benefits

Disadvantage

• Thrashing: If too many page faults occur, the system spends more time swapping than executing, severely degrading performance.