2019 question paper

COMPUTER ORGANIZATION & ARCHITECTURE

25 questions

1. Q1a. How many 128×8 bit RAMs are required to design 32 k x 32 bit RAM? - (i) 512 - (ii) 128 - (iii) 1024 - (iv) 3220192m

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

   How many 128×8 bit RAMs are required to design 32 k x 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:
   Required: $32K \times 32$ bit. Chip: $128 \times 8$ bit.

   • Depth factor: $32K/128 = 32768/128 = 256$
   • Width factor: $32/8 = 4$
   • Total = $256 \times 4 = 1024$ chips.

   Same as Q181.

2. Q1b. The intradata transfer techniques are implemented using - (i) serial I/O - (ii) parallel 1/0 - (iii) Both (i) and (ii) - (iv) Neither (i) nor (ii)20192m

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

   The intradata transfer techniques are implemented using

   • (i) serial I/O
   • (ii) parallel 1/0
   • (iii) Both (i) and (ii)
   • (iv) Neither (i) nor (ii)

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Correct option: (iii) Both serial and parallel I/O

   Note: Question prints intradata due to typo; read as intra-data / data transfer.

   The I/O subsystem can transfer data either:

   • Serial I/O - one bit at a time over single line, or
   • Parallel I/O - multiple bits simultaneously over parallel lines.

   Modern interfaces support both. Hence option (iii) is correct.

3. Q1b. (b) How is virtual memory managed using paging and TLB? Explain with suitable example.20197m

   Module 4: Memory Organization

   (b) How is virtual memory managed using paging and TLB? Explain with suitable example.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Virtual Memory, Paging and TLB

   Virtual Memory: Technique that allows execution of program larger than physical main memory by using disk (swap) as extension. CPU generates virtual/logical address, translated by MMU to physical address. Gives programmer illusion of large contiguous memory and provides isolation/protection.

   Paging: Virtual and physical memory divided into fixed equal blocks - pages (virtual) and frames (physical), e.g. 4KB. Virtual address = [Virtual Page Number (VPN) | Offset]. Page Table stores mapping VPN -> Frame No. + valid/dirty/protection bits. On page fault (valid=0), OS brings page from disk, updates table.

   Example: 32-bit virtual addr, 4KB pages (offset 12 bits). VA = 0x00403ABC -> VPN = 0x00403, Offset=0xABC. Page Table[0x00403]= Frame 0x00A -> PA=0x00AABC.

   TLB - Translation Lookaside Buffer: Small, fully-associative high-speed cache of recently used Page Table Entries inside MMU.

   • TLB Hit: VPN found in TLB -> frame number returned in ~1 cycle, no memory access.
   • TLB Miss: Search page table in memory (or walk), load entry into TLB, may cause page fault.

   Effective Access Time: $EAT = h \cdot (c+ m) + (1-h)(c+2m)$ where $h$= hit ratio, $c$= TLB time, $m$= memory time. With $h \approx 98\%$, EAT $\approx$ memory speed. TLB greatly reduces translation overhead. Replacement via LRU/random, flush on context switch.

4. Q1c. In case of pipelining processor, loop buffer is * (i) very high speed memory maintained by the instruction fetch stage * (ii) very high speed memory maintained by the instruction decode stage * (iii) very high speed memory maintained by the instruction execute stage * (iv) None of the above20192m

   Module 3: Pipelining

   In case of pipelining processor, loop buffer is

   • (i) very high speed memory maintained by the instruction fetch stage
   • (ii) very high speed memory maintained by the instruction decode stage
   • (iii) very high speed memory maintained by the instruction execute stage
   • (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Correct option: (i) High-speed memory at fetch stage (Loop Buffer)

   Loop buffer is a small, very high-speed memory at the instruction fetch stage that stores recently fetched instruction sequence of a loop. On loop repetition, instructions are fetched directly from buffer instead of main memory/cache, reducing fetch time and memory traffic. Hence answer is (i).

5. Q1c. The sequence of events that happen during a typical fetch operation is - (i) PC → MAR → Memory → MDR → IR - (ii) PC → Memory → MDR → IR - (iii) PC → Memory → IR - (iv) PC → MAR → Memory → IR20197m

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

   The sequence of events that happen during a typical fetch operation is

   • (i) PC → MAR → Memory → MDR → IR
   • (ii) PC → Memory → MDR → IR
   • (iii) PC → Memory → IR
   • (iv) PC → MAR → Memory → IR

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) PC → MAR → Memory → MDR → IR

   Typical Instruction Fetch Cycle (Fetch sequence) is:

   1. PC → MAR: Program Counter holds address of next instruction. Its content is transferred to Memory Address Register (MAR).
   2. MAR → Memory: MAR puts address on address bus, control unit issues READ.
   3. Memory → MDR: Instruction word read from memory is loaded into Memory Data Register (MDR) / MBR.
   4. MDR → IR: Instruction is then transferred to Instruction Register (IR) for decoding. Meanwhile PC is incremented (PC+1) to point to next instruction.

   This is the standard von Neumann fetch path. Options (ii)-(iv) skip MAR or MDR and are incomplete.

   Correct option: (i) PC → MAR → Memory → MDR → IR

6. Q1e. The average memory access time for a machine with a cache hit rate of 90% where the cache access time is 10 ns and the memory access time is 100 ns is * (i) 55 ns * (ii) 45 ns * (iii) 90 ns * (iv) 19 ns20192m

   Module 4: Memory Organization

   The average memory access time for a machine with a cache hit rate of 90% where the cache access time is 10 ns and the memory access time is 100 ns is

   • (i) 55 ns
   • (ii) 45 ns
   • (iii) 90 ns
   • (iv) 19 ns

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) 19 ns

   Average memory access time (hierarchical access: check cache first, go to memory only on miss):

   $$T_{avg} = h \cdot T_c + (1-h)\cdot T_m$$

   Given hit rate $h = 90\% = 0.9$, $T_c = 10$ ns, $T_m = 100$ ns:

   $$T_{avg} = 0.9 \times 10 + 0.1 \times 100 = 9 + 10 = 19 \text{ ns}$$

   If counting $T_c + T_m$ on miss (simultaneous vs hierarchical variants), then $0.9 \times 10 + 0.1 \times 110 = 20$ ns — but with given options, 19 ns is the expected answer.

   Correct option: (iv) 19 ns

7. Q1f. The minimum time delay between the initiations of two independent memory operations is called * (i) access time * (ii) cycle time * (iii) transfer rate * (iv) latency time20192m

   Module 4: Memory Organization

   The minimum time delay between the initiations of two independent memory operations is called

   • (i) access time
   • (ii) cycle time
   • (iii) transfer rate
   • (iv) latency time

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) Cycle time

   • Access time = time between initiation of read/write operation and completion (data available).
   • Cycle time = minimum time delay between initiations of two successive independent memory operations. It = access time + recovery/recharge time needed for memory to recover before next access (e.g., DRAM precharge).
   • Always cycle time ≥ access time.

   Hence delay between initiations of two independent operations is cycle time. So option (ii) cycle time is correct. Other options: transfer rate = bytes/sec, latency = delay to first bit.

8. Q1g. In case of vectored interrupt, interrupt vector means * (i) the branch information from the source which interrupts the system * (ii) an address that points to a location in memory where the beginning address of the I/O service routine is stored * (iii) Both (i) and (ii) * (iv) None of the above20192m

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

   In case of vectored interrupt, interrupt vector means

   • (i) the branch information from the source which interrupts the system
   • (ii) an address that points to a location in memory where the beginning address of the I/O service routine is stored
   • (iii) Both (i) and (ii)
   • (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) an address that points to a location in memory where the beginning address of the I/O service routine is stored

   Vectored Interrupt: Device supplies the interrupt vector – a pointer/index. The vector is an address (or index into Interrupt Vector Table) that points to the starting address of the ISR (Interrupt Service Routine).

   • Interrupt Vector Table (IVT) holds ISR addresses.
   • On interrupt, CPU uses vector to fetch ISR address and jumps directly – no polling/search needed. Fastest identification.
   • Contrasts with non-vectored where CPU must poll to find source.

   So correct is (ii). Option (i) is vague/branch info – not correct; (iii) includes wrong (i), so false. Hence (ii) only.

