Unit2 - Subjective Questions

General Register Organization

A CPU often contains a set of general-purpose registers that can be accessed more quickly than memory. These registers are connected via a bus system.

Block Diagram Components

1. Register File: A set of registers (e.g., to ).
2. Multiplexers (MUX): Used to select which register contents are placed on the A-bus and B-bus for the ALU.
3. ALU (Arithmetic Logic Unit): Performs the operation selected by the operation code (OPR).
4. Decoder: Selects the destination register to receive the result from the ALU via the input bus.

Control Word Format

The operation of the register unit is controlled by a Control Word, typically divided into four fields:

1. SELA (3 bits): Selects the register for the A-bus (Source A).
2. SELB (3 bits): Selects the register for the B-bus (Source B).
3. SELD (3 bits): Selects the destination register to store the result.
4. OPR (Operation Code - e.g., 5 bits): Specifies the ALU operation (ADD, SUB, XOR, etc.).

Example Operation:

• SELA: Binary code for .
• SELB: Binary code for .
• OPR: Binary code for ADD.
• SELD: Binary code for .

Register Stack vs. Memory Stack

Register Stack Operations

A register stack uses a Stack Pointer (SP) to track the top of the stack. A typical hardware stack might have 64 words.

1. PUSH Operation (Insert)

Inserting items into the stack:

1. (Increment stack pointer).
2. (Write data from Data Register to the top of the stack).
3. Check for overflow: If Limit, indicate Full.

2. POP Operation (Delete)

Removing items from the stack:

1. (Read data from the top of the stack).
2. (Decrement stack pointer).
3. Check for underflow: If , indicate Empty.

Arithmetic Statement:

1. Three-Address Instructions

Uses two source operands and one destination.

1. ADD R1, A, B ()
2. ADD R2, C, D ()
3. MUL X, R1, R2 ()

2. Two-Address Instructions

Destination is also a source.

1. MOV R1, A ()
2. ADD R1, B ()
3. MOV R2, C ()
4. ADD R2, D ()
5. MUL R1, R2 ()
6. MOV X, R1 ()

3. One-Address Instructions

Uses an Accumulator (AC) register implied.

1. LOAD A ()
2. ADD B ()
3. STORE T ()
4. LOAD C ()
5. ADD D ()
6. MUL T ()
7. STORE X ()

4. Zero-Address Instructions

Uses a Stack (TOS = Top of Stack).

1. PUSH A ()
2. PUSH B ()
3. ADD ()
4. PUSH C ()
5. PUSH D ()
6. ADD ()
7. MUL ()
8. POP X ()

Reverse Polish Notation (RPN)

RPN, or Postfix Notation, is a mathematical notation in which operators follow their operands (e.g., becomes ). It is advantageous for computers because it eliminates the need for parentheses and operator precedence rules during execution.

Stack Evaluation of

Postfix Conversion:

Steps:

1. Scan 3: Push 3. Stack: [3]
2. Scan 4: Push 4. Stack: [3, 4]
3. *Scan : Pop 4, Pop 3. Compute . Push 12. Stack:** [12]
4. Scan 5: Push 5. Stack: [12, 5]
5. Scan 6: Push 6. Stack: [12, 5, 6]
6. *Scan : Pop 6, Pop 5. Compute . Push 30. Stack:** [12, 30]
7. Scan +: Pop 30, Pop 12. Compute . Push 42. Stack: [42]

Final Result: 42

Addressing Modes

Addressing modes are rules used by the CPU to interpret the operand field of an instruction to locate the data (Effective Address).

1. Immediate Addressing

• Definition: The operand is specified directly in the instruction itself. No memory reference is needed to fetch data.
• Example: MOV R1, #5
  • Loads the value 5 directly into Register R1.

2. Register Indirect Addressing

