2023 question paper

COMPUTER ORGANIZATION & ARCHITECTURE

29 questions

1. Q1(a). A pipeline stage (i) Is sequential circuit (ii) Is combination circuit (iii) Consists of both sequential and combinational circuit (iv) None of these20232m

   Module 3: Pipelining

   A pipeline stage

   (i) Is sequential circuit
   (ii) Is combination circuit
   (iii) Consists of both sequential and combinational circuit
   (iv) None of these

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Consists of both sequential and combinational circuit

   Explanation: A pipeline stage typically contains combinational logic (ALU, adder) to perform operation and sequential elements (pipeline registers/latches) to hold intermediate results between stages and synchronize with clock. Hence it is not purely sequential or purely combinational.

2. Q1(b). A direct mapped cache memory with n blocks is nothing but which of the following set associative cache memory originations (i) 0-way set associative (ii) 1-way set associative (iii) 2-way set associative (iv) n-way set associative20232m

   Module 4: Memory Organization

   A direct mapped cache memory with $n$ blocks is nothing but which of the following set
   associative cache memory originations

   (i) 0-way set associative
   (ii) 1-way set associative
   (iii) 2-way set associative
   (iv) n-way set associative

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) 1-way set associative

   Direct-mapped cache is equivalent to 1-way set associative: each block maps to exactly one set (n blocks = n sets, 1 block per set). n-way would be fully associative.

3. Q1(c). The performance of a pipelined processor suffers if (i) The pipeline stages have different delays (ii) Consecutive instruction are dependent on each other (iii) The pipeline stages share hardware resources (iv) All of these20232m

   Module 3: Pipelining

   The performance of a pipelined processor suffers if
   (i) The pipeline stages have different delays
   (ii) Consecutive instruction are dependent on each other
   (iii) The pipeline stages share hardware resources
   (iv) All of these

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) All of these

   Explanation:
   Pipeline performance (Ideal CPI=1) degrades due to:

   1. Different stage delays: Clock period is set by slowest stage; faster stages idle => loss of efficiency. Unequal delays create bottlenecks/bubbles.
   2. Consecutive instruction dependency (Data hazard): RAW/WAR/WAW dependencies force stalls or forwarding.
   3. Shared hardware resources (Structural hazard): e.g., single memory for instruction & data, single ALU; simultaneous use by two stages causes conflict/stall.

   All three cause pipeline stalls/NOPs, reducing speedup < number of stages. Hence (iv).

4. Q1(d). A computer with cache access time of 100\,ns, a main memory access time of 1000\,ns, and a hit ratio of 0.9 produces an average access time of (i) 250\,ns (ii) 200\,ns (iii) 190\,ns (iv) None of these20232m

   Module 4: Memory Organization

   A computer with cache access time of $100\,ns$, a main memory access time of $1000\,ns$, and a hit ratio of $0.9$ produces an average access time of

   (i) $250\,ns$
   (ii) $200\,ns$
   (iii) $190\,ns$
   (iv) None of these

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) 190 ns (simple); 200 ns hierarchical - both shown

   Given: $T_c=100\,ns$, $T_m=1000\,ns$, $h=0.9$, $miss=0.1$

   • Simultaneous access (common textbook for this question):
     $T_{avg}= h\cdot T_c + (1-h)\cdot T_m = 0.9\times100 + 0.1\times1000 = 90+100 = 190\,ns$ → Option (iii)

   • Hierarchical access (cache checked first, then memory on miss):
     $T_{avg}= h\cdot T_c + (1-h)\cdot(T_c+T_m) = T_c+(1-h)T_m = 100+100 = 200\,ns$ → Option (ii)

   Most WBUT/MAKAUT PYQs expect (iii) 190 ns. If hierarchical model is assumed, answer is 200 ns.

5. Q1(e). Which of the following has no practical usage? (i) SISD (ii) SIMD (iii) MISD (iv) MIMD20232m

   Module 1: Functional Block of computer and Data representaion

   Which of the following has no practical usage?
   (i) SISD
   (ii) SIMD
   (iii) MISD
   (iv) MIMD

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) MISD

   Explanation (Flynn's taxonomy):

   • SISD - Single Instruction Single Data - standard uni-processor.
   • SIMD - Single Instruction Multiple Data - GPUs, vector processors.
   • MIMD - Multiple Instruction Multiple Data - multicore/multiprocessor.
   • MISD - Multiple Instruction Single Data - several instructions on single data stream - theoretically defined but has no practical/commercial realization; hence considered useless category.

   Duplicate of Q31_2.

6. Q1(e). Which of the following has no practical usage? (i) SISD (ii) SIMD (iii) MISD (iv) MIMD20232m

   Module 3: Pipelining

   Which of the following has no practical usage?

   (i) SISD
   (ii) SIMD
   (iii) MISD
   (iv) MIMD

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) MISD

   Explanation (Flynn's taxonomy):

   • SISD - Single Instruction Single Data - conventional von Neumann uni-processor - widely used.
   • SIMD - Single Instruction Multiple Data - vector/array processors, GPUs - widely used.
   • MIMD - Multiple Instruction Multiple Data - multicore, multiprocessor, distributed systems - widely used.
   • MISD - Multiple Instruction Single Data - multiple processors execute different instructions on same data stream - no practical commercial implementation; considered impractical/theoretical only (some argue systolic array is near example but not pure MISD).

   Hence MISD has no practical usage.

7. Q1(f). A micro programmed control unit: (i) Is faster than a hardwired control unit (ii) Facilitates easy implementation of new instructions (iii) Is useful when every small program is to be run (iv) Usually refers to the control unit of the microprocessor20232m

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

   A micro programmed control unit:
   (i) Is faster than a hardwired control unit
   (ii) Facilitates easy implementation of new instructions
   (iii) Is useful when every small program is to be run
   (iv) Usually refers to the control unit of the microprocessor

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) Facilitates easy implementation of new instructions

   Explanation:

   • Microprogrammed CU stores control signals as microinstructions in control memory (ROM). New instructions added by updating microcode - flexible, easy to modify.
   • Not faster than hardwired: hardwired is faster (combinational logic); microprogrammed is slower due to control memory access (so (i) is false).
   • (iii) and (iv) are incorrect descriptions.

   Hence microprogrammed CU's advantage = easy extensibility/modifiability.

8. Q1(g). In memory-mapped I/O: (i) The I/O devices and the memory share the same address space. (ii) The I/O device have a separate address space (iii) The memory and I/O device have an associated address space (iv) A part of the memory is specifically set aside for the I/O operation20232m

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

   In memory-mapped I/O:
   (i) The I/O devices and the memory share the same address space.
   (ii) The I/O device have a separate address space
   (iii) The memory and I/O device have an associated address space
   (iv) A part of the memory is specifically set aside for the I/O operation

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) The I/O devices and the memory share the same address space.

   Explanation:

   • Memory-mapped I/O: No separate I/O addresses; I/O registers are mapped into memory address space. CPU uses same LOAD/STORE instructions for both memory and I/O, decoded by address.
   • Isolated/ I/O-mapped I/O: Separate address spaces, requires special IN/OUT instructions (option ii describes isolated I/O).
   • Options (iii) and (iv) are incorrect descriptions.

   Advantage: no extra instructions; disadvantage: reduces memory address space available.

9. Q1(h). How many 128x8 bit RAMs are required to design 32 kx 32 bit RAM? (i) 512 (ii) 128 (iii) 1024 (iv) 3220232m

   Module 4: Memory Organization

   How many 128x8 bit RAMs are required to design 32 kx 32 bit RAM?
   (i) 512
   (ii) 128
   (iii) 1024
   (iv) 32

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) 1024

   Calculation:
   Desired: $32K \times 32$ bit
   Available: $128 \times 8$ bit

   • Depth expansion: $32K / 128 = 32768/128 = 256$ rows
   • Width expansion: $32 / 8 = 4$ chips per row
   • Total chips: $256 \times 4 = 1024$

   Hence 1024 chips required. Same as Q77.

