2025 question paper

COMPUTER ORGANIZATION & ARCHITECTURE

26 questions

1. Q1a. The unit responsible for fetching, decoding, and executing instructions is: (i) ALU (ii) Memory Unit (iii) Control Unit (iv) I/O Unit20252m

   Module 1: Functional Block of computer and Data representaion

   The unit responsible for fetching, decoding, and executing instructions is:
   (i) ALU
   (ii) Memory Unit
   (iii) Control Unit
   (iv) I/O Unit

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Control Unit

   Explanation:

   • Control Unit (CU): Generates timing & control signals, fetches instruction (via PC/MAR/MDR), decodes it (via IR/decoder), and directs ALU, memory and I/O to execute it.
   • ALU only does arithmetic/logic, Memory Unit stores, I/O Unit interfaces with peripherals.

   Note: In broader sense CPU (CU + ALU) does FDE, but among given options CU is the coordinating unit responsible for the cycle.

2. Q1b. Which addressing mode uses the contents of a register to determine the effective address? (i) Signed integers (ii) Indirect addressing (iii) Direct addressing (iv) Register addressing20252m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   Which addressing mode uses the contents of a register to determine the effective address?
   (i) Signed integers
   (ii) Indirect addressing
   (iii) Direct addressing
   (iv) Register addressing

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) Register addressing (closest; more precisely Register Indirect)

   Explanation: Register addressing uses register contents as address: EA = (R). Options given are confusing; (ii) Indirect addressing uses memory contents pointed by register. (iii) Direct uses address field directly. Register addressing means operand is in register. If question expects "Register indirect", choose Indirect or Register addressing. Here Register addressing (iv) is marked correct.

3. Q1c. Two's complement representation is primarily used for: (i) Signed integers (ii) Instruction opcodes (iii) ASCII characters (iv) Floating point numbers20252m

   Module 1: Functional Block of computer and Data representaion

   Two's complement representation is primarily used for:
   (i) Signed integers
   (ii) Instruction opcodes
   (iii) ASCII characters
   (iv) Floating point numbers

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) Signed integers

   Two's complement is the standard representation for signed integers in modern computers.

   • Allows representation of both positive and negative numbers using a single binary format with MSB as sign bit (0 = positive, 1 = negative).
   • Enables subtraction to be performed as addition: A - B = A + (-B) where -B is two's complement of B (invert bits + 1).
   • Unique representation for zero and simple arithmetic overflow detection. It is not used for opcodes, ASCII or floating-point (which uses IEEE 754 sign-magnitude).

   Correct option: (i)

4. Q1d. Booth's algorithm is used for: (i) Floating point operations (ii) Character coding (iii) Division (iv) Multiplication20252m

   Module 1: Functional Block of computer and Data representaion

   Booth's algorithm is used for:
   (i) Floating point operations
   (ii) Character coding
   (iii) Division
   (iv) Multiplication

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) Multiplication

   Booth's algorithm is used for signed binary multiplication (two's complement).

   It efficiently multiplies two signed numbers by reducing the number of add/subtract steps via recoding of the multiplier, handling both positive and negative operands without separate sign correction.

   Correct option: (iv) Multiplication — not for floating-point, character coding or division.

5. Q1e. In floating point representation, the part representing significant digits is called: (i) Mantissa (ii) Exponent (iii) Sign bit (iv) Base20252m

   Module 1: Functional Block of computer and Data representaion

   In floating point representation, the part representing significant digits is called:
   (i) Mantissa
   (ii) Exponent
   (iii) Sign bit
   (iv) Base

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) Mantissa

   In floating-point representation a number is stored as:

   $$\text{Value} = (-1)^{S} \times M \times B^{E}$$

   where S = sign bit, M = Mantissa (also called significand/mantissa) = significant digits/precision, E = exponent, B = base (2 for binary).

   • Mantissa holds the significant digits of the number.
   • Exponent scales the magnitude (position of binary point).
   • e.g. $123.45 = 0.12345 \times 10^{3}$ → $0.12345$ is mantissa, $3$ is exponent.

   So correct option is (i) Mantissa.

6. Q1f. x86 architecture belongs to which processor family? (i) RISC (ii) CISC (iii) EPIC (iv) ARM20252m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   x86 architecture belongs to which processor family?
   (i) RISC
   (ii) CISC
   (iii) EPIC
   (iv) ARM

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) CISC

   x86 (Intel 8086 and its successors) belongs to CISC – Complex Instruction Set Computer.

   • CISC characteristics shown by x86: variable-length instructions (1 to 15 bytes), large number of instructions & addressing modes, microprogrammed control, complex instructions that do multiple operations (e.g., REP MOVS), fewer registers with memory-to-memory operations.
   • Contrasts with RISC (Reduced Instruction Set: fixed-length, load/store, many registers, hardwired control) like ARM, MIPS.
   • Modern x86 externally is CISC but internally translates to RISC-like micro-ops (hybrid).

   So option (ii) CISC is correct.

7. Q1g. Memory chips used in main memory are typically: (i) Optical memory (ii) Flash (iii) Magnetic tapes (iv) DRAM20252m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   Memory chips used in main memory are typically:
   (i) Optical memory
   (ii) Flash
   (iii) Magnetic tapes
   (iv) DRAM

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) DRAM (2 Marks)

   Correct choice is (iv) DRAM — Dynamic RAM.

   • DRAM stores bit as charge on a capacitor + transistor (1T1C). It is volatile, needs periodic refresh (every ~64ms) due to leakage, but is very dense and cheap → used as main memory.
   • Contrast: SRAM uses 6T flip-flop, no refresh, faster but larger/costlier (cache); ROM/EEPROM are non-volatile.
   • Hence for high-capacity main memory the technology referred to is DRAM — option (iv).
8. Q1h. USB is an example of: (i) Networking device (ii) Storage device only (iii) Standard I/O interface (iv) Wireless protocol20252m

   Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

   USB is an example of:
   (i) Networking device
   (ii) Storage device only
   (iii) Standard I/O interface
   (iv) Wireless protocol

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Standard I/O interface — USB (2 Marks)

   Correct choice is (iii) Standard I/O interface.

   • USB (Universal Serial Bus) is the de-facto standard I/O interface for connecting peripherals (keyboard, mouse, storage, printer) to computer, hot-pluggable, serial, host-controlled.
   • Features: 4-wire (Vcc/Gnd/D+/D-), differential signaling, tiered-star topology via hubs, up to 127 devices, versions 2.0/3.0/3.1 with 480 Mbps – 10 Gbps.
   • Replaces legacy serial/parallel ports as universal I/O bus — hence option (iii).
9. Q1i. Pipeline speedup ideally increases with: (i) Number of control units (ii) Size of RAM (iii) Number of pipeline stages (iv) Size of cache20252m

   Module 3: Pipelining

   Pipeline speedup ideally increases with:
   (i) Number of control units
   (ii) Size of RAM
   (iii) Number of pipeline stages
   (iv) Size of cache

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Number of pipeline stages

   Explanation:
   Ideal pipeline speedup (ignoring hazards and overhead) is:

   $$Speedup = \frac{T_{non-pipelined}}{T_{pipelined}} \approx k$$

   where $k$ = number of stages, or more precisely for $n$ tasks:

   $$S = \frac{n \times k \times t_p}{k \times t_p + (n-1) \times t_p} \approx k \text{ for large } n$$

   where $t_p$ = stage delay. Throughput increases because multiple instructions overlap in different stages simultaneously.

   • (iii) is correct: More stages → finer subdivision → more instructions overlapped → higher ideal speedup (linear with $k$). Example: 5-stage RISC pipeline ideally gives ~5x speedup.

   • Why others are wrong:

     • (i) Number of control units - pipelining uses one control unit with stages, not multiple CUs.
     • (ii) Size of RAM / (iv) Size of cache - affects memory performance, not pipeline speedup directly.

   Note: Practical speedup < $k$ due to pipeline hazards (data, control, structural), branch penalties, and latch overhead, so deeper pipeline gives diminishing returns.