• Definition: The instruction specifies a register whose content is the memory address of the operand (Effective Address = Content of Register).
• Example: MOV R1, (R2) or LOAD R1, [R2]
  • If contains $1000$, the CPU goes to memory address $1000$ to get the data and loads it into .

3. Relative Addressing

• Definition: The Effective Address is calculated by adding the address part of the instruction to the content of the Program Counter (PC).
• Usage: Commonly used in Branch instructions (ZR, JMP).
• Example: JMP $ + 10
  • If PC is currently 200, execution jumps to address 210.

Given:

• Program Counter () = 200 (Assuming PC points to next instruction, typically or , but for standard academic problems often taken as current instruction address field relative to PC offset, or standard definitions. Standard Convention: usually holds address of next instruction. If the current instruction is at 200, next is 201. However, if 'Relative' implies adding the address field to PC, we use ).
• Address Field in Instruction = 500.
• = 400.
• = 100.

Calculations:

1. Direct Addressing:

2. Immediate Addressing:

   • The operand is the address field itself.
   • (The location of the operand is the next word in instruction stream) OR logically, Operand = 500.

3. Relative Addressing:

   • Usually calculated as .
   • Assuming PC has incremented to 201 (next instruction): .
   • (Note: Sometimes simpler problems assume PC=200, resulting in 700. Both are acceptable depending on specific CPU architecture defined in class).

4. Register Indirect Addressing (using R1):

5. Indexed Addressing:

Comparison: RISC vs. CISC

Characteristics of RISC

1. Simple Instructions: Executes within a single clock cycle.
2. Load/Store Architecture: Memory access is restricted to Load and Store instructions; ALU operations happen on registers.
3. Fixed Instruction Length: Simplifies decoding logic.
4. Hardwired Control: faster than microprogrammed control.
5. Large Register File: Reduces memory traffic.

Overlapping Register Windows

To handle the overhead of passing parameters during procedure calls, RISC architectures (like Berkeley RISC) use Overlapping Register Windows.

• Concept: The register file is divided into multiple small sets called windows.
• Structure:
  1. Global Registers: Accessible by all procedures.
  2. Local Registers: Local variables of the current procedure.
  3. High/Output Registers: Used to pass parameters to the called procedure.
  4. Low/Input Registers: Used to receive parameters from the calling procedure.
• Overlap: The Output registers of the calling window physically overlap with the Input registers of the called window. This allows passing parameters without moving data in memory.

Processor Status Word (PSW)

The PSW is a special register that contains status information about the state of the CPU. It typically includes the Condition Code Flags (Status bits) and other control bits (like Interrupt Enable, Supervisor mode).

Status Bit Flags

The ALU sets these bits after an arithmetic or logic operation:

1. C (Carry Flag):

   • Set to 1 if the operation resulted in a carry-out from the most significant bit (in addition) or a borrow (in subtraction).
   • Used for unsigned arithmetic overflow check.

2. S (Sign Flag):

   • Set to 1 if the MSB of the result is 1 (indicating a negative number).
   • Set to 0 if the result is positive.

3. Z (Zero Flag):

   • Set to 1 if the result of the ALU operation is zero.
   • Set to 0 if the result is non-zero.

4. V (Overflow Flag):

   • Set to 1 if the result of a signed arithmetic operation is too large to fit in the register (Signed Overflow).
   • Calculated as (XOR of carry into MSB and carry out of MSB).

The Interrupt Cycle

At the end of the execution of every instruction, the CPU checks for pending interrupts.

1. Check: If the Interrupt Enable flag is On and an interrupt signal is present.
2. Store Context: The CPU pushes the current Program Counter (PC) and PSW onto the stack to save the return address and status.
3. Branch: The PC is loaded with the address of the specific Interrupt Service Routine (ISR) (often via an Interrupt Vector).
4. Execute ISR: The CPU executes the ISR.
5. Restore: The ISR ends with a Return from Interrupt instruction, which pops the old PC and PSW from the stack, resuming the original program.