10. Q1(i). The stalling of the processor due to the unavailability of the instruction is called as: (i) Control hazard (ii) Structural hazard (iii) Input hazard (iv) None of the above20232m

    Module 3: Pipelining

    The stalling of the processor due to the unavailability of the instruction is called as:
    (i) Control hazard
    (ii) Structural hazard
    (iii) Input hazard
    (iv) None of the above

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: (ii) Structural hazard

    Explanation:

    • Structural hazard: Stall due to hardware resource unavailability, e.g., memory port conflict where instruction fetch and data access need same memory, or insufficient ALUs. Unavailability of instruction (I-cache miss / memory contention) falls under this.
    • Control hazard: Due to branches.
    • Data hazard: Due to operand dependency.

    Some texts specifically call "instruction hazard" as subtype of structural hazard.

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. Q1(j). The addressing mode, where you directly specify the operand value is: (i) Immediate (ii) Direct (iii) Definite (iv) Relative20232m

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

    The addressing mode, where you directly specify the operand value is:
    (i) Immediate
    (ii) Direct
    (iii) Definite
    (iv) Relative

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: (i) Immediate

    Explanation:

    • Immediate addressing mode - operand value is directly specified in instruction field itself (e.g., MVI A, 05H, ADD #5). No memory reference.
    • Direct: specifies address of operand.
    • Definite not standard; Relative: PC + offset.

    Hence direct value = Immediate.

13. Q2(a). What are the hazards in pipeline architecture? Explain its types with suitable example.20237m

    Module 3: Pipelining

    What are the hazards in pipeline architecture? Explain its types with suitable example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Pipeline Hazards - Types with Examples (7M)

    1. Pipeline Concept
    Pipelining overlaps fetch-decode-execute stages of multiple instructions. Ideal speedup = n stages. But dependencies cause hazards → pipeline stalls (bubbles) or flushes, reducing throughput. Clock must also handle slowest stage + latch delay.

    2. What is Hazard?
    Situation where next instruction cannot execute in its designated clock cycle due to resource / data / control dependency.

    3. Three Types (Stallings Classification):

    A) Structural Hazard - Resource Conflict

    Occurs when hardware resources insufficient to support overlapping execution.

    Example: Single memory for instruction + data (Von Neumann). IF stage needs memory to fetch, MEM stage needs memory for load/store at same cycle.

    Cycle: 1   2   3   4   5
    I1:    IF  ID  EX  MEM WB
    I2:         IF  ID  EX  MEM*  <- MEM conflict with I1 MEM
    I3:              IF*  ID ...  * structural stall 1 cycle
    

    Solutions: Harvard architecture (separate I-cache/D-cache), separate Instruction & Data memories, multi-port register file, pipelined ALU.

    Other example: Single ALU for EX and address calculation.

    B) Data Hazard - Data Dependency

    Instruction needs data still being computed/ not yet written back.

    Classification per register access:

    1. RAW (Read After Write) - True dependency - Most common

    I1: ADD R1, R2, R3   ; R1 = R2+R3
    I2: SUB R4, R1, R5   ; needs R1 -> must wait for WB of I1
    

    If pipelined without forwarding, I2 reads stale R1. With 5-stage pipeline, need 2 stalls or forwarding.

    2. WAR (Write After Read) - Anti-dependency (only in out-of-order)

    I1: ADD R2, R1, R3   ; reads R1
    I2: SUB R1, R4, R5   ; writes R1 - must not overwrite before I1 reads
    

    3. WAW (Write After Write) - Output dependency

    I1: ADD R1, R2, R3
    I2: SUB R1, R4, R5   ; both write R1 -> order matters
    

    Sub-types by pipeline stage:

    • Load-Use Hazard: Load followed by use needs 1 stall even with forwarding.

    LW  R1, 0(R2)
    ADD R3, R1, R4  ; needs R1 from MEM stage - 1 bubble inserted
    

    • EX-Use Hazard: ALU result forwarded from EX/MEM latch.

    Example Timing with Forwarding vs Stall:

    Without forwarding:
    ADD R1,R2,R3
    SUB R4,R1,R5  -> stall 2 cycles
    
    With forwarding (bypass EX->EX):
    ADD: IF ID EX MEM WB
    SUB:    IF ID --EX-- MEM WB  (forwarded path from EX/MEM to ALU input)
    

    Solutions: Data Forwarding/Bypassing, Register Scoreboarding, Tomasulo, Compiler scheduling (insert NOP), stalls/bubbles.

    C) Control Hazard - Branch / Jump Hazard

    Due to branches, next PC unknown until decode/execute.

    BEQ R1, R2, LABEL  ; branch taken ?
    Next instr fetch is speculative -> if taken, fetched instr wrong -> flush
    

    Cycle 1: IF BEQ
    Cycle 2: IF next (wrong) | ID BEQ -> branch decoded
    Cycle 3: IF next2 | ID next | EX BEQ -> target known -> flush IF,ID
    

    Penalty = 2-3 cycles in simple 5-stage (branch resolved in EX). Modern pipelines predict.

    Example: JMP Label, CALL, interrupts.

    Solutions:

    1. Stall until target known (simple)
    2. Branch Prediction - Static (predict not taken) / Dynamic (1-bit, 2-bit saturating counter, BTB)
    3. Branch Target Buffer (BTB) + Branch History Table
    4. Delayed Branch - Fill delay slot with useful instruction (MIPS)
    5. Speculative execution + flush on mispredict
    6. Loop unrolling

    4. Summary Table

    Hazard	Cause	Example	Stall Cycles	Fix
    Structural	Lack of HW	One memory	1	Add HW, split cache
    RAW Data	Need result	ADD->SUB R1	1-2 (0 with fwd)	Forwarding, NOP
    WAR/WAW	Write conflict	Out-of-order only	0 in-order	Renaming
    Control	Branch PC unknown	BEQ, JMP	2-3	Predict, BTB, delay slot

    5. Performance Impact

    Hazard stalls increase CPI:
    CPI_pipelined = 1 + stall_cycles_per_instr
Speedup = n / (1 + stalls) * (cycle_unpipelined / cycle_pipelined)

    Goal of hazard handling is to keep CPI ~1.

    Diagram to draw in exam: 5-stage pipeline (IF-ID-EX-MEM-WB) reservation table showing overlapping and bubble insertion for each hazard type.