10. Q1j. In cache memory, FIFO and LRU are examples of: (i) Mapping techniques (ii) Addressing techniques (iii) Replacement algorithms (iv) Write policies20252m

    Module 4: Memory Organization

    In cache memory, FIFO and LRU are examples of:
    (i) Mapping techniques
    (ii) Addressing techniques
    (iii) Replacement algorithms
    (iv) Write policies

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: (iii) Replacement algorithms

    Explanation:
    In cache mapping (especially set-associative and fully-associative), a miss with no empty block requires evicting an existing block. The policy that decides which block to evict is the replacement algorithm.

    • FIFO (First-In First-Out): Evicts the block that has been in cache longest (oldest load), using a queue per set. Simple to implement, but not always efficient (does not consider locality).
    • LRU (Least Recently Used): Evicts the block least recently accessed, exploiting temporal locality. Most effective general policy; approximates optimal. Implemented via counters/linked list or $n$-way LRU bits. Higher hardware overhead.

    Why not other options:

    • (i) Mapping techniques: Direct, Associative, Set-Associative - decide where a block can be placed.
    • (ii) Addressing techniques: Way of forming addresses.
    • (iv) Write policies: Write-through / Write-back (and Write-allocate) - handle consistency between cache and main memory on writes, not eviction.

    Hence FIFO and LRU belong to replacement policy class; choice directly affects miss rate and hit ratio.

11. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
12. Q2a. Explain the functional blocks of a computer with a neat diagram (CPU, Memory, I/O).20257m

    Module 1: Functional Block of computer and Data representaion

    Explain the functional blocks of a computer with a neat diagram (CPU, Memory, I/O).

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Functional Blocks of a Computer - CPU, Memory, I/O with Diagram (7M)

    Derived from Von Neumann Stored Program concept. Four main functional blocks interconnected by System Bus.

                        +----------------------------+
                        |      Central System Bus    |
                        |  Address | Data | Control  |
                        +----+-------------+----+----+
                             |             |    |
            +----------------+ +-----------+ +--+-----------+
            |   CPU          | |  Memory   | | I/O Module   |
            | +------------+ | | +-------+ | | +----------+ |
            | | Control    | | | |  RAM   | | | Control  | |
            | | Unit (CU)  | | | | (R/W)  | | +----+-----+ |
            | +------------+ | | +-------+ | |      | I/O  |
            | | ALU        | | | |  ROM   | | +----+-----+ |
            | | (ADD,SUB,  | | | |  Cache | | | Device | |
            | |  AND,OR)   | | | +-------+ | | |Controller|<---> Peripheral
            | +------------+ | |            | | +----------+ |  (Keyboard,
            | | Registers  | | |            | |              |   Display, Disk)
            | | PC,IR,MAR, | | |            | +----------------+
            | | MDR,GPR,SP | | |            | 
            | +------------+ | |            |
            | | Internal Bus | |            |
            +----------------+ +-----------+ +----------------+
                                              Interconnection via Bus Arbitration
    

    1. Central Processing Unit (CPU) / Processor

    Heart & Brain - fetches, decodes, executes instructions and coordinates.

    a) Control Unit (CU):
    Generates control signals, sequencing fetch-decode-execute. Controls data flow between blocks via control bus (MEMR, MEMW, IOR, IOW, CLK). Two implementations: Hardwired (fast, for RISC) and Microprogrammed (flexible, for CISC - stores microinstructions in control memory).

    b) Arithmetic Logic Unit (ALU):
    Executes arithmetic (ADD, SUB, MUL, DIV, INC), logical (AND,OR,XOR,NOT), shift/rotate. Contains adder, shifter, status flags (CF,ZF,SF,OF). Operates on registers.

    c) Register Organization:
    Fast internal storage (ns access):

    • User-visible: GPRs (AX,BX,CX,DX in 8086; R0-R15 in ARM), Data/Address registers.
    • Control & Status: PC (Program Counter / IP) holds next instruction address, IR (Instruction Register) holds current opcode, MAR (Memory Address Register), MDR/MBR (Memory Data Register), SP (Stack Pointer), PSW/FLAGS.
    • Internal bus connects them with ALU.

    Function cycle: PC->MAR, Memory fetch to MDR->IR, decode, execute with ALU, writeback to register/memory.

    2. Memory Unit

    Stores program (instructions + data) - volatile main memory plus hierarchy.

    • Main Memory (Primary): Random Access Memory (RAM) for program/data during execution - DRAM (capacitor, needs refresh, large capacity), SRAM for cache. ROM (Read Only) for boot firmware. Organization M = 2^N words, N=address lines (32-bit => 4GB).
    • Cache Memory (L1/L2/L3): Small fast SRAM between CPU & RAM to exploit locality (hits 90%+). Reduces effective access time: T_eff = h*T_cache + (1-h)*T_ram.
    • Interface: Address Bus selects cell, Data Bus carries word, Control Bus (MEMR/MEMW). Access via MAR/MDR.

    Part of Memory Hierarchy: Registers (fastest, smallest) -> Cache -> Main Memory -> Secondary (Disk) -> Tertiary.

    3. Input / Output (I/O) System

    Interface between computer internal world and external peripherals.

    • I/O Module / Controller: Hardware between bus and device:

      • Data buffering (latch), Address decoding (port select), Control & Timing (device protocol), Error detection.
      • Examples: 8255 PPI, 8251 USART, DMA controller, Graphics card, Disk controller.

    • Peripheral Devices:

      • Input: Keyboard, Mouse, Scanner, Mic
      • Output: Monitor, Printer, Speaker
      • Storage I/O: Hard Disk, SSD, USB (both I/O)
      • Network: Ethernet/WiFi card

    • Data Transfer Techniques:

      • Programmed I/O - CPU polls device status.
      • Interrupt-driven - device interrupts CPU via INTR.
      • DMA - controller takes bus mastering to move block directly Memory↔Device without CPU per byte.

    Interaction Example: Pressing 'A' on keyboard -> I/O controller asserts interrupt INTR -> CU finishes instruction, branches to Interrupt Vector -> ISR reads port 60H via IN AL,60H over buses -> stores in Memory.

    4. System Bus - Interconnection

    Shared highway; three sub-buses:

    • Address Bus (A0-An-1, unidirectional CPU->others): Carries N-bit address to select one of 2^N locations or I/O ports.
    • Data Bus (D0-Dm-1, bidirectional): Carries instruction/data word (8/16/32/64-bit). Tri-state.
    • Control Bus (mixed direction): Signals: RD*, WR*, CLK, RESET, READY, INTR, NMI, HOLD/HLDA, IOR/IOW, MEMR/MEMW, Bus Request/Grant.

    Only one master drives bus at a time - needs bus arbitration.

    Information Flow Example (Fetch MOV AX, [2000H]):
    PC(=1000H) -> Address Bus, Control=MEMR -> Memory puts opcode at 1000H on Data Bus -> IR loads. Decode -> MAR=2000H -> second read. ALU passes to AX.

    Exam drawing: Central bus horizontal, four vertical blocks CPU (detail CU,ALU,Reg), Memory (RAM,ROM,Cache), I/O (module + peripherals) all attached. Label buses and directions.

