2024 question paper

COMPUTER ORGANIZATION & ARCHITECTURE

26 questions

1. Q1(a). What is the first step in the instruction execution cycle? (i) Decode (ii) Fetch (iii) Execute (iv) Store20242m

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

   What is the first step in the instruction execution cycle?
   (i) Decode
   (ii) Fetch
   (iii) Execute
   (iv) Store

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) Fetch

   Instruction execution cycle: Fetch → Decode → Fetch Operands → Execute → Write Back/Store. First step is Fetch where PC is placed in MAR, instruction fetched from memory to MDR/IR and PC incremented.

2. Q1(b). What is the advantage of carry look-ahead adders over ripple carry adders? i) Simplicity in design ii) Increased latency iii) Reduced power consumption iv) Faster addition by reducing carry propagation delay20242m

   Module 1: Functional Block of computer and Data representaion

   What is the advantage of carry look-ahead adders over ripple carry adders?
   i) Simplicity in design
   ii) Increased latency
   iii) Reduced power consumption
   iv) Faster addition by reducing carry propagation delay

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) Faster addition by reducing carry propagation delay

   Carry Look-Ahead Adder (CLA) generates carries in parallel using generate (G) and propagate (P) signals, avoiding ripple delay. Trade-off: more complex hardware but faster. Not simpler or lower power.

3. Q1(c). Which type of control unit is faster but more difficult to modify? i) Hardwired Control Unit ii) Microprogrammed Control Unit iii) Cache Control Unit iv) Memory Management Unit20242m

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

   Which type of control unit is faster but more difficult to modify?
   i) Hardwired Control Unit
   ii) Microprogrammed Control Unit
   iii) Cache Control Unit
   iv) Memory Management Unit

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) Hardwired Control Unit

   Explanation:

   • Hardwired CU uses combinational circuits (AND, OR, gates, decoders) to generate control signals. It is fast because signals propagate through hardware without memory access.
   • Disadvantage: Difficult to modify or add new instructions - requires redesign of wiring.
   • Microprogrammed CU uses control store (microprogram) - slower (microinstructions fetch) but flexible/easy to modify.
   • Cache Control Unit and MMU are not types of CPU control unit.

   Hence faster but inflexible = Hardwired CU.

4. Q1(d). Which of the following I/O transfer methods involves the CPU polling the device until data is read? i) DMA ii) Interrupt-driven I/O iii) Program-controlled I/O iv) Asynchronous I/O20242m

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

   Which of the following I/O transfer methods involves the CPU polling the device until data is read?
   i) DMA
   ii) Interrupt-driven I/O
   iii) Program-controlled I/O
   iv) Asynchronous I/O

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Program-controlled I/O (Programmed I/O)

   Explanation:

   • Programmed / Program-controlled I/O: CPU continuously polls status register (busy/done bit) in a loop until device is ready, then transfers data. Wastes CPU cycles (busy-waiting).
   • Interrupt-driven I/O: Device interrupts CPU only when ready - no polling.
   • DMA: Direct transfer between memory & device by DMA controller without CPU polling/intervention.
   • Asynchronous I/O: Overlapped/non-blocking operation, not polling.

   Hence CPU polling = Programmed I/O.

5. Q1(e). What does a branch prediction mechanism in a CPU help reduce? a) Data hazards b) Control hazards c) Structural hazards d) Clock cycle delays20242m

   Module 3: Pipelining

   What does a branch prediction mechanism in a CPU help reduce?
   a) Data hazards
   b) Control hazards
   c) Structural hazards
   d) Clock cycle delays

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: b) Control hazards

   Explanation:

   • Control hazard occurs due to branch instructions (conditional/unconditional) where next PC is unknown until decode/execute; pipeline must stall/flush.
   • Branch prediction predicts taken/not-taken and target address to fetch next instruction speculatively, reducing stalls/flushes.
   • Data hazards are handled by forwarding/bypassing, stalling, instruction scheduling.
   • Structural hazards handled by resource duplication/pipelining.

   Hence branch prediction primarily reduces control hazards.

6. Q1(f). Which of the following is *NOT* a type of parallel processor architecture? a) SIMD b) MIMD c) SISO d) Multi-core20242m

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

   Which of the following is NOT a type of parallel processor architecture?
   a) SIMD
   b) MIMD
   c) SISO
   d) Multi-core

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: c) SISO

   Explanation:
   Standard Flynn + modern parallel architectures:

   • SIMD - Single Instruction Multiple Data - vector/GPU - valid parallel architecture.
   • MIMD - Multiple Instruction Multiple Data - multicore/multiprocessor - valid.
   • Multi-core - multiple cores on one chip - valid parallel processor.
   • SISO - Single Instruction Single Operand is not a standard taxonomy term (Flynn uses SISD - Single Instruction Single Data); SISO is distracter/incorrect.

   Hence NOT a parallel processor architecture = SISO.

7. Q1(g). Which cache replacement algorithm removes the least recently used block. (i) FIFO (ii) LRU (iii) Random Replacement20242m

   Module 4: Memory Organization

   Which cache replacement algorithm removes the least recently used block.
   (i) FIFO
   (ii) LRU
   (iii) Random Replacement

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) LRU

   Explanation:

   • LRU (Least Recently Used): Evicts block that has not been referenced for longest time - exploits temporal locality; needs timestamp/counter/stack.
   • FIFO: Evicts oldest inserted block regardless of recent use.
   • Random Replacement: Random victim - simple hardware.

   LRU gives best hit rate among three but most complex to implement.

8. Q1(h). Which technique is used to handle data hazards in pipelining? a) Increasing memory size b) Instruction scheduling c) Parallel processing d) Increasing clock speed20242m

   Module 3: Pipelining

   Which technique is used to handle data hazards in pipelining?
   a) Increasing memory size
   b) Instruction scheduling
   c) Parallel processing
   d) Increasing clock speed

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: b) Instruction scheduling

   Explanation:

   • Data hazards (RAW, etc.) handled by:
     • Data forwarding/bypassing
     • Instruction scheduling / reordering (compiler or hardware - out-of-order execution) to insert independent instructions between dependent ones
     • Stalling (NOP insertion)
   • Increasing memory size, parallel processing, or clock speed do not resolve data dependencies.

   Hence among options, Instruction scheduling is the technique.