14. Q2(b). What is addressing mode? Why do computers use addressing mode techniques? Explain two modes with example, which do not use address fields.20237m

    Module 1: Functional Block of computer and Data representaion

    What is addressing mode? Why do computers use addressing mode techniques?
    Explain two modes with example, which do not use address fields.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Addressing Mode - Why Techniques & Two Modes Without Address Field (7M)

    A) What is Addressing Mode?

    Field A in instruction format OPCODE | A is not necessarily the operand itself. Addressing mode is the rule CPU uses to interpret A to locate the operand or Effective Address (EA). Decoder uses mode bits (ModR/M in x86) to compute EA = f(A, Registers, PC, Indirect chain).

    Without modes, every instruction would need full absolute address → large code, inflexible.

    Example formats:

    Format: | Opcode | Mode | Address field A |  (16-32 bit system)
    EA derivation depends on Mode:
     Mode 00: EA = A           (Direct)
     Mode 01: EA = (A)         (Indirect)
     Mode 10: Operand = A      (Immediate)
    

    B) Why Do Computers Use Addressing Mode Techniques?

    1. Flexibility to High-Level Constructs:

       • Arrays: Base + Index*Scale access A[i] without computing address manually each time.
       • Pointers/Dynamic structures: Indirect Mov R,(P) dereferences pointer.
       • Records/Structs: Displacement Struct + Offset.
       • Position-Independent Code: Relative PC + Disp for branching/ PIC.

    2. Reduce Instruction Size / Code Density:

       • Immediate 8-bit vs 32-bit address, Register mode uses 3 bits to select register vs 32-bit absolute. Keeps program shorter → fewer instruction fetches.

    3. Support Multiple Data Structures with Few OpCodes:

       • One ADD opcode works for ADD #5, ADD [2000H], ADD [BX+SI] differing only by mode bits, not separate opcode per operand location.

    4. Efficient Loop & Stack Handling:

       • Auto-increment/decrement (R)+ , -(R) for traversing arrays/stacks without extra INC instruction; Stack mode implied via SP.

    5. Virtual Memory & Protection (x86):

       • Segmentation + indexed modes hide physical address calculation.

    6. Performance: Register mode fastest (no memory access); with modes, compiler can keep hot variables in registers, use immediate for constants (no memory load). Reduces memory traffic.

    In summary: Modes bridge gap between programmer's abstract view (variables, pointers, arrays, constants) and hardware's physical view (linear memory addresses) while minimizing instruction bits.

    C) Two Modes That Do NOT Use Address Field

    Some instructions have no address operand at all; operand location is implied or is the instruction itself.

    1. Implied / Implicit / Stack Mode
    No address field present; operand(s) implicitly assumed.

    • Definition: Opcode itself implies where operand resides - typically top of stack, accumulator, or flags register.
    • Operation: EA not needed; CPU internally uses SP or accumulator.

    Examples:

    • Stack Zero-address: PUSH AX ; POP BX ; ADD (in stack machine) → pops TOS and TOS-1, pushes sum. E.g., PUSH 2; PUSH 3; ADD → stack top = 5.
    • Accumulator implied: CMA (Complement Accumulator), INCA (Increment A) - operand is always AC.
    • Flag implied: CLC (Clear Carry), STC, CLI/STI - operates on FLAGS, no operand.
    • Example encoding: CLC = F8H (8086) - 1 byte, no address bits. PUSH AX = 50H.
    • EA calculation: None, SP used: PUSH: SP=SP-2, Mem[SP]=AX. No address in instruction stream.

    2. Immediate Mode
    Operand value itself IS the address field - no memory/register address is referenced beyond instruction.

    • Definition: Operand = A where A is the value encoded in instruction after opcode. No EA computation, no extra memory fetch beyond instruction fetch.
    • Distinctness: Technically it has an "address field" but it does not contain an address; it contains data. For exam classification, it counts as no-address-field-needed for operand location (value fetched alongside instruction).

    Examples:

    • MOV AX, 1234H (8086: B8 34 12) - moves constant 0x1234 to AX. 1234H is part of instruction.
    • ADD R1, #10 (Assembly # denotes immediate): R1 = R1 + 10, 10 encoded as 8-bit immediate 00001010.
    • CMP AL, 5 Immediate 5 compared to AL.
    • Encoding advantage: 2-4 byte instruction vs 6-byte load from memory pool.

    Note: Some texts also call Register mode as not using address field (register ID is attribute, not memory address), but exam expects Implied and Immediate as canonical two that use no memory address. Mention Register as alternative if needed.

    Contrast:
     Direct:  | LDA | 2000H | -> need to fetch Mem[2000H] (extra cycle)
     Immediate:| MVI | 25H   | -> value 25H used directly, no extra fetch
     Implied: | CLC |       -> no field at all
    

    Tip for diagram: Draw instruction format boxes: Immediate shows Opcode | Immediate Value and Implied shows only Opcode.

15. Q3(a). A 4-way set associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB. Find the number of bits for TAG, SET, and WORD fields in the address generated by CPU.20237m

    Module 4: Memory Organization

    A 4-way set associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB. Find the number of bits for TAG, SET, and WORD fields in the address generated by CPU.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Given

    • Cache size $C =16$ KB $=16384$ B $=2^{14}$ B
    • Associativity $k=4$ (4-way set associative)
    • Block size = $8$ words, Word = $32$ bits $=4$ B
      $\Rightarrow$ Block = $8\times4=32$ B $=2^{5}$ B
    • Physical address space $4$ GB $=2^{32}$ B $\Rightarrow$ Physical address $32$ bits

    Calculations

    1. Number of blocks in cache:
    $N_{blocks}= C / Block =16384/32=512$ blocks $=2^{9}$

    2. Number of sets:
    $N_{sets}= N_{blocks}/k =512/4=128$ sets $=2^{7}$
    $\Rightarrow$ SET field $s = \log_2 N_{sets}=7$ bits

    3. WORD / Offset field:
    Block = $32$ B. Byte offset within block = $\log_2 32 =5$ bits.
    This $5$ bits comprises:

    • Word offset within block: $\log_2 8 =3$ bits (select 1 of 8 words)
    • Byte offset within word: $\log_2 4 =2$ bits (select 1 of 4 bytes)

    If address is word-addressable, WORD field = $3$ bits.
    If byte-addressable (standard), combined offset = $5$ bits.

    Common naming in question: WORD field = $5$ bits (or split $3+2$).

    4. TAG field:
    $TAG = Physical\_bits - SET - OFFSET$

    • Byte-addressable: $TAG =32 -7 -5 =20$ bits
    • Word-addressable with byte split: $TAG =32 -7 -3 -2 =20$ bits same.

    Answer

    Physical Address (32 bits)
    +-----------+---------+---------------+
    | TAG 20b   | SET 7b  | WORD/OFFSET 5b|
    |           |         | (3b word+2b byte)|
    +-----------+---------+---------------+
    

    • TAG = 20 bits
    • SET = 7 bits
    • WORD/Offset = 5 bits (3 bits word + 2 bits byte)

    If counting WORD only (word index): WORD=3 bits, BYTE=2 bits, TAG=20, SET=7.

    Check: $20+7+5=32$.

    Alternative: If cache size given as $16$ KB words (unlikely), then $C=16K\times4=64KB$ $\Rightarrow$ sets $=512$ $\Rightarrow$ SET=9, TAG=18. But standard is bytes → answer above.

16. Q3(b). How is the virtual address mapped into physical address? What are the different methods of writing into cache?202314m

    Module 4: Memory Organization

    How is the virtual address mapped into physical address? What are the different methods of writing into cache?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    A) Virtual address → Physical address mapping (Paging)

    Virtual address generated by CPU is not real RAM address. MMU translates via Page Table + TLB.

    Assume $V=32$ bits, page $4$ KB $=2^{12}$ B $\Rightarrow$ offset $12$b, VPN $20$b.

    VA (32b): [ VPN 20b | Offset 12b ]
                     |
                     v
              +-------------------+
              | TLB (cache)       |---- hit ----> PFN
              | VPN -> PFN        |
              +---------+---------+
                        | miss
                        v
              Page Table in RAM (PTBR points)
              PTE: [ PFN | valid | prot | dirty | ref ]
                        |
                        v
    PA (32b): [ PFN 20b | Offset 12b ]  (concatenation)
    

    Steps:

    1. Split VA into VPN + offset.
    2. Search TLB ( ~64-512 entries, associative). Hit → PFN in 1 cycle.
    3. Miss → hardware walks page table (often 2-level: Dir + Page table) in memory; may fault.
    4. If PTE valid=1 → $PA = PFN \ll 12 | offset$; check protection.
    5. If valid=0 → Page fault → OS loads page from disk to frame, updates PTE, restarts.
    6. TLB updated.

    Segmentation variant: $VA = segment+offset$ → segment table → page table. But paging alone is core.

    ---

    B) Cache Write Methods

    When CPU writes, cache and main memory can become incoherent. Policies:

    1. Write-Through

    • Write to both cache and main memory simultaneously.
    • Simple, coherent, but every write goes to bus → high traffic, slow.
    • Usually with write buffer to hide latency.
    • On read miss, block fetched.

    CPU Write → Cache + Memory (together)
    

    2. Write-Back (Copy-Back)

    • Write only to cache; set Dirty bit per block. Memory updated only on eviction of dirty block.
    • Reduces bus traffic (many writes coalesced). Faster.
    • Needs dirty bit + extra control; memory stale until write-back.

    CPU Write → Cache (dirty=1)  ---- later on replace ---> Memory
    

    3. Allocation policy on Write Miss

    • Write-Allocate (Fetch on Write): On write miss, load block to cache then write (common with write-back).
    • No-Write-Allocate (Write-Around): On write miss, write directly to memory, not loading to cache. Common with write-through to avoid polluting cache with write-only data.

    Typical combos:

    • Write-Through + No-Write-Allocate
    • Write-Back + Write-Allocate (most performant, used in L1/L2)

    Comparison:

    Property	Write-Through	Write-Back
    Memory update	Immediate	Deferred (on evict)
    Bus traffic	High	Low
    Dirty bit	No	Yes
    Speed	Slower	Faster
    Coherence	Simple	Complex (need snooping)

    Example: $4$-way cache: Write hit in write-back sets dirty; on replacement if dirty=1, 32B block written back to RAM before loading new block.