9. Q1i. A microprogrammed 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 microprocessor20192m

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

   A microprogrammed 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

   Correct option is (ii).

   Explanation:
   A microprogrammed control unit generates control signals from microinstructions stored in a Control Memory (control store). Each machine instruction is executed as a sequence of micro-operations defined by firmware.

   • Why (ii) is correct: To add a new instruction, only the microprogram in control memory needs to be modified/extended. No hardware rewiring is required, so implementation of new instructions, complex CISC instruction sets, and design changes is flexible and easy. It also simplifies debugging via microcode changes.

   • Why other options are wrong:

     • (i) is faster: False. Hardwired CU using combinational logic (gates, encoders) is faster because microprogrammed CU requires fetch of microinstruction from control memory. Microprogrammed is slower.
     • (iii) useful when every small program is to be run: Irrelevant. Control unit type has no relation to running small user programs.
     • (iv) usually refers to CU of microprocessor: False. Both types can be used in microprocessors; this is not a definition.

   Hence microprogrammed CU trades speed for flexibility and ease of modification.

10. Q1j. Which of the following holds data and processing instructions temporarily until the CPU needs it? * (i) ROM * (ii) Control unit * (iii) Main memory * (iv) Coprocessor chip20192m

    Module 1: Functional Block of computer and Data representaion

    Which of the following holds data and processing instructions temporarily until the CPU needs it?

    • (i) ROM
    • (ii) Control unit
    • (iii) Main memory
    • (iv) Coprocessor chip

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: (iii) Main memory

    Explanation:
    Main Memory (Primary Memory / RAM) holds both data and instructions temporarily while CPU processes them. CPU fetches instructions and operands from main memory into registers, executes, and writes results back. It is volatile, provides fast random access to the active program and data.

    • Why (iii) is correct: In von Neumann architecture, main memory is the working store - it contains the currently executing program, intermediate data, and results until needed. Its contents are directly addressable by CPU via MAR/MDR.

    • Why others are incorrect:

      • (i) ROM: Non-volatile, read-only, holds firmware/BIOS permanently, not temporary processing data/instructions.
      • (ii) Control Unit: Generates control signals and decodes instructions; does not store user data/instructions.
      • (iv) Coprocessor chip: Auxiliary processor (e.g., 8087 floating-point coprocessor) for specialized computation, not storage.

    Hence the unit that temporarily buffers code and data for CPU is main memory (RAM).

11. Budget App•POCKETLY

    Pocketly on Android

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

    Install Pocketly
12. Q2a. How do instruction set, compiler technology, CPU implementation and control, and cache and memory hierarchy affect the CPU performance? Justify the effects in terms of program length, clock rate and effective CPI.20197m

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

    How do instruction set, compiler technology, CPU implementation and control, and cache and memory hierarchy affect the CPU performance? Justify the effects in terms of program length, clock rate and effective CPI.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Effect of Instruction Set, Compiler, CPU Implementation, Cache/Memory Hierarchy on CPU Performance - CPI Analysis (7M)

    Fundamental Performance Equation

    $CPU_{time} = IC \times CPI \times T_{c} = IC \times CPI / f$

    Where $IC$ = dynamic Instruction Count, $CPI$ = cycles per instruction (average, effective), $f$ = clock frequency, $T_c$ = clock period.

    Also $MIPS = f / (CPI \times 10^6)$; $CPI_{effective} = \sum_i (CPI_i \times F_i) + Stall_{memory}+Stall_{pipeline}$ ; with memory: $CPI = CPI_{base} + MissRate \times MissPenalty$.

    Every factor influences one or two of those three terms; optimal performance balances them.

    1. Instruction Set Architecture (ISA) Effect

    ISA defines operations, formats, addressing modes, registers.

    • Program Length (IC):

      • CISC (x86): Complex instructions (REP MOVS, MUL, CALL) do more work per instruction => fewer instructions ($IC$ down) but longer and variable-length (1-15 bytes) => higher $CPI$ per instruction (5-12). Code dense, good for small memory.
      • RISC (ARM, MIPS): Simple load-store, fixed 4-byte, 3-operand => more instructions needed to do same task ($IC$ up ~30%) but each executes in 1 cycle ideal, easy pipelining.

      Example: Memory copy: x86 REP MOVSB = 1 instruction; MIPS needs loop: LW, SW, ADDI, BNE = 4 instructions. IC difference.

    • Clock Rate ($f$):

      • CISC decode complex → longer critical path → lower max $f$. RISC decode trivial → higher $f$ (can pipeline deeper).

    • Effective CPI:

      • ISA determines $CPI_i$ per instruction class. Variable CISC CPI varies widely; RISC keeps near 1 (plus load-use stalls). Also ISA addressing mode complexity adds extra µ-cycles.

    Trade-off: $IC \downarrow$ vs $CPI \uparrow$ and $f \downarrow$.

    2. Compiler Technology Effect

    Compiler maps high-level code to ISA sequence; determines actual $IC$, instruction mix $F_i$, and how well CPI hides hazards.

    • IC:

      • Optimization -O2 removes dead code, common subexpression elimination, loop unrolling, inlining → $IC \downarrow$ 10-50%.
      • Poor code: extra spills, redundant loads → $IC \uparrow$.

    • CPI:

      • Instruction scheduling: Reorders to avoid RAW stalls, fills branch delay slots, uses forwarding effectively → stalls ↓ → $CPI_{effective} \downarrow$ from 1.5 to 1.1 (30% gain).
      • Register allocation: Keeps variables in registers → fewer loads/stores (memory CPI high) → $CPI \downarrow$ and $IC$ of memory ops ↓.
      • Choice of instructions: Uses cheap sequences (shift instead of multiply by 8) → $CPI_i$ lower.

    • Clock Rate: Little direct effect, but better code may allow better branch prediction locality.

    Example: Without scheduling: LW R1; ADD R2,R1 → 1 stall; scheduled: insert independent instruction between → 0 stalls → CPI saved.

    3. CPU Implementation & Control Effect

    Implementation is microarchitecture realizing same ISA (e.g., 486 vs Pentium for same x86 ISA).

    • Clock Rate ($f$):

      • Technology: Smaller transistor, deeper pipeline (15-20 stages) enables higher $f$ (3 GHz vs 100 MHz).
      • Control: Hardwired CU → faster decode → higher $f$; microprogrammed → lower $f$ but more complex instruction support.

    • CPI:

      • Pipelining: Converts $CPI$ from ~5 (non-pipelined multicycle) to ~1 + stall; $Speedup \approx n_{stages}$.
      • Superscalar / Superpipelined: Issue 2-8 instructions per cycle → $CPI <1$ (IPC >1). E.g., 4-wide processor can have $CPI_{effective}=0.25$.
      • Hazards & Stalls: Deeper pipeline increases branch mispredict penalty (15 cycles vs 3) → CPI penalty up if prediction poor.
      • Multicycle vs Single-cycle: Single-cycle CPU $CPI=1$ but long $T_c$ (slowest instr), multicycle average $CPI=3-4$ but short $T_c$ plus pipeline gives best both.

    Equation with pipeline: $T_c = max(T_{stage}) + T_{latch}$. Better implementation reduces $T_{stage}$ variance.

    • IC: Generally none (same ISA → same dynamic instruction count if ignoring micro-ops). But micro-op translation (x86 translates 1 CISC to 2-4 RISC µops) can affect internal IC count but not programmer visible IC.

    Result: Implementation trades $CPI$ ↔ $f$. e.g., Deep pipeline: $f \uparrow 2x$ but branch miss CPI penalty rises, golden point exists.

    4. Cache and Memory Hierarchy Effect

    Memory hierarchy bridges CPU (ns) ↔ DRAM (100 ns) gap; determines stall component of CPI.

    • Clock Rate: Cache access time is part of cycle: L1 hit ~ 1 cycle keeps $f$ high; larger cache slower but reduces miss. Design chooses split.

    • Effective CPI - Dominant:

      • No cache: Every $LW/SW$ suffers 50-100 cycles miss → $CPI_{effective} = CPI_{base} + Memory\_access\_per\_instr \times (1 - h) \times MissPenalty$.
      • With hierarchy: $T_{eff} = h_1 T_{L1} + (1-h_1)[h_2 T_{L2} + (1-h_2)T_{RAM}]$.
      • Example: Base CPI=1.0, 30% loads/stores, miss rate 5%, penalty 20 cycles → $CPI =1.0 +0.3*0.05*20 =1.30$ (+30% time). Improving hit rate from 95% to 98% via larger cache → CPI → 1.12.

    • Program Length (IC):

      • Larger block/cache with prefetch can reduce instruction fetch IC stalls but adds overhead of coherence/ TLB misses. Prefetch / O-O-O hides.

    • Interactions:

      • Larger cache → lower miss rate → $CPI\downarrow$ but larger access time → may limit $f$ and higher power/cost.
      • Write policy: Write-back reduces bus traffic → less stall.

    Overall $CPU_{time}$ with hierarchy: $CPU_{time} = IC \times (CPI_{execution} + Stall_{mem}) \times T_c$.

    Summary Matrix (Mark-Scoring Table)

    Factor	Primary effect on	Direction	Example justification
    ISA - CISC complexity	$IC \downarrow$	fewer instr	REP MOVS vs loop
    	$CPI \uparrow$, $f\downarrow$	each CISC takes micro-steps, complex decode	CPI 5 vs 1
    Compiler optimization	$IC \downarrow$	eliminate	DCE -20%
    	$CPI \downarrow$	schedule to avoid stalls	reorder LW-USE
    CPU Implementation (pipeline, superscalar, hardwired)	$f \uparrow$	deeper pipe, faster tech	3 GHz vs 33 MHz
    	$CPI \downarrow$ (~1 to <1)	overlap, parallel issue	4-wide IPC=3
    Cache Hierarchy	$CPI_{eff} \downarrow$ greatly	hit reduces stall	$h$=95% saves 20 cycles
    	$f$ slightly ↓ if large	size ↔ speed	L1 32KB 2 cycles vs L2 1MB 10 cycles

    Combined Formula Justification:
    $Performance \propto 1 / CPU_{time} \propto f / (IC \times CPI_{base+stall})$

    To improve performance: Reduce IC via RISC? Actually need product minimal. Recent trends: Keep ISA fixed (x86), aggressively improve Compiler, Implementation (O-O-O, branch prediction, speculative), and Hierarchy (multi-level cache, prefetch, TLB) to hide $CPI_{stall}$ while pushing $f$ via scaling. Amdahl emphasizes bottleneck - e.g., even infinite $f$ but 20% memory stalls caps speedup.

    For 7M answer: Write equation first, then 4 subsections each stating effect on IC, f, CPI with 2-line justification + numeric example, conclude with trade-offs matrix.