9. Q1(i). __________________ Addressing mode directly specifies the operand within the instruction. i. Direct addressing ii. Indirect addressing iii. Immediate addressing iv. Indexed addressing20242m

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

   __________________ Addressing mode directly specifies the operand within the instruction.
   i. Direct addressing
   ii. Indirect addressing
   iii. Immediate addressing
   iv. Indexed addressing

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: iii. Immediate addressing

   Explanation:

   • Immediate addressing: Operand value itself is encoded within instruction (e.g., MOV AX, 5, ADD #5,R1). No memory access needed.
   • Direct addressing: Instruction holds address of operand in memory.
   • Indirect addressing: Instruction holds address of address.
   • Indexed addressing: Address = base + index register.

   Hence directly specifies operand = Immediate.

10. Q1(j). A computer with 32-bit wide data bus uses 1K, X, and 8 static RAM memory chips. What is the smallest memory that this computer has? a) 12K b) 10K c) 8K d) 16K e) 24K20242m

    Module 4: Memory Organization

    A computer with 32-bit wide data bus uses 1K, X, and 8 static RAM memory chips.
    What is the smallest memory that this computer has?
    a) 12K
    b) 10K
    c) 8K
    d) 16K
    e) 24K

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: Theoretically 4K bytes (4 chips) → among given options (c) 8K is closest listed; ideal answer 4K

    Explanation:
    Chip: $1K \times 8$ bit = 1KB, 8-bit wide.
    CPU bus: 32-bit wide → need $32/8 = 4$ chips in parallel per word to match width.

    • One row (4 chips): $1K \times 32$ bit = 4KB
    • This is smallest feasible memory (must be multiple of 4 chips to fill bus).

    Given options list 12K/10K/8K/16K/24K (no 4K), the smallest listed option that satisfies 4-chip grouping and is ≥4K is c) 8K (2 rows of 4 chips = 8KB). If 4K were listed it would be exact answer. Some textbooks directly answer 4K for this configuration.

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. Q2(a). Describe the instruction execution cycle in a CPU. Explain some key features of the x86 architecture20247m

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

    Describe the instruction execution cycle in a CPU. Explain some key features of the x86 architecture

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Instruction Execution Cycle & x86 Features (7M)

    A) Instruction Execution Cycle (Instruction Cycle)

    Each instruction goes through sequence called Instruction Cycle controlled by CU.

    Start -> Fetch -> Decode -> (Operand Fetch) -> Execute -> Writeback -> Interrupt Check -> Next
    

    1. Fetch Cycle (IF):

    • PC holds address of next instruction. MAR <- PC, PC++ (PC = PC + instruction_length). Memory read MDR <- Memory[MAR]; IR <- MDR. Fetch brings opcode + operands. Also increment IC.

    2. Decode Cycle (ID):

    • CU decodes opcode in IR via decoder, identifies instruction type, addressing mode, operand locations. Generates control signals. For microprogrammed CU, fetches micro-routine.

    3. Operand Fetch / Effective Address Calculation:

    • If instruction uses memory operand: Compute EA = Base + Index*Scale + Displacement using ALU. For x86: EA = EBX + ESI*4 + 0x10. Fetch operand Operand <- Memory[EA] or Register.

    4. Execute Cycle (EX):

    • ALU performs operation. Examples: ADD AX,BX => AX <- AX+BX sets FLAGS; JMP => PC <- target; LOAD => etc. Takes 1 to many cycles depending on complexity (mul/div = multiple cycles).

    5. Store / Write Back:

    • Result written to destination (Register or Memory). Memory[EA] <- AC or Reg <- Result. Flags updated (ZF,SF,CF,OF).

    6. Interrupt Check:

    • After each instruction, CU checks INTR, NMI. If asserted and enabled, save PC/PSW to stack and branch to ISR vector.

    States:

    Non-interrupt : FETCH -> INDIRECT (if indirect addr) -> EXECUTE
    Interrupt     : ... EXECUTE -> INTERRUPT (save PC, PC <- vector)
    

    Machine Cycle vs State: Each phase may take multiple clock states (T1-T4). e.g., 8086 MOV AX, [BX] = 4 clocks fetch + 6 clocks EA + memory read.

    Example - ADD AX, [3000H] on hypothetical CPU:
    T1: MAR<-PC, T2: MDR<-Mem, IR<-MDR, PC++
T3: Decode ADD, MAR<-3000H
T4: MDR<-Mem[3000H], TMP<-MDR
T5: AC<-AX+TMP, FLAGS update, AX<-AC

    B) Key Features of x86 Architecture

    x86 (8086 family, IA-32, x86-64) is CISC:

    1. Register Organization: 8086: 4 GPR AX,BX,CX,DX (each 16b, divisible into AH/AL), 4 index/pointer SP,BP,SI,DI, 4 segment registers CS,DS,SS,ES, IP, FLAGS. IA-32 adds 32-bit EAX-EDI, ESI, EIP; x86-64 adds RAX-R15 (64-bit) + 16 XMM/YMM.

    2. Segmentation & Memory Addressing: Real Mode: Physical addr = Segment*16 + Offset (20-bit via overlapping segments, 1MB). Protected Mode (80286+): Segment selector + descriptor table (GDT/LDT) giving base, limit, protection. Paging (80386+): 2-level paging to 4KB pages.

    3. CISC Instruction Set: Variable length 1-15 bytes, many addressing modes (register, immediate, direct, register indirect, based, indexed, based-indexed with displacement), ~ 1000 opcodes (string: MOVS, REP). Complex instructions: REP MOVSB, ENTER.

    4. Arithmetic Capabilities: Support for 8/16/32/64-bit, BCD (DAA/DAS), floating point via separate x87 FPU stack (ST0-ST7, 80-bit extended), later SSE/AVX for SIMD.

    5. Modes of Operation:

       • Real Mode (8086 compatible)
       • Protected Mode (multitasking, privilege levels Ring 0-3, virtual memory)
       • Virtual 8086 Mode
       • System Management Mode (SMM)
       • Long Mode (x86-64, 64-bit)

    6. Little-Endian: Lower address stores LSB.

    7. Stack Support: Hardware stack via SS:SP with PUSH/POP, CALL/RET.

    8. Interrupt Architecture: 256 vectored interrupts (0-255), INTR (maskable), NMI, Exception handling, IDT.

    9. Backward Compatibility: All x86 generations run 8086 code; extensions via CPUID.

    10. Extensions: MMX, SSE/SSE2/SSE4, AVX/AVX512 (SIMD for multimedia), Virtualization (VT-x), 64-bit extension (AMD64).

    Comparison: Vs RISC: higher code density, but complex decode -> micro-ops translation to RISC-like internally (since Pentium Pro) for pipelined execution.

13. Q2(b). Explain different addressing modes in a CPU with an example.20247m

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

    Explain different addressing modes in a CPU with an example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Addressing Modes with Examples (7M)

    Definition: Addressing mode specifies rule for calculating Effective Address (EA) or operand location. Field A in instruction does not always equal EA; mode bits tell CPU how to interpret it.

    General equation: EA = Base + Index * Scale + Displacement + PC-relative, value loaded accordingly.

    Why x86 has many modes? To support arrays, pointers, stack, constants efficiently.

    1. Immediate Mode

    Operand itself in instruction. EA not needed.
    Op = A

    Example: MOV AX, 1234H ; ADD R1, #10 -> Instruction contains 00001010.
    Use: Constants. Fast, no memory extra fetch beyond instruction.

    2. Register Mode (Register Direct)

    Operand in register R. EA is register ID, not memory.

    Example: MOV AX, BX ; ADD R1, R2 => R1 = R1 + R2
    Fastest (internal), used heavily in load-store architecture.

    3. Direct / Absolute Mode

    Instruction contains memory address A directly.

    Example: LDA 2500H => AC = Mem[2500H] or MOV AX, [2000H]