Interrupt vs. Subroutine Call

Data transfer instructions move data between registers, memory, and I/O devices without changing the data content.

1. Register-to-Register:

   • Moves data inside the CPU.
   • Example: MOV R1, R2 (Copy content of R2 to R1).

2. Register-to-Memory (and vice versa):

   • Moves data between the CPU and RAM.
   • Example: LOAD R1, [1000] (Load data from memory address 1000 to R1).
   • Example: STORE R1, [2000] (Store R1 content to memory address 2000).
   • Example: PUSH R1 / POP R1 (Stack operations).

3. Register-to-Input/Output:

   • Moves data between CPU and peripherals.
   • Example: IN R1, PortA (Read from input port).
   • Example: OUT PortB, R1 (Write to output port).

Types of Interrupts

1. External Interrupts (Hardware Interrupts):

   • Initiated by hardware devices outside the CPU.
   • Examples: I/O device requesting data transfer, Timer expiration, Power failure signal.
   • These are asynchronous to the program execution.

2. Internal Interrupts (Traps or Exceptions):

   • Arise from illegal or erroneous use of an instruction or data.
   • Examples: Divide by zero, Arithmetic overflow, Stack overflow, Invalid Opcode.
   • These are synchronous with the program execution.

3. Software Interrupts:

   • Initiated by executing a special instruction.
   • Used by the programmer to request services from the Operating System (System Calls).
   • Example: INT 21H in x86 assembly to call DOS services, Switching from User Mode to Supervisor Mode.

Program Control Instructions

These instructions alter the sequence of program execution by changing the content of the Program Counter (PC).

• Typical Instructions: Branch (JMP), Call, Return, Compare, Test.

Unconditional vs. Conditional Branch

1. Unconditional Branch (JMP)

• Action: Always jumps to the specified address.
• Mechanism: The PC is loaded with the target address provided in the instruction.
• Example: JMP Label (Execution continues at Label immediately).

2. Conditional Branch

• Action: Jumps to the specified address only if a specific condition (based on Status Flags) is met. Otherwise, it executes the next sequential instruction.
• Mechanism: Checks flags (Z, S, C, V).
• Examples:
  • BZ Label (Branch if Zero flag is 1).
  • BNE Label (Branch if Zero flag is 0).
  • BC Label (Branch if Carry flag is 1).

The number of address fields in an instruction determines the organization of the CPU.

1. Three-Address Format:

   • Opcode Dest, Src1, Src2
   • Example: ADD R1, A, B
   • Trade-off: Shortest code (fewer instructions needed), but long instruction bits (requires more memory width).

2. Two-Address Format:

   • Opcode Dest, Src (Dest also acts as one source).
   • Example: ADD R1, B ()
   • Trade-off: Most common in commercial computers; balanced instruction length.

3. One-Address Format:

   • Opcode Operand
   • Uses an implied Accumulator (AC) register.
   • Example: ADD B ()
   • Trade-off: Simpler hardware, but requires more instructions to complete a task.

4. Zero-Address Format:

   • Opcode
   • Uses a Stack (operands are popped from top of stack).
   • Example: ADD
   • Trade-off: Very short instructions, excellent for complex expression evaluation, but requires stack hardware overhead.

Data manipulation instructions perform operations on data and provide the computational capabilities for the computer.

1. Arithmetic Instructions

• Perform numerical operations.
• Examples:
  • ADD, SUB, MUL, DIV.
  • INC (Increment), DEC (Decrement).
  • ADDC (Add with Carry) - used for multi-precision arithmetic.

2. Logical and Bit Manipulation Instructions

• Perform binary operations on bits strings. Often used to manipulate individual bits or check status.
• Examples:
  • AND (Masking).
  • OR (Setting bits).
  • XOR (Inverting bits).
  • NOT (Complement).

3. Shift Instructions