13. Q3a. Explain register reference and memory reference instructions in detail with suitable examples.20197m

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

    Explain register reference and memory reference instructions in detail with suitable examples.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Register Reference vs Memory Reference Instructions (Mano Basic Computer - 16-bit)

    In Mano's Basic Computer, instructions are 16-bit: I (15) | Opcode (14-12) | Address (11-0). Whether an instruction is Memory-reference, Register-reference or I/O is decided by the opcode and I bit.

    1. Memory Reference Instructions ( $I \times 2^{12} + opcode$ )

    Opcode 000 to 110 with $I=0/1$ = 7 instructions. Bits 11-0 give memory address; $I=0$ = direct, $I=1$ = indirect (EA = M[address]).

    Opcode	Symbol	Operation	Example
    000	AND	$AC \leftarrow AC \land M[EA]$	AND 100 / AND I 100
    001	ADD	$AC \leftarrow AC + M[EA]$	ADD 200
    010	LDA	$AC \leftarrow M[EA]$	LDA 300
    011	STA	$M[EA] \leftarrow AC$	STA 400
    100	BUN	$PC \leftarrow EA$	BUN 500 Unconditional branch
    101	BSA	$M[EA]\leftarrow PC,\; PC\leftarrow EA+1$	BSA 600 Branch & save return
    110	ISZ	$M[EA]\leftarrow M[EA]+1$, if $M[EA]=0$ then $PC\leftarrow PC+1$ (skip)	ISZ 700

    Format: 1xxx xxxx xxxx xxxx where xxx=opcode.
    E.g. LDA 0x005 direct: 0 010 000000000101 = 0x2005; indirect: 1 010 000000000101 = 0xA005.

    Executed in Fetch -> Decode -> Execute using $T_0-T_4$. Need memory access in execute phase.

    2. Register Reference Instructions

    Recognized when opcode = 111 and I=0 (IR = 0111 0xxx xxxx xxxx). Bits 11-0 specify which micro-operation on AC, E, etc. No memory access, executed in one cycle ($T_3$). Bit =1 means operation performed; multiple bits can be 1 together.

    Bit	Symbol	Micro-operation
    11	CLA 7800	$AC \leftarrow 0$
    10	CLE 7400	$E \leftarrow 0$
    9	CMA 7200	$AC \leftarrow \overline{AC}$
    8	CME 7100	$E \leftarrow \bar{E}$
    7	CIR 7080	$AC,E \leftarrow shr(AC,E)$
    6	CIL 7040	$AC,E \leftarrow shl(AC,E)$
    5	INC 7020	$AC \leftarrow AC+1$
    4	SPA 7010	If $AC(15)=0$ then $PC\leftarrow PC+1$ (skip if positive)
    3	SNA 7008	Skip if $AC$ negative
    2	SZA 7004	Skip if $AC=0$
    1	SZE 7002	Skip if $E=0$
    0	HLT 7001	$S\leftarrow 0$ halt

    E.g. CLA = 0111 1000 0000 0000 = 0x7800; CMA INC (complement and increment = negate) = 0x7200|0x7020 = 0x7220.

    Key difference:

    Feature	Memory-Reference	Register-Reference
    Opcode	000-110	111
    I bit	selects direct/indirect	must be 0
    Operands	in Memory	in AC/E/PC
    Cycles	needs $M[EA]$ access	single micro-op, no memory
    Example	ADD 0100 does $AC+M[0100]$	CLA clears AC

    I/O instructions are third type: opcode 111, I=1, bits 11-0 select I/O micro-op e.g. INP, OUT.