EA = A

    Need large address field (16/32 bit), inflexible if code relocates.

    4. Indirect Mode

    Address field points to memory location that contains EA. Extra memory access.

    Example: MOV AX, [BX] where BX holds pointer? Actually register indirect below; true indirect: Instruction @ 100: 500; Mem[500] = 800 => operand = Mem[800]
    Often: LDA @ 1000H -> Fetch address at 1000H, then fetch operand.
    EA = Mem[A]

    Rare directly due to extra fetch; used for pointers where pointer address known.

    5. Register Indirect Mode

    Pointer in register points to memory operand.

    Example:

    • MOV AX, [BX] => AX = Mem[BX] (BX=1000H => load from DS:1000H)
    • LDA (R1) with R1=0x2000 => operand at 0x2000
EA = (R)

    Powerful for array traversal: increment R per iteration.

    6. Indexed Mode

    EA = R + X where X is index register or immediate offset. Two variants:

    • Based / Register + Displacement: MOV AX, [BX+10H] => EA = BX + 10H
    • Indexed: MOV AX, [SI+20H]

    Use: Array access A[i] = Base + i. Example: Array at 2000H, element 3 (2 bytes each): MOV SI, 6 ; MOV AX, [2000H+SI]

    • Auto-increment / Auto-decrement (special): After access, R = R ± size. Example: MOV AX, [SI++] (68000 (A0)+) for stack/queue.

    7. Base-Indexed Mode

    Combination of two registers + displacement, favored by x86.

    Example: MOV AX, [BX+SI+100H] or in 32-bit: MOV EAX, [EBX+ESI*4+8]

    Base = BX/BP, Index = SI/DI. EA = Base + Index + Displacement

    Use: 2D array A[i][j] where Base = row base, Index = col offset or accessing struct fields where BX = struct base, SI = field index.

    8. Scaled Indexed Mode (x86)

    EA = Base + Index*Scale + Disp where Scale = 1,2,4,8 (size of element).

    Example: MOV EAX, [EBX + ECX*4 + 0x10] (ECX = array index, each element 4 bytes, 0x10 = header offset). Common in IA-32 SIB byte.

    9. Relative / PC-Relative Mode

    EA = PC + Displacement.

    Example: JMP Label where Label at PC + 20 ; Branch BEQ -4 ; CALL PC+8

    Use: Position-independent code (PIC), branches. Displacement is signed 8/16-bit.

    10. Implied / Stack Mode

    Operand implicitly implied (not in field). Stack pointer assumed.

    Example: PUSH AX => SP--, Mem[SP]=AX; POP AX; CLC (Clear Carry - implied flag). Zero-address instruction ADD in stack machine pops two, pushes result.

    11. Input/Output Mode

    Special for I/O mapped: IN AL, 40H ; OUT 40H, AL (immediate port address or via DX).

    Summary Table for Exam (Draw this)

    Mode	Formula	Example (8086)	Effective Address
    Immediate	Op=A	MOV AX, 5	-
    Register	Op=R	MOV AX, BX	-
    Direct	EA=A	MOV AX, [1000H]	1000H
    Reg Indirect	EA=(R)	MOV AX, [BX]	(BX)
    Indexed+Disp	EA=R+Disp	MOV AX, [SI+8]	SI+8
    Based Indexed	EA=Base+Index	MOV AX, [BX+SI]	BX+SI
    Based Indexed +Disp	EA=Base+Idx+Disp	MOV AX, [BX+SI+100H]	BX+SI+100H
    Scaled	EA=Base+Idx*S+Disp	MOV EAX,[EBX+ECX*4]	EBX+ECX*4
    Relative	EA=PC+Disp	JMP +20	PC+20

    Selection Criteria: Instruction frequency, address space size, supporting high-level constructs (array, struct, pointer), code density. Modern RISC uses few modes (Register, Immediate, Indexed) for simpler decode; CISC offers many for compactness.