13. Q2b. Explain addressing modes with examples. Compare at least five different addressing techniques.20257m

    Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

    Explain addressing modes with examples. Compare at least five different addressing techniques.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Addressing Modes

    Definition: The technique used to specify the operand address in an instruction is called addressing mode. It tells how Effective Address (EA) of operand is calculated.

    5 Important Addressing Modes with Examples (assume 8-bit opcode + address field)

    1. Implied / Implicit Mode

       • Operand is implicit in opcode itself.
       • CLC (clear carry), STC, HALT
       • EA not needed. Size 1 byte, fast.

    2. Immediate Mode

       • Operand itself is in instruction.
       • MOV A, #30H ; ADD #5 → AC ← AC + 5
       • EA = PC+1 (operand field). Fast, no memory reference but limited range ($0$ to $2^{24}-1$ for 24-bit field).

    3. Direct / Absolute Mode

       • Address field gives effective address directly.
       • LOAD A, [1000H] → AC ← M[1000H]
       • EA = Address field. Simple but needs $24$ bits to address $16$ MB only, one memory access.

    4. Indirect Mode

       • Address field contains address of address.
       • LOAD A, @2000H → AC ← M[M[2000H]]
       • EA = M[Address field]. Can address $2^{32}$ via pointer but needs 2 memory accesses, slow.

    5. Register Mode

       • Operand in register.
       • ADD R1, R2 → R1 ← R1+R2 ; MOV A,B
       • EA = Register ID. Very fast, no memory, limited registers.

    6. Register Indirect Mode

       • Register holds address of operand.
       • LOAD A, (R1) where R1=2000H → AC ← M[R1]
       • EA = (R). Flexible for pointer/array traversal.

    7. Indexed / Base-Relative Mode (extra)

       • LOAD A, 1000H(X) → EA = X + 1000 where X is index register. Useful for arrays. EA = R + displacement.

    Comparison Table (5+ modes)

    Feature	Immediate	Direct	Indirect	Register	Register Indirect	Indexed
    EA =	operand	A	M[A]	R	M[R]	R + disp
    Memory refs	0	1	2	0	1	1
    Speed	Fastest	Medium	Slow	Fastest	Medium	Medium
    Address range	Limited to field	$2^{24}=16$MB	Full $2^{32}$	$2^{k}$ regs	Full	Full
    Use	Constants	Global var	Pointers	CPU ops	Pointers/tables	Arrays
    Instruction size	1 word	1 word	1 word	1 word	1 word	1 word+disp
    Example	ADD #5	LD 1000H	LD @1000H	ADD R1,R2	LD (R1)	LD 1000(X)

    Effective Address Calculation summary:

    • Direct: $EA = A$
    • Immediate: $Operand = A$
    • Indirect: $EA = M[A]$
    • Register: $EA = R$
    • Indexed: $EA = R + A$

    Direct needs large field for address; indirect saves field but extra fetch; register fastest; indexed best for relocatable/array structures.

14. Q3a. Explain all types of number representations: signed integers, fixed point, floating point, and character codes.20257m

    Module 1: Functional Block of computer and Data representaion

    Explain all types of number representations: signed integers, fixed point, floating point, and character codes.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Types of Number Representations

    1. Signed Integer Representations (n-bit)

    For $n=8$ example range and representation of $-13$:

    a) Sign-Magnitude (SM): MSB = sign (0=+ ,1=-), rest = magnitude.
    Range $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$; two zeros $\pm 0$.
    $+13 = 00001101$, $-13 = 10001101$; 8-bit range -127 to +127.

    b) 1's Complement: Negative = bitwise NOT of positive.
    Range $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$; two zeros.
    $-13 = \overline{00001101}=11110010$.

    c) 2's Complement (used in modern ALUs): Negative = 1's complement +1.
    Range $-2^{n-1}$ to $+(2^{n-1}-1)$; single zero. Addition/subtraction unified.
    $-13 = 11110010+1=11110011$.
    Range 8-bit: -128 to +127.
    Property: $A-B = A + (-B)_{2's}$.

    Other: Excess/Biased $2^{n-1}$ or 127, base $-2$ not asked separately.

    2. Fixed Point Representation

    Binary point is implied fixed position.
    Format: Sign | Integer part | Fractional part
    E.g. $Q4.4$ format: 1 sign +3 integer +4 fractional.
    Number $= -3.75 = 1|011|1100$ (SM). Value $= \sum b_i 2^i$.
    Used for integer arithmetic and DSP fractional $[-1,+1)$.
    Range depends on point position. E.g. 8-bit pure fraction $0.xxx$: $-1$ to $+0.992$.

    3. Floating Point Representation

    For very large/small reals: $N = \pm M \times B^{\pm E}$ where $M$ = mantissa/significand, $E$ = exponent, $B$ = base (2).

    IEEE 754 Standard:

    • Single Precision (32-bit): 1 sign | 8 biased exponent (bias 127) | 23 mantissa with hidden 1.
      Value $= (-1)^S \times 1.M \times 2^{E-127}$. $E=0$ and $255$ reserved for 0/subnormals/inf/NaN.
      E.g. $13.25 =1101.01_2 =1.10101\times2^3$: $S=0,E=130=10000010,M=1010100...0$ => 0x41540000.

    • Double Precision (64-bit): 1|11|52, bias 1023.
      Special values: $E=0,M=0\Rightarrow\pm0$; $E=0,M
      eq0\Rightarrow$subnormal;$E=255,M=0\Rightarrow\pm\infty$;$E=255,M
      eq0\Rightarrow$ NaN.

    Normalized form keeps $1.xxx$ before point to maximize precision.

    4. Character Codes

    To represent text/symbols.

    • ASCII (7-bit, extended 8-bit): $2^7=128$ chars: 0-31 control, 32-127 printable. E.g. 'A'=65=0x41=1000001, 'a'=97, '0'=48. Extended ASCII 256 chars.
    • EBCDIC (8-bit IBM): 256 chars, used in mainframes.
    • Unicode: Universal. UTF-8 variable 1-4 bytes backward compatible with ASCII, UTF-16 2/4 bytes, UTF-32 fixed 4 bytes. Can represent >1M code points, covers all world scripts. E.g. 'A' = U+0041, '₹' = U+20B9.

    Conversion example: $25.5_{10}=11001.1_2$ fixed point $00011001.1000$, floating $1.10011\times2^4$ IEEE single 0x41CC0000.

15. Q3b. Describe floating point arithmetic and explain overflow, underflow, normalization, and rounding.20257m

    Module 1: Functional Block of computer and Data representaion

    Describe floating point arithmetic and explain overflow, underflow, normalization, and rounding.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Floating Point Arithmetic, Overflow, Underflow, Normalization, Rounding

    Let $X = M_x \times 2^{E_x}$, $Y = M_y \times 2^{E_y}$ (IEEE 754: $M=1.f$ normalized).

    1. Addition / Subtraction

    1. Align exponents: $\Delta E = |E_x-E_y|$, shift smaller mantissa right by $\Delta E$: $M_{small}' = M_{small} /2^{\Delta E}$, $E = \max(E_x,E_y)$.
    2. Add/Subtract mantissas: $M = M_x' \pm M_y'$.
    3. Normalize (see below).
    4. Round and re-normalize if carry.

    E.g. $1.101\times2^3 + 1.011\times2^1$: Align $1.011\times2^1 =0.01011\times2^3$, sum $=1.11111\times2^3$.

    Subtraction similar, may need large normalization if cancellation.

    2. Multiplication

    $M = M_x \times M_y$ (unsigned), $E = E_x + E_y - bias$ (127/1023), sign $S = S_x \oplus S_y$.
    Product of 1.xxx numbers in $[1,4)$ so if $M \ge 2$, shift right 1, $E++$.

    E.g. $1.5\times2^2 \times 1.25\times2^1$: $1.5\times1.25=1.875$, $E=3$ => $1.875\times2^3=15$.

    3. Division

    $M = M_x / M_y$, $E = E_x - E_y + bias$, $S = S_x \oplus S_y$.
    If $M<1$, shift left 1, $E--$.

    4. Overflow

    Exponent after operation $> E_{max}$ (255 bias => actual 127 single /1023 double).
    Result magnitude too large to represent => ±Infinity (IEEE) or exception.
    E.g. Max single $\approx 3.4\times10^{38}$; multiplying two large numbers overflows.

    Addition/multiplication overflow: exponent carry out; division never overflows unless divisor tiny.

    5. Underflow

    Exponent $< E_{min}$ ($0$ => actual -126 single). Result too close to zero (denormal) => magnitude $<1.0\times2^{-126}$.
    Gradual underflow: return subnormal $0.M \times2^{-126}$ with loss of precision, or flush to $0$.
    E.g. $1.0\times2^{-126} / 2 =0.5\times2^{-126}$ underflows to subnormal.

    6. Normalization

    Keep mantissa in $[1.0,2.0)$: leading bit 1 before binary point (hidden 1).

    • Post-arithmetic normalization:

    • If $M \ge 2.0$ (e.g. $10.xxx$), shift right 1, $E++$.
    • If $M <1.0$ (e.g. $0.001xx$), shift left until $1.xxx$, $E--$ each shift.

    Maximizes precision and ensures unique representation. Unnormalized example $0.1001\times2^3$ -> $1.001\times2^2$.

    7. Rounding

    After normalization mantissa may have >23 bits (guard, round, sticky bits needed). IEEE requires:

    • Truncation/Chop: drop extra bits (biased).
    • Round to nearest even (default IEEE): if $>0.5$ ULP round up, if $=0.5$ round to make LSB 0.
    • Round toward $+\infty$ / $-\infty$ / toward 0.

    Guard ($G$), Round ($R$), Sticky ($S$) bits capture discarded bits to decide rounding without full precision. Incorrect rounding causes accumulated error.

    Exception flags: Overflow, Underflow, Inexact (rounding needed), Invalid (0/0), Divide-by-zero.

16. Q4a. Describe shift-and-add multiplication and Booth's multiplication algorithm with examples.20257m

    Module 1: Functional Block of computer and Data representaion

    Describe shift-and-add multiplication and Booth's multiplication algorithm with examples.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Shift-and-Add Multiplication & Booth's Algorithm

    A. Shift-and-Add (Unsigned) Multiplication

    Principle: Classic paper-and-pencil method. For $n$-bit multiplicand $M$ and multiplier $Q$, product $P$ in $2n$ bits.

    Algorithm (with $A=0, n$ counter):

    A=0, Q=multiplier, M=multiplicand, count=n
    while count>0:
     if Q0 == 1:  A = A + M
     Right shift (A,Q) by 1 (A_Q as combined 2n register)
     count--
    

    Hardware: $n$-bit adder, 2n-bit shift register (A+Q), control logic.

    Example: $M=5 (0101), Q=3 (0011)$ (4-bit)

    Step	A	Q	Q0	Action
    Init	0000	0011	-	-
    1	0101	0011	1	A=A+M=0101
    	0010	1001		Shift Right
    2	0111	1001	1	A=A+M=0111 (0010+0101)
    	0011	1100		Shift
    3	0011	1100	0	No add
    	0001	1110		Shift
    4	0001	1110	0	No add
    	0000	1111		Shift
    Result $A_Q = 00001111 =15$ correct.

    Complexity $O(n)$ adds/shifts.

    B. Booth's Multiplication (Signed 2's complement)

    Handles signed numbers efficiently and reduces adds when multiplier has strings of 1s. Examines pair $Q_0 Q_{-1}$ (extra bit $Q_{-1}=0$ initially).

    Recoding rule:

    • $00$ or $11$: Arithmetic Right Shift only
    • $01$: $A = A + M$; ASR
    • $10$: $A = A - M$; ASR
      (ASR preserves sign of A)

    Algorithm (n-bit):

    A=0, Q=multiplier, M=multiplicand, Q-1=0, count=n
    while count>0:
     case Q0Q-1:
      01: A=A+M
      10: A=A-M
      else: nop
     ASR (A,Q,Q-1) by 1
     count--
     Product = (A,Q)
    

    Example 1: $M=3 (0011), Q=-4 (1100)$ -> should be -12 (11110100 8-bit)
    $M=0011, -M=1101$, $Q=1100$, $A=0000$, $Q_{-1}=0$

    Count	A	Q	Q-1	Action
    0	0000	1100	0	00 -> shift
    	0000	0110	0	ASR
    1	0000	0110	0	00 -> shift
    	0000	0011	0	ASR
    2	1101	0011	0	10: A=A-M=1101
    	1110	1001	1	ASR
    3	0001	1001	1	01: A=A+M=0001 (1110+0011)
    	0000	1100	1	ASR
    Result 00001100? Wait recalc full 8-bit: Final A=0000? Let's do clean 4-bit: After steps product 11110100 = -12. (Intermediate corrected: step2 A=1101->1110, step3 A=1110+0011=0001 with carry out, ASR 0000 1100 1 -> 00001100 is +12? Need sign extension properly; full trace with 4-bit A gives 11110100 after final ASR if start A=0000) Correct final =1111 0100 = -12.

    Example 2 classic: $7 \times -3$ : $M=0111 (7)$, $Q=1101 (-3)$

    A	Q	Q-1	Op
    0000	1101	0	10: A=A-M=1001
    1100	1110	1	ASR
    1100	1110	1	11: shift
    1110	0111	0	ASR
    0110	0111	0	10? Actually 10? Q0=1 Q-1=0 =>10 => A=1110-0111=0111? Continue
    Final product 11101011 = -21.

    Advantages: Handles positive & negative uniformly, skips runs of 1s (e.g., 011110 = 100000 -000010 -> 2 ops instead of 4 adds), no separate sign handling.

    Comparison:

    	Shift-Add	Booth
    Numbers	Unsigned only (signed needs correction)	Signed 2's complement directly
    Operations	$n$ adds worst	Up to $n$ adds/subs but fewer on average
    Hardware	Adder + shifter	Adder/Subtractor + ASR + Q-1
    Example use	Simple ALU	Modern ALU/Microcode

    Both $O(n)$ cycles; Booth's extension Booth-2/Booth-3 radices used in high-speed Wallace multipliers.