14. Q3b. Draw the block diagram of control unit of basic computer. Explain in detail with control timing diagrams.20197m

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

    Draw the block diagram of control unit of basic computer. Explain in detail with control timing diagrams.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Control Unit of Basic Computer (Mano)

    Hardwired control unit generates signals for registers, memory, ALU timed by Sequence Counter (SC) $T_0$ to $T_{15}$.

    Block Diagram (Textual)

                        +-------------------+
    Clock --------------| Sequence Counter  |---- T0..T15 (decoded)
    Reset -------------|   SC (4-bit)      |
                        +---------+---------+
                                  | Increment / Clear
                                  v
      Opcode (IR12-14) ->+--------+--------+      +--------------+
      I bit (IR15) ------> Decoder (3x8)  |----->| Control Logic|
                         +--------+--------+      |  Gates       |--- Control signals:
      T0-T7 ------------->                       |  (AND-OR)    |    LDAR,LDPC,LDAC,LDDR,LDAC
      Flags(E,AC,etc) --->                       +------+-------+    RD/WR,MEM, INCPC, CLRSC...
                                                        |
      IR 0-11 Address ----------------------------------+
    

    Components:

    1. Sequence Counter SC: 4-bit counts $0$ to $15$, decoded to $T_i=1$ only at that count.
    2. Instruction Register IR(15-0): IR(12-14)→ 3x8 decoder gives $D_0$-$D_7$, IR(15)=$I$, IR(11-0)= address.
    3. Control Logic Gates: Combine $D_i \cdot T_j \cdot I/\bar I$ and flags to produce register transfer signals.

    Control Timing Diagrams

    Sequence for every instruction: Fetch ($T_0$-$T_1$), Decode ($T_2$), Execute ($T_3$-$T_7$).

    Time	Micro-operations	Control signals
    $T_0$	$AR \leftarrow PC$	$PC_{out}, AR_{in}$
    $T_1$	$IR \leftarrow M[AR], PC \leftarrow PC+1$	$MEM_{read}, IR_{in}, PC_{inc}$
    $T_2$	$D_0..D_7 \leftarrow Decode IR(12-14)$,<br>$AR \leftarrow IR(11-0)$,<br>$I \leftarrow IR(15)$	$Decode, AR_{in}$
    $T_3$	Memory-ref with I=1: $AR\leftarrow M[AR]$ (indirect)	$MEM_{read}, AR_{in}$
    	Register-ref ($D_7,I=0$): Execute $rB_i$ (e.g. $CLA$) and $SC\leftarrow0$	$r\cdot T_3$
    	I/O ($D_7,I=1$): Execute $pB_i$	$p\cdot T_3$
    $T_4$	$D_0 T_4$: $DR\leftarrow M[AR]$ (AND)<br>$D_1 T_4$: $DR\leftarrow M[AR]$ (ADD)...	$MEM_{read}, DR_{in}$
    $T_5$	$D_0 T_5$: $AC\leftarrow AC\land DR,\; SC\leftarrow0$<br>$D_1 T_5$: $AC\leftarrow AC+DR,\; E\leftarrow C_{out},\; SC\leftarrow0$<br>$D_2 T_4$: $AC\leftarrow DR$ etc.	$AC_{in}, CLRSC$
    $T_6$	For BSA, ISZ etc.

    Timing diagram sketch:

    Clock _|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_
    SC    0   1   2   3   4   5   0 ...
    T0    ‾‾|__ ____________________
    T1    __|‾‾|__ _________________
    T2    ____|‾‾|__ _______________
    T3    ______|‾‾|__ ____________
    D7·T3 triggers register micro-op and clears SC -> next Fetch.
    D0·T4, D0·T5 etc. shown as narrow pulses.
    

    Example - ADD direct (D1,I=0):
    $T_0: AR<-PC$, $T_1: IR<-M[AR],PC++$, $T_2: Decode$, $T_3: idle$, $T_4: DR<-M[AR]$, $T_5: AC<-AC+DR, E<-carry, SC<-0$.

    Example - CLA (D7,I=0,B11=1):
    $r = D_7 \cdot \bar I \cdot B_{11}$, $rT_3: AC<-0, SC<-0$ single cycle.

    Hardwired version uses gates; microprogrammed version would store above $T_iD_j$ combinations in control memory.

15. Q4a. Explain one-, two- and three-address instruction with suitable examples.20197m

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

    Explain one-, two- and three-address instruction with suitable examples.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    One-, Two- and Three-Address Instructions

    Based on number of address fields in instruction format. Trade-off: code size vs registers vs memory accesses.

    1. Three-Address Instruction

    • Format: OPCODE Destination, Source1, Source2 e.g., ADD R1, R2, R3 => R1 <- R2 + R3
    • 3 address fields: 2 sources, 1 destination. All operands can be registers/memory.
    • Example:

      ADD R1, R2, R3   ; R1 = R2 + R3
      MUL R4, R1, R2   ; R4 = R1 * R2
      ADD R1, R2, M[X] ; R1 = R2 + M[X]  (if memory allowed)
      Evaluate X=(A+B)*(C+D):  ADD R1,A,B ; ADD R2,C,D ; MUL X,R1,R2
      

    • Pros: Most expressive, one instruction per operation, compiler friendly, shorter program (fewer instructions). Good for RISC with many registers.
    • Cons: Long instruction word (e.g., 4+4+4+4=16-32 bits), needs 3 register fields, large code size if memory addresses are long.

    2. Two-Address Instruction

    • Format: OPCODE Destination, Source => Destination <- Destination OP Source
    • One field is both source and destination (accumulative).
    • Example:

      MOV R1, R2   ; R1 <- R2
      ADD R1, R2   ; R1 <- R1 + R2
      ADD R1, X    ; R1 <- R1 + M[X]
      For X=(A+B)*(C+D): MOV R1,A ; ADD R1,B ; MOV R2,C ; ADD R2,D ; MUL R1,R2 ; MOV X,R1
      

    • Popular in CISC (Intel x86): ADD AX, BX , MOV AX, [500H]
    • Pros: Shorter than 3-address (saves one field), still flexible, fewer bits.
    • Cons: Destructive (source overwritten) -> extra MOV needed, more instructions than 3-address.

    3. One-Address Instruction (Accumulator-based)

    • Format: OPCODE Address => AC <- AC OP M[Address] (one implicit accumulator)
    • Second operand implicit in AC (Accumulator). Result back to AC.
    • Example (Mano basic computer):

      LDA X   ; AC <- M[X]
      ADD Y   ; AC <- AC + M[Y]
      STA Z   ; M[Z] <- AC
      For X=(A+B)*(C+D): LDA A ; ADD B ; STA T1 ; LDA C ; ADD D ; STA T2 ; LDA T1 ; MUL T2 ; STA X  (needs temp)
      

    • Pros: Shortest instruction (opcode + one address), minimal hardware (one register).
    • Cons: Many instructions needed, temporary memory storage, AC becomes bottleneck, high memory traffic.

    Comparison Table

    Type	Addresses	Example	Instructions for (A+B)*(C+D)	Length
    3-address	3	ADD R1,A,B	3	Longest
    2-address	2	ADD R1,A	6	Medium
    1-address	1 + AC	LDA A	8-9	Shortest
    0-address	0 (Stack)	PUSH A; ADD	8 + stack ops	Stack machine

    Modern RISC (ARM, MIPS) uses 3-address register-register, x86 uses 2-address, older machines (8085, Mano) use 1-address accumulator. Choice depends on register file size and instruction length constraints.