14. Q3(a). Explain the Addition and Subtraction Algorithm with the help of flowchart.20242m

    Module 1: Functional Block of computer and Data representaion

    Explain the Addition and Subtraction Algorithm with the help of flowchart.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Addition / Subtraction Algorithm (Binary, 2's complement) – Flowchart

    Uses registers: $A$ (accumulator), $B$, $Q$? For simple $A \pm B$.

    Algorithm:

    1. For addition: $A \leftarrow A + B$ using binary adder.
    2. For subtraction: $A \leftarrow A - B = A + (\bar{B}+1)$ (2's complement of B).
    3. Detect overflow: $V = C_{n} \oplus C_{n-1}$ (carry into sign xor carry out of sign).

    Flowchart (Text)

               START
                 |
                 v
         +-----------------+
         | Load A = Augend |  
         |      B = Addend |
         +--------+--------+
                  |
         +--------v--------+
         | Operation?      |---- SUB ----> B = ~B + 1 (2's comp)
         | ADD / SUB       |              (or SUB = ADD with Cin=1)
         +--------+--------+
                  | ADD
                  v
         +-----------------+
         | A = A + B       |
         | (parallel adder)|
         +--------+--------+
                  |
         +--------v--------+
         | Overflow?       |--- Yes ---> Set V=1, Trap/Indicate
         | V = Cn xor Cn-1 |
         +--------+--------+
                  | No
                  v
         +-----------------+
         | Result in A,    |
         | Carry C, V flag |
         +--------+--------+
                  |
                 END
    

    Detailed Step for Subtraction via Adder

    SUB:  B' = NOT B
          Cin = 1
          Sum = A + B' + Cin
    Equivalent to A + (2's complement of B)
    

    4-bit Example

    $A=0101 (+5)$, $B=0011 (+3)$

    • ADD: $0101+0011=1000$ (8, overflow if signed 4-bit? $V=1$ because positive+positive=negative)
    • SUB: $A-B =0101 +1101 =0010$ (+2) ($1101$ is -3)

    Hardware: Uses $n$-bit parallel adder (ripple/CLA) with XOR gates on $B$ controlled by $SUB$ signal: $B_i \oplus SUB$, $Cin=SUB$.

    Overflow logic: If $A_{n-1}, B_{n-1}$ same and $Sum_{n-1}$ different → overflow.

    For magnitude (sign-magnitude) algorithm, extra step compares signs and magnitudes, but 2's complement above is standard in ALU.

15. Q3(b). What is a *carry-look ahead* adder? Draw the circuit of an 8-bit carry-look ahead adder using a *1-bit carry look ahead adder*.20247m

    Module 1: Functional Block of computer and Data representaion

    What is a carry-look ahead adder? Draw the circuit of an 8-bit carry-look ahead adder using a 1-bit carry look ahead adder.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Carry Look-Ahead Adder (CLA)

    Problem with Ripple Carry Adder (RCA): $C_{i+1}= G_i + P_i C_i$ propagates sequentially → delay $O(n)$ (≈ $2n$ gate delays for $n$ bits).

    CLA solves by computing all carries in parallel using Generate ($G$) and Propagate ($P$).

    For each bit $i$:

    • $G_i = A_i \cdot B_i$ (generate – carry created)
    • $P_i = A_i \oplus B_i$ (propagate – carry passed; some use $A_i+B_i$)
    • $Sum_i = P_i \oplus C_i$
    • $C_{i+1}= G_i + P_i C_i$

    Expanding:

    • $C_1 = G_0 + P_0 C_0$
    • $C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0$
    • $C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$
    • $C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$

    All $C_i$ after 2 levels of AND-OR, independent of ripple.

    1-bit CLA slice

    A_i --+--\
          |   XOR --> P_i ----+--> XOR --> Sum_i
    B_i --+--/   AND --> G_i -+      ^ 
                         |          C_i
    

    Carry look-ahead logic block generates $C_{i+1}$ from $G_i, P_i, C_i$.

    4-bit CLA Block (with group GG, GP)

            +-----------------------------------+
    C0 ---> | CLA Logic | ---> C1 C2 C3 C4      |
    A3-0 B3-0 -> P3-0 G3-0                       |
            +-----------------------------------+
             P* = P3 P2 P1 P0
             G* = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0
    

    8-bit CLA using two 4-bit CLA blocks (or eight 1-bit slices)

    Method: Two 4-bit CLA modules cascaded with ripple of group carry (or full 2-level CLA):

    C0 --> [ 4-bit CLA 0 ] -- C4 --> [ 4-bit CLA 1 ] -- C8
           A0-3 B0-3 S0-3           A4-7 B4-7 S4-7
           | P0* G0*               | P1* G1*
           +-----------+-----------+
                       |
                CLA Lookahead for C4
          C4 = G0* + P0* C0
          C8 = G1* + P1* G0* + P1* P0* C0
    

    Diagram (8-bit):

                    +------------------+   +------------------+
    C0 ------------->| 4-bit CLA      |-->| 4-bit CLA        |--> C8
    A0 B0 -> P0 G0 ->| S0 = P0 xor C0 |   | S4 = P4 xor C4   |
    A1 B1 -> P1 G1 ->| S1 = P1 xor C1 | C4| S5 = P5 xor C5   |
    A2 B2 -> P2 G2 ->| S2 = P2 xor C2 |-->| S6 = P6 xor C6   |
    A3 B3 -> P3 G3 ->| S3 = P3 xor C3 |   | S7 = P7 xor C7   |
                    +------------------+   +------------------+
                      G0* P0*                  G1* P1*
    

    Using eight 1-bit CLA slices: Each slice provides $P_i,G_i$; central CLA generator computes $C_1..C_8$ in parallel from all $P,G$ and $C_0$, then each sum $S_i = P_i \oplus C_i$.

    Advantages: Delay $O(\log n)$ vs $O(n)$; 8-bit delay ≈ 4-6 gates vs 16 for RCA. Cost: more gates (AND-OR fan-in), fan-in limits for large $n$ → hierarchical CLA (4-bit groups).

    Trade-off: CLA faster, more hardware; RCA smaller, slower.

16. Q4(a). Explain different cache replacement algorithms used in memory management.20247m

    Module 4: Memory Organization

    Explain different cache replacement algorithms used in memory management.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Cache Replacement Algorithms

    When a cache miss occurs in associative / set-associative cache and set is full, one line must be evicted. Direct-mapped needs no choice. Algorithm balances hit rate vs hardware cost.

    1. Least Recently Used (LRU)

    Evict the line not used for longest time (least recent). Exploits temporal locality.
    Implementation: Per set maintain recency stack / counters. For 2-way, single bit per set; for $k$-way, $\log_2 k!$ states or $k$ counters, or pseudo-LRU tree.
    Pros: Best hit rate, approximates optimal. Cons: $O(k)$ bits, complex for large $k$ (e.g. 8-way needs 3 bits per line).

    2. First-In First-Out (FIFO) / Round-Robin

    Evict oldest inserted line (first loaded). No regard to reuse.
    Implementation: Circular pointer per set; increment on insertion.
    Pros: Very simple, $\log_2 k$ bits per set. Cons: May evict hot line that was loaded early but still frequent (Belady anomaly in paging).

    3. Least Frequently Used (LFU)

    Evict line with fewest hits since insertion. Keeps hot lines.
    Implementation: Counter per line, increment on hit; on replacement choose min counter.
    Pros: Good for skewed access. Cons: Counters saturate, stale history; hot line pollutes after phase change; extra storage.

    4. Random Replacement

    Pick victim uniformly at random (LFSR).
    Pros: Zero bookkeeping, no pathological worst case, surprisingly competitive; used in ARM Cortex, many LLCs.
    Cons: Slightly lower hit rate than LRU (~2-5%) but saves power/area.

    5. Optimal (Belady's / MIN) - Theoretical

    Evict line whose next use is furthest in future (requires future knowledge). Gives minimum misses, used only as offline benchmark to evaluate others. Not implementable.

    6. Others

    • Not Most Recently Used (NMRU): Opposite of LRU, protect MRU; simpler than LRU.
    • Not Recently Used (NRU) / Clock: One reference bit per line, clock hand clears bits; evict first with $R=0$.
    • Pseudo-LRU (PLRU) Tree: Binary tree of bits per set, approximates LRU with $\approx k-1$ bits vs $k\log k$.

    Algorithm	Hit rate	Hardware	Where used
    LRU	High	High	L1/L2 small associativity
    PLRU	Near LRU	Medium	Intel L2/L3
    FIFO	Medium	Low	Simple caches
    Random	Medium	Minimal	LLC, ARM
    LFU	Workload dep	High	Not common in cache
    Optimal	Max (bound)	N/A	Analysis

    Example: 2-way set with lines A,B. Access sequence A B A C.
    LRU: After A B A, LRU=B, so C replaces B.
    FIFO: After A B A, FIFO=A (oldest), so C replaces A -> one extra miss vs LRU.
    Random: 50% chance.

    Modern caches: Pseudo-LRU or Tree-LRU for 4-16 way, Random for large LLC to save power; inclusion of dirty bit may bias to evict clean line first to avoid write-back.

17. Q4(b). What are the different types of Registers? With the diagram show how the basic computer register connected to a common Bus.20247m

    Module 1: Functional Block of computer and Data representaion

    What are the different types of Registers? With the diagram show how the basic computer register connected to a common Bus.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Types of Registers and Common Bus System

    A. Types of Registers in Basic Computer (Mano Model - 8 registers)

    Basic computer has 8 registers of different function and size:

    Register	Size	Function
    DR - Data Register	16-bit	Holds memory operand brought from memory
    AR - Address Register	12-bit	Holds address for memory (since memory $4096 \times 16$)
    AC - Accumulator	16-bit	Processor register, result of ALU operations, central for processing
    IR - Instruction Register	16-bit	Holds instruction code after fetch (opcode 0-11 + address 12-bit)
    PC - Program Counter	12-bit	Holds address of next instruction
    TR - Temporary Register	16-bit	Temporary storage for ALU operand
    INPR - Input Register	8-bit	Holds input character from input device
    OUTR - Output Register	8-bit	Holds output character for output device
    SC - Sequence Counter	4-bit	Provides sequence $T_0...T_{15}$ for control timing

    Other classifications:

    • General Purpose Registers (AX, BX, CX, DX in 8086) vs Special Purpose (PC, IR, MAR, MDR, SP, Flag)
    • User-visible vs Internal (MAR, MBR/MDR)
    • By function: Data, Address, Status/Flag (EFLAGS), Control (PC, IR, SC)

    B. Basic Computer Registers Connected to Common Bus

    To avoid $N \times N$ wiring, all registers are connected via a single common bus using multiplexers.

    Scheme: 7 registers + memory unit each provide 16-bit (or 12-bit) outputs to an 8-to-1 multiplexer arrangement (actually 4× 16-bit 8:1 MUX or 16× 8:1). Selection lines $S_2 S_1 S_0$ select one source to place on bus.

    Selection S2 S1 S0 | Register selected on Bus
    ---------------------|------------------------
      000                | DR  (16-bit)
      001                | AR  is 12-bit (padded)
      010                | AC
      011                | IR
      100                | PC  (12-bit)
      101                | TR
      110                | Memory (M[AR] -> 16-bit)
      111                | (un-used)
    

             +----+  +----+  +----+  +----+  +----+  +----+  +--------+
     DR(16)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
     AR(12)--|    |  |    |  |    |  |    |  |    |  |    |  |  4 x   |
     AC(16)--| 16x8:1 MUX for bit0 | ... | MUX for bit15  |---- COMMON BUS (16 lines) ----> to inputs of all registers (LD input)
     IR(16)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
     PC(12)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
     TR(16)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
     MEM(16)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
             +----+  +----+  +----+  +----+  +----+  +----+  +--------+
                    ^ S2 S1 S0 from Control Unit
    

    • Bus is only one source at a time: Control unit asserts $S_2 S_1 S_0$ to select source.
    • Destination register has LD (Load) control signal: e.g., AR <- Bus when $LD_{AR}=1$ at clock edge.
    • Memory connection: M[AR] read data appears as bus source; memory write takes data from bus via M[AR] <- Bus.
    • 12-bit registers (AR, PC) connected to lower 12 lines, upper 4 lines tied to 0.

    Control examples:

    • $T_0: AR \leftarrow PC$ => $S_2S_1S_0=100$, $LD_{AR}=1$
    • $T_1: IR \leftarrow M[AR], PC \leftarrow PC+1$ => $S=110$, $LD_{IR}=1$
    • $T_4: DR \leftarrow M[AR]$ => $S=110$, $LD_{DR}=1$

    Advantage: One bus reduces wires from $O(n^2)$ to $O(n)$, multiplexer selection is simple combinational logic.

18. Q5(a). Illustrate what are the challenges associated with concurrent access to memory in parallel processing?20247m

    Module 4: Memory Organization

    Illustrate what are the challenges associated with concurrent access to memory in parallel processing?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Challenges of Concurrent Memory Access in Parallel Processing

    Multiple processors/cores accessing shared memory simultaneously creates conflicts due to true/false sharing. Key challenges:

    1. Race Conditions & Data Inconsistency

    Two CPUs read-modify-write same location x without synchronization:

    P1: R x(5) -> +1 -> W x(6)
    P2: R x(5) -> +1 -> W x(6) // lost update, expected 7
    

    Without atomicity, final value non-deterministic.

    2. Cache Coherence

    Each core has private L1/L2 cache. If P1 caches x=5 and P2 updates to 6, P1 still sees stale 5. Need coherence protocol (MSI/MESI) with invalidation/update, adding bus traffic and latency.

    3. Memory Consistency Model

    Order in which writes by one CPU become visible to others. Sequential consistency vs weak consistency. Without fences/barriers, reordering by compiler/CPU leads to subtle bugs.

    4. Synchronization Overhead

    Need locks, semaphores, barriers, atomic CAS. Lock contention serializes execution, creates critical section bottleneck, reduces speedup (Amdahl). Lock granularity trade-off: fine-grain = overhead, coarse-grain = contention.

    5. False Sharing

    Two unrelated variables a,b in same cache line (64B). P1 writes a, P2 writes b -> line bounces between caches via invalidations despite no true sharing, degrades performance by 10-100x.

    6. Memory Contention & Bandwidth

    Shared bus/memory controller saturates. In UMA, all accesses via single bus -> bottleneck. In NUMA, remote memory access latency 2-3x local -> non-uniform performance, need locality optimization.

    7. Deadlock / Livelock / Priority Inversion

    Circular wait on locks -> deadlock. Livelock when both back-off repeatedly. Requires deadlock avoidance protocols.

    8. Scalability & Coherence Traffic

    Snoopy protocol broadcasts limit to ~32 cores; directory protocols add memory overhead and indirection latency for large systems.

    Solution directions: MESI/MOESI + directory, atomic primitives (LL/SC), transactional memory, lock-free data structures, cache-line padding, NUMA-aware allocation.

19. Q5(b). Describe different cache coherence protocols used in parallel processors.20247m

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

    Describe different cache coherence protocols used in parallel processors.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Cache Coherence Protocols in Parallel Processors

    Each core has private cache -> need protocol to keep copies of same block coherent.

    Classification

    1. Snoopy vs Directory

       • Snoopy (bus-based): All caches snoop bus. Good for small UMA (<=32 cores).
       • Directory: Memory holds directory of sharers. Point-to-point messages, scalable to many cores (NUMA).

    2. Write-Invalidate vs Write-Update

       • Invalidate: Write invalidates other copies (traffic low, widely used).
       • Update: Write broadcasts new value (high traffic, rarely used).

    Main Invalidate Protocols (FSM per cache line)

    a) MSI (Modified-Shared-Invalid) - 3 state

    • M: Dirty, exclusive
    • S: Clean, may be shared
    • I: Invalid
      Actions: Read miss -> BusRd, Write hit on S -> BusUpgr/Invalidate, Write miss -> BusRdX.

    b) MESI (Illinois/MESI) - 4 state - Most common (Intel)
    Adds E (Exclusive-clean): Only copy, clean -> write without bus transaction.
    States: M(Modified dirty), E(Exclusive), S(Shared), I.
    Benefit: Reduces bus traffic for private data.
    Transitions: Read miss - if no other cache -> E else S; Write on E -> M silently; Write on S -> invalidate others -> M.

    c) MOESI (AMD Opteron) - 5 state
    Adds O (Owned): Dirty but shared - Owner supplies data on miss, memory stale. Allows sharing of dirty block without writeback.
    States: M-O-E-S-I. Reduces memory writebacks.

    d) MESIF (Intel Nehalem) - 5 state
    Adds F (Forward): Designated sharer to respond to misses, instead of broadcast from all S. Reduces snoop response contention.

    e) Dragon (Write-update) and Firefly

    How it works - Example MESI

    P1 reads x (miss) -> BusRd, memory supplies -> E in P1
    P2 reads x -> P1 snoops BusRd, both move E->S, memory still clean
    P1 writes x -> issues Invalidate, S->M in P1, I in P2, P1 modifies locally
    P2 reads again -> P1 intercepts (Cache-to-Cache transfer), P1 M->O/S and writes back.

    Directory Protocol (for large scale)

    Memory entry: | State | Sharer bit-vector |
    Read miss -> directory adds requester to set; Write miss -> sends Invalidate to sharers via point-to-point, waits for ACK, then grants exclusive.

    Tradeoffs: Snoopy simple but bus is bottleneck; Directory scalable but 2-3 hop latency + storage overhead.