17. Q4(a). What are the different types of instruction formats?20237m

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

    What are the different types of instruction formats?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Types of Instruction Formats

    Instruction format defines fields in a machine instruction: opcode, operand addresses, mode. Length and field count trade code density vs decode simplicity.

    Let $Op$ = opcode, $A_i$ = address/operand.

    1. Zero-Address Format (Stack-organized)

    No address field; operands on stack (TOS). Implicit.
    $Op$ alone; $T \leftarrow T \circ TOS$; push/pop.
    Example: PUSH A; PUSH B; ADD; POP C does $C\leftarrow A+B$.
    Need PUSH, POP, ADD, SUB, MUL etc. Zero addresses in arithmetic instr.
    e.g. ADD = $TOS\leftarrow TOS + TOS_{-1}$.

    Adv: No address bits, short instr. Dis: Stack bottleneck, extra pushes.

    2. One-Address Format (Accumulator)

    One field: $Op\; A$ where one operand is Accumulator (AC) implicitly.
    $AC \leftarrow AC \circ M[A]$
    Example: LOAD X ($AC\leftarrow M[X]$), ADD Y ($AC\leftarrow AC+M[Y]$), STORE Z ($M[Z]\leftarrow AC$), MUL X.
    Only one memory address per arithmetic instr. Used in Mano Basic Computer.

    3. Two-Address Format

    Fields: $Op\; A_1\; A_2$ : $A_1 \leftarrow A_1 \circ A_2$
    Both operands specified, one also destination. Reduces moves.
    Example: MOV R1,R2 ($R1\leftarrow R2$), ADD R1, X ($R1\leftarrow R1+M[X]$), SUB R1,R2 ($R1\leftarrow R1-R2$).
    8086 ADD AX,BX is two-address (register-register). Saves fetch vs three-address.

    4. Three-Address Format

    Fields: $Op\; A_1\; A_2\; A_3$ : $A_1 \leftarrow A_2 \circ A_3$
    All operands specified, destination separate. Most expressive, but longest (e.g. 32-bit: 8-bit Op +3x8-bit addr).
    Example: ADD R1,R2,R3 ($R1\leftarrow R2+R3$), MUL X,Y,Z ($X\leftarrow Y\times Z$).
    Used in RISC (ARM, MIPS uses register variant $R$-type).

    5. Other / Variable Formats (per COA syllabus)

    • Variable-length: CISC (x86) mixes 1 to 15 bytes; opcode + ModR/M + displacement + immediate. Dense but complex decode.
    • Fixed-length: RISC (MIPS 32-bit): $R$ (register), $I$ (immediate), $J$ (jump) formats.
      Example MIPS: R: op(6)|rs(5)|rt(5)|rd(5)|shamt|funct, I: op|rs|rt|imm16, J: op|addr26.

    Format	Addresses per instr	Memory refs per operation	Example
    3-addr	3	3-4	ADD R1,R2,R3
    2-addr	2	2-3	ADD R1,R2
    1-addr	1	2	ADD X (AC implicit)
    0-addr	0	1 (stack)	ADD

    Choice affects instruction length, code size, registers needed, and CPI. Modern designs favor 2/3-address register formats + load/store architecture.

18. Q4(b). Discuss the different mapping techniques used in cache memories and their relative merits and demerits.20237m

    Module 4: Memory Organization

    Discuss the different mapping techniques used in cache memories and their relative merits and demerits.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Cache Mapping Techniques

    Cache maps main memory blocks to cache lines. For memory address: Tag | Line/Set Index | Word/Offset. Three techniques:

    1. Direct Mapping

    • Rule: Each memory block $j$ maps to exactly one cache line: Line = j mod (number_of_lines)
    • Address: Tag | Line | Word (e.g., 12-bit tag, 8-bit line, 6-bit word for 64-byte block)
    • Hardware: One comparator per access, simple.
    • Pros: Simple, cheap, fast hit time (one tag compare).
    • Cons: Conflict misses high - if two blocks map to same line they thrash (even if other lines empty). No flexibility. Worst hit ratio.
    • Use: Low-cost caches.

    2. Fully Associative Mapping

    • Rule: Any memory block can go to any cache line. No index field.
    • Address: Tag | Word only. Cache stores Tag per line.
    • Hardware: CAM - all tags compared in parallel (content-addressable memory) + valid bit. Replacement algorithm needed (LRU, FIFO, Random).
    • Pros: Most flexible, lowest conflict misses - best hit ratio for given size. No thrashing.
    • Cons: Expensive (parallel comparators for every line), slow for large cache (many comparators, high power). Replacement logic complex. Suitable only for small caches (e.g., TLB).
    • Use: Small fully-associative TLB, victim caches.

    3. Set-Associative Mapping (k-way)

    • Compromise between 1 and 2. Cache divided into sets, each set has $k$ lines. Set = j mod (number_of_sets). Block can go to any of $k$ lines within set.
    • Address: Tag | Set | Word
    • Examples: 2-way, 4-way, 8-way. If $k=1$ -> Direct, if $k = lines$ -> Fully associative.
    • Hardware: $k$ comparators per set (parallel within set), plus set decode.
    • Pros: Good balance - reduces conflict misses greatly (e.g., 4-way removes most thrashing) with modest hardware cost. Most used in modern CPUs (L1: 4-8 way, L2/L3: 8-16 way).
    • Cons: Slightly slower than direct (k compares + mux), needs replacement within set (LRU approx).
    • Intel Example: 32KB 8-way L1, 1MB 16-way LLC.

    Comparison Summary

    Technique	Lines per block	Comparators	Hit time	Miss rate	Cost
    Direct	1	1	Fastest	Highest	Lowest
    2/4-way Set	k	k	Medium	Medium-Low	Medium
    Fully Associative	All	All lines	Slow (large)	Lowest	Highest

    Other merits/demerits:

    • Capacity vs Conflict vs Compulsory misses: Direct suffers conflict; Fully associative only compulsory+capacity; Set-associative reduces conflict sharply even 2-way improves miss rate ~30-40%.
    • Replacement: Direct - no choice; Associative/Set - need LRU.
    • Victim Cache / Pseudo-associative: Extra small fully-associative buffer for direct-mapped conflict blocks.

    Modern processors use Set-Associative (typically 4-16 way) as sweet spot; TLBs use Fully-Associative; cheap microcontrollers may use Direct-mapped.

