2016 question paper

COMPUTER ORGANIZATION & ARCHITECTURE

18 questions

1. Q1a. (a) Write the range of decimal integer that can be represented by *n-bit 1’s complement representation.*20162m

   Module 1: Functional Block of computer and Data representaion

   (a) Write the range of decimal integer that can be represented by n-bit 1’s complement representation.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: Range $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$

   Explanation (n-bit 1's complement):

   • Positive numbers: $0$ to $2^{n-1}-1$ (leading bit 0)
   • Negative numbers obtained by complementing bits: $-(2^{n-1}-1)$ to $-0$
   • Two zeros: $+0 = 00...0$ and $-0 = 11...1$ - wasted code, hence $2^n-1$ effective values but $2^n$ encodings.
   • e.g., n=8: $-127$ to $+127$; n=4: $-7$ to $+7$.
   • Contrast with 2's complement: $-2^{n-1}$ to $2^{n-1}-1$ (single zero, one extra negative value).
2. Q1b. What is zero address instruction format?20162m

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

   What is zero address instruction format?

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Zero-address instruction format: Instruction contains only opcode, zero address fields. Operand sources are implicit stack top. Architecture is stack-organized. Example: ADD, SUB, PUSH X, POP. Execution: PUSH A (A→TOS), PUSH B, ADD → pop TOS-1+TOS → push result. Advantage: short instruction, good for expression compilation; disadvantage: many stack operations, not flexible for random access.

3. Q1c. What do you mean by interrupt-initiated I/O?20162m

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

   What do you mean by interrupt-initiated I/O?

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Interrupt-Initiated I/O:

   In programmed I/O the CPU continuously polls the device status, wasting CPU cycles. In interrupt-initiated I/O the CPU does not poll.

   • I/O device informs CPU of its readiness / completion by asserting an interrupt signal (INTR).
   • CPU continues executing its current program; when interrupt is acknowledged, it suspends current work, saves PC/PSW, branches to Interrupt Service Routine (ISR) to transfer data.
   • After ISR completes, CPU resumes original program.

   Advantage: CPU utilization is greatly improved — CPU is free during I/O wait, interrupted only when device actually needs service. Basis for modern interrupt-driven and DMA systems.

4. Q1d. What do you mean by cache coherence problem?20162m

   Module 4: Memory Organization

   What do you mean by cache coherence problem?

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Cache Coherence Problem:

   Occurs in multiprocessor / multi-cache systems where multiple caches may hold copies of the same memory block.

   If one processor (P1) writes to its cached copy of block X, other caches holding X become stale/inconsistent with main memory and with each other. Subsequent reads by other processors would get old data.

   • Problem: Ensuring all caches and main memory see a consistent view of shared data after writes.
   • Solutions: Snooping protocols (write-invalidate, write-update / write-broadcast), directory-based protocols, MESI state machine.

   Without coherence, program correctness is violated.

5. Q1e. How many 128 × 8 RAM chips are needed to provide a memory capacity of 2048 bytes?20162m

   Module 4: Memory Organization

   How many 128 × 8 RAM chips are needed to provide a memory capacity of 2048 bytes?

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: 16 chips

   Each RAM chip = $128 \times 8$ = 128 bytes (128 locations of 8-bit words).

   Required capacity = 2048 bytes.

   $$\text{No. of chips} = \frac{\text{Required capacity}}{\text{Chip capacity}} = \frac{2048}{128} = 16$$

   So 16 chips of $128 \times 8$ are needed (arranged as $16 \times 128 = 2048$ bytes; 8-bit width matches, no width expansion needed — only depth expansion; needs 11 address lines, 7 for chip internal, 4 for chip select via decoder).

6. Q1f. Briefly explain the conflicts in instruction pipeline.20162m

   Module 3: Pipelining

   Briefly explain the conflicts in instruction pipeline.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Conflicts/Hazards in Instruction Pipeline: pipeline cannot overlap execution. Three types:

   1. Structural Hazard (Resource conflict): Two stages need same hardware resource in same cycle. e.g., single memory for instruction fetch and data access, single ALU. Solved by separate I-cache/D-cache, extra functional units, pipeline stalls.

   2. Data Hazard: Next instruction needs data not yet produced by previous instruction. Types: RAW (Read After Write - true dependency), WAR, WAW. Causes stalls/bubbles. Solved by forwarding/bypassing, register renaming, compiler scheduling.

   3. Control Hazard (Branch hazard): Due to branch/jump instructions. Pipeline doesn't know next PC until branch resolved, so wrong instructions fetched. Causes flushing. Solved by branch prediction, delayed branch, branch target buffer, prefetch.

   All reduce speedup from ideal $k$ to $<k$ and need hazard handling.

7. Q1g. Explain the use of subroutine with the help of suitable example.20162m

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

   Explain the use of subroutine with the help of suitable example.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Subroutine Uses (2 Marks)

   A subroutine is a self-contained sequence of instructions called from different points in program to avoid code duplication.

   Uses:

   1. Modularity & Reuse: Common task (e.g. I/O, math) written once and called many times — saves memory, improves readability.
   2. Return Address Management: On CALL addr, CPU saves return address (next PC) automatically — either in link register or on top of stack: SP ← SP-1, M[SP] ← PC, PC ← addr.
   3. RET instruction: On RET, address popped back: PC ← M[SP], SP ← SP+1 and execution resumes after call.
   4. Nesting & Recursion: Stack LIFO allows nested calls; parameters passed via registers/stack, and CALL/RET use stack pointer.

   Thus subroutine supports structured programming with hardware stack mechanism.

8. Q1h. What is a micro-operation? Explain the four categories of the most common micro-operations.20162m

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

   What is a micro-operation? Explain the four categories of the most common micro-operations.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Micro-operation Categories (2 Marks)

   A micro-operation is an elementary operation performed on data in registers during one clock pulse. Four categories:

   1. Register Transfer: Moves data between registers or between register and memory, without alteration. e.g. R1 ← R2, MAR ← PC, MDR ← M[MAR]. Triggered by control signals and bus.

   2. Arithmetic Micro-operations: Performed by ALU. e.g. R3 ← R1 + R2, R1 ← R1 + 1 (increment), R2 ← R2 - 1 (decrement), Add with carry, Subtract.

   3. Logic Micro-operations: Bitwise operations on registers. e.g. R1 ← R1 ∧ R2 (AND), R1 ← R1 ∨ R2 (OR), R1 ← not R1 (COMPLEMENT), XOR. Used for masking/clearing.

   4. Shift Micro-operations: Shift/rotate register contents. e.g. R1 ← shl R1 (logical shift left), shr, ashl/ashr (arithmetic preserves sign), cir/cil (circular rotate). Used for serial transfer & multiply/divide by 2^n.

9. Q1i. Define hit ratio and explain its significance.20162m

   Module 4: Memory Organization

   Define hit ratio and explain its significance.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Definition:
   $$\text{Hit Ratio } (h) = \frac{\text{Number of hits}}{\text{Total number of accesses}} = \frac{\text{Hits}}{\text{Hits + Misses}}$$

   $$Miss\ Ratio = 1 - h$$

   Where hit = data found in faster memory (Cache), miss = data not found and must be fetched from lower level (Main memory).

   Hit ratio is usually expressed for cache: $h_{cache}$, also applicable to TLB, etc.

   Significance - AMAT (Average Memory Access Time):

   The effective access time depends critically on hit ratio:

   $$AMAT = h \times T_{hit} + (1-h)\times T_{miss}$$

   or for hierarchical memory:

   $$AMAT = T_{cache} + (1-h) \times T_{memory}$$

   • High $h$ ($\approx$ 0.9-0.99 due to locality of reference) → $AMAT \approx T_{cache}$ → system performs near cache speed, despite large cheap main memory.
   • Low $h$ → AMAT → approaches main memory time, cache is ineffective and penalty dominates.
   • Used to evaluate/design cache: organization, block size, associativity, replacement policy all aim to maximize $h$. Helps in deciding cache size vs. cost trade-off and in calculating effective CPU stall cycles due to memory.

   Example: $T_{cache}=10ns$, $T_{memory}=100ns$, $h=0.95$ → $AMAT = 0.95\times10 + 0.05\times(10+100)=14.5ns$ vs $100ns$ without cache.

10. Q2. With neat block diagram, explain how DMA controller is initialized for DMA data transfer.201614m

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

    With neat block diagram, explain how DMA controller is initialized for DMA data transfer.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    DMA Controller Initialization for DMA Data Transfer (14 Marks)

    1. Introduction - What is DMA?

    Direct Memory Access (DMA) allows I/O devices to transfer data directly to/from main memory without continuous CPU intervention. CPU only initializes the DMA controller, then DMA handles the transfer via cycle stealing / bus mastering, freeing CPU for other work.

    Ideal for high-speed transfers: Disk, Network, Audio/Video, ADC.

    Without DMA, CPU does programmed I/O - fetch each byte, poll status - very inefficient.

    2. DMA System Block Diagram

                        SYSTEM BUS (Data, Address, Control)
         ┌─────────────────────────────────────────────────────────────────┐
         │                                                                 │
         │   ┌───────┐      ┌──────────────┐      ┌────────────┐  ┌──────┐ │
         └──►│  CPU  │◄────►│ DMA Controller│◄────►│   Memory   │  │ I/O  │ │
             └───┬───┘      │  (8237/82357) │      └────────────┘  │Device│ │
                 │          │ ┌───────────┐ │                     └──────┘ │
                 │  HOLD/HLDA│ │ Registers │ │                            │
                 │◄─────────►│ │ - CAR     │ │                            │
                 │          │ │ - CWCR    │ │  DREQ ──► Peripherals      │
                 │          │ │ - Mode Reg│ │  DACK ◄── request/ack      │
                 │          │ │ - Command │ │  HRQ/HLDA to CPU           │
                 └──────────┴─┴───────────┴─┴──────────────────────────────┘
    
    Detailed DMA Controller Inside:
    ┌─────────────────────────────────────────┐
    │  DMA Controller (4 channels example)    │
    │ ┌──────────────┐ ┌──────────────────┐   │
    │ │ Channel Logic│ │ Address Register │   │
    │ │ 0-3          │ │ (16/32 bit) CAR  │   │
    │ ├──────────────┤ │ Count Register   │   │
    │ │ Mode Register│ │ (CWCR)           │   │
    │ │ Command Reg  │ │ Data Buffer      │   │
    │ │ Status Reg   │ │ Timing & Control │   │
    │ │ Request Reg  │ │ Priority Encoder │   │
    │ └──────────────┘ └──────────────────┘   │
    └─────────────────────────────────────────┘
    
    Signals: HRQ (Hold Request) -> CPU HOLD, HLDA <- CPU, DREQ (DMA Request from I/O), DACK (DMA Acknowledge), MEMR/MEMW, IOR/IOW, AEN (Address Enable), ADSTB
    

    Connections: DMA sits between CPU, Memory and I/O. When idle, bus controlled by CPU. When active, DMA becomes bus master.

    3. DMA Registers to be Initialized

    Before any transfer, CPU (as program) must program following internal registers of DMA via I/O mapped writes (using CS, A0-A3, IOW):

    Register	Purpose	Example
    Starting Address Register (CAR)	Base address in memory where transfer starts	0x2000
    Count Register (CWCR / Terminal Count)	Number of bytes/words to transfer -1	N-1 (e.g., 1023 for 1KB)
    Mode Register	Transfer type: Read/Write/Verify, Auto-init, Address inc/dec, Demand/Single/Block	0x58 = Block, Inc, Write
    Command Register	Controller enable/disable, priority (fixed/rotating), DREQ sense, memory-to-memory	0x00
    Mask Register	Mask/unmask channel, enable DREQ	Clear mask
    Request Register	Software request (for M-M transfer)

    For 8237A: 4 channels, each 16-bit address + 16-bit count + 6-bit mode.

    4. Step-by-Step Initialization Sequence

    Assumption: Want to transfer 1KB from Disk (I/O port) to Memory address 0x20000 using Channel-1 Burst/Block mode.

    Phase A: CPU Preparation

    1. CPU executes setup routine with interrupts disabled (or handling).
    2. CPU checks DMA idle - reads Status Register - ensure no ongoing transfer, channel not masked busy.

    Phase B: Programming DMA (CPU as master, DMA as slave)

    CPU writes via I/O instructions (OUT) to DMA port addresses:

    Step 1: Send starting address

    OUT CommandReg, 0x0C (clear First/Last flip-flop for 8237)
    OUT AddressReg Ch1, Low Byte (0x00)
    OUT AddressReg Ch1, High Byte (0x00)  -> also Page Register for A16-A23 if 24-bit (0x02)
    

    Step 2: Send word count (N-1)

    OUT CountReg Ch1, Low Byte (0xFF)  // 1024-1 = 1023 = 0x03FF
    OUT CountReg Ch1, High Byte (0x03)
    

    Step 3: Program Mode Register for Channel 1

    Mode byte: [D7-D6=01][D5=0][D4=0][D3-D2=01][D1-D0=01]
               Channel select+ Transfer type (Write: I/O->Mem) + Auto-init 0 + Addr inc + Demand/Block
    OUT ModeReg, 0x58
    

    Step 4: Program Command Register

    Bits: Fixed priority, Late write, DREQ active high, DACK active low
    OUT CommandReg, 0x00
    

    Step 5: Unmask Channel

    OUT MaskReg, 0x01 (bit0=1 unmasks Ch1) or 0x01 -> using single mask: 0x01
    Actually 8237 single mask: bit2=0 -> unmask, bits1-0=01 -> Ch1 => 0x01
    

    Phase C: Initiate Transfer

    3. I/O device enabled: Disk controller programmed via its own registers (sector, drive) to be ready.
    4. Device asserts DREQ1 (when data ready)
    5. DMA asserts HRQ -> CPU responds HLDA -> CPU tristates buses (floats Address/Data/Control) -> DMA asserts AEN=1, takes bus mastership, signals HLDA to device?
    6. DMA outputs memory address on bus from CAR, asserts DACK1 to device, MEMW + IOR (for I/O->Memory) or MEMR+IOW (Memory->I/O). Data moves directly without CPU register.
    7. After each byte: CAR increment/decrement, Count decrement. Bus stays with DMA in Block mode until TC, else released per byte in Single mode.
    8. When Count = 0xFFFF (roll-over) => Terminal Count (TC) reached, DMA pulses EOP*, raises interrupt TC, deasserts HRQ, releases bus, sets Status bit.

    Phase D: Termination & CPU Resumes

    • Status Register can be polled / interrupt: CPU ISR reads status, checks TC for channel, handling completion.
    • If Auto-initialization set, registers reload original values for next block; else channel masked.
    • CPU resumes: HLDA deasserted, clears AEN, regains bus.

    5. Initialization Flow Chart

    CPU Program Start
          │
          ▼
    Disable DMA? Check Status Idle
          │
          ▼
    Write Base Address → CAR + Page Reg
          │
          ▼
    Write Block Length → CWCR
          │
          ▼
    Write Mode Reg (DIR, TYPE, MODE)
          │
          ▼
    Write Command Reg
          │
          ▼
    Unmask Channel (Enable DREQ)
          │
          ▼
    Program I/O Device registers
          │
          ▼
    Device asserts DREQ → DMA HRQ → CPU HLDA
          │
          ▼
    DMA Bus Master → Transfer (Cycle Steal/Block)
          │
          ▼
    TC? → EOP/Interrupt → CPU ISR → Done
    

    6. Transfer Modes Programmed During Init

    • Single Mode: One byte per DREQ, release bus - fair to CPU
    • Block/Burst Mode: Entire block in one HRQ - fastest
    • Demand Mode: Until DREQ deasserted - e.g. disk not ready
    • Cascade: Connect multiple controllers

    7. Example 8086 + 8237 Connection

    CPU 8237 pins: CLK, RESET, CS*, IOR*, IOW*, A0-A3, D0-D7 to bus via latch 8282/8286. HRQ to 8086 HOLD, HLDA from 8086, DREQ0-3 from peripherals, DACK0-3 back, AEN to bus controller 8288 to disable CPU addresses, ADSTB to latch high address.

    8. Importance / Advantages

    • CPU free for computation during transfer → ~10-100x faster for bulk data
    • Near memory speed transfer (limited by memory cycle + bus)
    • Essential for modern systems - integrated DMA in PCI/PCIe bus mastering, not just 8237.

    Exam Tip: Always draw block diagram + label registers + stepwise OUT sequence. For 14 marks, include both diagram, table of registers, sequence code, and timing (HRQ/HLDA handshaking).

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. Q3. Discuss Flynn’s classification of computer.201614m

    Module 3: Pipelining

    Discuss Flynn’s classification of computer.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Flynn's Classification (1966) – based on number of Instruction streams and Data streams

    Streams = sequence of instructions / data operated by CPU.

    	Single Data (SD)	Multiple Data (MD)
    Single Instruction (SI)	SISD	SIMD
    Multiple Instruction (MI)	MISD	MIMD

    1. SISD – Single Instruction Single Data

    • One control unit, one ALU, one data stream. Sequential execution (von Neumann).
    • Eg: Uniprocessor 8086, RISC, single-core CPU.
    • Instruction: $I_1 \rightarrow D_1$ then $I_2 \rightarrow D_2$ …
    • No parallelism. Performance via pipelining.

       CU ---> PU ---> Memory
        1      1      1
    

    2. SIMD – Single Instruction Multiple Data

    • One instruction stream broadcast to many processing elements (PEs), each with own data.
    • Array / Vector processors, GPU.
    • Eg: ILLIAC-IV, Vector supercomputers, MMX/SSE, GPU warps.
    • Operation: One opcode ADD executes on vectors $A[0..n]+B[0..n]$ in lockstep.

             CU
              |
       +------+------+------+
       PE     PE     PE     PE
       D1     D2     D3     D4
    

    • Exploits data parallelism, high throughput for multimedia, matrix ops. Requires synchronous control.

    3. MISD – Multiple Instruction Single Data

    • Many instructions operate on same data stream. Rare / theoretical.
    • Eg: Systolic arrays, fault-tolerant systems where same data through different algorithms ($N$-version programming), pipeline MISD interpretation: successive stages apply different operations on same data flowing through.
    • No commercial general MISD.

      CU1 ---> PU1 --\
      CU2 ---> PU2 ---> same Data stream (pipelined)
      CU3 ---> PU3 --/
    

    4. MIMD – Multiple Instruction Multiple Data

    • Multiple autonomous processors each with own instruction and data stream. Most general, multiprocessors / multicomputers.
    • Two subclasses:
      • Tightly coupled / Shared memory (SMP, multi-core): All CPUs share common RAM via bus/crossbar. Eg: Intel i7 quad-core, Xeon.
      • Loosely coupled / Distributed memory (message passing): Each node has private memory, communicates via network. Eg: Clusters, supercomputers (Beowulf).

      CU1->PU1->M1 \
      CU2->PU2->M2 ---> Interconnection Network
      CU3->PU3->M3 /
    

    • Exploits task parallelism, true concurrency, scales (but needs synchronization, coherence).

    Summary Table

    Type	#CU	#PU	Use	Example	Parallelism
    SISD	1	1	General	8086, ARM single	ILP only
    SIMD	1	N	Vector	GPU, AVX	Data
    MISD	N	1	Special	Systolic, fault-tolerant	Rare
    MIMD	N	N	General parallel	Multi-core, Cluster	Task/Data

    Extended taxonomies: SPMD (Single Program Multiple Data – subset of MIMD), MPMD. Modern machines are hybrid: MIMD of SIMD cores (multi-core GPU).

    Diagram: All 4 types [SISD = single lane, SIMD = single instruction fan-out, MISD = multiple instr single data pipeline, MIMD = multiple independent lanes].

13. Q4. What is associative memory? Explain with the help of a block diagram. Also mention the situation in which associative memory can be effectively utilized.201614m

    Module 4: Memory Organization

    What is associative memory? Explain with the help of a block diagram. Also mention the situation in which associative memory can be effectively utilized.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Associative Memory (Content Addressable Memory - CAM)

    Definition: Memory accessed by content (data) rather than by address. CPU supplies a search word (key); memory simultaneously compares it with all stored words in parallel and marks those that match. Access time is constant $O(1)$ irrespective of location. Opposite of Random Access Memory (RAM) where $address \rightarrow data$.

    Also called Associative Storage / Content Addressable Memory.

    Block Diagram

                       +-----------------------------+
    Search Word (Argument) -->| Argument Register (A)     |
      (key + mask)     |   Key Register (K)  Mask (M) |
                       +-------------+---------------+
                                     | (unmasked bits)
                                     v
                       +-----------------------------+
                       | Associative Memory Array    |  Word0: bit0..bit n + Match logic
                       |  Word1  } each with         |  Word1:  comparator (XNOR per bit)
                       |  ...    } comparison logic  |  ...     + AND of bits
                       |  Wordm  }                   |
                       +-------------+---------------+
                                     | Match lines Mi (Mi=1 if word i matches A on K=1 bits)
                                     v
                       +-----------------------------+
                       | Encoder / Priority or       |
                       | Match Register + Selector   |----> Matched word(s) out
                       +-----------------------------+
    

    • Argument Register A: holds search key.
    • Key Register K: 1 means compare that bit, 0 = don't care (maskable).
    • Mask Register M (optional): disables masked bits.
    • Match Logic per word: $M_i = \bigwedge_{j: K_j=1} (A_j \oplus \text{Word}_{ij})'$ =1 only if all unmasked bits equal.
    • Output is either first matching word (priority encoder) or all matches flagged.

    Operation: Load $A$ and $K$, assert search, all words compare in parallel (one clock), $M_i$ vector produced, encoder outputs address/data of matched word. Write modifies matched word(s).

    Example: 4 words 1010, 1100, 1011, 0010; search $A=1010$, $K=1110$ (don't care LSB) => matches word0 (1010) and word2 (1011).

    Cost & Characteristics

    • Fast search $O(1)$ but hardware heavy: comparator per bit per word => $m \times n$ XNOR gates. Expensive, power hungry, so used small.
    • Word size typically 16-64 bits, capacity $32$ to $4K$ words.

    Effective Utilization

    1. Cache Memory / TLB (Translation Lookaside Buffer): Most important use. Fully associative cache / TLB stores block tags; CPU searches tag in parallel to find hit/miss without set indexing. E.g. TLB maps virtual page -> physical frame: associative lookup of VPN yields PPN in one cycle.

    2. Virtual Memory Page Table Cache: Hardware search of page table.

    3. Database / Pattern Matching: Search records by field (e.g. find all employees with age=30) without scanning.

    4. Networking: Router's forwarding table, packet classification, firewall ACLs, Ethernet switch MAC lookup, IP longest prefix match -> ternary CAM (TCAM) with don't-care.

    5. AI / Fault tolerance: Associative recall, spare memory remapping.

    In COA syllabus: used to implement fully associative cache and TLB where hit time must be minimal; otherwise direct-mapped is cheaper. Hybrid set-associative + CAM for tags is practical trade-off.

14. Q5. Discuss the different ways in which ROM can be programmed.201614m

    Module 4: Memory Organization

    Discuss the different ways in which ROM can be programmed.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Different Ways ROM Can Be Programmed

    ROM (Read Only Memory) programming refers to how data is written into ROM. Based on programmability and erasability, types are:

    1. Mask Programmed ROM (MROM)

    • When programmed: At time of manufacturing by manufacturer using photographic mask.
    • Mechanism: Transistor connections at crosspoints defined by mask. Presence/absence of transistor = 1/0.
    • Features: Non-field programmable, cheapest per unit in mass production but high setup cost, 100% non-erasable.
    • Use: Firmware, character generators, microcode where volume high and code never changes.

    2. PROM (Programmable ROM) - One Time Programmable (OTP)

    • Mechanism: Manufactured as all 0s/1s with fusible NiCr links at each bit. User programs with PROM programmer which applies high current pulse (20-50mA, ~10-12V) to blow fuses for desired bits.
    • Process: Address selected -> data applied -> programming pulse for each word.
    • Features: Field programmable once, cannot be erased; if mistake chip discarded.

    3. EPROM (Erasable PROM)

    • Uses FAMOS transistors with floating gate storing charge.
    • Programming: Electrical - with EPROM programmer, apply Vpp ~21-25V pulse to inject hot electrons into floating gate via avalanche. 0 = charged, 1 = uncharged.
    • Erasing: UV light (~253.7nm) through quartz window for 15-20 min erases entire chip by photoelectric discharge. Then reprogrammable (typically ~1000 cycles).
    • Types: UV-EPROM

    4. EEPROM (Electrically Erasable PROM) / E²PROM

    • Uses FLOTOX/ MNOS structure with thin oxide allowing Fowler-Nordheim tunneling.
    • Programming & Erasing: Both electrically - no UV, no removal from circuit. Byte/word erasable using ~20V internal charge pump.
    • Features: ~10^4-10^5 cycles, slower write (ms vs ns read), more expensive per bit due to 2 transistor per cell.

    5. Flash Memory (Advanced EEPROM)

    • Bulk/ sector erase instead of byte erase using same tunneling.
    • Programming: Electrical with on-chip charge pump. Erase entire block at once (~1s), program byte/page wise.
    • Features: High density, in-system programmable, ~10^5-10^6 cycles, used in SSD, pen drives, BIOS.

    Summary Table:

    Type	Programmability	Erasability	Volatility
    MROM	Factory mask only	No	Non-volatile
    PROM	Once by user (fuse)	No	Non-volatile
    EPROM	User, electrical	UV whole chip	Non-volatile
    EEPROM	User, electrical byte-wise	Electrical byte-wise	Non-volatile
    Flash	User, electrical sector-wise	Electrical block-wise	Non-volatile

    For exam, diagram of ROM array with row/column decoders and fuse/ floating gate cell should be drawn.

15. Q6. What is meant by pipelining? Why do we require instruction pipelining? Explain its working procedure. Discuss the pipeline performance measures.201614m

    Module 3: Pipelining

    What is meant by pipelining? Why do we require instruction pipelining? Explain its working procedure. Discuss the pipeline performance measures.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Pipelining

    1. Definition

    Pipelining is an implementation technique where multiple instructions are overlapped in execution, analogous to an assembly line. Each instruction is split into $k$ sequential stages; different stages of successive instructions execute concurrently using separate hardware resources.

    Ideally $k$-stage pipeline can execute $k$ instructions simultaneously and achieve speedup $\approx k$.

    2. Why Require Instruction Pipelining?

    • Performance without increasing clock rate: Single-cycle CPU has long critical path (IF+ID+EX+MEM+WB). Pipelining breaks it into shorter stages -> higher clock frequency and throughput.
    • Exploit Instruction-Level Parallelism (ILP): Sequential model wastes hardware when one unit is active, others idle. Pipelining keeps all units busy.
    • CPI approaches 1: Without pipeline CPI = 1 (single-cycle) but long $T_{clk}$ or CPI >1 (multi-cycle). With pipeline, throughput = 1 instruction/cycle in steady state.
    • Cost-effective speedup: No need for multiple CPUs; just pipeline registers.

    3. Working Procedure (5-stage Classic RISC Pipeline)

    Stages:

    1. IF - Instruction Fetch: IR <- M[PC]; PC <- PC+4
    2. ID - Instruction Decode/Register Fetch: decode opcode, read $Rs,Rt$, generate immediates.
    3. EX - Execute/ALU: ALU operation or effective address ALUout <- Rs op Rt or Rs + imm
    4. MEM - Memory Access: MDR <- M[ALUout] for LOAD or M[ALUout] <- Rt for STORE
    5. WB - Write Back: Rd <- ALUout or Rd <- MDR

    Pipeline registers between stages: IF/ID, ID/EX, EX/MEM, MEM/WB isolate stages.

    Timing diagram (no hazards, 5 instructions):

    Cycle:  1    2    3    4    5    6    7    8
    I1:    IF | ID | EX | MEM| WB |
    I2:         IF | ID | EX | MEM| WB |
    I3:              IF | ID | EX | MEM| WB |
    I4:                   IF | ID | EX | MEM| WB |
    I5:                        IF | ID | EX | MEM| WB |
    

    After 5 cycles (fill), one instruction completes per cycle.

    Non-pipelined: 5 cycles per instruction sequentially -> 25 cycles for 5 instr. Pipelined: 9 cycles.

    Hazards (practical issues)

    • Structural: two instr need same resource (e.g., single memory for IF and MEM) - solve by separate I/D caches.
    • Data hazard: I2 needs result of I1 (RAW) - forward/bypass or stall (bubble).
    • Control hazard: branch target unknown until ID/EX - flush pipeline, branch prediction.

    4. Pipeline Performance Measures

    Let $k$ = stages, $t_p$ = time per stage, $t_{latch}$ = latch overhead, $n$ = number of instructions.

    • Clock period: $T_{clk,pipelined}= \max(t_i) + t_{latch}$ vs $T_{clk,non-piped}= \sum t_i$

    • Time for n instructions:
      $T_{non-pipe}= n \cdot k \cdot t_p$
      $T_{pipe}= k\cdot t_p + (n-1)\cdot t_p = (k+n-1)t_p$ (ideal)

    • Speedup: $S = \frac{T_{non-pipe}}{T_{pipe}} = \frac{n k}{k+n-1}$. For $n \gg k$, $S \to k$ (ideal).
      With overhead: $S = \frac{k t_p}{t_p + t_{latch}} \cdot \frac{n}{n+k-1}$

    • Efficiency: $\eta = \frac{S}{k} = \frac{n}{k+n-1}$ . For large $n$, $\eta \to 1$.

    • Throughput: $W = \frac{n}{T_{pipe}} = \frac{1}{t_p}$ instr/sec in steady state (vs $\frac{1}{k t_p}$ non-piped). $n/(k+n-1)t_p$.

    • CPI: Ideal CPI = 1, effective CPI = $1 + stalls/instr$ (due to hazards).

    • Example: $k=5$, $t_p=2ns$, $n=100$: $T_{non}=1000ns$, $T_{pipe}= (5+99)*2=208ns$, $S=4.8$, $\eta=96\%$.

    Pipeline improves throughput, not single-instruction latency (latency stays $k t_p$). Maximum speedup limited by stage imbalance, latches, and hazards.

16. Q7. A virtual memory system has an address space of 8k words, memory space of 4k words and page & block size of 1k words. The following page reference changes occur during a given time interval: 4, 2, 0, 1, 2, 6, 1, 4, 0, 1, 0, 2, 3, 5, 7 Determine the four pages that are resident in main memory after each page reference change if the replacement algorithm used is - (i) FIFO - (ii) LRU.201614m

    Module 4: Memory Organization

    A virtual memory system has an address space of 8k words, memory space of 4k words and page & block size of 1k words. The following page reference changes occur during a given time interval:

    4, 2, 0, 1, 2, 6, 1, 4, 0, 1, 0, 2, 3, 5, 7
    Determine the four pages that are resident in main memory after each page reference change if the replacement algorithm used is

    • (i) FIFO
    • (ii) LRU.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Address space $8K=2^{13}$, memory $4K$, page $1K \Rightarrow 8$ virtual pages (0-7), $4$ page frames. Reference string length $15$:

    $$4,2,0,1,2,6,1,4,0,1,0,2,3,5,7$$

    Table shows resident set after each reference. F = page fault.

    (i) FIFO - evict oldest loaded page

    Ref	Hit/Fault	Resident set (4 frames)	Evicted	FIFO queue (oldest→newest)
    4	F	4, -, -, -	-	[4]
    2	F	4, 2, -, -	-	[4,2]
    0	F	4, 2, 0, -	-	[4,2,0]
    1	F	4, 2, 0, 1	-	[4,2,0,1]
    2	Hit	4, 2, 0, 1	-	[4,2,0,1]
    6	F	6, 2, 0, 1	4	[2,0,1,6]
    1	Hit	6, 2, 0, 1	-	[2,0,1,6]
    4	F	6, 4, 0, 1	2	[0,1,6,4]
    0	Hit	6, 4, 0, 1	-	[0,1,6,4]
    1	Hit	6, 4, 0, 1	-	[0,1,6,4]
    0	Hit	6, 4, 0, 1	-	[0,1,6,4]
    2	F	6, 4, 2, 1	0	[1,6,4,2]
    3	F	6, 4, 2, 3	1	[6,4,2,3]
    5	F	5, 4, 2, 3	6	[4,2,3,5]
    7	F	5, 7, 2, 3	4	[2,3,5,7]

    • Faults $=10$, Hits $=5$, Hit ratio $5/15=33.3\%$.
    • Final resident pages {2,3,5,7}.

    (ii) LRU - evict least recently used

    Maintains recency; on hit update timestamp.

    Ref	Hit/Fault	Resident set	Evicted (LRU)
    4	F	4, -, -, -	-
    2	F	4, 2, -, -	-
    0	F	4, 2, 0, -	-
    1	F	4, 2, 0, 1	-
    2	Hit	4, 2, 0, 1	- (2 MRU)
    6	F	6, 2, 0, 1	4 (LRU)
    1	Hit	6, 2, 0, 1	- (1 MRU)
    4	F	6, 2, 4, 1	0 (LRU, not used since time 3)
    0	F	6, 0, 4, 1	2 (LRU)
    1	Hit	6, 0, 4, 1	-
    0	Hit	6, 0, 4, 1	-
    2	F	2, 0, 4, 1	6 (LRU)
    3	F	2, 0, 3, 1	4 (LRU)
    5	F	2, 0, 3, 5	1 (LRU)
    7	F	2, 7, 3, 5	0 (LRU)

    • Faults $=11$, Hits $=4$, Hit ratio $26.7\%$.
    • Final resident pages {2,3,5,7} (same final set but different intermediate eviction order; LRU has one extra fault).

    Note for this string FIFO outperforms LRU by 1 fault - shows FIFO not always worse, but LRU generally avoids Belady's anomaly and is stack-optimal.

17. Q8. Explain the Strobe Control method of asynchronous data transfer. What are the disadvantages of this method?201614m

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

    Explain the Strobe Control method of asynchronous data transfer. What are the disadvantages of this method?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Asynchronous Data Transfer - Strobe Control

    In asynchronous transfer source and destination use different clocks; data transfer is coordinated by a control signal called strobe - a single pulse that validates data.

    1. Source-Initiated Strobe:
    Source places data on data bus and after a brief delay (to allow data to settle) asserts STROBE. Destination on detecting strobe, captures data; data must remain valid while strobe is active.

    Timing: Data valid → Strobe ↑ → Destination loads data → Strobe ↓ → Data invalid

    2. Destination-Initiated Strobe:
    Destination asserts strobe to request data; source on detecting strobe places data on bus. Destination captures data when source indicates data valid.

    Block diagram: Source (Data + Strobe line) → Data Bus → Destination with strobe line directly connecting control.

    Disadvantages

    1. No Handshake / No Acknowledgement: Source strobes without knowing if destination received data or was ready. If destination not ready or strobe delayed/ distorted, data is lost.
    2. Timing Critical: Correct operation depends on accurate delay - data must be stable before strobe reaches destination. Variation in bus length, gate delays, or clock skew can violate setup/hold time.
    3. Susceptible to Noise: Single pulse can be corrupted; no error detection.
    4. No Flow Control: Cannot handle speed mismatch; fast source can overrun slow destination.
    5. Not Suitable for Long Distances: Strobe and data propagation delays differ.

    Hence Handshaking method (using STROBE + ACK / REQ + ACK) is preferred which provides interlocked feedback and eliminates timing constraints at cost of an extra signal and longer transfer time.

18. Q9a. Write short notes on the following: - (a) Shift instructions20167m

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

    Write short notes on the following:

    • (a) Shift instructions

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Shift Instructions [7M]

    Shifts move bits left/right within register/word. Crucial for scaling (multiply/divide by $2^k$), bit manipulation, floating point normalization, I/O serialization.

    Types:

    1. Logical Shift:
    Vacated bits filled with 0. Used for unsigned numbers.

    • SHL / LSL Logical Shift Left: C <- b_{n-1} ... b0 <- 0 . E.g. 01010111 <<1 = 10101110, carry out =0. Equivalent to *2 (unsigned).
    • SHR / LSR Logical Shift Right: 0 -> b_{n-1} ... b0 -> C. E.g. 10110011 >>2 = 00101100. Equivalent to unsigned /4.
      Example x86: SHL AX,1 , SHR BX, CL (CL = count).

    2. Arithmetic Shift:
    Preserves sign (for signed 2's complement).

    • SAL = SHL (same for left).
    • SAR Arithmetic Shift Right: vacated left bits filled with sign bit (MSB replicated). 1XXXX -> 11XXX. E.g. 11100100 (-28) SAR 1 = 11110010 (-14) correctly divides by 2. 01000000 (64) SAR1 =00100000 (32). LSR would give incorrect negative.

    • Arithmetic left shift: sign bit not replicated; overflow checked via V flag if sign changes.

    3. Circular / Rotate (no loss):
    Bits that fall off are wrapped around.

    • ROL Rotate Left: b_{n-1} -> b0 and -> Carry. ROR opposite. E.g. 10001111 ROL1 =00011111.
    • RCL/RCR Rotate through Carry: Includes carry in loop (9-bit rotation for 8-bit reg). Used for multi-precision shifts: RCL propagates carry across words.
    • Used for cryptography, bit extraction.

    Hardware: Barrel shifter - combinational $n \times \log n$ mux network can shift any $k$ (0..n-1) in single cycle vs sequential shift register ($k$ cycles).

    Applications & Examples:

    • Multiplication/Division by power of 2: X *8 = SLL X,3 much faster than MUL. X/8 = SAR X,3 (signed).
    • Example 8-bit: 00001101 (13) <<2 =00110100 (52)=13*4 .
    • Multiplication of $14 *5$: 14 <<2 +14 = 56+14=70 without multiplier.
    • Normalization: Floating addition requires align exponents via right shift of mantissa.
    • Field extraction: MOV AL,mask; AND; SHR.

    Flags: Shift updates C (last bit out), Z,S,P, arithmetic checks V/O.

    Summary table:

    Type	Fill	Use
    LSL/SHL	0	Unsigned *$2^k$
    LSR	0	Unsigned /$2^k$
    ASR/SAR	sign	Signed /$2^k$
    ROL/ROR	wrap	Rotate

    Modern ISAs provide SHL, SHR, SAR, ROL, ROR, RCL, RCR, SHLD/SHRD (double precision shift).

19. Q9b. Write short notes on the following: - (b) Daisy chaining priority20167m

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

    Write short notes on the following:

    • (b) Daisy chaining priority

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Daisy Chaining Priority (Daisy Chain Interrupt Arbitration) [7M]

    Context: When multiple I/O devices share single interrupt line ($INTR$) to CPU, need to decide priority if several request simultaneously. Daisy chain is hardware serial priority method.

    Structure:

    Devices connected in series like chain. CPU's Interrupt Acknowledge ($INTA$ / $BG$ - Bus Grant) propagates serially.

    CPU INTA (BG) ----> Device1 --BGout--> Device2 --BGout--> Device3 ---->
             ^           |                 |                 |
             +-----------+-----------------+-----------------+---- INTR (wired-OR) to CPU
    

    Each device has Interrupt Request (IR) and Priority In / Priority Out.

    • Device generates $IR$ when needs service.
    • $INTR = IR1\ OR\ IR2\ OR\ ...$ -> to CPU.
    • CPU responds with $INTA=1$ (daisy chain enable) when ready to serve.

    Logic per device:

    if IR=1 and PriorityIn=1  =>  PriorityOut=0, acquire bus, put vector on bus, block downstream
    else PriorityOut = PriorityIn
    

    Propagation: $PriorityIn_{i+1} = PriorityOut_i = PriorityIn_i \cdot \overline{IR_i}$

    Thus highest physical position gets highest priority (closest to CPU). Need to insert higher priority devices nearer CPU.

    Operation Sequence:

    1. Device 2 and 3 request simultaneously: $IR2=IR3=1$, $INTR=1$ -> CPU finishes current instruction, saves PC/PSW, disables further interrupts.
    2. CPU asserts $INTA$. Device1 $PriorityIn=1$ but $IR1=0$, so passes $PriorityOut=1$ to Device2.
    3. Device2 sees $PriorityIn=1$ and $IR2=1$ -> blocks propagation ($PriorityOut=0$), puts its interrupt vector address on data bus, clears IR.
    4. Device3 sees $PriorityIn=0$ -> cannot respond even though $IR3=1$, waits for next INTA.
    5. CPU reads vector, jumps to ISR for Device2.

    Advantages:

    • Simple: 1 INTR + 1 INTA lines, no encoder. Easy to add devices (plug into chain).
    • No separate priority encoder. Software can poll via vector.

    Disadvantages:

    • Priority fixed by position - re-wiring needed to change priority.
    • Propagation delay linear in $n$ - limits number of devices ($t_{ack}= n \cdot t_{gate}$). Fail in one device breaks chain unless bypass logic.
    • Starvation of low priority devices.

    Variants:

    • Parallel priority encoder (8259 PIC) solves delay via hardware priority resolver.
    • Polling alternative: CPU polls each device SR via software (flexible priority but slower).

    Example use: Unibus, Intel Multibus Bus Grant ($BPRN/BPRO$), SPI devices with daisy chain.

    Contrast: Independent request (each device has separate IR line) allows programmable priority but needs $n$ lines. Daisy chain trades flexibility for wiring simplicity.