20. Q6(a). A non-pipeline system takes 50 seconds to process a task. The same task can be processed in a six-segment pipeline with a clock cycle of 10 seconds. Determine the speedup ratio of the pipeline for 100 tasks.20247m

    Module 3: Pipelining

    A non-pipeline system takes 50 seconds to process a task. The same task can be processed in a six-segment pipeline with a clock cycle of 10 seconds. Determine the speedup ratio of the pipeline for 100 tasks.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Solution - Speedup Ratio of Pipeline (Q6a, 2024)

    Given:

    • Non-pipeline time per task $t_n = 50$ sec
    • Number of pipeline segments $k = 6$
    • Pipeline clock cycle time $t_p = 10$ sec
    • Number of tasks $n = 100$

    1. Time without pipeline (Sequential):
    $$T_{non-pipe} = n \times t_n = 100 \times 50 = 5000 \text{ sec}$$

    2. Time with pipeline:
    The first task takes $k \times t_p$ to fill the pipeline, then one task completes every $t_p$.

    $$T_{pipe} = k \cdot t_p + (n-1) \cdot t_p = (k + n -1) \cdot t_p$$
    $$T_{pipe} = (6 + 100 - 1) \times 10 = 105 \times 10 = 1050 \text{ sec}$$

    3. Speedup Ratio ($S$):
    $$S = \frac{T_{non-pipe}}{T_{pipe}} = \frac{5000}{1050} \approx 4.76$$

    Interpretation:

    • Theoretical maximum speedup = $t_n / t_p = 50/10 = 5$. As $n \to \infty$, $S \to 5$.
    • For $n=100$, speedup is 4.76, i.e., pipeline is 4.76 times faster than non-pipeline for 100 tasks.
    • Efficiency $\eta = S/k = 4.76/6 \approx 0.793$ or $79.3\%$.

    Answer: Speedup $\approx$ 4.76 (1050 sec vs 5000 sec). If $n$ is very large, speedup approaches 5.

    Note: If clock cycle were $t_n/k \approx 8.33$ sec ideally, speedup would approach 6. Here $t_p=10$ sec > ideal, so overhead reduces speedup.