• Shift bits of a register left or right.
• Types:
  • Logical Shift: Inserts 0s (SHL, SHR).
  • Arithmetic Shift: Preserves the sign bit (SAL, SAR).
  • Rotate: Bits shifted out re-enter at the other end (ROL, ROR).

Arithmetic Shift Right (ASR)

ASR is used for signed binary numbers. When shifting right (dividing by 2), the sign of the number must remain unchanged.

• Mechanism:
  1. Shift all bits to the right.
  2. The Least Significant Bit (LSB) is shifted out (lost or into Carry).
  3. The Most Significant Bit (MSB / Sign Bit) is replicated.
     • (Sign bit stays same)
     • (for other bits)

Difference from Logical Shift Right (LSHR)

• LSHR: Used for unsigned numbers. It shifts right and inserts a 0 into the MSB position.
• Example:
  • Binary: 1100 (-4 in 4-bit signed)
  • ASR: 1110 (-2)
  • LSHR: 0110 (+6)

Micro-operations are the most basic atomic operations that a processor can perform. A single machine instruction (like ADD R1, R2) is actually executed as a sequence of several micro-operations.

Categories

1. Register Transfer: Transfer binary info from one register to another ().
2. Arithmetic: Perform arithmetic on register contents ().
3. Logic: Perform bit manipulation ().
4. Shift: Shift register contents.

Context in Execution Loop

• Fetch Cycle: Micro-ops transfer PC to MAR, read Memory to MBR.
• Decode Cycle: Micro-ops decode opcode.
• Execute Cycle: The control unit generates signals to trigger specific ALU and Register micro-ops to complete the instruction.

In a General Register Organization, the Control Word is a binary code that configures the hardware (Multiplexers, Decoders, and ALU) for a specific clock cycle.

Structure

It generally consists of about 14 bits (depending on architecture):

• SELA (3 bits): Selects Source A register.
• SELB (3 bits): Selects Source B register.
• SELD (3 bits): Selects Destination register.
• OPR (5 bits): Selects the ALU function.

ALU Operation Selector (OPR)

The OPR field connects directly to the control inputs of the Arithmetic Logic Unit.

• If OPR = 00001, the ALU adds A and B.
• If OPR = 00010, the ALU subtracts B from A.
• If OPR = 00100, the ALU performs logical AND.

The result of this operation is then routed via the system bus to the register selected by SELD.

RISC and Compiler Optimization

RISC (Reduced Instruction Set Computer) shifts the complexity from hardware to software (the compiler).

1. Simple Instructions: Since RISC instructions are simple (Load, Store, Add), complex high-level language constructs (like a for loop or matrix multiplication) require a sequence of many RISC instructions. The compiler is responsible for generating these efficient sequences.
2. Register Allocation: RISC has a large register file. The compiler must use advanced graph-coloring algorithms to keep variables in registers as long as possible to minimize slow memory access.
3. Pipeline Management: To avoid pipeline stalls (hazards), RISC compilers reorder instructions (Instruction Scheduling) to ensure data is ready when needed.
4. Delayed Branching: In many RISC designs, the compiler must insert useful instructions (or NOPs) in the delay slot after a branch instruction.

In contrast, CISC handles these complexities via microcode in hardware, requiring less aggressive optimization from the compiler.

Implied Addressing Mode

• Definition: The operands are specified implicitly in the definition of the instruction. No address field is needed.
• Examples:
  • CLA: Clear Accumulator (Operand is AC).
  • CMA: Complement Accumulator.
  • CLC: Clear Carry Flag.
  • Zero-address instructions in a stack organization (e.g., ADD implicitly operates on the top two stack items).

Auto-Increment / Auto-Decrement Mode

This is a variation of Register Indirect addressing, useful for iterating through arrays.

• Auto-Increment:
  • The address is taken from the register.
  • After accessing memory, the register content is automatically incremented.
  • ; then .
• Auto-Decrement:
  • The register content is decremented before accessing memory.
  • ; then .