19. Q5(a). Design a 4-bit carry-look ahead adder and explain its operation with an example.20237m

    Module 1: Functional Block of computer and Data representaion

    Design a 4-bit carry-look ahead adder and explain its operation with an example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    4-bit Carry Look-Ahead Adder (CLA)

    Problem with Ripple Carry: Carry propagates serially: $C_{i+1}$ waits for $C_i$ -> delay $O(n)$, $4\times2\Delta$ gates.

    CLA generates all carries in parallel using $G$ (generate) and $P$ (propagate).

    For bit $i$: $A_i, B_i, C_i$

    $$G_i = A_i \cdot B_i$$
    $$P_i = A_i \oplus B_i \quad (\text{or } A_i+B_i)$$

    Sum: $S_i = P_i \oplus C_i$
    Carry: $C_{i+1}= G_i + P_i C_i$

    Design Equations ($C_0$ = input carry)

    $$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$$

    Hardware: 4 G/P gates (1 level), 4 carry AND-OR networks (2 levels), 4 XOR for sum -> total delay ~ $3\Delta$ independent of $n$ (vs $8\Delta$ for RCA).

    Block Diagram: $A[3:0], B[3:0]$ -> G/P generator -> CLA logic (generates $C_1$-$C_4$) -> XOR -> $S[3:0]$, $C_4$ is Cout. Draw 2-level AND-OR.

    Example: Add $A=1011$ (11) + $B=0101$ (5), $C_0=0$ -> Expect $10000$ (16)

    i	$A_i$	$B_i$	$G_i$	$P_i$
    0	1	1	1	0
    1	1	0	0	1
    2	0	1	0	1
    3	1	0	0	1

    Compute:
    $C_1 = 1+0\cdot0=1$
    $C_2 = 0+1\cdot1=1$
    $C_3 = 0+1\cdot0+1\cdot1\cdot1=1$
    $C_4 = 0+1\cdot0+1\cdot1\cdot0+1\cdot1\cdot1\cdot1+1\cdot1\cdot1\cdot0\cdot0=1$

    Sums: $S_0=0\oplus0=0$, $S_1=1\oplus1=0$, $S_2=1\oplus1=0$, $S_3=1\oplus1=0$ + $C_4=1$ => $10000$.

    All carries generated simultaneously -> ~3 gate delays. For wider adders, use hierarchical CLA (4-bit blocks with block $G^*, P^*$).

20. Q5(b). Consider a direct mapped cache with 8 cache blocks (numbered 0-7). If the memory block requests are in the following order 3, 5, 2, 8, 0, 63, 9, 16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82, 17, 24. What would be the status of cache blocks (block numbers residing in cache) at the end of the sequence.20237m

    Module 4: Memory Organization

    Consider a direct mapped cache with 8 cache blocks (numbered 0-7). If the memory block requests are in the following order 3, 5, 2, 8, 0, 63, 9, 16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82, 17, 24. What would be the status of cache blocks (block numbers residing in cache) at the end of the sequence.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Direct Mapped Cache - Final Block Status

    Cache size $C=8$ blocks (0-7). Direct mapped: index = block mod 8.

    Requests: 3,5,2,8,0,63,9,16,20,17,25,18,30,24,2,63,5,82,17,24

    Trace:

    #	Block	Index ($mod8$)	Action	Cache state 0-7
    -	-	-	init	[-,-,-,-,-,-,-,-]
    1	3	3	miss	[-,-,-,3,-,-,-,-]
    2	5	5	miss	[-,-,-,3,-,5,-,-]
    3	2	2	miss	[-,-,2,3,-,5,-,-]
    4	8	0	miss	[8,-,2,3,-,5,-,-]
    5	0	0	miss evict 8	[0,-,2,3,-,5,-,-]
    6	63	7	miss	[0,-,2,3,-,5,-,63]
    7	9	1	miss	[0,9,2,3,-,5,-,63]
    8	16	0	miss evict 0	[16,9,2,3,-,5,-,63]
    9	20	4	miss	[16,9,2,3,20,5,-,63]
    10	17	1	miss evict 9	[16,17,2,3,20,5,-,63]
    11	25	1	miss evict 17	[16,25,2,3,20,5,-,63]
    12	18	2	miss evict 2	[16,25,18,3,20,5,-,63]
    13	30	6	miss	[16,25,18,3,20,5,30,63]
    14	24	0	miss evict 16	[24,25,18,3,20,5,30,63]
    15	2	2	miss evict 18	[24,25,2,3,20,5,30,63]
    16	63	7	hit	[24,25,2,3,20,5,30,63]
    17	5	5	hit	[24,25,2,3,20,5,30,63]
    18	82	2	miss evict 2	[24,25,82,3,20,5,30,63]
    19	17	1	miss evict 25	[24,17,82,3,20,5,30,63]
    20	24	0	hit	[24,17,82,3,20,5,30,63]

    Final Cache Status

    • Block 0: 24
    • Block 1: 17
    • Block 2: 82
    • Block 3: 3
    • Block 4: 20
    • Block 5: 5
    • Block 6: 30
    • Block 7: 63

    Vector form: [24, 17, 82, 3, 20, 5, 30, 63] for indices 0-7.

    Hits = 3 (63,5,24); Misses = 17. No fully associative/LRU needed - direct mapped deterministic.