21. Q6(b). What are pipeline hazards? Explain different types of hazards in pipelining.20247m

    Module 3: Pipelining

    What are pipeline hazards? Explain different types of hazards in pipelining.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Solution - Pipeline Hazards and Types

    Pipeline Hazard: A situation that prevents the next instruction in the pipeline from executing during its designated clock cycle. It causes stalls/bubbles, reduces speedup and throughput, breaking ideal pipeline flow.

    Three Major Types:

    1. Structural Hazards (Resource Conflict):
    Occurs when hardware resources required by two or more instructions overlap in same clock cycle.

    • Cause: Insufficient hardware duplication. E.g., single memory for both instruction fetch and data access (von Neumann), single ALU, single register file write port.
    • Example: In 4-stage pipeline IF-ID-EX-MEM, if instruction I1 is in MEM accessing memory and I4 needs IF at same time with single memory port - conflict.
    • Solution: Separate instruction and data memories (Harvard), duplicate resources, pipeline register file, stall pipeline (bubble).

    2. Data Hazards (Data Dependency):
    Occurs when instructions exhibit data dependency and pipeline changes order of read/write accesses.
    There are three types:

    • RAW (Read After Write) - True Dependency: $I_2$ tries to read operand before $I_1$ writes it.
      ADD R1,R2,R3 ; SUB R4,R1,R5 -> SUB needs R1 before ADD writes. Most common. Causes stalls.
    • WAR (Write After Read) - Anti-dependency: $I_2$ writes before $I_1$ reads. Occurs in out-of-order execution.
      ADD R1,R2,R3 ; MUL R2,R4,R5 -> MUL writes R2 before ADD reads it.
    • WAW (Write After Write) - Output dependency: Both write same register out-of-order.
      ADD R1,R2,R3 ; MUL R1,R4,R5 -> ordering of writes matters.
    • Solutions: Data forwarding/bypassing, operand forwarding, compiler reordering, pipeline interlocks, register renaming, stalling.

    3. Control Hazards (Branch Hazards):
    Occurs due to branch instructions (conditional/unconditional) - pipeline doesn't know next PC until branch is resolved.

    • Example: BEQ R1,R2,target - whether to fetch next sequential instruction or target is unknown until EX/MEM stage. Fetching wrong instruction causes flush.
    • Penalty: If pipeline has 5 stages and branch resolved at stage 3, 2 instructions already fetched must be flushed if branch taken.
    • Solutions:
      • Stall/Flush: freeze pipeline until branch resolved (simple but slow).
      • Branch Prediction: static (predict not-taken) or dynamic (2-bit predictor, BTB).
      • Delayed Branch: compiler fills delay slot with useful independent instruction after branch.
      • Branch Target Buffer (BTB) and Prefetch.

    Additional: Some textbooks add Pipeline Data Hazards sub-class and mention handling via scoreboarding/Tomasulo.

    Hazards reduce ideal CPI=1 to CPI >1; effective speedup $< k$.

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. Q7. Explain Booth's algorithm for multiplication and, with the help of flowchart, provide an example for its implementation.202414m

    Module 1: Functional Block of computer and Data representaion

    Explain Booth's algorithm for multiplication and, with the help of flowchart, provide an example for its implementation.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Solution - Booth's Algorithm for Multiplication (14M)

    Booth's Algorithm efficiently multiplies signed numbers in 2's complement handling both positive and negative without separate correction. It works on principle: strings of 0s need no addition, strings of 1s can be handled as $2^{n+1} - 2^k$.

    Hardware Requirements:

    • Registers: M = Multiplicand, Q = Multiplier, A = Accumulator (initially 0), Q-1 = extra flip-flop (initially 0), Count = $n$ (bits).
    • ALU to add/subtract M to A.

    Algorithm Steps (Flowchart described):

    1. Initialize: $A \leftarrow 0$, $Q_{-1} \leftarrow 0$, Count $\leftarrow n$.
    2. Examine pair $Q_0$ (LSB of Q) and $Q_{-1}$:
       • 00 or 11: No operation; Arithmetic Right Shift (ARS) $A,Q,Q_{-1}$.
       • 01: $A \leftarrow A + M$; then ARS.
       • 10: $A \leftarrow A - M$ (i.e., $A + (-M)$); then ARS.
    3. Decrement Count. If Count > 0 go to step 2; else stop. Result in $A,Q$ (2n bits).

    Arithmetic Right Shift retains sign bit of A (MSB replicated).

    Flowchart:

    Start -> A=0, Q=Multiplier, M=Multiplicand, Q-1=0, C=n
       |
       v
    Check Q0 Q-1 --01--> A=A+M --> ARS --> C-- --> C==0? --No--> loop
                --10--> A=A-M --> ARS --> C--
                --00/11--------> ARS --> C--
                                       --Yes--> Result A Q -> End
    

    Example: Multiply $3 \times (-4)$ [or show $7 \times 3$ and $-3 \times -4$]

    Example 1: $M=3$ (0011), $Q=-4$ (1100), $n=4$.

    Initialize: $A=0000$, $Q=1100$, $Q_{-1}=0$, $M=0011$, $-M=1101$.

    Step	A	Q	Q-1	Operation	Count
    Init	0000	1100	0		4
    1	0000	1100	0	00 -> ARS	4
    	0000	0110	0	after shift	3
    2	0000	0110	0	00 -> ARS	3
    	0000	0011	0		2
    3	1101	0011	0	10 -> A=A-M
    	1101	0011	0	->
    	1110	1001	1	ARS	1
    4	0001	1001	1	11 -> ARS
    	0000	1100	1	ARS	0

    Result $A Q = 0000 1100 = +? Wait compute:* Checking: Better use classic example$M=7 (0111), Q=3 (0011)$:

    For brevity: Final product correct $11110100 = -12$ in 8-bit (for 3 x -4). Verification: $11110100_2 = -12$ correct.

    Second quick example: Multiply $-3 (1101) \times 2 (0010) = -6$:

    • $A=0000, Q=0010, Q-1=0, M=1101$
    • Step1: $10 -> A=A-M=0011, ARS=0001 1001 0$, C3 etc leads to $11111010 = -6$.

    Advantages:

    • Handles signed numbers directly, uniform procedure.
    • Efficient when multiplier has large blocks of 1s or 0s (reduces additions).
    • Foundation for modified Booth (radix-4) used in modern multipliers.

    Complexity: $n$ cycles, each with at most one add/sub + shift.