16. Q4b. Give an integrated diagram showing the TLB and cache operations for a logical/virtual address generated by a processor.20197m

    Module 4: Memory Organization

    Give an integrated diagram showing the TLB and cache operations for a logical/virtual address generated by a processor.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    TLB and Cache Operations for Virtual Address

    Virtual (Logical) address from CPU is translated to Physical address via TLB + Page Table, then Physical address accesses Cache + Main Memory.

    Address Split Example (32-bit VA, 4KB pages, 32KB 4-way cache 64B blocks)

    • VA: Virtual Page Number (VPN) | Page Offset (12 bits) (20+12 for 4KB)
    • PA: Physical Page Number (PPN) | Page Offset
    • PA for cache: Tag | Set | Block Offset (e.g., PPN part provides Tag+Set)

    Integrated Flow

    CPU generates VIRTUAL ADDRESS (VA)
                |
                v
          +------------+      TLB Hit (80-99%)       +-----------------+
          |    TLB     | --------------------------->|   CACHE         |
          |(Translation|  VPN -> PPN translation    | (Physically     |
          | Lookaside  |                             |  tagged/indexed)|
          | Buffer)    |  TLB Miss -> Page Table     |                 |
          | CAM 64-1024|  walk (hardware / OS)       | Tag | Set | Off |
          +------------+  -> refill TLB              +--------+--------+
                |                                      |Hit | Miss
                | Miss                                 v      v
          +------------+                          +-------+ +--------+
          | Page Table |                          | Data to CPU | Main Memory |
          | in Memory  |                          +-------+  (fetch block -> cache)
          |(2-level)   |
          +------------+
                |
                v
          Physical Address (PA) = PPN + offset  ---> to Cache & Memory protection check
    

    Step-by-Step Operations

    1. CPU issues VA: VPN + Offset. Also permission bits checked.

    2. TLB Lookup (parallel with cache - virtually indexed):

       • TLB Hit: CAM compares VPN with all entries (valid+ASID). Returns PPN in ~1 cycle. Form PA = PPN || offset.
       • TLB Miss: Hardware page table walker reads page table in memory (2-4 accesses for multi-level), brings PTE to TLB. If page not in memory -> Page Fault -> OS loads from disk.

    3. Cache Access (using PA - physically indexed physically tagged PIPT, most common):

       • Decode PA: Set = (PA >> blockOffset) % sets, compare Tag array for that set (4-way).
       • Cache Hit: Data returned to CPU (~4-10 cycles L1). No memory access.
       • Cache Miss: Request goes to L2/L3 / Main Memory; block (64B) fetched to cache line (with Tag), then to CPU. TLB and cache may be accessed in parallel or sequentially depending on design:
         • PIPT: TLB first, then cache (safe, needs translation).
         • VIPT: Index with VA bits (no alias), Tag with PA -> overlaps TLB.
         • VIVT: Both virtual - needs flush on context switch.

    4. Overlap / Virtually Indexed Physically Tagged (VIPT) optimization: L1 cache can start set decode using page offset bits (12 bits = not translated) while TLB translates VPN. On translation complete, tag compare uses PPN.

    Protection & Extras

    • TLB PTE contains Valid, Dirty, Referenced, R/W/X, U/S, Cacheability bits - checked on translation.
    • On context switch, TLB flush or ASID-tagged entries avoid flush.
    • Multi-level Inclusive TLB + L1/L2 Cache hierarchy: TLB miss cost 20-100 cycles; Page fault ms.

    Summary: VA -> TLB (VPN->PPN) -> PA -> Cache(Tag/Set match) -> Hit? -> CPU : Memory. TLB is cache for page table, Cache is cache for memory blocks.

17. Q5a. Explain the daisy chaining mechanism for bus arbitration. Analyze the three bus arbitration methods – daisy chaining, polling, and independent requesting – with respect to communication reliability in the event of hardware failures.20197m

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

    Explain the daisy chaining mechanism for bus arbitration. Analyze the three bus arbitration methods – daisy chaining, polling, and independent requesting – with respect to communication reliability in the event of hardware failures.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Bus Arbitration - Daisy Chaining & Reliability Comparison

    Daisy Chaining Mechanism

    Daisy chaining is centralized serial arbitration. A common Bus Grant (BG) line is daisy-chained through all masters in order of priority.

    • Arbiter receives Bus Request (BR) (wired-OR) from any device.
    • Arbiter asserts BG - passes through devices sequentially.
    • First requesting device in chain closest to arbiter blocks propagation and takes bus, others starved.
    • Signals: BR (common) -> Arbiter -> BG1 -> Device1 -> BG2 -> Device2 -> ...
    • Simple, fixed priority by physical position, no address needed.

    Timing: Request -> Arbiter senses BR -> asserts BG -> ripples via gates (priority logic) -> device asserts Bus Busy (BB) and starts transfer.

    ---

    Comparison w.r.t. Communication Reliability on Hardware Failure

    Feature	Daisy Chaining	Polling	Independent Requesting
    Wiring	Single BG daisy chain + wired-OR BR + BB	Common BR, Binary count lines + BB from arbiter	Separate BRi/BGi per device + BB
    Priority	Fixed by position	Programmable by polling order (arbiter can change)	Programmable via priority encoder, can be fixed/rotating
    Failure: BG/BR line open	Single point failure: Break in chain disconnects all downstream devices - entire subsystem beyond fault loses bus. Failure of one device's grant forwarding logic disables lower priority devices.	BG not daisy-chained. Polling counter broadcast to all devices. Open in one device's select logic isolates only that device; others continue. More reliable than daisy.	Most reliable: Each device has dedicated pair. Failure of one device's BR/BG affects only that device. Others unaffected. Full isolation.
    Failure: Device power off	If device does not forward BG when idle (must bypass), chain broken unless bypass hardware added.	Unaffected - poll address still generated, non-responding device just skipped.	Unaffected - other lines independent.
    Failure: BB stuck	Bus appears busy forever - system hangs for all.	Same - common BB.	Same - common BB is still single point (all methods share this).
    Hardware cost	Cheapest - few wires	Moderate - need $\log_2 N$ poll lines + decoder	Highest - $2N$ lines
    Response time	Propagation delay $O(N)$ gate delays down chain, slowest.	Polling time $O(N)$ cycles to scan max.	Fastest - arbiter decides in 1 arbitration cycle.

    Reliability ranking: Independent Requesting > Polling > Daisy Chain

    Daisy chain least reliable because serial grant creates single path failure domain; any device/connector failure cascades downstream. Independent requesting is most fault-isolated, preferred for fault-tolerant multiprocessors though at cost of lines and arbiter complexity. Polling is intermediate - software/hardware reconfigurable polling order can also bypass faulty device dynamically.

18. Q5b. Give the block diagram of the microprogram sequencer for a control memory and explain it properly.20197m

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

    Give the block diagram of the microprogram sequencer for a control memory and explain it properly.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Microprogram Sequencer for Control Memory

    Microprogrammed control unit uses Control Memory (ROM) to store microinstructions instead of hardwired logic. The microprogram sequencer generates the next address in control memory.

    Block Diagram

                         +-------------------+
                         | Control Memory    |
                         | (ROM) micro-      |----> Control Word
                         | instructions      |      (to datapath)
                         +---------+---------+
                                   |
                            +------v------+
                            |  Control    |
                            | Data Register|
                            |   (CDR) /   |
                            | Pipeline Reg|
                            +------+------+
                                   |
    +--------------------------------------------------------------+
    |                    Microprogram Sequencer                     |
    |                                                               |
    |  External                                    +----------------+ |
    |  Inputs ----> +----------------+             |  Multiplexer   | |
    |  (I, Flags,  |  Mapping Logic |-----------> |  (MUX)         | |
    |   IR op)     |  (Address gen) |             |                | |
    |              +----------------+             |                | |
    |                                            |   +----------+ | |
    |  +------+    +------------+    +-------+   +-->| Control  | | |
    |  | SBR  |<-->| CAR (µPC)  |<---| Inc.  |<------| Address  | | |
    |  |Stack |    | Address Reg|    | +1    |       | Register | | |
    |  |      |    +------------+    +-------+       |  (CAR)   | | |
    |  +------+         ^                             +----------+ | |
    |     ^             |                                           | |
    |     |        +----+------+                                    | |
    |     +--------|  MUX Select|<-- Flags (S,Z,C) + CDR bits (cond)| |
    |              |  Logic    |                                    | |
    |              +-----------+                                    | |
    +--------------------------------------------------------------+
             |                           ^
             |                           |
          CALL/RET              Branch Address from CDR
    

    Simplified alternative view (standard textbook):

                    +-------------------+
      MUX Select -->|  MUX (4:1)        |---> CAR ---> Control Memory ---> CDR
                    |  0: CAR+1         |     (µPC)     Address
                    |  1: Branch Addr   |
                    |  2: Mapping       |
                    |  3: SBR Top       |
                    +-------------------+
                        ^      ^
                        |      +-- Mapping Logic <- IR (opcode)
                        |
                   SBR (Stack for CALL/RET) <-- CDR condition bits + Flags
    

    Components and Explanation

    1. Control Address Register (CAR) / µPC: Holds address of next microinstruction to fetch. Like PC for microprogram.

    2. Control Data Register (CDR) / Pipeline Register: Holds current microinstruction fetched from control memory. Its fields provide:

       • Control signals for datapath
       • Next-address information (branch address, condition select bits)
       • Condition to test

    3. Incrementer (+1): Generates CAR+1 for sequential execution (next microinstruction).

    4. Multiplexer (MUX): Selects one of several next-address sources:

       • Incrementer (CAR+1) - for sequential continuation
       • Branch address from CDR (for conditional/unconditional branch in microprogram)
       • Mapping logic output - maps macro opcode (from IR) to starting micro-routine address
       • SBR Top - return address from subroutine stack

    5. Mapping Logic: Combinational circuit that converts instruction opcode (e.g., ADD, BRA) into starting address in control memory where its micro-routine is stored. Avoids sequential search.

    6. SBR - Subroutine Register (Stack): Small LIFO stack to save/restore CAR during microprogram subroutine calls (CALL pushes CAR+1, RET pops to CAR). Needed for reusable micro-subroutines (e.g., fetch).

    7. MUX Select Logic: Determines MUX selection based on:

       • Conditional bits in current microinstruction (e.g., JCC field)
       • Status flags (Zero, Carry, Sign) and external inputs
       • Unconditional branch bit

    Operation Sequence

    1. CAR addresses control memory -> microinstruction loaded into CDR.
    2. Control field of CDR drives datapath; next-address field goes to sequencer.
    3. Incrementer computes CAR+1.
    4. Select logic evaluates condition flags + CDR condition bits -> chooses MUX input.
    5. Chosen address loaded into CAR at next clock.
    6. If microinstruction is CALL, current CAR+1 pushed to SBR; if RET, popped.

    This enables conditional branching, subroutine calls, and opcode mapping inside control memory, making control unit flexible - only ROM contents need change to modify instruction set.