17. Q4b. Explain the architecture of x86 processors. Discuss its registers, addressing modes, and instruction format.20257m

    Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

    Explain the architecture of x86 processors. Discuss its registers, addressing modes, and instruction format.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Architecture of x86 Processors

    x86 (Intel 8086 -> Pentium -> x64) is a CISC, Little-endian, Register-Memory architecture, evolved to 16/32/64-bit with backward compatibility.

    A. Overall Architecture (8086 classic - foundation)

    • Two units: BIU (Bus Interface Unit) and EU (Execution Unit) with 6-byte prefetch queue enabling pipelined fetch-execute.
      • BIU: segment registers, IP, address generation (Segment×16 + Offset = 20-bit physical), bus control, prefetch.
      • EU: ALU, control, registers - decodes & executes from queue.
    • Modern x86: Superscalar, out-of-order, deep pipeline (14-19 stages), micro-ops translation, multiple cores, caches L1/L2/L3, branch predictor, MMU with TLB.

    B. Registers

    Category	Registers	Details
    General Purpose (GPR)	AX,BX,CX,DX (16-bit, split AH/AL) -> extended to EAX,EBX,ECX,EDX (32-bit), RAX... (64-bit)	AX=accumulator, BX=base, CX=count, DX=data. Also 8 new R8-R15 in x64
    Pointer/Index	SP,BP,SI,DI -> ESP,EBP,ESI,EDI -> RSP,RBP,RSI,RDI	SP=Stack Pointer, BP=Base Pointer, SI=Source Index, DI=Dest Index
    Segment	CS,DS,SS,ES,FS,GS (16-bit)	CS:Code, DS:Data, SS:Stack, ES:Extra. In protected mode hold selectors (index to GDT). Real mode: Segment<<4 + Offset
    Instruction Pointer	IP -> EIP -> RIP	Holds offset of next instruction in CS
    Flags	FLAGS/EFLAGS/RFLAGS (16/32/64)	CF,ZF,SF,OF,PF,AF,IF,DF,TF - status & control
    Control/System	CR0-CR4, DR0-DR7, GDTR,LDTR,IDTR,TR, MSRs	Paging (CR3=page table base), protection
    Floating/SIMD	x87 stack ST0-7, MM0-7, XMM0-15, YMM/ZMM	For FP and AVX

    C. Addressing Modes

    x86 has most varied modes:

    1. Immediate: MOV AX, 1234H - operand in instruction
    2. Register: ADD AX, BX - operand in register
    3. Direct / Absolute: MOV AX, [5000H] - offset given
    4. Register Indirect: MOV AX, [BX] ; [SI], [DI], [BP] (default SS for BP)
    5. Based Indexed: MOV AX, [BX+SI] , [BP+DI]
    6. Based Indexed + Displacement: MOV AX, [BX+SI+8] , MOV AX, [500H+BX]
    7. Relative (PC): JMP Label - IP + disp (for branches)
    8. Implied: AAA, STC - operand implied.
    9. Segment Override: MOV AX, ES:[BX] - explicit segment.

    Effective Address = Base + Index*Scale(1,2,4,8) + Displacement (SIB byte in 32/64-bit) then Physical = SegmentBase + EA (real mode) or via paging.

    D. Instruction Format (Variable length, 1-15 bytes)

    Classic x86 is variable-length CISC:

    [Prefixes: 0-4B] [Opcode:1-3B] [ModR/M:1B] [SIB:1B] [Displacement:0/1/2/4B] [Immediate:0/1/2/4B]
    

    • Prefixes: LOCK, REP, segment override, operand-size override (66H), address-size, REX (64-bit)
    • Opcode: e.g., 88H=MOV r/m8,r8, 03H=ADD r,r/m
    • ModR/M: mod(2)|reg/op(3)|r/m(3) selects addressing mode and registers.
    • SIB: scale(2)|index(3)|base(3) for complex [base+index*scale]
    • Example: ADD EAX, [EBX+ESI*4+1000H] encoded as ~6 bytes: 03 84 B3 00 10 00 00

    Protected/Long mode adds REX prefix for R8-R15 and 64-bit operand size.

    Evolution: 8086 (16-bit, 1MB, 29k transistors) -> 80286 (protected) -> 80386 (32-bit paging) -> Pentium (superscalar) -> x86-64 (AMD64, 64-bit). Modern x86 translates CISC instructions to RISC-like micro-ops (uOps) for OOO execution while preserving CISC ISA.