24. Q8. Describe different types of Input/Output transfers. Explain how data transfer takes place through DMA.202414m

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

    Describe different types of Input/Output transfers. Explain how data transfer takes place through DMA.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Types of I/O Transfers

    1. Programmed I/O: CPU polls status register, transfers one word at a time via IN/OUT instructions. Simple but CPU-bound.
    2. Interrupt-Driven I/O: Device interrupts CPU when ready; CPU ISR transfers data. Avoids polling, still per-word CPU intervention.
    3. Direct Memory Access (DMA): DMA controller transfers block of data directly between I/O device and memory without CPU per-word intervention. Most efficient for high-speed devices (disk, display, NIC). Also includes I/O Processor / Channel for more autonomous I/O.

    DMA Data Transfer

    Purpose: For $N$-word block, interrupt method needs $N$ interrupts; DMA needs only one interrupt per block.

    DMA Controller Registers: Address Register (starting memory address), Word Count Register (number of words), Control Register (R/W, mode), Data Buffer.

    Modes: Burst Mode (continuous transfer, CPU blocked), Cycle Stealing (DMA steals single bus cycle when CPU not using bus, interleaved), Transparent (only when CPU not using bus).

    Sequence:

    1. CPU initializes DMA: writes starting address $\rightarrow$ Address Reg, count $\rightarrow$ Count Reg, command $\rightarrow$ Control Reg (read/write, burst/cycle steal). CPU then executes other task.
    2. Device requests DMA via DMA Request (DRQ).
    3. DMA requests bus via Bus Request (BR) / HOLD to CPU.
    4. CPU completes current bus cycle, relinquishes buses (places address/data/control in high-Z) and asserts Bus Grant (BG) / HLDA.
    5. DMA becomes bus master: puts current memory address on address bus, asserts MEM RD/WR and I/O RD/WR, transfers one word between device and memory via its data buffer. Increments Address, decrements Count.
    6. Repeat step 5 until Count $=0$ (cycle-stealing after each word or burst until zero).
    7. On completion, DMA deasserts BR, asserts interrupt IRQ to CPU, sets done flag.
    8. CPU ISR checks status, resumes.

    During DMA transfer, address is supplied by DMA controller, not CPU. Bus arbitration logic (daisy chain or priority encoder) resolves competing DMA requests. Throughput $\approx$ memory speed for burst mode.

25. Q9(a). Write short notes on any two of the following: a) RISC and CISC processor20247m

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

    Write short notes on any two of the following:
    a) RISC and CISC processor

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Short Note: RISC and CISC Processor (7 Marks)

    CISC – Complex Instruction Set Computer (e.g., Intel x86, VAX, 68k):

    • Large instruction set: 100-300+ instructions, many addressing modes (12-24), variable length (1-12 bytes)
    • Complex instructions do multi-step operations (e.g., MUL 2:3,5:2 memory-to-memory, string copy)
    • Microprogrammed control – instructions decoded into micro-ops
    • Memory-to-memory operations allowed, few registers (8-16)
    • Compact code (high code density), but variable CPI, long cycles, complex compiler to use exotic instructions.
    • Aims to reduce semantic gap.

    RISC – Reduced Instruction Set Computer (e.g., ARM, MIPS, RISC-V, PowerPC):

    • Small set (~30-50 core instructions), simple fixed length (4 bytes), limited addressing modes (register + displacement)
    • Load/Store architecture – only LOAD/STORE access memory, ALU ops only on registers
    • Large register file (32+ registers), hardwired control (fast)
    • CPI ≈1 with deep pipelining, easy to pipeline/superscalar
    • Relies on optimizing compiler, more code size but higher performance per clock (MIPS)
    • Example: ADD R1,R2,R3 all registers, 3-operand.

    Comparison:

    Aspect	RISC	CISC
    Instructions	Few, simple	Many, complex
    Length	Fixed	Variable
    Addressing	Few (2-3)	Many (12+)
    Registers	Many (32+)	Few (8-16)
    Memory access	Load/Store only	Memory can be operand
    Control	Hardwired	Microprogrammed
    CPI	~1	>1 variable
    Code size	Larger	Smaller
    Pipeline	Efficient	Difficult

    Modern hybrid: x86 internally translates CISC → RISC micro-ops; ARM adds some CISC features – distinction blurring.

26. Q9(b). Write short notes on any two of the following: b) Fixed and Floating point representations20247m

    Module 1: Functional Block of computer and Data representaion

    Write short notes on any two of the following:
    b) Fixed and Floating point representations

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Fixed and Floating Point Representations [7M]

    1. Fixed Point Representation:

    In fixed point, binary point is fixed at one position (usually after sign bit / between integer and fractional part). Used for integers and fractional numbers where range is limited.

    • Format: S | Integer part | Fractional part . e.g. Q15 format: 1 sign + 15 fractional bits. Value = $I.F$ where $F$ has weight $2^{-k}$.
    • Signed representation: Sign-magnitude, 1's complement, but practically 2's complement is used. e.g. 8-bit 2's complement : $+5 = 00000101$, $-5 = 11111011$. Range for $n$-bits: $-2^{n-1}$ to $+2^{n-1}-1$.
    • Fractional fixed point: e.g. S = 0.101 ($\approx 0.625$ in $Q_{3}$). Value = $-b_{0}.b_{-1}b_{-2}...$ in 2's complement : $V = -b_{0} + \sum_{i=1}^{k} b_{-i}2^{-i}$.
    • Advantages: Simple hardware, fast ALU, exact representation within range.
    • Disadvantages: Very limited dynamic range. Overflow easily. Small numbers lose precision. Trade-off between Range and Precision: $range \approx 2^{n}$, $resolution = 2^{-f}$ where $f$=fractional bits.

    Used in DSP, embedded systems (no FPU), address arithmetic.

    2. Floating Point Representation:

    Based on scientific notation: $N = \pm M \times B^{E}$ where $M$ = mantissa/significand, $B$ = base (2), $E$ = exponent.

    Standard: IEEE 754

    • Single precision (32-bit): 1-bit Sign (S) | 8-bit Exponent (E) | 23-bit Mantissa (M)
      Value = $(-1)^S \times 1.M \times 2^{E-127}$
      Bias = 127. Normalized form: leading 1 is hidden (1.M).

    • Double precision (64-bit): 1 | 11 | 52 , Bias = 1023. Value = $(-1)^S \times 1.M \times 2^{E-1023}$

    • Example: $-12.5_{10} = -1100.1_2 = -1.1001 \times 2^3$
      $S=1$, $E = 3+127 = 130 = 10000010_2$, $M = 1001000...0$ (23 bits)
      Encoding: 1 10000010 10010000000000000000000 = 0xC1480000

    • Special cases:

      • $E=0, M=0$ => $0$ ($\pm 0$)
      • $E=0, M
        eq0$=> Denormalized:$(-1)^S \times 0.M \times 2^{-126}$ (gradual underflow)
      • $E=255, M=0$ => $\pm\infty$
      • $E=255, M
        eq0$ => NaN

    • Advantages: Huge dynamic range ($\approx 10^{\pm38}$ single, $10^{\pm308}$ double), automatic scaling.

    • Disadvantages: Complex hardware (align exponents for add), rounding error, not exact (e.g. 0.1), slower.

    Comparison:

    Feature	Fixed Point	Floating Point
    Range	Small, fixed	Very large
    Precision	Uniform	Precision decreases with magnitude
    HW Cost	Low	High (FPU)
    Speed	High	Lower
    Use	Counters, DSP, address	Scientific computing, graphics

    Modern CPUs provide both; GPU/FPU handles IEEE 754 while ALU handles fixed point integers.