21. Q6(a). What is DMA? Describe how DMA is used to transfer data from peripherals.20237m

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

    What is DMA? Describe how DMA is used to transfer data from peripherals.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    DMA - Direct Memory Access

    1. What is DMA?

    DMA is an I/O technique where data is transferred directly between memory and peripheral (I/O device) without continuous CPU intervention. A dedicated hardware controller - DMAC (DMA Controller) - takes control of the system buses (steals cycles) and performs the transfer at memory speed.

    Without DMA, CPU does programmed I/O (polling/interrupt) moving each byte/word via IN/OUT instructions - slow and wastes CPU cycles.

    With DMA, CPU only initiates transfer (source, destination, count) and gets interrupt on completion; it is free to do other work meanwhile.

    2. Why Needed?

    • Transfers large blocks (disk, display, ADC) at high speed (MB/s).
    • Frees CPU: CPU involvement is O(1) vs O(n) for programmed I/O.
    • Overcomes speed mismatch: peripheral can burst at memory speed via bus mastering.

    3. Block Diagram

                  +-----+   Bus Request/Grant
                  | CPU |-----------------+
                  +-----+                 v
                     |   +----------+  +------+  +--------+
                     +-->|  DMAC    |<->|Memory|<->|Peripheral|
                         | - Address|<->|      |  | (Disk) |
                         |  Counter |  Data/Addr Bus |
                         | - Word   |  +------+  +--------+
                         |  Count   |
                         | - Control|
                         +----------+
      CPU programs: Source Addr, Dest Addr, Count, Mode (Read/Write)
    

    Inside DMAC: Address Register, Word Count Register, Control/Status Register, Data Buffer.

    4. How DMA Transfer Works (Cycle Stealing / Burst Mode)

    Steps:

    1. Program: CPU writes to DMAC registers: Memory start address, I/O port/device ID, block length (word count), direction (Memory->Device or Device->Memory). Also programs peripheral.

    2. Request: Peripheral ready (e.g., disk sector buffered) asserts DMA Request (DRQ) to DMAC.

    3. Bus Request: DMAC asserts Bus Request (BR/HOLD) to CPU.

    4. Bus Grant: CPU finishes current bus cycle, tristates its buses, asserts Bus Grant (BG/HLDA) and suspends.

    5. Transfer: DMAC now bus master:

       • Puts address on address bus (incrementing each word)
       • Generates MEM READ + I/O WRITE (or vice versa) control signals
       • Data moves directly Memory <-> Peripheral via data bus, without going through CPU.
       • Word Count decremented, Address incremented. Repeat each bus cycle.

       Two modes:

       • Cycle Stealing: DMAC takes one bus cycle at a time, interleaving with CPU.
       • Burst/B block transfer: DMAC holds bus for entire block (CPU idle).

    6. Completion: When Word Count = 0, DMAC deasserts BR, asserts interrupt DMA Complete to CPU. CPU regains bus.

    7. CPU ISR: Reads status, checks error.

    5. DMA Transfer Types

    • Single Transfer (Flyby): Data flies from source to destination in one bus cycle (Memory and I/O strobes together).
    • Two-cycle: Data latched in DMAC buffer first then written.

    Modes: Block, Demand, Cascade (multiple DMACs chained, e.g., 8237).

    6. Advantages / Disadvantages

    Adv: High speed near memory bandwidth, low CPU overhead, ideal for disk, GPU, network.
    Disadv: Needs DMAC hardware, bus arbitration logic, cache coherence issue (DMA modifies memory behind cache - needs snooping/flush), cycle stealing slightly slows CPU.

    Modern systems use Bus Mastering DMA where peripherals themselves contain DMAC (e.g., PCIe devices become bus masters).

    Example: Disk read of 4KB: CPU issues DMA Read 4KB from LBA 100 to 0x2000, continues computation; DMAC moves 4096 bytes at ~100 MB/s; CPU interrupted only at end vs 4096 interrupts otherwise.

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. Q6(b). Differentiate between hardwired and micro programmed control unit. Explain each component of hardwired control unit organization.20237m

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

    Differentiate between hardwired and micro programmed control unit. Explain each component of hardwired control unit organization.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Solution - Hardwired vs Microprogrammed Control & Hardwired Organization

    A) Difference between Hardwired and Microprogrammed Control Unit:

    Basis	Hardwired Control	Microprogrammed Control
    Implementation	Combinational logic: gates, flip-flops, decoders, encoders	Control memory (ROM/RAM) storing microinstructions (firmware)
    Speed	Very fast (no memory access)	Slower (requires control memory fetch)
    Flexibility	Inflexible - modification requires rewiring/redesign	Flexible - just change microprogram in control memory
    Complexity	Becomes very complex and difficult to design if instruction set is large	Simple, systematic design even for complex instruction set (CISC)
    Cost	Costly for complex ISAs	Cheaper for complex ISAs
    Control Signals	Generated directly by hardware	Generated by microinstructions (MW)
    Used in	RISC processors, simple CPUs	CISC processors (e.g., x86), older IBM 360
    Modification	Difficult to add new instruction	Easy - add new routine to control store

    B) Hardwired Control Unit Organization - Components:

    A hardwired CU generates control signals as Boolean functions of inputs: Instruction Register (IR), Flags/Condition Codes, Timing signals (T1..Tn) from sequencer, Clock.

    Block diagram components:

    1. Instruction Register (IR) and Decoder:
       Opcode from IR is decoded by instruction decoder to set one of $2^n$ lines (one per instruction). This selects the required sequence of control signals.

    2. Timing Generator / Sequence Counter (SC) and Control Counter:
       Clock pulses are counted by a 4-bit ringJohnson counter or sequence counter that generates time states $T_0, T_1, T_2, T_3 ...$. Each instruction executes as sequence of micro-operations in successive T-states.

    3. Control Logic Gates / Encoder:
       Combinational logic (AND-OR gates or PLA) combines decoder output ($I_i$), T-state ($T_j$) and flags ($Z,C$) to generate individual control signals:
       Example: $LoadPC = T_1 \cdot FETCH + T_2 \cdot BRANCH \cdot Z$

    4. Flags / Condition Code Register:
       Provides status (Zero, Carry, Sign) to alter control sequence - e.g., for conditional branching or skip.

    5. Mode / Processor Status Register:
       Indicates addressing mode, interrupt enable etc. to modify control generation.

    Operation:
    For each $T_x$ pulse, decoder output and flags are combined in the encoder matrix to assert required signals e.g., $PC_{out}, MAR_{in}, Read, IR_{in}, AC_{in}$ etc. After last T-state, SC is reset to $T_0$ and next instruction fetch starts.

    Advantages: High speed. Disadvantage: No flexibility, complex design and testing.

24. Q7(a). What do you mean by asynchronous data transfer? Explain strobe control and hand shaking mechanism.20237m

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

    What do you mean by asynchronous data transfer? Explain strobe control and hand shaking mechanism.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Asynchronous Data Transfer

    Transfer where source and destination do not share a common clock. Timing is established by control signals rather than clock edges, allowing devices with different speeds to communicate and eliminating clock-skew problems, at cost of extra handshaking overhead.

    Used for slow I/O, inter-system bus (Unibus), UART, etc.

    Two schemes:

    1. Strobe Control (Single control line)

    One STROBE signal times the data.

    • Source-initiated strobe:

      1. Source places data on data bus.
      2. After $t_{setup}$ (data stable), source asserts STROBE (e.g. high pulse).
      3. Destination on strobe edge latches data.
      4. Source de-asserts strobe and removes data after hold time.
         Waveform: DATA valid → STROBE ↑ → Dst latches → STROBE ↓
         Risk: No acknowledgement; source assumes worst-case propagation+setup hold time. If destination not ready, data lost.

    • Destination-initiated strobe:

      1. Destination asserts STROBE requesting data.
      2. Source places data on bus, informs (no explicit ack).
      3. Destination latches on data valid (uses delay or timeout).
         Similar limitation: no feedback.

    Advantage: Simple, 1 wire. Disadvantage: No handshake → needs known timing, cannot handle variable-latency slave.

    2. Handshaking (Two-wire, fully interlocked)

    Adds REPLY / ACK to guarantee transfer. Two variants:

    a) Source-initiated handshaking (most common):

    Source                      Destination
      | Data valid on bus            |
      |----------------------------->|
      | STROBE (Data Ready) -------->| 
      |                              | latch data
      | <-------- ACK / Data Accepted|
      | STROBE ↓                     |
      | <-------- ACK ↓ (idle)       |
    

    Sequence:

    1. Source: DATA valid → STROBE=1 (Request).
    2. Destination: when ready and data latched, asserts ACK=1.
    3. Source sees ACK=1, de-asserts STROBE=0, removes data.
    4. Destination sees STROBE=0, de-asserts ACK=0 → ready for next.

    b) Destination-initiated handshaking:
    Roles reversed: Destination initiates REQ / Ready for Data, source responds with Data Valid as ack.

    Handshaking is fully interlocked - each edge waits for response, so works for any speed mismatch. Double-handshake (four-event) eliminates races.

    Comparison:

    Feature	Strobe	Handshaking
    Lines	1	2
    Feedback	No	Yes
    Speed adaptive	No	Yes
    Hardware	Minimal	More flip-flops
    Use	Fast known delay (e.g. memory)	Variable I/O, bus arbitration

    Diagram should show two control lines plus data bus with the four-phase pulse sequence labelled.