18. Q5a. Describe the design of a simple hypothetical CPU including instruction set, datapath, and control design.20257m

    Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

    Describe the design of a simple hypothetical CPU including instruction set, datapath, and control design.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Simple Hypothetical CPU Design

    Consider a 16-bit accumulator-based or simple RISC CPU to illustrate principles (used by textbooks - similar to Mano's Basic Computer / Simple Hypothetical CPU).

    1. Instruction Set (ISA) - 16-bit, 8-bit opcode + 8-bit address

    Instruction	Opcode	Semantics
    LDA addr	0001	AC <- M[addr]
    STA addr	0010	M[addr] <- AC
    ADD addr	0011	AC <- AC + M[addr]
    SUB addr	0100	AC <- AC - M[addr]
    AND addr	0101	AC <- AC & M[addr]
    JMP addr	0110	PC <- addr
    JZ addr	0111	if AC==0 PC <- addr
    HLT	1111	Halt

    Types: Memory-reference (LDA/STA), Arithmetic, Branch, Halt. Addressing: Direct (can extend to Immediate/Register).

    2. Datapath

    Registers: PC (8b), IR (16b: OP+ADDR), AR/MAR (8b), DR/MDR (16b), AC (16b), Status Z-flag.

    Components:

    • Memory (256x16b) - MAR selects, MDR buffers.
    • ALU (16b) - inputs AC + MDR, ops ADD/SUB/AND, output -> AC, sets Z.
    • Buses: Single internal bus or multiplexers connecting PC/IR/MAR/AC to memory/ALU.

    Interconnections:

    PC -> MUX -> MAR -> Memory -> MDR -\
    IR(Addr) -> MAR                       -> MUX -> ALU -> AC
    AC -> MDR -> Memory (store)           /
    MDR -> IR (fetch)
    PC+1 -> PC (incrementer)
    

    3. Control Unit - Microcoded/Hardwired FSM

    Fetch-Decode-Execute cycle (3-4 states):

    • T0 Fetch: MAR <- PC; MDR <- M[MAR]; IR <- MDR; PC++
    • T1 Decode: Decode IR[15:8] -> control signals; MAR <- IR[7:0]
    • T2 Execute:
      • LDA: MDR <- M[MAR]; AC <- MDR
      • STA: MDR <- AC; M[MAR] <- MDR
      • ADD: MDR <- M[MAR]; AC <- AC+MDR
      • JMP: PC <- MAR
      • JZ: if Z PC <- MAR

    Hardwired: State counter + PLA generates MemRead/Write, LoadPC/IR/MAR/MDR/AC, ALUop, BusSel.
    Microprogrammed: Control memory 16 microwords storing same signals, MPC steps.

    Diagram: Draw datapath with registers, ALU, memory, and control unit FSM outputting control lines.

    This minimal CPU demonstrates Von-Neumann fetch-execute, single-bus bottleneck, and can be extended to multi-cycle with GPRs and pipeline.

19. Q5b. Explain semiconductor memory organization with diagrams.20257m

    Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

    Explain semiconductor memory organization with diagrams.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Semiconductor Memory Organization

    Semiconductor memory (SRAM/DRAM, ROM) is built from arrays of cells organized to provide $2^{n}$ words of $m$ bits each. Access is by address decoding.

    1. Basic Cell

    • SRAM cell: 6T flip-flop (bistable), no refresh, fast, large.
    • DRAM cell: 1T + capacitor, needs refresh, dense.
    • ROM cell: mask transistor.

    2. Overall Organization Diagram

                             Address Bus A0..An-1
                                  |
                  +---------------v----------------+
                  |      Row Decoder (n/2 bits)    |
                  +---------------+----------------+
                                  | word lines (rows)
                   +--------------+--------------+
                   |   Memory Cell Array         |
                   |   ( 2^n rows x m columns )  |
                   |   each row = one word       |
                   +--------------+--------------+
                                  | bit lines (columns)
                  +---------------v----------------+
                  | Column Decoder / MUX +         |
                  | Sense Amplifiers + I/O Buffers|
                  +---------------+----------------+
                                  |
                              Data Bus D0..Dm-1
               CS (Chip Select), WE, OE , R/W
    

    For $1024 \times 8$ chip: 10 address lines ($2^{10}=1024$), 8 data lines.

    3. 2D Organization (Linear Decoding)

    • One decoder decodes all $n$ bits to select 1 of $2^{n}$ word lines directly.
    • Each word line enables $m$ cells forming a word.
    • Simple but decoder size grows exponentially (for 64K, 16-to-65536 decoder impossible).

    4. 2.5D / Coincident Decoding (Most common)

    Address split into Row + Column: e.g., 10 bits -> 5 row + 5 column.

    • Row decoder selects one of $32$ rows.
    • Column decoder selects one of $32$ columns via column MUX.
    • Only one cell at intersection selected per bit plane. Reduces decoder complexity.
    • 3D organization: Adds bit plane selection.

    Coincident decoding diagram:

     A0-A4 -> Row Decoder -> 32 word lines
     A5-A9 -> Column Decoder -> 32 column select
                    Array 32x32 per bit plane x 8 planes = 1024x8
    

    5. Building Larger Memories - Chip Organization

    Using $k \times m$ chips to make $K \times M$ memory:

    • Word expansion (depth): Use address MSB for chip select via decoder. e.g., Two $1K\times8$ -> $2K\times8$: A10 selects chip.
    • Bit expansion (width): Parallel chips share address, each provides part of word. e.g., Two $1K\times4$ -> $1K\times8$: data buses combined.

    Example: $4K\times8$ using $1K\times8$ chips:

     A0-A9 ----> all chips (address)
     A10-A11 -> 2-to-4 Decoder -> CS0,CS1,CS2,CS3 (one active)
     D0-D7 combined via tri-state buffers
    

    6. Control Signals

    • CS/CE: chip enable
    • OE: output enable
    • WE/R/W: read/write
    • Tri-state buffers isolate bus when not selected.

    This organization allows random access, high speed (SRAM 1-10ns, DRAM 50-70ns), and modular expansion by decoding.

20. Q6a. Explain I/O transfer techniques: program-controlled I/O, interrupt-driven I/O, and DMA.20257m

    Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

    Explain I/O transfer techniques: program-controlled I/O, interrupt-driven I/O, and DMA.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Solution - I/O Transfer Techniques

    Three modes by which CPU communicates with I/O devices:

    1. Program-Controlled I/O (Programmed I/O / Polling):

    • CPU directly controls transfer under program. CPU executes I/O instruction, checks (polls) device status register (Busy/Ready flag) in a loop and transfers data when ready.
    • Flow: CPU initiates I/O -> polls status -> if Ready, transfer 1 byte/word -> update count -> repeat.
    • Types: Synchronous and Asynchronous; Memory-mapped vs Isolated I/O.
    • Advantages: Simple hardware, no extra controller needed.
    • Disadvantages: CPU busy waiting (wastage), very slow for fast devices, throughput low. CPU cannot do other work.
    • Use: For slow devices like keyboard, or when data rate low.

    2. Interrupt-Driven I/O:

    • Removes polling waste. Device interrupts CPU only when ready to transfer.
    • Flow: CPU initiates I/O and continues other work. Device when ready sends Interrupt Request (INTR) -> CPU completes current instruction -> saves PC/PSW -> executes Interrupt Service Routine (ISR) to transfer data -> restores context (IRET).
    • Hardware: Requires Interrupt Controller (PIC e.g., 8259), interrupt vector table, enable/disable logic.
    • Advantages: CPU utilization improves drastically vs polling; suitable for handling multiple devices with priority.
    • Disadvantages: Still byte-by-byte transfer through CPU registers (CPU involved per word); context switch overhead per interrupt; not efficient for high-speed block transfers (disks).
    • Variants: Vectored vs Non-vectored, priority interrupts (daisy chain).

    3. Direct Memory Access (DMA):

    • For high-speed block transfers (disk, network), a dedicated DMA Controller (DMAC e.g., 8237) transfers data directly between I/O device and Memory, bypassing CPU.
    • Hardware: DMAC with registers: Address, Word Count, Control. Steals bus cycles via HOLD/HLDA (bus request/grant) or cycle stealing.
    • Flow:
      1. CPU programs DMAC: source/destination address, count, direction (Read/Write), mode.
      2. CPU executes other program; DMAC waits for DREQ from device.
      3. DMAC asserts HOLD -> CPU releases buses (HLDA).
      4. DMAC generates addresses and controls MEMRD/MEMWR + IOR/IOW to move block, decrements count until 0, then sends Terminal Count interrupt to CPU.
    • Modes: Burst (block) mode, Cycle Stealing (single word per time), Transparent mode.
    • Advantages: Fastest, CPU free during transfer (except cycle stealing), ideal for bulk data.
    • Disadvantages: Extra hardware controller, bus arbitration complexity, cache coherence issues.

    Comparison Table:

    Feature	Programmed I/O	Interrupt I/O	DMA
    CPU Involvement	Full polling	Per word via ISR	Only init & end
    Speed	Slowest	Medium	Fastest
    Hardware Cost	Lowest	Moderate	Highest
    CPU Utilization	Poor	Better	Best

    In modern systems all three co-exist: polling for simple status, interrupts for events, DMA for bulk transfers (with bus mastering and I/O processors/channels).

21. Q6b. Describe different types of interrupts: hardware, software, vectored, non-vectored, and exceptions.20257m

    Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

    Describe different types of interrupts: hardware, software, vectored, non-vectored, and exceptions.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Solution - Types of Interrupts

    An Interrupt is a signal that diverts CPU from normal execution to handle an urgent event, then resumes. Classified as:

    1. Hardware Interrupt (External):

    • Generated by external hardware devices (I/O, timer, power failure).
    • Asynchronous to program, via intr pins: INTR (maskable) and NMI (non-maskable) in 8086.
    • Requires hardware lines (INTR, INTA). Handled by PIC (8259).
    • Example: Keyboard press, timer tick, disk completion.

    2. Software Interrupt (Internal / Programmed):

    • Generated by executing an instruction, e.g., INT n (8086), SWI, SYSCALL.
    • Synchronous, intentional. Used to invoke OS services, BIOS calls, debugging.
    • Example: INT 21h DOS service, INT 10h video, INT 3 breakpoint. Not due to failure, is a trap for system call.

    3. Vectored Interrupt:

    • Device/interrupt source provides vector address (interrupt vector number). CPU uses vector to index Interrupt Vector Table (IVT) to find ISR address.
    • In 8086, IVT at 00000h has 256 vectors $\times$ 4 bytes; e.g., INT n vector = $n \times 4$.
    • Example: 8259 supplies vector for INTR; INT n is vectored. Fast response, prioritized.

    4. Non-Vectored Interrupt:

    • No vector supplied; CPU branches to a single fixed address for all such interrupts.
    • CPU must poll devices to identify source (software polling). Slower.
    • Example: Some systems where multiple devices share one interrupt line without vector encoder, or 8085's RST? Actually RST is vectored - classic example is polling-based interrupts where ISR polls each device status register.

    5. Exceptions:

    • Synchronous interrupts arising from CPU internal error conditions during instruction execution (often called traps/faults).
    • Subtypes:
      • Fault: Re-executable after handling (e.g., Page fault, divide by zero) - returns to faulting instruction.
      • Trap: Reported after instruction execution (e.g., overflow, breakpoint TRAP).
      • Abort: Severe unrecoverable error (e.g., machine check, double fault) - no precise return.
    • Examples: Divide by zero (#DE), General Protection Fault (#GP), Page Fault (#PF) in x86 protected mode, Undefined opcode, Overflow.
    • Exceptions are synchronous and often vectored (IDT vectors 0-31 reserved in x86).

    Additional Classification:

    • Maskable vs Non-Maskable: INTR can be disabled via IF flag; NMI cannot.
    • Priority: NMI > Exceptions > INTR.

    Handling Flow (x86-like): Finish current instruction -> push FLAGS, CS:IP -> clear IF/TF -> load CS:IP from vector table -> execute ISR -> IRET restores context.

22. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
23. Q7a. Explain the basic concepts of pipelining, including speedup and throughput. Discuss pipeline hazards.20257m

    Module 3: Pipelining

    Explain the basic concepts of pipelining, including speedup and throughput. Discuss pipeline hazards.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Pipelining - Basic Concepts

    Pipelining is an implementation technique where multiple instructions are overlapped in execution, like an assembly line. An $k$-stage pipeline divides instruction execution into $k$ stages (classic RISC: IF-ID-EX-MEM-WB) operating concurrently.

    Basic Operation

    Each stage has combinational logic + pipeline register/latch. Clock period $T_p = \max(T_{stage}) + T_{latch}$. While stage $i$ processes instruction $n$, stage $i-1$ processes $n+1$.

    For $k=4$, $n$ instructions: non-pipelined time $= n\cdot k\cdot T_p$, pipelined time $= (k+n-1)T_p$.

    Speedup

    $$S = \frac{T_{non-pipe}}{T_{pipe}} = \frac{n\cdot k}{k+n-1} \xrightarrow{n\gg k} k$$
    Ideal speedup = number of stages. With stage imbalance and latch overhead: $S = \frac{k\cdot T_{seq}}{T_p}$.

    Example $k=5$, $n=100$: $S = 500/104 \approx 4.8$.

    Efficiency $\eta = S/k$, Throughput $= n/(k+n-1)T_p \xrightarrow{n\to\infty} 1/T_p$ instructions/sec = $f_{clk}$ (one per cycle).

    Throughput

    Rate of instruction completion. Non-pipelined: $1/(kT_s)$, Pipelined (steady): $1/T_p$. Improvement factor same as speedup. Supercalar/superpipelined increase further.

    Pipeline Hazards - prevent next instruction from executing in next cycle

    1. Structural Hazards: Hardware resource conflict (e.g. single memory for IF+MEM, single ALU). Solution: Separate I/D caches (Harvard), duplicate units, stalling (bubble).

    2. Data Hazards: Dependency on previous result still in pipe.

    • RAW (true) ADD R1,R2,R3 followed by SUB R4,R1,R5 (R1 not written back)
    • WAR, WAW in out-of-order pipes.
      Solution: Forwarding/bypassing (EX→EX), compiler code scheduling, pipeline interlock + stall, register renaming.

    3. Control Hazards: Branch/jump changes PC, next fetched instructions wrong.

    • Unconditional: 1-cycle bubble
    • Conditional: taken/not-taken decision at EX/MEM → flush.
      Solutions: Stall/flush, branch prediction (static: not-taken/backward-taken; dynamic: 2-bit saturating counter, BTB), delayed branch (branch delay slot, predication), speculative execution.

    Additional classification Data hazards = load-use: LW R1,0(R2); ADD R3,R1,R4 requires 1 stall even with forwarding (mem latency).

    Performance impact: $CPI_{pipe}= CPI_{ideal} + stall_{structural}+stall_{data}+stall_{control}$ ; $CPI_{ideal}=1$.

    Ideal pipeline CPI=1, real $1.2\text{-}1.5$ due to hazards; longer pipe → higher hazard penalty.

    Diagram should show 5 stages overlapped in time (Gantt chart) and hazard bubble insertion.

24. Q7b. Describe parallel processors and the problem of cache coherency in shared memory systems.20257m

    Module 3: Pipelining

    Describe parallel processors and the problem of cache coherency in shared memory systems.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Parallel Processors

    Parallel processors execute multiple operations concurrently to increase throughput. Classified by Flynn's taxonomy:

    • SISD: Single Instruction Single Data - conventional uniprocessor.
    • SIMD: Single Instruction Multiple Data - array/vector processors, e.g., GPU, vector supercomputer.
    • MISD: Multiple Instruction Single Data - rare, pipelined architectures.
    • MIMD: Multiple Instruction Multiple Data - most parallel computers. Two models:
      1. Shared Memory (Tightly coupled): All processors share a common main memory via interconnection network (bus, crossbar, multistage). Sub-types: UMA (uniform memory access / SMP) - equal access time; NUMA - distributed shared memory, non-uniform latency; COMA/COMA.
      2. Distributed Memory (Loosely coupled): Each processor has private memory, communicates via message passing.
    • Multicore / Multiprocessor: Modern CMPs are MIMD shared-memory on single chip.

    Parallelism levels: Job-level, task-level, instruction-level and loop-level.

    Cache Coherency Problem in Shared Memory

    In shared-memory MIMD, each processor has private cache for latency reduction. Coherency problem: If multiple caches hold a copy of same memory block $X$, and one processor writes $X$, other copies become stale, leading to inconsistent views.

    Example: $P_1$ and $P_2$ cache $X=5$. $P_1$ does $X \leftarrow 10$ in its cache, $P_2$ still sees $X=5$. Memory may be 5 or 10 depending on write-through/write-back - inconsistency.

    Coherence requires: (1) Writes to same location seen in same order by all processors (write serialization), (2) Read returns last written value.

    Solutions:

    1. Snooping (Snoopy) Protocol - for bus-based SMPs: Every cache monitors (snoops) bus transactions.

       • Write-Invalidate: On write hit, processor broadcasts invalidate to all other caches holding block. Others discard copy. Most common (MESI/MOESI).
       • Write-Update (Write-Broadcast): Write is broadcast to update all copies.

    2. Directory-Based Protocol - for scalable networks / NUMA: Central directory keeps state of each block (which caches have copy, dirty/clean). On write, directory sends point-to-point invalidates only to holders. Avoids broadcast overhead.

    3. MESI States (Illinois Protocol):

       • M (Modified): Dirty, exclusive.
       • E (Exclusive): Clean, exclusive.
       • S (Shared): Clean, may be shared.
       • I (Invalid): Not valid.

    On Read Miss → BusRd, on Write → BusRdX / BusUpgr, state transitions enforce coherence.

    Coherence is handled in hardware; software must ensure consistency model (sequential consistency, etc.).

25. Q8a. Explain cache memory organization. Discuss mapping techniques (direct, associative, set-associative), replacement algorithms, and write policies.20257m

    Module 4: Memory Organization

    Explain cache memory organization. Discuss mapping techniques (direct, associative, set-associative), replacement algorithms, and write policies.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Cache Memory Organization (7 Marks)

    1. Introduction:
    Cache is a small, very fast SRAM between CPU and main memory that exploits locality of reference (temporal & spatial) to reduce average access time. CPU first checks cache; on hit data returned quickly, on miss block fetched from main memory.

    Hierarchy: CPU ↔ L1 ↔ L2 ↔ Main Memory ↔ Disk. Cache stores blocks/lines consisting of tag + data block + valid/dirty bits.

    2. Mapping Techniques:
    Mapping determines where a main memory block can be placed in cache.

    a) Direct Mapping:
    Each memory block $j$ maps to exactly one cache line: Cache Line = j mod m where $m$ = number of lines. Address split: | Tag | Line | Word |.

    • Advantage: Simple hardware, low cost, fast lookup.
    • Disadvantage: High conflict misses – two blocks mapping to same line thrash even if other lines empty. Hit ratio lower.

    b) Fully Associative Mapping:
    Any block can go into any line. Address split: | Tag | Word |. Tag compared associatively with all line tags in parallel.

    • Advantage: Most flexible, minimum conflict misses, best hit ratio.
    • Disadvantage: Expensive – requires associative CAM comparator for every line, slow for large cache.

    c) k-Way Set-Associative Mapping: Compromise.
    Cache divided into $v = m/k$ sets, each set has $k$ lines. Block $j$ maps to Set = j mod v, can occupy any of $k$ lines within that set. Address split: | Tag | Set | Word |.
    Example: 2-way, 4-way. Direct ($k=1$) and Fully Associative ($k=m$) are extremes.

    • Advantage: Reduces conflicts while keeping hardware manageable. Widely used (e.g., Intel uses 8-way/16-way).
    • Disadvantage: Moderate hardware complexity.

    3. Replacement Algorithms (needed when set is full):

    • LRU (Least Recently Used): Replaces block not used longest time. Best hit ratio, implemented via counters/stack. Common.
    • FIFO: Replaces first-loaded block. Simple but not optimal, suffers Belady effect.
    • LFU: Replaces least frequently used.
    • Random: Random selection, simple hardware, average performance.

    4. Write Policies (on write hit):

    • Write-Through: Data written to both cache and main memory simultaneously. Simple, consistent but high bus traffic. Uses write buffer.
    • Write-Back (Copy-Back): Write only to cache and set dirty bit. Block written back to memory only on replacement. Less traffic, better performance but coherence complex.
    • On write miss: Write-Allocate (fetch block to cache then write) vs No-Write-Allocate (write directly to memory).

    Performance: $T_{avg}=h \cdot T_c + (1-h)\cdot T_m$ where $h$=hit rate.