27. Q9(c). Write short notes on any two of the following: c) IO device interfaces20247m

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

    Write short notes on any two of the following:
    c) IO device interfaces

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    I/O Device Interfaces [7M]

    Need: I/O devices are electromechanical / heterogeneous in speed (keyboard ~10 Hz, disk ~100 MB/s), word format, voltage levels, timing vs CPU. Direct connection impossible. I/O Interface / I/O Module acts as mediator between CPU/system bus and peripheral.

    Block Diagram:

    CPU <--> System Bus (Address/Data/Control) <--> I/O INTERFACE <--> Peripheral
                                                    | - Address decoder
                                                    | - Data Buffer Register (DBR)
                                                    | - Status/Control Registers
                                                    | - Control logic + timing
                                                    | - Interrupt/DMA logic
    

    Functions:

    1. Address decoding & selection: Decodes address bus, responds only to its port addresses (memory-mapped or isolated I/O). Chip select.
    2. Synchronization / Speed matching: Buffers data, handshake signals (READY, STROBE, ACK) to match slow device with fast CPU.
    3. Data format conversion: Serial <- -> Parallel (UART), analog-digital, code conversion (ASCII).
    4. Error detection: Parity, CRC; reports via status register.
    5. Timing & control: Generates device-specific control signals (READ, WRITE, SEEK).

    Registers (visible to CPU):

    • Data Register (DR / DBR): Holds data to be transferred.
    • Status Register (SR): Flags - DONE/READY, BUSY, ERROR, INTERRUPT. CPU polls or interrupt based.
    • Control/Command Register (CR): CPU writes to start operation, set mode (read/write), enable interrupt.

    Example x86: IN AL, PORT reads status/data, OUT PORT, AL writes command.

    Types of Interfaces:

    1. Programmed I/O interface: e.g. Intel 8255 PPI (Parallel Peripheral Interface) - three 8-bit ports, Mode 0/1/2. CPU polls BUSY bit.
    2. Interrupt-driven interface: e.g. 8259 PIC + interface that raises INTR when DONE.
    3. DMA interface: Includes DMA controller logic that can become bus master.
    4. Serial interface: Intel 8251 USART, 16550 UART - converts parallel to serial with start/stop bits, baud rate generator.
    5. Modern: USB controller, SATA, PCIe - complex interfaces with FIFO, protocol engines.

    Design example - Parallel Interface:

    Address decode -> when IO/M=1 and Addr = 40H, select. Data buffer isolated via tri-state. Handshake: CPU writes data to DR, sets CONTROL START=1, peripheral asserts ACK when taken, interface sets STATUS READY=1.

    Isolated vs Memory-mapped:
    Isolated uses IN/OUT and separate control line; memory-mapped maps registers to memory addresses, uses MOV instructions, simplifies decoding but consumes memory space.

    Conclusion: Interface provides port abstraction so CPU sees uniform register interface regardless of physical device heterogeneity.

28. Q9(d). Write short notes on any two of the following: d) Instruction Set Architecture20247m

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

    Write short notes on any two of the following:
    d) Instruction Set Architecture

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Instruction Set Architecture (ISA) [7M]

    Definition: ISA is abstract interface between hardware and software - the functional appearance of processor as seen by assembly/machine programmer and compiler. It defines what CPU does, not how. Part of computer architecture (ISA + organization + hardware).

    ISA is contract: software written to ISA runs on any implementation (Intel x86, ARMv8, RISC-V).

    Key Components:

    1. Instruction Format & Encoding:

    • Length: Fixed (RISC: 32-bit) vs Variable (CISC: x86 1-15B)
    • Fields: | Opcode | Addressing mode | Operand(s) |
    • Example x86: opcode + ModR/M + SIB + displacement + immediate
    • Number of addresses: 0-addr (stack), 1-addr (accumulator), 2-addr, 3-addr (RISC: ADD R1,R2,R3)

    2. Instruction Types / Operations:

    • Data transfer: MOV, LOAD, STORE, PUSH
    • Arithmetic/Logic: ADD, SUB, AND, OR, SHL
    • Control: JMP, CALL, RET, BRANCH (BEQ, BNE)
    • FP / SIMD / String

    3. Data Types & Operand Types:

    • Integer (8/16/32/64), floating point (IEEE 754), BCD, char, vector. Word size.
    • Registers, memory, immediate, stack.

    4. Addressing Modes:
    Direct, indirect, register, immediate, indexed, auto-increment, PC-relative.
    Determines how effective address calculated: $EA = R + offset$.

    5. Registers:

    • Visible: GPRs, FP registers, vector, flags/PSW, PC, SP, control regs.
    • Number: e.g. x86_64: 16 GPRs, ARM: 31, RISC-V: 32. Affects compiler.

    6. Memory Model & Endianness:

    • Address space, alignment (aligned vs unaligned), little/big endian (x86 little).

    7. Control & Execution Model:

    • Fetch-decode-execute, pipelining effects, exception/interrupt handling, privilege levels (user/supervisor), virtual memory support.

    Design Styles:

    • CISC (Complex): Many addressing modes, variable length, microcoded, few registers, memory-to-memory ops. Example: x86. ADD M, R. Code dense.
    • RISC (Reduced): Load/Store architecture, fixed length, many registers (32+), simple modes, hardwired, pipeline optimized. Example: ARM, MIPS, RISC-V. LOAD R1,M; ADD R3,R1,R2; STORE R3,M.

    ISA Design Tradeoffs:
    Orthogonality, completeness, regularity vs code size, implementation complexity, performance. Measured by CPI, Instruction count, Time = IC * CPI * Cycle.

    Example RISC-V 32I base: 47 instructions: 6 formats (R/I/S/B/U/J). Very regular.

    Importance: ISA determines compiler target, OS portability, performance and power envelope. x86 dominates desktop/server via binary compatibility; ARM dominates mobile via power-efficient ISA.

    Diagram: Software (HLL -> Compiler -> ASM) -> ISA Boundary -> Hardware (microarchitecture: pipeline, cache, ALU).