19. Q6a. What do you understand by hardwired control? Give various methods to design a hardwired control unit. Describe any one with a suitable example.20197m

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

    What do you understand by hardwired control? Give various methods to design a hardwired control unit. Describe any one with a suitable example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Solution - Hardwired Control

    What is Hardwired Control?
    Hardwired control is a method of control unit design where control signals are generated by fixed combinational logic circuits (gates, encoders, decoders, flip-flops) as Boolean functions of input variables: Opcode ($I$), Timing signals ($T$), Flags ($F$), and Clock. No control memory is used. Each control signal $C_k = f(I,T,F)$. It is fast but inflexible - any change requires physical rewiring.

    Various Methods to Design Hardwired Control Unit:

    1. State Table / Classical Method (Sequence Table + Logic)
    2. Delay Element (Switching Delay) Method
    3. Sequence Counter (Counter) Method - Most Popular
    4. PLA (Programmable Logic Array) Method

    Describe in Detail: Sequence Counter Method (with example):

    This is the most widely used textbook method.

    Hardware:

    • A $k$-bit Sequence Counter (SC) / ring counter that counts clock pulses and generates timing states $T_0,T_1,T_2...T_{n-1}$ cyclically. Usually decoded to one-hot.
    • An Instruction Decoder that decodes IR-opcode into $D_0...D_{m-1}$ lines.
    • Combinational Encoder (AND-OR network / PLA) to generate control signals.
    • Control logic also uses Flags and mode bits.

    Working - Example: 3-instruction CPU (LDA, ADD, BUN):
    Suppose SC counts $T_0$ to $T_3$. Control signals are:

    • Fetch (common to all):
      $T_0: PC_{out} \to AR$
      $T_1: M[AR] \to DR, PC+1 \to PC$
      $T_2: DR \to IR, Decode$
    • Execute depends on $D_i$:
      $D_0 T_3: M[IR_{addr}] \to DR$ (LDA)
      $D_0 T_4: DR \to AC$
      $D_1 T_3: M[IR_{addr}] \to DR$ (ADD)
      $D_1 T_4: AC+DR \to AC$
      $D_2 T_3: IR_{addr} \to PC$ (BUN)

    Boolean expression: $AC_{load} = D_0 T_4 + D_1 T_4$

    Sequence:

    1. Initially $SC=0$. At $T_0$ fetch step.
    2. After each clock, SC increments; decoder selects instruction-specific path.
    3. At $T_{last}$ SC is cleared to 0 for next fetch, END signal generated.

    Advantages of Counter Method: Systematic, easy to understand timing.
    Disadvantage: Many gates, counter delay.

    Other methods briefly:

    • Delay Element: Chain of delay elements propagates control pulse sequentially to generate $T_i$ without counter - simple but delay not precise.
    • PLA Method: All combinational logic fused into one PLA - compact, used in modern RISC hardwired CU for high speed.
20. Q6b. Describe autoincrement and decrement addressing modes with proper examples.20197m

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

    Describe autoincrement and decrement addressing modes with proper examples.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Solution - Autoincrement and Autodecrement Addressing Modes

    Both are Register Indirect with automatic update modes, useful for array/table traversal and stack operations.

    1. Autoincrement Addressing Mode: $(R)+$ or $[R+]$

    • Definition: Effective Address $EA = [R]$ (content of register gives address). After operand is accessed, register is automatically incremented by size of operand ($+1$ for byte, $+2$ for 16-bit word, $+4$ for 32-bit).
    • Operation: $EA \leftarrow R$; $R \leftarrow R + d$ (where $d$ = operand size).
    • Use: For traversing arrays/buffers in forward direction, popping from stack, reading sequential data.

    Example (8086-like / PDP-11 style):
    Suppose $R_1 = 1000H$, Memory[1000]= $AB$, Memory[1001]= $CD$ (16-bit).
    Instruction: MOV (R1)+, R2 ; or MOV @R1+, AC

    • Fetch operand from address 1000H into R2.
    • Then $R_1 \leftarrow 1000H + 2 = 1002H$ (for word).
      Now $R_1$ points to next element automatically.

    Array sum loop:

          MOV #ARRAY, R1   ; R1 -> start
          CLR  R3          ; sum=0
    LOOP: ADD (R1)+, R3    ; add *R1 to sum, R1 moves to next
          DEC  R2          ; count
          BNE  LOOP
    

    2. Autodecrement Addressing Mode: $-(R)$ or $-[R]$

    • Definition: Register is first decremented by operand size, then its content is used as Effective Address. $R \leftarrow R - d$; $EA \leftarrow R$.
    • Use: For traversing arrays backward, pushing onto stack (stack grows downward).

    Example:
    Suppose $R_1 = 1002H$, $SP = 2000H$.
    Instruction: MOV R2, -(R1) or PUSH R2 is MOV R2, -(SP)

    • First $SP \leftarrow 2000H - 2 = 1FFEH$
    • Then Memory[$1FFEH$] $\leftarrow R_2$.
      So decrement-before-store prevents overwriting.

    Array reverse traversal:

          MOV #ARRAY_END, R1  ; point beyond last element
    LOOP: MOV -(R1), R2       ; R1-- first, then fetch
    

    Combined Example - Stack:

    • PUSH A = MOV A, -(SP) (autodecrement)
    • POP A = MOV (SP)+, A (autoincrement)

    Comparison Table:

    Feature	Autoincrement $(R)+$	Autodecrement $-(R)$
    Order	Use then increment	Decrement then use
    Pointer moves	Forward	Backward
    For Stack	POP	PUSH
    Initial R points	To current operand	To next free location

    Both modes eliminate extra ADD/SUB instructions, improving code density and loop efficiency.