25. Q7(b). Show the systematic multiplication process of (20) x (-19) using Booth's algorithm.20237m

    Module 1: Functional Block of computer and Data representaion

    Show the systematic multiplication process of (20) x (-19) using Booth's algorithm.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Booth's Algorithm: $20 \times (-19) = -380$

    Take $n=6$ bits (sign inclusive). Result $2n=12$ bits.

    • Multiplicand $M = 20_{10}=010100_2$, $-M = 101100_2$ (2's complement)
    • Multiplier $Q = -19_{10}=101101_2$ (since $19=010011$, invert+1)
    • Registers: $A=000000$, $Q_{-1}=0$, count $=6$

    Rule per step: inspect $Q_0 Q_{-1}$:

    • $00$ or $11$: no add, ASHR $A,Q,Q_{-1}$
    • $01$: $A \leftarrow A+M$
    • $10$: $A \leftarrow A-M$, then ASHR

    Step	$Q_0Q_{-1}$	Action	$A$	$Q$	$Q_{-1}$
    Init	-	$A=0$	000000	101101	0
    1	10	$A=A-M$	101100	101101	0
    		ASHR	110110	010110	1
    2	01	$A=A+M$	001010	010110	1
    		ASHR	000101	001011	0
    3	10	$A=A-M$	110001	001011	0
    		ASHR	111000	100101	1
    4	11	none	111000	100101	1
    		ASHR	111100	010010	1
    5	01	$A=A+M$	010000	010010	1
    		ASHR	001000	001001	0
    6	10	$A=A-M$	110100	001001	0
    		ASHR	111010	000100	1

    After 6 shifts, count=0.

    $$A\,Q = 111010\,000100_2 = 12\text{-bit 2's complement}$$

    Check: $111010000100_2$ → invert $000101111011+1=000101111100_2=380_{10}$ → value $-380_{10}$.

    $$\mathbf{20 \times (-19) = -380}$$

    If using $6$-bit unsigned representation: $111010000100$ ($0xE84$). In decimal $380 = 000101111100$, $-380 =111010000100$.

    For $5$-bit demo ($M=010100$ still 6-bit needed because $20>15$), same result. Any $n \ge 6$ yields same 12-bit product with sign extension.

26. Q8(a). The stage delays in a four-stage pipeline are 800, 500, 400 and 300 picoseconds. The first stage (with delay 800 picoseconds) is replaced with a functionally equivalent design involving two stages with respective delays 600 and 350 picoseconds. What would be the throughput increase (in percentage) of the pipeline?20237m

    Module 3: Pipelining

    The stage delays in a four-stage pipeline are 800, 500, 400 and 300 picoseconds. The first stage (with delay 800 picoseconds) is replaced with a functionally equivalent design involving two stages with respective delays 600 and 350 picoseconds. What would be the throughput increase (in percentage) of the pipeline?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Given stage delays: $T_1=800$, $T_2=500$, $T_3=400$, $T_4=300$ ps. Pipeline clock $T_{clk}= \max(T_i)$ (+ latch overhead ignored).

    Before modification:
    $$T_{clk1}= \max(800,500,400,300)=800\text{ ps}$$
    Throughput $= 1/T_{clk1}$ instructions per ps.
    $$f_1 = \frac{1}{800\text{ ps}} =1.25\times10^{9}\text{ instr/s}$$

    After splitting first stage into $600$ ps + $350$ ps, stages become: $600,350,500,400,300$.

    $$T_{clk2}= \max(600,350,500,400,300)=600\text{ ps}$$
    $$f_2 = \frac{1}{600\text{ ps}} =1.667\times10^{9}\text{ instr/s}$$

    Throughput increase:
    $$\%\Delta = \frac{f_2-f_1}{f_1}\times100 = \frac{\frac{1}{600}-\frac{1}{800}}{\frac{1}{800}}\times100 = \left(\frac{800}{600}-1\right)\times100$$
    $$= \left(1.333...-1\right)\times100 = 33.33\%$$

    Speedup $= 800/600 = 1.33$.

    If latch overhead $t_l$ (e.g., 20ps) included, then $T_{clk1}=800+t_l$, $T_{clk2}=600+t_l$, increase $= \frac{800+t_l}{600+t_l}-1 \approx 32.25\%$ for $t_l=20$ps. Ideal approx 33.33% increase.

    Note: Total latency increases slightly ($2000$ ps → $2150$ ps) but steady-state throughput improves due to smaller max stage delay (pipeline bottleneck reduced).

27. Q8(b). Explain IEEE standard for floating point representation with example.20237m

    Module 1: Functional Block of computer and Data representaion

    Explain IEEE standard for floating point representation with example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    IEEE 754 Floating Point Standard

    Represents real numbers in binary scientific notation: $(-1)^S \times (1.F) \times 2^{E-bias}$ for normalized numbers.

    Single Precision (32-bit):

    | S (1) | Exponent (8) | Mantissa/Fraction (23) |
    

    • $S=0$ positive, $1$ negative.
    • Exponent = true exponent $E$ + bias $127$ (range $-126$ to $+127$).
    • Mantissa stores fractional part after leading 1. (hidden bit).
    • Value $= (-1)^S \times 1.M \times 2^{E-127}$.

    Double Precision (64-bit): $S(1)$ | Exponent(11, bias 1023) | Mantissa(52). Value $= (-1)^S \times 1.M \times 2^{E-1023}$.

    Special values:

    • $E=0, M=0$ → $\pm0$; $E=0, M
      eq0$→ denormalized$0.M \times 2^{-126}$ (gradual underflow).
    • $E=255, M=0$ → $\pm\infty$; $E=255, M
      eq0$ → NaN.
    • Normalized: $1\le E\le254$.

    Example - Single Precision

    Represent $-12.75_{10}$ in IEEE 754 32-bit:

    1. Sign: negative → $S=1$.
    2. Binary: $12.75 = 1100.11_2 = 1.10011 \times 2^{3}$ (normalize).
    3. Exponent: $E_{true}=3$ → $E_{biased}=3+127=130=10000010_2$.
    4. Mantissa: fractional part 10011 padded to 23 bits → 10011000000000000000000.

    Result:

    1 | 10000010 | 10011000000000000000000
    

    Hex = 0xC14C0000.

    Another example - $0.085$? $6.5_{10}=110.1_2=1.101\times2^{2}$ → $S=0, E=129=10000001, M=1010...$ → 0 10000001 10100000000000000000000 = 0x40D00000.

    To decode, reverse: $S$, $E-127$, insert 1., compute $(-1)^S\times1.M\times2^{E-bias}$.

28. Q9(a). Write short notes on: Paging20237m

    Module 4: Memory Organization

    Write short notes on: Paging

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Short Note: Paging (7 Marks)

    Concept: Paging is a memory management scheme that eliminates external fragmentation by dividing logical memory into fixed-size pages and physical memory into same-size frames. Pages are mapped to available frames via page table.

    Terminology: Page size power of 2 (512B-8KB typical, e.g., 4KB in x86). Logical address = | Page Number (p) | Offset (d) |. Physical address = | Frame Number (f) | Offset (d) |.

    Mechanism:

    • CPU generates logical address. MMU extracts $p$ and $d$.
    • Page Table (per process, in RAM) gives $p \to f$ mapping. Accessed via Page Table Base Register (PTBR).
    • Physical address = $f \times \text{pageSize} + d$. Translation via TLB cache for speed.

    Page Table Entry contains: Frame number, valid/invalid bit, protection (R/W/X), dirty, referenced, present bit.

    Example: 16-bit logic, page 1KB (10 bits offset): | p(6) | d(10) |. If $p=2$ maps to $f=7$, logic 00 0010 00 0000000000 → physical 00 0111 00....

    Types:

    • Single-level: Simple but large for 32-bit (1M entries).
    • Multi-level/Hierarchical paging (2/3-level): Used in x86 (Page Directory → Page Table), reduces table size.
    • Inverted Page Table: One entry per frame, for large address spaces.

    Advantages: No external fragmentation, simple allocation, supports virtual memory and swapping (pages to disk), protection and sharing (shared frames).

    Disadvantages: Internal fragmentation (last page waste avg ½ page), page table memory overhead, translation overhead (TLB miss penalty), needs TLB for performance.

    Demand Paging: Pages loaded from disk only on page fault (valid=0) → supports virtual memory larger than physical, uses page replacement (FIFO/LRU).

    Paging vs Segmentation: paging fixed size, invisible to programmer; segmentation variable, logical units.

29. Q9(b). Write short notes on: Memory interleaving20237m

    Module 4: Memory Organization

    Write short notes on: Memory interleaving

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Memory Interleaving [7M]

    Need: CPU is faster than DRAM. Single memory module can serve only one access at a time (access time $t_a \approx 60ns$). Pipelining requests to multiple modules can increase effective bandwidth and hide latency (similar to pipeline).

    Definition: Divide main memory into $m$ independent modules/banks that can be accessed in parallel/overlapped. Interleaving defines how consecutive addresses are spread across modules.

    1. Types:

    • High-order interleaving (Memory banking): MSB selects module.
      Address: | Module (k bits) | Offset (n-k bits) |
      e.g. 4 modules (0-3), addresses 0-255: Module 0 holds 0-63, M1:64-127, M2:128-191, M3:192-255. Consecutive addresses map to same module -> no advantage for sequential access. Useful when program has locality in different segments (code in M0, data in M1).

    • Low-order interleaving (true interleaved): LSB selects module.
      Address: | Offset | Module |
      e.g. 4 modules: $Addr$ mapping -> Module = $Addr \mod 4$.
      Module 0: 0,4,8,12... Module1:1,5,9... Sequential addresses map to successive modules.

    Low-order is generally called memory interleaving and used for cache line fill and vector access.

    Example: 4-way low-order, $t_a=80ns$ , $t_c=40ns$ cycle.

    Without interleaving: 4 words sequentially takes $4 \times 80 = 320ns$.
    With interleaving: Issue request to M0 at $t=0$, M1 at $t=20ns$, M2 at $40ns$, M3 at $60ns$ (pipelined). M0 returns at $80ns$, M1 at $100ns$... Total $\approx 80+3\times20 = 140ns$ . Effective access time $\approx t_c$ not $t_a$.

    2. Address generation:

    For $m=2^k$ modules, $k$ bits of address select module. For low-order $k$ LSBs.
    Memory controller has $m$ MAR/MDR, can latch $m$ requests.

    3. Advantages:

    • Higher bandwidth : $m$ times potential.
    • Reduced effective access time for sequential / stride-1 and vector operations.
    • Avoids bank conflicts : If accesses are uniformly distributed, probability of conflict $\approx 1/m$.
    • Essential for cache block transfer (burst mode) and SIMD/vector processors.

    4. Disadvantages / Limitations:

    • Bank conflict: If successive accesses map to same module before it recovers (e.g. stride = $m$), pipeline stalls. e.g. stride 4 with 4 modules -> all accesses to M0.
    • Cost: $m$ sets of decoders, buffers, bus arbitration more complex.
    • Not helpful for random access with poor locality.

    5. Relation to DRAM banks:
    Modern DDR SDRAM internally has 4-16 banks with interleaving. Also C-access interleaving used in supercomputers (e.g. Cray). Need also interleaved cache (non-blocking).

    Diagram: CPU Address Bus -> Decoder (LSB->Bank Select) -> Banks 0..m-1 -> Data Bus Multiplexer -> CPU.

    Conclusion: Low-order $m$-way interleaving converts memory latency-bound system into bandwidth-bound by overlapping access cycles.

30. Q9(c). Write short notes on: Privileged and non-privileged instructions20237m

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

    Write short notes on: Privileged and non-privileged instructions

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Privileged vs Non-Privileged Instructions [7M]

    Context: Modern OS must protect itself, memory and devices from user programs. CPU provides dual-mode operation: Supervisor/Kernel mode (privileged) and User mode (non-privileged). Mode indicated by PSW bit (e.g. x86 CPL / PE flag, ARM M bits). Some instructions allowed only in supervisor mode.

    1. Privileged Instructions:

    Define: Executable only when CPU in supervisor mode ($mode=0$). If attempted in user mode, triggers privileged instruction trap / General Protection Fault.

    • Examples:

      • I/O instructions: IN, OUT, INS, OUTS (x86), HLT, CLI, STI (halt, disable/enable interrupts)
      • Control registers: MOV CR0, EAX, LIDT, LGDT, WRMSR, TLB flush (INVLPG)
      • Memory management: LMSW, MOV to CR3 (page table base)
      • Interrupt & DMA control: IRET, enable/disable DMA
      • HALT, RESET processor

    • Purpose: Directly manipulates shared hardware resources. Only OS kernel should do that.

    2. Non-Privileged (Unprivileged / User) Instructions:

    Executable in any mode. Ordinary computation not affecting system state.

    • Examples: MOV, ADD, SUB, MUL, CMP, JMP, CALL, PUSH, POP (within user stack), floating point arithmetic.
    • Some sensitive but non-privileged: e.g. POPF may not allow changing interrupt flag if in user mode (x86 masks it).

    3. Why distinction? Protection

    • Prevents user program from: corrupting other processes' memory (via MMU), stealing devices, masking interrupts, halting system, changing scheduling.
    • System calls: User wants I/O -> executes trap / INT 0x80 / SYSCALL which switches to kernel mode, OS validates parameters then executes privileged operation on behalf.
    • Virtualization: Hypervisor uses privileged instructions to emulate hardware for guest.

    4. Mechanism:

    Hardware checks mode bit before decoding. E.g. pseudo:

    if (instruction.isPrivileged && PSW.mode == USER) -> exception(13)
    

    x86 has 4 rings (0=kernel most privileged, 3=user). I/O privilege level (IOPL) in EFLAGS controls IN/OUT access. ARM has SVC (supervisor) vs USR.

    Comparison Table:

    Aspect	Privileged	Non-privileged
    Mode	Kernel only	User & Kernel
    Function	System control	Computation
    Trap if violated	Yes - #GP fault	No
    Example	HLT, CLI, IN, LGDT	ADD, MOV, AND

    Without this separation, multi-programming and OS isolation would be impossible.

31. Q9(d). Write short notes on: Locality of reference20237m

    Module 4: Memory Organization

    Write short notes on: Locality of reference

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Locality of Reference [7M]

    Principle: Program memory access is not random but clustered. Observed empirically (Denning, 1968). Foundation for cache, virtual memory and hierarchy design. $90\%$ execution time in $10\%$ code.

    1. Types:

    • Temporal Locality: If location $X$ is referenced at time $t$, it will likely be referenced again soon (near future).
      Reason: Loops, reuse of variables, stack, counters.
      Example:

      for(i=0;i<1000;i++) sum += a[i]; // `sum` reused every iteration
      

      sum accessed every iteration -> temporal.

    • Spatial Locality: If location $X$ is referenced, nearby locations $X+\Delta$ will likely be referenced soon.
      Reason: Sequential instruction execution, array traversal, contiguous structures.
      Example: a[0], a[1], a[2]... contiguous words -> fetching a[i] brings cache block of 64B (8 words) -> next 7 accesses are hits. Instructions are sequential as well.

    • Sequential Locality: Special case of spatial - next instruction is $PC+1$ unless branch.

    2. Implications / Applications:

    • Cache Memory: Block size $>1$ word exploits spatial locality. Upper level stores working set exploiting temporal. LRU replacement exploits temporal. Without locality, hit ratio $\to 0$ and cache useless.
    • Virtual Memory / Paging: Keep working set in RAM; pages brought on locality basis. Thrashing occurs when locality violated / working set exceeds frames.
    • Prefetching: Hardware prefetcher fetches $next\ line$ based on spatial.
    • Branch prediction & instruction cache: Sequential locality predicts next fetch.
    • Quantified: Hit ratio $h \approx 0.9-0.98$ for L1 when locality high. Effective access time: $T_{eff}= h\cdot T_{cache} + (1-h)\cdot T_{memory}$ -> makes $T_{eff}\approx T_{cache}$.

    3. Working Set Theory:

    Denning: $W(t,\tau)$ = set of pages referenced in last $\tau$ references. Locality implies $|W|$ small (e.g. 2-4 pages) vs total size. OS tries to keep $W$ resident. If $\sum W_i >$ physical memory -> thrashing.

    4. Example Calculation:

    Loop touches 1K word array stride 1 with 64B block (16 words):
    Without spatial exploitation: 1000 misses. With block: $\approx 1000/16 =63$ misses -> 93% hit rate due to spatial.

    5. Violations:
    Linked list with nodes scattered, random pointer chasing, large stride $> block size$ defeats spatial locality; large data set with no reuse defeats temporal -> cache pollution.

    Conclusion: Locality of reference bridges speed gap between CPU and memory; hierarchy design (register-cache-main-disk) succeeds only because of it.