26. Q8b. Explain signed number representation using sign-magnitude, 1's complement, and 2's complement. Include advantages and disadvantages of each.20257m

    Module 1: Functional Block of computer and Data representaion

    Explain signed number representation using sign-magnitude, 1's complement, and 2's complement. Include advantages and disadvantages of each.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Signed Number Representation – Sign-Magnitude, 1's and 2's Complement (7 Marks)

    For $n$ bits, MSB is sign bit: $0$=+ve, $1$=-ve.

    1. Sign-Magnitude:
    MSB = sign, remaining $(n-1)$ bits = magnitude.
    Example $n=4$: $+3=0\,011$, $-3=1\,011$
    Range: $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$. Zero has two forms: $0\,000$ (+0) and $1\,000$ (-0).

    • Advantages: Simple for humans, easy to find magnitude.
    • Disadvantages: Two zeros, addition/subtraction needs separate logic checking signs and magnitudes (complex ALU), not used internally.

    2. 1's Complement:
    +ve numbers as in sign-magnitude; -ve numbers obtained by complementing all bits of +ve.
    Example $n=8$: $+25=00011001$, $-25=11100110$
    Range: $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$, two zeros: $00000000$ and $11111111$.
    Addition: binary add, then end-around carry (carry out added back to LSB).

    • Advantages: Subtraction via addition, better than sign-magnitude.
    • Disadvantages: Two zeros, end-around carry makes arithmetic slower, extra circuitry.

    3. 2's Complement:
    +ve as usual; -ve = 1's complement +1.
    Example $n=8$: $+25=00011001$, $-25=11100110+1=11100111$
    Range: $-2^{n-1}$ to $+(2^{n-1}-1)$ (one extra negative value, e.g., 8-bit $-128$ to $+127$). Single zero $00000000$.
    Addition/Subtraction: simple binary addition, ignore carry out beyond $n$ bits. Subtraction $A-B = A + (-B)_{2's}$.
    Example $5-3 = 0101 + 1101 = 0010$ (2) correct (carry discarded).

    • Advantages: One zero, simplest arithmetic (single adder for add/sub), no end-around carry, widely used in modern ALUs (x86, ARM).
    • Disadvantages: Asymmetric range, human interpretation slightly less intuitive, negation needs add.

    Comparison Table:

    Feature	Sign-Mag	1's Comp	2's Comp
    Zeros	2	2	1
    Range (8-bit)	-127 to +127	-127 to +127	-128 to +127
    Arithmetic	complex	end-around carry	simple add

    Conclusion: 2's complement dominates due to uniform add/sub hardware.

27. Q9a. Explain the organization of semiconductor memories such as SRAM and DRAM. Discuss refresh cycles, access times, and their applications.20257m

    Module 2: x86 Architecture, CPU Control, I/O, Memory System Design

    Explain the organization of semiconductor memories such as SRAM and DRAM. Discuss refresh cycles, access times, and their applications.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Organization of SRAM and DRAM [7M]

    Semiconductor main memory built from MOS cells.

    1. SRAM Cell (Static RAM):

    • Cell: 6-transistor (6T) flip-flop - 4 transistors form cross-coupled inverters (latch) + 2 access transistors, or 4T + 2 resistors. Stores bit as long as power on - no refresh.
    • Operation: Word line (WL) enables access transistor, bit lines $B$ and $\bar{B}$ read/write differentially. Sense amplifier detects small swing.
    • Organization: Array of $m \times n$ cells with row decoder, column decoder/mux, sense amps. Example 1Kx8 chip: 32x32 array, 5-bit row decode, 5-bit column.
    • Characteristics: Access time 1-10 ns (cache speed), density low (6T area large), cost high, power moderate (static + dynamic). No refresh logic.

    2. DRAM Cell (Dynamic RAM):

    • Cell: 1 Transistor + 1 Capacitor (1T1C). Capacitor stores charge (charged=1, discharged=0). Transistor acts as switch to bitline.
    • Destructive read: Reading discharges capacitor onto bitline; data must be written back (restore) via sense amp (which also acts as latch). Charge leaks within ms -> refresh needed.
    • Organization: Folded bitline architecture; rows called pages. Access: RAS (row address) latches row into row buffer (sense amps), CAS selects column. Burst mode.
    • Refresh: Each row must be refreshed every $t_{REF}$ typically 64ms. Refresh is RAS-only cycle reading row and restoring. Controller does distributed refresh: e.g. 8192 rows /64ms => one row every $7.8\mu s$ . Overhead ~1-2% bandwidth. Variations: Burst, distributed, hidden refresh.
    • Characteristics: Access time 40-70 ns, cycle time longer due to precharge, but density high (1T vs 6T), cost per bit 1/8th of SRAM, low power per bit, needs refresh + precharge overhead.

    3. Chip Organization Example:

    Build larger memory from chips: $n$ chips in parallel for word width, address decoding across chips. e.g. To make $16K \times 8$ from $4K \times8$ chips, need 4 chips, 2-bit chip-select decode from $A_{12},A_{13}$.

    Internal: $2^k$ words, $w$ bits: decoder $k \to 2^k$, array $2^k \times w$.

    Modern DDR SDRAM: Banks (4-16) -> each bank is DRAM array with row buffer; interleaving across banks hides precharge. Synchronous burst: access time defined as $CL$ (CAS latency).

    4. Comparison:

    Feature	SRAM	DRAM
    Cell	6T latch	1T1C capacitor
    Density	Low	High (4-8x)
    Access	1-10 ns, no refresh	50 ns + refresh, slower
    Refresh	No	Yes ~64ms
    Cost/bit	High	Low
    Use	Cache (L1/L2/L3), register file	Main memory (DIMMs), frame buffer
    Power	High leakage	Low per bit, refresh power

    System: SRAM for cache where speed matters, DRAM for main memory where capacity/cost matters. Emerging: SRAM+DRAM+3D stacked (HBM).

28. Q9b. Discuss memory hierarchy design principles. Explain how access time, cost, and size influence memory organization.20257m

    Module 4: Memory Organization

    Discuss memory hierarchy design principles. Explain how access time, cost, and size influence memory organization.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Memory Hierarchy Design Principles [7M]

    Why hierarchy? No single technology gives simultaneously large capacity + low cost + high speed. Hierarchy combines multiple levels giving illusion of large fast cheap memory by exploiting locality of reference.

    Levels (pyramid top=fast):

    Registers (32-64 words, 0.5 ns, highest cost/bit)
       |
    Cache L1/L2/L3 (SRAM, KB-MB, 1-10 ns)
       |
    Main Memory (DRAM, GB, 50-70 ns)
       |
    Secondary (SSD/HDD, TB, 0.1-10 ms)
       |
    Tertiary (Tape/Cloud, PB, seconds)
    

    Design Principles:

    1. Inclusiveness & Locality:
    Upper levels store subset (copy) of lower level working set. Temporal locality -> reuse in cache; spatial locality -> block size >1 word (cache line 64B, page 4KB, disk block 4KB). Hit ratio $h \approx 0.95+$ needed for effectiveness.

    2. Cost-Performance Tradeoff:
    Cost/bit decreases downwards, Access time increases. Average cost/bit:
    $$C_{avg} = \frac{\sum C_i S_i}{\sum S_i}$$
    Dominated by cheap large lower level, while average access time dominated by fast upper level if $h$ high:
    $$T_{eff} = h \cdot T_{L1} + (1-h)(T_{L1}+T_{L2}) \approx h T_1 + (1-h)T_2$$
    For memory hierarchy: $T_{eff}= h \cdot 5ns + (1-h)\cdot 70ns$. With $h=0.95$, $T_{eff}=8.25ns$ ~ Cache speed but capacity ~RAM.

    3. Size vs Time vs Cost:

    • Faster -> Smaller (SRAM 6T cell area >> DRAM 1T, register file tiny)
    • Larger -> Slower (address decode delay, physical distance)
    • Cheaper -> Larger (DRAM $0.01/GB$ vs SRAM $1/GB$). Hierarchy picks sweet spot at each point.

    4. Block Replacement & Mapping:
    Direct/associative mapping, write-through/write-back, LRU replacement, demand paging - all to approximate optimal (Belady) with minimal overhead.

    5. Policies:

    • Access locality principle: $90/10$ rule.
    • Consistency: Write policies keep levels coherent.
    • VM: Page tables allow hierarchy to appear as linear address space.

    Influence on Organization:

    • Cache size tradeoff: Too small -> low hit rate, too large -> slower hit time (increases $T_1$) and higher cost. Optimum ~32KB L1, 256KB L2.
    • Main memory sized to hold working sets of multiprogrammed processes: $Size \gg \sum W_i$ to avoid thrashing.
    • Use interleaving/banking and wide buses to match bandwidth between levels (e.g. 64B cache line burst from DRAM).

    Example: Evolution from 1980: No cache -> 1-level -> 3-level + TLB hierarchy improved effective CPI from ~10 to ~1 despite 100x gap between CPU and DRAM.

    Conclusion: Hierarchy succeeds because $T_{eff} \approx T_{fast}$ if locality holds, while $C_{eff} \approx C_{slow}$, bridging technology gap.