21. Q7a. What is Direct Memory Access (DMA)? Explain. Give the block diagram of circuitry required for direct memory access.20197m

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

    What is Direct Memory Access (DMA)? Explain. Give the block diagram of circuitry required for direct memory access.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Direct Memory Access (DMA)

    Why DMA?

    Programmed I/O and interrupt-driven I/O transfer word-by-word via CPU, executing IN/OUT instructions and busy-waiting. For bulk transfers (disk, display) this wastes CPU cycles. DMA allows peripheral to transfer block of data directly between I/O device and memory, bypassing CPU except for setup and completion.

    CPU initiates DMA, then continues other work; DMA controller (DMAC - e.g. Intel 8237, controller in modern chipsets) steals bus cycles (cycle stealing) or bursts.

    Block Diagram - DMA Circuitry

    CPU --- Address Bus --------------------------> Memory
     |      Data Bus ----------------------------> Memory
     |      Control Bus (MEMRD/MEMWR, IOR/IOW)   |
     |                                          |
     |  ┌─────────────────────────────────┐     |
     └──┤ DMA Controller (DMAC)           ├─────┘
         │  • Address Reg (start)        │  HRQ→ CPU HOLD
         │  • Word Count Reg             │  HLDA← CPU
         │  • Control Reg (R/W, mode)    │  DREQ← Peripheral (DMA Request)
         │  • Bus buffers & timing       │  DACK→ Peripheral (DMA Ack)
         └──────┬────────────────────────┘
                | DREQ/DACK, Data bus via buffers
           Peripheral Device (Disk, etc.)
    

    Key registers inside DMAC (per channel):

    • Address Register - starting memory address, auto-increment/decrement after each word.
    • Byte/Word Count Register - decrements to 0 → terminal count (TC) → interrupt.
    • Control/Status Register - direction (read/write), mode (burst, cycle-steal, transparent), auto-init.
    • Bus Request/Grant Logic

    Operation Sequence

    1. Init: CPU programs DMAC via I/O writes: load MAR, WC, control. CPU also loads peripheral command.
    2. Request: Peripheral ready → asserts DREQ.
    3. Handshaking: DMAC asserts HRQ (Hold Request) to CPU. CPU finishes current bus cycle, tristates address/data/control, asserts HLDA (Hold Ack). DMAC becomes bus master.
    4. Transfer: DMAC puts memory address on address bus, asserts MEMRD (for I/O→Mem) or MEMWR (Mem→I/O) + DACK+IOR/IOW to device; data flows directly Device↔Memory without CPU register. After each word: MAR++, WC--.
    5. Termination: When WC==0, DMAC asserts TC and optionally interrupts CPU (TC/INT), releases HRQ, CPU regains bus.

    Transfer Modes

    • Burst/Block: Holds bus until entire block done (fast, CPU blocked).
    • Cycle-stealing: Transfers one word per bus cycle stolen between CPU cycles (common).
    • Transparent: Only when CPU not using bus.

    Advantages

    • Speed: memory-limited (no instruction fetch/decode per word) → $10\text{-}100\times$ faster.
    • CPU free for computation, overlapped I/O.

    DMA vs Interrupt

    Interrupt still needs CPU per word; DMA needs CPU only twice (setup + completion interrupt).

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. Q7b. A digital computer has a common bus system of 16 registers of 32 bits each. The bus is constructed with multiplexers. - (i) How many selection inputs are there in each multiplexer? - (ii) What size of multiplexers is needed?20197m

    Module 1: Functional Block of computer and Data representaion

    A digital computer has a common bus system of 16 registers of 32 bits each. The bus is constructed with multiplexers.

    • (i) How many selection inputs are there in each multiplexer?
    • (ii) What size of multiplexers is needed?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Given: Common bus with 16 registers, each 32 bits, bus built from multiplexers.

    We construct bus by bit-slicing: one multiplexer per bit position that selects same source register bit across all registers.

    (i) Number of selection inputs per multiplexer

    To select 1 of 16 sources, number of select lines $s$ satisfies $2^{s} \ge 16$.

    $$s = \lceil \log_{2}16 \rceil = 4$$

    So each multiplexer needs 4 select lines ($S_3S_2S_1S_0$). A 4-bit binary code chooses register $0\text{-}15$ (decoder internal to mux).

    If enable considered, $4$ selects + $1$ enable.

    (ii) What size multiplexers are needed? / How many?

    • Size per multiplexer: $16\text{:}1$ (16 data inputs → 1 output). Strictly $16\times1$ MUX.
    • Number of multiplexers: One per bit slice → 32 multiplexers, each $16\!:\!1$.

    Total $32 \times 16 = 512$ data input lines, 32 outputs form the 32-bit bus. Selection inputs (4 lines) are common to all 32 muxes.

    Implementation note: If only $4{:}1$ mux ICs available, each $16{:}1$ can be built from five $4{:}1$ muxes (4 first-level +1 second-level), requiring $32\times5=160$ chips. With $8{:}1$ muxes, $2+1$ per bit.

24. Q8a. When do you say the floating point number is normalized? Explain how floating point representation of number is done. Represent the number (+46.25) as floating point binary number with 32 bits.20197m

    Module 1: Functional Block of computer and Data representaion

    When do you say the floating point number is normalized? Explain how floating point representation of number is done. Represent the number (+46.25) as floating point binary number with 32 bits.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Normalized Floating Point & Representation of +46.25 in IEEE 754 32-bit (7 Marks)

    1. When is Floating Point Number Normalized?
    A floating point number $N = \pm M \times B^{E}$ (mantissa $M$, base $B=2$, exponent $E$) is said to be normalized when the mantissa is adjusted so that the most significant digit is non-zero, i.e. $1 \le M < 2$ for binary. In binary this means form $1.xxxxx... \times 2^{E}$ (leading 1 before binary point).

    Purpose: (i) unique representation, (ii) maximum precision (no leading zeros wasted), (iii) efficient exponent use.
    Example: $0.00101 \times 2^{5}$ is unnormalized, normalized is $1.01 \times 2^{2}$.

    Denormalized/subnormal numbers have exponent zero and leading 0 to represent very small numbers near zero.

    2. Floating Point Representation:
    General format: Sign (S) + Exponent (E with bias) + Mantissa/Fraction (M).
    IEEE 754 single precision (32 bits): | S (1) | Exponent (8) | Mantissa (23) |

    • $S=0$ for +ve, $1$ for -ve
    • Biased exponent: $E_{biased}=E_{true}+127$ (bias 127)
    • Mantissa stores fractional part after hidden 1 (normalized). Value $= (-1)^S \times 1.M \times 2^{(E-127)}$

    Double precision 64-bit uses 1-11-52 with bias 1023.

    3. Represent +46.25 in 32-bit:

    Step 1: Binary conversion
    $46_{10}=101110_2$ ($32+8+4+2$)
    $0.25=0.01_2$
    So $46.25=101110.01_2$

    Step 2: Normalize
    $101110.01 = 1.0111001 \times 2^{5}$ (shift binary point 5 left)
    True exponent $E=5$, Mantissa $M=0111001$

    Step 3: Encode
    $S=0$ (+ve)
    $E_{biased}=5+127=132_{10}=10000100_2$
    Mantissa 23 bits: $01110010000000000000000$ (pad zeros to 23 bits, after the hidden 1, we store $0111001$)

    Result:
    0 | 10000100 | 01110010000000000000000

    Grouping into Hex for verification:
    $0100\ 0010\ 0011\ 1001\ 0000\ 0000\ 0000\ 0000 = 0x42390000$

    Value $= +1.0111001 \times 2^5 = +46.25$. Normalized because leading 1 is implicit.

25. Q8b. What are hazards in pipeline architecture? Explain its types with suitable examples.20197m

    Module 3: Pipelining

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

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Hazards in Pipeline Architecture (7 Marks)

    Pipelining overlaps fetch-decode-execute stages to increase throughput (ideal CPI=1). Hazards prevent next instruction from executing in designated cycle, causing stalls/bubbles.

    1. Structural Hazards – Resource Conflict
    Two instructions need same hardware at same time.
    Example: Single memory for instruction + data. Stage IF and MEM both need memory in same cycle. Solution: separate I-Cache/D-Cache (Harvard) or stall.
    Other examples: Single ALU used for EX and address calculation; insufficient registers ports.

    2. Data Hazards – Data Dependency
    Occurs when instruction depends on result of previous instruction not yet completed. Three types:

    a) RAW (Read After Write) – True Dependency: $I2$ reads register $I1$ writes.

    ADD R1,R2,R3   ; R1 written
    SUB R4,R1,R5   ; R1 read – needs forwarding/stall
    

    Most common. Solved by forwarding/bypassing, operand forwarding, compiler reordering, stalling.

    b) WAR (Write After Read) – Anti-Dependency:

    ADD R4,R1,R5
    SUB R1,R2,R3   ; writes R1 before first reads it
    

    Not in classic 5-stage in-order pipeline but appears in out-of-order execution. Solved by register renaming.

    c) WAW (Write After Write) – Output Dependency:

    ADD R1,R2,R3
    SUB R1,R4,R5   ; both write R1
    

    Also for out-of-order. Solved by renaming.

    3. Control Hazards (Branch Hazards)
    Caused by branches/jumps – next PC unknown until branch resolved.

    BEQ R1,R2, LABEL ; whether to take branch known in EX/MEM
    ADD R3,R4,R5     ; next instruction fetched incorrectly if branch taken
    

    Penalty = flush pipeline. Solutions:

    • Stall until decision known
    • Branch prediction (static: predict not taken; dynamic: 1-bit/2-bit predictor, BTB)
    • Delayed branch (fill delay slot with useful/no-op instruction)
    • Speculative execution

    All hazards reduce speedup: $Speedup = \frac{n}{\text{ideal cycles + stalls}}$.

26. Q9a. What is an array processor? Explain SIMD array processor with a suitable example.20197m

    Module 3: Pipelining

    What is an array processor? Explain SIMD array processor with a suitable example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Array Processor and SIMD Array Processor [7M]

    Classification (Flynn):
    SISD (Single Instruction Single Data - uniprocessor), SIMD (Single Instruction Multiple Data - array/vector), MISD, MIMD (multiprocessor).

    What is Array Processor?
    Processor that performs same operation on multiple data elements simultaneously via array of Processing Elements (PEs). Specially for vector/matrix operations: image processing, scientific simulation, ML.

    Also called Vector processor if pipelined single ALU, Array processor if many ALUs.

    SIMD Array Processor Architecture:

                +-------------------+
                | Control Unit (CU)/|
                | Instruction Unit  |--- Master Control (Fetch/Decode)
                +---------+---------+
                          | broadcast
            +-------------+-------------+
            |             |             |
         PE0           PE1 ....      PE_{n-1}
       |ALU|RAM|    |ALU|RAM|      |ALU|RAM|
         \             |             /
          +---- Interconnection N/w ----+ (Mesh, Cube, Bus, Crossbar)
                          |
                       Shared Memory / I/O
    

    • Components:

      1. Master Control Unit / Front-end CPU: Fetches/decodes instructions, executes scalar instructions, broadcasts vector instruction and address to all PEs.
      2. N Processing Elements (PEs): Each has own ALU, local memory/registers, and indexing logic. Identical. e.g. 64 to 65536 PEs.
      3. Interconnection Network: Permits data exchange between PEs: nearest neighbour mesh, hypercube, crossbar. Needed for permutations (shuffle, transpose).
      4. Mask register: Enables/disables subset of PEs for conditional execution (if).

    • Execution: Single instruction stream -> all enabled PEs execute lock-step synchronously on their own data stream element. E.g.

    Instruction: C[i] = A[i] + B[i] for i=0..1023
    CU broadcasts ADD
    PE0: C0 = A0+B0
    PE1: C1 = A1+B1  (...1024 parallel)
    ...
    

    Time taken = 1 vector instruction vs 1024 SISD loop iterations.

    Example:

    • ILLIAC IV (historical): 64 PEs in 8x8 mesh, CU broadcast, used for air dynamics.
    • BSP (Burroughs Scientific Processor): 16 PEs.
    • Modern: GPU (NVIDIA) - each SM is SIMD (warp of 32 threads executes same instruction - SIMT variant), Intel AVX-512 (vector width 16 floats), Connection Machine CM-2 (65536 bit-serial PEs).

    Another example: Adding two $4\times4$ matrices: distribute rows to 4 PEs, single ADD does 16 additions in parallel.

    Advantages:

    • Huge speedup for data-parallel problems: $Speedup \approx N_{PE}$.
    • Simple control (single fetch unit), regular structure, high throughput per cost.

    Limitations:

    • Only data-parallel problems benefit; branching causes idle PEs (divergence).
    • Requires alignment of data; communication overhead via network.
    • Amdahl's law: scalar part limits. I/O handling through CU bottleneck.

    vs MIMD: Multiple instruction streams (multicore) more general but complex control.

27. Q9b. A DMA controller transfers 16-bit words to memory using cycle stealing. The words are assembled from a device that transmits characters at the rate of 2400 characters per second. The CPU is fetching and executing instructions at an average rate of 1 million instructions per second. By how much will the CPU be slowed down because of DMA transfer?20197m

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

    A DMA controller transfers 16-bit words to memory using cycle stealing. The words are assembled from a device that transmits characters at the rate of 2400 characters per second. The CPU is fetching and executing instructions at an average rate of 1 million instructions per second. By how much will the CPU be slowed down because of DMA transfer?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    DMA Cycle Stealing Slowdown Calculation [7M]

    Given: DMA transfers 16-bit words using cycle stealing. Device transmits characters at 2400 chars/sec. Characters assumed 8-bit (1 byte). CPU average 1 million instructions/sec (1 MIPS). Assume 1 instruction = 1 memory cycle stolen per DMA word. Find slowdown %.

    Understanding cycle stealing: DMA steals one bus/memory cycle from CPU per word. CPU pauses (or bus is held) for that cycle, so instruction rate reduces proportionally.

    Step 1: DMA word rate

    Device rate = 2400 characters/s = 2400 bytes/s

    Words are 16-bit = 2 bytes = 2 characters per word (assembled)

    So word assembly rate:

    $$f_{DMA} = \frac{2400 \text{ chars/s}}{2 \text{ chars/word}} = 1200 \text{ words/s}$$

    Each word needs one steal cycle.

    Step 2: CPU cycles

    Assume CPU fetch-execute average needs 1 memory cycle per instruction => 1 MIPS = $1 \times 10^6$ cycles/s demanded.

    Step 3: Fraction stolen

    $$\text{Fraction} = \frac{\text{DMA cycles stolen per sec}}{\text{Total CPU cycles per sec}} = \frac{1200}{1\,000\,000} = 0.0012$$

    Percentage slowdown:

    $$0.0012 \times 100 = 0.12\%$$

    Alternate interpretation if each instruction itself takes multiple cycles (e.g. 4 cycles avg) vs steal of one bus cycle ~1 cycle, then instruction slowdown = $1200/(4 \times 10^6)$? But problem states average instruction rate not clock rate, and 1 word = 1 instruction-equivalent slot, so above is expected answer.

    Result:

    CPU slowed by 0.12 % - negligible ($\approx 1200$ cycles stolen per second).

    If DMA burst mode instead of cycle steal were used, CPU would be blocked for contiguous 1200 cycles ($\approx 1.2 ms$) per second.

    General formula:

    $$\%\text{slowdown} = \frac{\text{Device throughput (bytes/s)}}{\text{bytes/word}} \times \frac{1}{\text{MIPS}} \times 100$$

    Even at 240k chars/s (100x faster), slowdown only 12% - justifies cycle stealing for slow character devices.

    Note: If character = 16-bit word (i.e. device directly gives 2400 words/s), then $2400/10^6 = 0.24\%$ slowdown. With given answer 0.12% exam expects 2 chars/word assembly, hence 1200 words/s.