2022 question paper

COMPUTER ORGANIZATION & ARCHITECTURE

22 questions

1. Q1(a). (a) The 8-bit encoding format used to store data in a computer is (i) ASCII (ii) EBCDIC (iii) ANCI (iv) USCII20222m

   Module 1: Functional Block of computer and Data representaion

   (a) The 8-bit encoding format used to store data in a computer is
   (i) ASCII
   (ii) EBCDIC
   (iii) ANCI
   (iv) USCII

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) EBCDIC (8-bit) — with note:

   • EBCDIC (Extended Binary Coded Decimal Interchange Code) is 8-bit encoding used in IBM mainframes to store data. ASCII is originally 7-bit (extended 8-bit later), but classic textbook for 8-bit format cites EBCDIC.
   • USCII/ANCI are not standard encodings.

   If strict modern context: Extended ASCII is also 8-bit, but among given options EBCDIC is the intended 8-bit format. Some keys mark EBCDIC as correct.

2. Q1(b). (b) The bus used to connect the monitor to the CPU is (i) PCI bus (ii) SCSI bus (iii) memory bus (iv) ram bus20222m

   Module 1: Functional Block of computer and Data representaion

   (b) The bus used to connect the monitor to the CPU is
   (i) PCI bus
   (ii) SCSI bus
   (iii) memory bus
   (iv) ram bus

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) PCI bus

   Explanation: PCI (Peripheral Component Interconnect) bus is commonly used to connect graphics/monitor via graphics adapter to CPU. SCSI is for disks, memory bus connects CPU to main memory. RAM bus is not standard term for monitor connection. Modern: PCIe for graphics.

3. Q1(c). \(c\) The alternate way of writing the instruction, ADD #5, R1 is (i) ADD [5],[R1]; (ii) ADDI 5,R1; (iii) ADDIME 5,[R1]; (iv) There is no other way20222m

   Module 1: Functional Block of computer and Data representaion

   (c) The alternate way of writing the instruction, ADD #5, R1 is
   (i) ADD [5],[R1];
   (ii) ADDI 5,R1;
   (iii) ADDIME 5,[R1];
   (iv) There is no other way

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) ADDI 5, R1

   Explanation:
   ADD #5, R1 is Immediate addressing mode - #5 denotes constant 5 as operand, added to register R1.

   • ADDI = ADD Immediate - dedicated mnemonic for immediate operation. ADDI 5,R1 is architecturally identical to ADD #5,R1.
   • (i) ADD [5],[R1] - is direct/memory addressing, wrong.
   • (iii) ADDIME is not a standard mnemonic.

   Note: Syntax varies by assembler (ADD R1, #5), but ADDI is the conventional alternate.

4. Q1(d). (d) The instruction fetch phase ends with (i) placing the data from the address in MAR into MDR (ii) placing the address of the data into MAR (iii) completing the execution of the data and placing its storage address into MAR (iv) decoding the data in MDR and placing it in IR20222m

   Module 1: Functional Block of computer and Data representaion

   (d) The instruction fetch phase ends with

   (i) placing the data from the address in MAR into MDR

   (ii) placing the address of the data into MAR

   (iii) completing the execution of the data and placing its storage address into MAR

   (iv) decoding the data in MDR and placing it in IR

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) decoding the data in MDR and placing it in IR

   Explanation:
   Instruction Fetch Cycle steps:

   1. MAR ← PC - place address of next instruction in MAR
   2. MDR ← M[MAR] - read memory word into MDR (option i)
   3. IR ← MDR - transfer instruction to Instruction Register and decode
   4. PC ← PC + 1

   The phase ends when instruction is available in IR for decode/execution. Option (ii) is start of fetch, (i) is middle. Hence (iv) is correct. Note: Some texts stop fetch at MDR loading (i), but classical fetch-decode cycle includes IR loading as final step.

5. Q1(e). (e) For converting a virtual address into the physical address, the programs are divided into (i) pages (ii) frames (iii) segments (iv) blocks20222m

   Module 4: Memory Organization

   (e) For converting a virtual address into the physical address, the programs are divided into
   (i) pages
   (ii) frames
   (iii) segments
   (iv) blocks

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) pages

   Explanation:

   • Virtual memory - Programs (logical address space) are divided into fixed-size blocks called pages.
   • Physical memory is divided into same-size blocks called frames/page frames.
   • Page table maps virtual page number → physical frame number for address translation via MMU.
   • Segments are variable-size logical divisions (segmentation), while blocks is generic; for pure paging the division is pages.

   Hence programs are divided into pages, physical memory into frames.

6. Q1(f). (f) The transfer of large chunks of data with the involvement of the processor is done by (i) DMA controller (ii) arbitrator (iii) user system programs (iv) None of the above20222m

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

   (f) The transfer of large chunks of data with the involvement of the processor is done by
   (i) DMA controller
   (ii) arbitrator
   (iii) user system programs
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) DMA controller (intended question = WITHOUT processor involvement)

   Explanation:

   • Large block I/O via Programmed I/O burdens CPU (polling/interrupt per word).
   • DMA (Direct Memory Access) controller steals/borrows bus and transfers large chunks directly between I/O and memory without continuous CPU involvement, only initial setup and final interrupt by CPU.
   • The question wording "with involvement of the processor" is likely a typo; strictly with involvement would be (iv) None of the above. For "WITHOUT CPU involvement", answer is (i) DMA controller.

   DMA registers: Address, Count, Control/Status - handles burst/cycle-stealing modes and bus arbitration.

7. Q1(g). (g) The computer architecture *aimed at* reducing the time of execution of instructions is (i) CISC (ii) RISC (iii) ISA (iv) ANNA20222m

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

   (g) The computer architecture aimed at reducing the time of execution of instructions is

   (i) CISC
   (ii) RISC
   (iii) ISA
   (iv) ANNA

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) RISC

   Explanation:

   • RISC (Reduced Instruction Set Computer): Aimed at reducing CPI / execution time per instruction via simple, fixed-length instructions, load/store architecture, hardwired control, pipelining - executes each instruction in ~1 cycle.
   • CISC (Complex Instruction Set Computer): Aimed at reducing number of instructions/code size via complex variable-length instructions, microprogrammed control - but each instruction takes multiple cycles.
   • ISA = Instruction Set Architecture (interface), ANNA = not relevant.

   Hence architecture focused on time of execution = RISC.

8. Q1(h). Which table handle stores the addresses of the interrupt handling sub-routines? (i) Interrupt-vector table (ii) Vector table (iii) Symbol link table (iv) None of the above20222m

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

   Which table handle stores the addresses of the interrupt handling sub-routines?

   (i) Interrupt-vector table
   (ii) Vector table
   (iii) Symbol link table
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) Interrupt-vector table

   Explanation:

   • Interrupt Vector Table (IVT) is an array in low memory (e.g., 0x00000 in x86) storing addresses (vectors) of ISRs (Interrupt Service Routines) indexed by interrupt number/type.
   • On interrupt, CPU uses interrupt number × entry size to fetch vector and jump to handler.
   • Vector table (ii) is generic; Symbol link table is unrelated (linking).

   Hence correct is Interrupt-vector table.

9. Q1(i). (i) The situation wherein the data of operands are not available is called (i) data hazard (ii) stock (iii) deadlock (iv) structural hazard20222m

   Module 3: Pipelining

   (i) The situation wherein the data of operands are not available is called

   (i) data hazard
   (ii) stock
   (iii) deadlock
   (iv) structural hazard

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) data hazard

   Explanation:

   • Data hazard: Operand/data not yet available/computed by previous instruction (RAW - Read After Write) when needed, causing stall.
   • Structural hazard: Hardware resource conflict (e.g., same memory port used by two stages).
   • Control hazard: Due to branch/jump altering PC.
   • Stock/deadlock are not pipeline hazard terms (stock is typo for stall).

   Hence unavailable operand = data hazard.

10. Q1(j). (j) The DMA controller has ____ registers. (i) 4 (ii) 2 (iii) 3 (iv) 120222m

    Module 4: Memory Organization

    (j) The DMA controller has ____ registers.

    (i) 4
    (ii) 2
    (iii) 3
    (iv) 1

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: (iii) 3

    Explanation:
    Standard DMA controller (e.g., Intel 8237) has 3 main registers per channel:

    1. Address Register - holds starting address of memory block (source/destination)
    2. Word Count Register - number of words/bytes to transfer
    3. Control/Status Register - direction, mode (burst/cycle stealing), enable

    Some descriptions count 4 including Data Buffer register, but classic exam answer is 3 registers.

11. Budget App•POCKETLY

    Pocketly on Android

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

    Install Pocketly
12. Q2(a). (a). List and briefly define the main structural components of a computer.20227m

    Module 1: Functional Block of computer and Data representaion

    (a). List and briefly define the main structural components of a computer.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Main Structural Components of a Computer (7M)

    Derived from Von Neumann model (Stallings). Four top-level components interconnected via System Bus.

                    +-------------------+
                    |   System Bus      |
                    | A (Address) D (Data) C (Control) |
                    +--+-----+------+---+
                       |     |      |
            +----------+ +---+----+ +--+----------+
            |   CPU    | | Memory | | I/O System  |
            |Processor | |        | |Module/Device|
            +----------++----+-----+ +-------------+
                   |          |            |
            (Control, ALU, Registers)
    

    1. Central Processing Unit (CPU) - Brain

    • Function: Fetches instructions, decodes, executes, controls entire system.
    • Sub-components:
      • ALU (Arithmetic Logic Unit): Performs arithmetic (ADD, SUB, MUL) and logical (AND, OR, NOT, SHIFT). Operates on registers.
      • Control Unit (CU): Generates timing & control signals (micro-operations) to coordinate fetch-decode-execute. Hardwired or Microprogrammed.
      • Registers: Very fast internal storage - PC (Program Counter), IR (Instruction Register), MAR/MDR (Memory Address/Data Registers), GPRs, PSW/FLAGS, SP.
      • Internal Bus: Connects CU-ALU-Registers.

    CPU performs Fetch Cycle (MAR <- PC, MDR <- Memory, IR <- MDR, PC++) and Execute Cycle.

    2. Main Memory - Storage for Program & Data

    • Function: Stores instructions & data temporarily while program runs. Byte-addressable, random access.
    • Types: RAM (Volatile, read/write) - DRAM/SRAM for main memory; ROM (Non-volatile) - BIOS, bootstrap.
    • Organization: Address space 2^n locations, n = address bus width (e.g., 32-bit CPU -> 4GB). Memory hierarchy includes Cache (SRAM, L1/L2/L3 between CPU & RAM) to bridge speed gap.
    • Interface: Address Bus selects location, Data Bus carries data, Control (MEMR/MEMW) signals read/write. Access time ~ 50-100 ns vs CPU cycle ~ 1 ns -> cache needed.

    3. I/O System (Input / Output) - Interface to External World

    • Function: Transfers data between computer and peripherals / outside. Also called I/O Module / I/O Subsystem.
    • Examples: Keyboard, Mouse, Display, Disk, Network card, Printer, Sensors.
    • I/O Module Functions: Control & timing, CPU communication (decode address, data buffering), device communication, error detection.
    • Techniques: Programmed I/O, Interrupt-driven I/O, DMA (direct memory access). Includes ports, device controllers, bus adapters.

    4. System Bus - Communication Highway

    • Function: Set of shared communication lines interconnecting CPU, Memory, I/O. Uses bus protocols/arbitration.

    Three buses (can be multiplexed):

    • Address Bus (Unidirectional, CPU -> Memory/I/O): Carries address k-bits to select one of 2^k locations. With 32-bit bus => 4GB.
    • Data Bus (Bidirectional): Carries data/instruction word (8/16/32/64-bit) - width determines word size.
    • Control Bus (Mixed): Carries control signals - MEMR*, MEMW*, IOR*, IOW*, CLK, RESET, READY, INTR, HOLD/HLDA, INTA*.

    In single-bus structure, only one transfer at a time; arbitration needed (centralized 8289 or distributed).

    Operation Cycle Example: CPU places address on Address Bus -> asserts MEMR* on Control Bus -> Memory puts data on Data Bus -> CPU latches via MDR.

    Supplementary Interconnections:
    Some texts list Interconnection Structure as 5th view, but exam expects 4. Mention that performance depends on bus width/speed (bandwidth = data_width * clock_rate).

    For diagram: Draw central System Bus as three lines linking four blocks; inside CPU expand to CU+ALU+Registers; show I/O module between bus and peripheral.

13. Q2(b). (b) Discuss the design and logic of a microprogram sequence.20227m

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

    (b) Discuss the design and logic of a microprogram sequence.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Design and Logic of a Microprogram Sequence (7M)

    1. Microprogrammed Control Unit Basics

    Instead of hardwired logic, Control Unit stores microinstructions (control words) in Control Memory (CM) / microstore (ROM/Flash). Each microinstruction is a set of control signals (PCout, MARin, Read etc.). A macro-instruction (e.g., ADD) is executed as a sequence of microinstructions - called microprogram.

    Wilkes (1951) proposed this concept.

    Example: Fetch phase micro-sequence

    T1: PCout, MARin, Read, Select4, Yin, WMFC
    T2: MDRout, IRin, PC+4
    

    2. Microinstruction Format

    • Control field (CW): n bits, one per control line (horizontal) or encoded (vertical).
    • Next Address field: Address of next microinstruction in CM.
    • Branch/Sequencing field: Condition select + branch control.

    Two types control encoding:

    • Horizontal: 1 bit per signal (wide, fast, e.g., 40-60 bit microinstruction)
    • Vertical: Encoded fields (narrow, slow, needs decoder)
    • Nanoprogramming: Two-level.

    3. Design of Microprogram Sequence Logic - Next Microaddress Generation

    After executing current microinstruction at address uPC, how to find next uPC ?

    Three techniques:

    a) Sequential + Explicit Address:
    Next address supplied in current microinstruction. Simple but wastes bits if many sequential steps.

    uPC_next = Addr field of current microinstruction

    b) Incremental uPC + Branch (Most common):
    Use microprogram counter uPC that increments by 1 by default; if branch condition true, load address from current microinstruction.

    if (Branch = 0)   uPC = uPC + 1
    else if (Cond true) uPC = BranchAddress
    else              uPC = uPC + 1
    

    Uses uPC register + incrementer + MUX. Condition flags: ZERO, CARRY, OPCODE bits, INTERRUPT, BUSY.

    c) Mapping via Opcode (Dispatch):
    After fetch & decode, opcode bits in IR map to starting address of corresponding microprogram via mapping ROM / decoder.

    Start Address = Mapping(IR[opcode])
    E.g., ADD (opcode 0010) -> µaddr 0x10, SUB -> 0x18.

    Implemented as: High bits from table + low bits from opcode. Often a Dispatch ROM does µAddr = Base + opcode * offset.

    d) Combinations: Two-phase sequencing

    Modern microprogrammed CU does:

    1. Fetch sequence (fixed at µaddr 0)
    2. Decode/dispatch (branch on IR opcode)
    3. Execute sequence for that opcode
    4. Branch back to fetch or handle indirect addressing / interrupt.

    4. Logic Diagram (Next Address Generator)

             +-----+  Condition codes (FLAGS, IR bits)
             | MUX |<-----------------+
             +-----+                  |
                ^  +-------------+   +-----------+
                |  | Branch Addr |   | Condition |
                |  | from µIR    |   | Select    |
                |  +-------------+   +-----------+
    +-----+ +---+----+ +--------+    +----------+   +----+
    | uPC |->| CM   |->| µIR    |---->| Next Addr|-->|uPC |
    | Reg |<-| (ROM)|  | (hold) |    | Logic    |   |    |
    +-----+ +---+----+ +--------+    +----------+   +----+
       ^        |         | control signals ---------> to CPU datapath
       +--------+ Incrementer (uPC+1) ---------------+
    

    Components: Control Memory (512 x 36 bit typical), Control Address Register (CAR/uPC), Control Data/Register (CDR/µIR), Next-address logic (incrementer + branch MUX + mapping PROM).

    5. Example Microprogram Sequence for ADD R1, (R2)

    Assume instruction: ADD R1, [R2] (R1 = R1 + Mem[R2])

    µAddr : Microoperation Comment
    0 : PCout, MARin, Read, WMFC Fetch opcode
    1 : MDRout, IRin, PC++ Load IR
    2 : R2out, MARin, Read Use R2 as address
    3 : MDRout, Yin, WMFC Load operand to Y
    4 : R1out, SelectY, Add, Zin ALU ADD
    5 : Zout, R1in, END Write back, return to fetch

    Dispatch after µaddr1: If opcode = ADD, µPC = 2, if BRA then goto branch routine, etc.

    6. Design Steps (for exam)

    1. List datapath control signals needed (Register in/out, ALU function, Memory Read/Write, PC inc).
    2. Write micro-operation sequences for each macro instruction (fetch-decode-execute).
    3. Encode signals into µinstruction control field (horizontal/vertical choice) - consider control word width vs decode delay.
    4. Determine sequencing needed: sequential flow, conditional branch on flags/ opcode, subroutine calls (e.g., for interrupt handling, CALL micro-subroutine with µ-stack).
    5. Choose next-address logic implementation: plain counter vs mapping ROM; assign CM addresses; generate mapping function.
    6. Optimize with field encoding, nanostore, or writable control memory (WCS) for vertical microprogramming to reduce size.

    Advantages: Flexible (change microprogram to change instruction set), easier debugging, supports complex CISC (IBM 360, 68000, x86). Disadvantage: Slower than hardwired due to CM access (1 cycle extra); modern RISC uses hardwired, but x86 internally translates CISC to RISC µops via microcode.

    Diagram to draw: Microprogrammed CU block with CM, CAR, CDR, mapping logic, and next-address generation MUX branching back.

14. Q3. (3). Consider a hypothetical 32-bit microprocessor having 32-bit instructions composed of two fields—the first byte contains the opcode and the remainder the immediate operand or an operand address. (a) What is the maximum directly addressable memory capacity (in bytes)? (b) Discuss the impact on the system speed if the microprocessor bus has— &nbsp;&nbsp;&nbsp;&nbsp;i) a 32-bit local address bus and a 16-bit local data bus, or &nbsp;&nbsp;&nbsp;&nbsp;ii) a 16-bit local address bus and a 16-bit local data bus. \(c\) How many bits are needed for the program counter and the instruction register?202214m

    Module 4: Memory Organization

    (3). Consider a hypothetical 32-bit microprocessor having 32-bit instructions composed of two fields—the first byte contains the opcode and the remainder the immediate operand or an operand address.

    (a) What is the maximum directly addressable memory capacity (in bytes)?

    (b) Discuss the impact on the system speed if the microprocessor bus has—
        i) a 32-bit local address bus and a 16-bit local data bus, or
        ii) a 16-bit local address bus and a 16-bit local data bus.
    (c) How many bits are needed for the program counter and the instruction register?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Hypothetical: Instruction = 32 bits = 8 bits opcode + 24 bits address/immediate.

    (a) Maximum Directly Addressable Memory Capacity

    Direct field = $32-8 = 24$ bits.

    If byte-addressable: $Capacity = 2^{24}$ bytes $=16,777,216$ B $=16$ MB.

    If word-addressable (32-bit word =4B): $2^{24}$ words $= 2^{24}\times4 = 2^{26}$ B $=64$ MB, i.e. $4M$ words.

    Note: If microprocessor internally has full 32-bit address bus, theoretical max = $2^{32}$ B $=4$ GB, but with given format without indirect/indexing you can only encode 24-bit direct address $\Rightarrow$ only $16$ MB directly without using indirect or paging.

    (b) Impact of Bus Width on Speed

    Assume memory and CPU are 32-bit, but buses narrower:

    i) 32-bit address bus, 16-bit data bus

    • Address bus 32-bit $\Rightarrow$ can address full $2^{32}=4$ GB.
    • Data bus 16-bit $\Rightarrow$ each 32-bit instruction or operand needs 2 bus cycles to fetch/transfer (16 bits per cycle).
      • e.g. Instruction fetch: $T_{fetch}=2\times T_{bus}$ vs $1\times$ with 32-bit data bus.
      • Data read/write of 32-bit word also 2 cycles. Bus bandwidth halved: $BW = 16$ bits/cycle vs $32$.
      • Needs two memory accesses, causes wait states, effective CPI increases.
      • Still functionally correct, but speed roughly ~50% for memory-intensive code + extra control logic (byte assembly, multiplexing).

    ii) 16-bit address bus, 16-bit data bus

    • Address 16-bit $\Rightarrow$ directly addressable = $2^{16}=64$ KB only! Massive limitation.
      • To access beyond 64KB need banking, segment registers, page registers, or multiplexed address (like 8086 with 20-bit via segment:offset) – adds software/hardware overhead and slowdown.
      • Cannot use full 32-bit address field; higher bits must be latched in two cycles (address multiplexing) or ignored.
    • Data 16-bit $\Rightarrow$ same 2-cycle fetch as case (i).
    • Overall: Much slower than (i) + severely limited memory. Requires extra bus cycles to send full 32-bit address (send low 16 then high 16) if attempting to address 4GB, effectively 2 address cycles + 2 data cycles per access. System speed degraded by $> 2\times$ and programmability restricted.

    Summary: Widening address bus increases address space; widening data bus increases throughput. Halving data bus doubles memory cycles. Halving address bus collapses address space.

    (c) Bits needed for PC and IR

    • Instruction Register (IR): Must hold full instruction $=32$ bits (8 opcode +24 operand). So $IR=32$ bits.
    • Program Counter (PC): Must hold address of next instruction.
      • If holding direct field only: $24$ bits (to address $16$ MB).
      • If holding full memory address (32-bit address bus): $32$ bits to address full $4$ GB, even though instruction can only encode 24 bits directly (rest via indirect).
      • Practical design: $PC=32$ bits, $IR=32$ bits. For byte-addressable with word-aligned instructions (4B), PC increments by 4.

    Exam answer: $IR=32$ bits, $PC=24$ bits minimum ($32$ bits for full 4GB system).

15. Q4(a). A set-associative cache has a block size of four 16-bit words and a set size of 2. The cache can accommodate a total of 4096 words. The main memory size that is cacheable is 64K 32 bits. Design the cache structure and show how the processor’s addresses are interpreted.20227m

    Module 4: Memory Organization

    A set-associative cache has a block size of four 16-bit words and a set size of 2. The cache can accommodate a total of 4096 words. The main memory size that is cacheable is 64K 32 bits. Design the cache structure and show how the processor’s addresses are interpreted.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Set-Associative Cache Design (Numerical)

    Given: Block = $4 \times 16$-bit words $=64$ bits $=8$ bytes
    Cache capacity $=4096$ words $\times16$ bit $=65536$ bits $=8192$ bytes
    Set size $k =2$ (2-way set-associative)
    Cacheable main memory $=64K \times32$ bits $=65536\times4$ bytes $=256$ KB

    1. Number of Blocks & Sets

    $$N_{blocks}= \frac{\text{Cache words}}{\text{words per block}} = \frac{4096}{4}=1024 \text{ blocks}$$

    $$N_{sets}= \frac{N_{blocks}}{k}= \frac{1024}{2}=512 \text{ sets}$$

    $$Set\;index\;bits = \log_2 N_{sets}= \log_2 512 =9 \text{ bits}$$

    $$Block\;offset\;(word) = \log_2 4 =2 \text{ bits (selects one of 4×16-bit words)}$$
    If normalized to 32-bit CPU word: block $=2\times32$ bits $\Rightarrow$ offset $=1$ bit. Add byte offset $1$ bit if byte-addressed.

    2. Address Interpretation

    Main memory $64K\times32$ bits needs $16$ bits for 32-bit word address ($2^{16}=64K$). Equivalent $128K\times16$ bits needs $17$ bits for 16-bit word address.

    Case A - 16-bit word address (most exam-expected):
    Total 17 bits ($0$-$16$ for $128K$)

    $$Tag\;bits = 17 - Set\;bits - Word\;offset =17-9-2=6 \text{ bits}$$

    17-bit word address:
    | Tag (6) | Set index (9) | Word (2) |
      16-11      10-2            1-0
    

    If CPU byte-addressed: add $1$ bit byte offset inside 16-bit word:
    Tag(6) | Set(9) | Word(2) | Byte(1) =18 bits total for $256$KB.

    Case B - 32-bit word address (normalized):
    Total $16$ bits, block $=2$ words

    16-bit address:
    | Tag (6) | Set (9) | Block offset (1) |
     15-10      9-1          0
    

    With byte offset: Tag(6)|Set(9)|Word(1)|Byte(2) =18 bits ($Byte2$ because 32-bit =4 bytes).

    3. Cache Structure Design

    • Organization: $512$ sets $\times$ $2$ lines/set $=1024$ lines.
    • Each line: Valid(1) + Dirty(1) + Tag(6) + Data(64 bits = 4×16 bits). Optionally LRU bit per set (1 bit for 2-way).
    • Data RAM: $8192$ bytes, divided into $1024$ blocks of 8 bytes.
    • Tag RAM: $1024 \times 6$ bits (or $512\times2\times6$ ).
    • Size: Total tag storage $\approx 1024\times6=6144$ bits.

    CPU Address (17-bit word) ---> [Tag 6] [Set 9] [W 2]
                                      |       |      |
                              +-------+ +-----+ +----+
                              |         |      |    word mux 4:1
                      Tag compare (×2)  --> set decoder 512 --> selected set's 2 tags
                              | HIT if tag match & Valid=1
                              v
                        Data out (selected 16-bit word or 32-bit word)
    

    Operation: Set field selects one of 512 sets (both ways read in parallel); Tag field compared associatively with 2 tags in set; if match, Word offset selects one of 4 words in block (or 1 of 2×32-bit words). Replacement uses LRU per set.

    For exam diagram show set decoder, two comparators, $2:1$ MUX and valid/LRU bits. Numbers: 512 sets, 2 lines/set, 8 bytes/block, 9+2+6 split.

    Check: Cache ratio $= 8\text{KB} / 256\text{KB}=1/32$.

16. Q4(b). Explain two techniques for enhancing the performance of computers with multiple execution pipelines.20227m

    Module 3: Pipelining

    Explain two techniques for enhancing the performance of computers with multiple execution pipelines.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Two Techniques for Enhancing Performance with Multiple Execution Pipelines

    Multiple execution pipelines (superscalar / superpipelined architecture) allow Instruction Level Parallelism (ILP) by executing more than one instruction per clock. Two key techniques:

    1. Superscalar Execution (Multiple Issue Pipeline)

    • Concept: Processor contains $m$ parallel pipelines (e.g., Integer pipe, FP pipe, Load/Store pipe). In each cycle, issue logic fetches and issues $n$ instructions simultaneously ($n$-way superscalar) if no dependencies.
    • Hardware required:
      • Multiple functional units: ALU1, ALU2, FPU, Branch unit, Load/Store unit
      • Instruction Fetch & Decode capable of $n$ instructions/cycle
      • Dependency checking / Scoreboarding / Tomasulo algorithm to detect data hazards (RAW, WAR, WAW)
      • Register renaming to remove false dependencies
    • Example: 2-way superscalar can issue ADD R1,R2,R3 and MUL R4,R5,R6 together if independent.
    • Advantage: Increases throughput ideal CPI $\to 1/n$ (e.g., CPI 0.5 for 2-way). Exploits ILP without compiler support (dynamic).
    • Limitation: Complex issue logic, requires out-of-order execution and large window; limited by true dependencies and branches.

    2. Superpipelining and Out-of-Order / Speculative Execution (Complementary techniques)

    Often paired with superscalar; other major technique is VLIW-like / Superpipelined + Branch Prediction & Speculative Execution (can also be answered as Superpipelining or VLIW).

    a) Superpipelining:

    • Divides pipeline into many finer stages (e.g., 8-10 stages vs classic 5-stage: IF1, IF2, ID1, ID2, EX1, EX2, WB). Clock period = 1/m of base, so multiple instructions are in different sub-stages of same functional pipe - higher clock rate.
    • Combination Superscalar + Superpipelining = Super-speculative processor (e.g., Pentium 4).

    b) Out-of-Order Execution + Register Renaming + Speculative/Branch Prediction (essential to keep multiple pipelines busy):

    • Multiple pipelines stall on hazards/branches. Solution:
      • Register Renaming: maps architectural registers to larger physical register file to eliminate WAR/WAW, allowing parallel execution.
      • Out-of-Order Execution: Instructions wait in Reservation Stations; execute as soon as operands ready, not program order. ReOrder Buffer (ROB) commits in order.
      • Branch Prediction + Speculative Execution: Predict branch direction (2-bit predictor, BTB) and speculatively execute down predicted path to keep pipelines filled. On mispredict, flush.
      • Dynamic Scheduling: Tomasulo / Scoreboard.

    Alternative valid answer - VLIW (Very Long Instruction Word):
    Compiler packs $k$ independent operations into one very long instruction word (e.g., 128-256 bit). Hardware is simple (no dependency check), compiler does static scheduling. Example: IA-64/Itanium. Merits: simple hardware; Demerits: poor code density, compiler dependent, binary incompatibility.

    Performance gain summary: With $N$ pipelines ideal speedup $\to N$ if hazards avoided. Combination of ** Superscalar (space parallelism) + Superpipelining (time parallelism) + OOO/Speculation/Renaming** yields practical speedup 1.5x-3x per core.

    Feature	Superscalar	Superpipeline/VLIW
    Parallelism	Space - multiple pipes	Time - finer clocks / compiler-packed
    Dependency check	Hardware dynamic	VLIW: Compiler static
    Complexity	High hardware	VLIW: simple HW, complex compiler

17. Q5(a). Calculate (72530 - 13250) using ten's complement arithmetic. Assume rules similar to those for two's complement arithmetic.20227m

    Module 1: Functional Block of computer and Data representaion

    Calculate $(72530 - 13250)$ using ten's complement arithmetic. Assume rules similar to those for two's complement arithmetic.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Ten's Complement Subtraction: $72530 - 13250$

    For $n=5$ digits, ten's complement of $N$ is $10^n - N = 9\text{'s complement}+1$.

    Rule (like 2's complement): $A-B = A + \text{10's comp}(B)$. If end carry =1, discard carry, result positive. If no carry, result negative and is the 10's complement of magnitude.

    Step 1: 9's complement of B=13250
    $$99999 - 13250 = 86749$$

    Step 2: 10's complement of B
    $$86749 + 1 = 86750$$
    Check: $13250+86750 = 100000 = 10^5$

    Step 3: Add to A
    $$A + \text{10's comp}(B) = 72530 + 86750 = 159280$$

    Step 4: Discard end carry
    We have $n=5$ digits, the 6th digit 1 is end carry. Discard it $\rightarrow$ $59280$.

    $$159280 \xrightarrow{\text{drop carry}} 59280$$

    Verification: $72530-13250 = 59280$.

    If the sum had no end carry, e.g., $13250-72530$, result would be $26520$ without carry, indicating negative. Then negate: $10\text{'s comp}(26520)=73480$, so answer $-73480$.

18. Q5(b). List and briefly explain five important instruction set design issues.20227m

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

    List and briefly explain five important instruction set design issues.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Five Important Instruction Set Design Issues

    1. Operation Repertoire (Operations to Provide)

    What operations - data movement (LOAD/STORE), arithmetic (ADD,SUB,MUL,DIV), logical (AND/OR/SHIFT), control (BRANCH,CALL), I/O. Need completeness (all uses) vs orthogonality. Too many ops -> complex decode; too few -> inefficient programs (e.g., no multiply must emulate). RISC keeps ~50-100 simple ops; CISC has >200 complex.

    2. Data Types & Operand Representations

    What types supported natively - integer (8/16/32/64b), floating (IEEE754), decimal/BCD, char/string, boolean. Affects ALU design and format. Choice of word length, endianness, signed (2's complement) vs unsigned.

    3. Instruction Format & Length

    Fixed vs variable length, number of fields: opcode + operands + addressing mode + immediate. Tradeoff: fixed (RISC, e.g., 32b, 3-reg) simple fetch/decode but code density low; variable (x86, 1-15B) dense but complex decoder. Number of addresses per instruction: 0 (stack),1 (accumulator),2,3-address.

    4. Addressing Modes

    How operand address specified:

    • Immediate, Direct, Register, Register-Indirect, Indexed ($EA=Base+Index\times scale$), Autoincrement, PC-relative, Stack.
      More modes -> flexibility but hardware complexity & CPI variance. Must balance for compilers (RISC favors Reg+Immediate+Displacement only).

    5. Registers - Number, Use, Organization

    How many visible registers? 8 (x86), 32 (MIPS/ARM). General Purpose vs specialized (accumulator, index). Affects operand fetching, procedure call convention, spill to memory, context switch cost. Also interacts with instruction format (3-bit vs 5-bit reg fields).

    Bonus (mention any):

    • Instruction Set Orthogonality & Completeness - all modes work with all ops vs irregular.
    • Control Flow & Condition Codes - how branches/flags handled.
    • Memory Alignment & Byte Ordering

    Good design balances code density, CPI, decode simplicity, compiler target, backward compatibility.

19. Q6. The x86 architecture includes an instruction called decimal adjust after addition (DAA). DAA performs the following sequence of instructions: ``plaintext if((AL AND 0FH) > 9) OR (AF = 1) then AL ← AL + 6; AF ← 1; else AF ← 0; endif; if(AL > 9FH) OR (CF = 1) then AL ← AL + 60H; CF ← 1; else CF ← 0; endif. `` "H" indicates hexadecimal. AL is an 8-bit register that holds the result of addition of two unsigned 8-bit integers. AF is a flag set if there is a carry from bit 3 to bit 4 in the result of an addition. CF is a flag set if there is a carry from bit 7 to bit 8. Explain the function performed by the DAA instruction.202214m

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

    The x86 architecture includes an instruction called decimal adjust after addition (DAA). DAA performs the following sequence of instructions:

    if((AL AND 0FH) > 9) OR (AF = 1) then
        AL ← AL + 6;
        AF ← 1;
    else
        AF ← 0;
    endif;
    if(AL > 9FH) OR (CF = 1) then
        AL ← AL + 60H;
        CF ← 1;
    else
        CF ← 0;
    endif.
    

    "H" indicates hexadecimal. AL is an 8-bit register that holds the result of addition of two unsigned 8-bit integers. AF is a flag set if there is a carry from bit 3 to bit 4 in the result of an addition. CF is a flag set if there is a carry from bit 7 to bit 8. Explain the function performed by the DAA instruction.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Function of DAA Instruction

    1. Context

    x86 AL holds two packed BCD digits (Binary Coded Decimal): high nibble = tens digit 0-9, low nibble = units digit 0-9, e.g. 0x27 = decimal 27. Binary ADD AL, BL adds them as 8-bit binary and sets flags AF (auxiliary carry from bit3) and CF. Result may be invalid BCD (nibble >9 or unadjusted carry) and needs correction to remain valid packed BCD.

    DAA = Decimal Adjust after Addition converts the binary result in AL to correct packed BCD and sets CF/AF to represent decimal carry.

    2. What the pseudo-code does

    if (low_nibble >9) OR (AF=1) then AL+=6; AF=1 else AF=0;  // correct low digit
    if (AL >9FH) OR (CF=1) then AL+=0x60; CF=1 else CF=0;      // correct high digit
    

    • AL AND 0FH isolates low nibble.
    • +6 = 0000 0110 : adds 6 to low nibble; causes carry to high nibble if needed, skipping the 6 invalid hex values A-F.
    • +60H = 0110 0000 : adds 6 to high nibble (60H = 96 = 6*16).

    AF and CF after DAA represent decimal carries (not binary), for multi-byte BCD addition (propagate with ADC+DAA).

    3. Why +6 ?

    In BCD, counting after 9 should go to 10 (0x10), but binary after 0x09 goes to 0x0A. Gap = 6 (0x0A - 0x0F are invalid). Adding 6 forces carry and wraps to correct BCD value:
    9+1 = 0x0A -> +6 = 0x10 (correct BCD for 10).

    4. Examples

    Example 1: AL=0x29 + 0x15 = 0x3E (binary). Low nibble E=14>9

    • First IF true: AL=0x3E+0x06=0x44, AF=1
    • Second IF: AL=0x44 <=0x9F and CF=0 -> CF=0
    • Result 0x44 = BCD 44 . Correct: 29+15=44 decimal.

    Example 2: AL=0x49+0x38=0x81 . AF=0? 9+8=17 -> low nibble 1 with AF=1 (carry from bit3)

    • First IF: (1>9? No) but AF=1 -> AL=0x81+0x06=0x87, AF=1
    • Second: 0x87 <=9F and CF=0 -> CF=0
    • Result 0x87 = 87 . Correct: 49+38=87.

    Example 3: AL=0x99+0x99=0x32 binary (0x132 truncated) with CF=1, AF=1

    • First IF: 0x2>9?No but AF=1 -> AL=0x32+0x06=0x38, AF=1
    • Second IF: CF=1 -> AL=0x38+0x60=0x98, CF=1
    • Result 0x98 with CF=1 => BCD 198 (CF is hundreds carry). Correct: 99+99=198.

    5. Summary of Function

    DAA performs binary-to-BCD correction after an 8-bit ADD of two packed BCD numbers:

    • Makes each 4-bit nibble a valid decimal digit 0-9
    • Propagates decimal carry correctly between digits
    • Leaves AL = low two decimal digits of sum (00-99) and CF = high decimal carry (0 or 1) for extended BCD arithmetic (e.g., ADC + DAA chain for multi-byte BCD such as 4-digit BCD with AL+AH).

    Without DAA, binary addition would yield hex digits A-F which have no BCD meaning. With DAA, x86 can do decimal arithmetic directly used in financial/cobol applications where binary rounding errors unacceptable.

20. Q7. A non-pipelined processor has a clock rate of 2.5 GHz and an average CPI (cycles per instruction) of 4. An upgrade to the processor introduces a five-stage pipeline. However, due to internal pipeline delays, such as latch delay, the clock rate of the new processor has to be reduced to 2 GHz. (a) What is the speedup achieved for a typical program? (b) What is the MIPS rate for each processor?202214m

    Module 3: Pipelining

    A non-pipelined processor has a clock rate of $2.5$ GHz and an average CPI (cycles per instruction) of $4$. An upgrade to the processor introduces a five-stage pipeline. However, due to internal pipeline delays, such as latch delay, the clock rate of the new processor has to be reduced to $2$ GHz.

    (a) What is the speedup achieved for a typical program?

    (b) What is the MIPS rate for each processor?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    (a) Speedup

    Let $N$ = no. of instructions.

    Non-pipelined:

    • Clock $f_{np}=2.5\text{ GHz} \Rightarrow T_{np}=0.4\text{ ns}$
    • $CPI_{np}=4$
    • $T_{old}= N\cdot CPI_{np}\cdot T_{np}= N\cdot 4 / f_{np}= N\cdot 1.6\text{ ns}$

    Time per instruction $= 1.6\text{ ns}$.

    Pipelined (5-stage, ideal, no hazards):

    • $f_{p}=2.0\text{ GHz} \Rightarrow T_{p}=0.5\text{ ns}$
    • Ideal $CPI_{p}=1$ (one instruction completes per cycle in steady state). Ignoring fill/drain overhead for large $N$: $T_{new}= N\cdot 1 \cdot T_{p}= N\cdot 0.5\text{ ns}$.

    With fill overhead: $T_{new}= (k+N-1)T_{p}$ where $k=5$, $\approx N T_{p}$ for $N\gg k$.

    $$Speedup = \frac{T_{old}}{T_{new}} = \frac{CPI_{np}/f_{np}}{CPI_{p}/f_{p}} = \frac{4/2.5}{1/2}= \frac{1.6}{0.5}=3.2$$

    So $\approx 3.2\times$ speedup in the ideal hazard-free case. If pipeline stalls/hazards raise $CPI_{p}$ to e.g. 1.2 then $Speedup = (4/2.5)/(1.2/2)=2.67$.

    Maximum theoretical speedup ignoring clock reduction: $CPI_{np}/CPI_{p}=4$; with clock penalty $2/2.5=0.8$, net $4\times0.8=3.2$.

    (b) MIPS rate

    $$MIPS = \frac{f}{CPI\times10^{6}}$$

    • Non-pipelined: $MIPS_{np}= \dfrac{2.5\times10^{9}}{4\times10^{6}} = \mathbf{625\ MIPS}$

    • Pipelined (ideal $CPI=1$): $MIPS_{p}= \dfrac{2.0\times10^{9}}{1\times10^{6}} = \mathbf{2000\ MIPS}$

    If hazards included, e.g. $CPI_{p}=1.14$, $MIPS_{p}\approx 1754$. In general $MIPS_{p}=2000/CPI_{p}$.

    Throughput gain $=2000/625=3.2$ same as speedup.

21. Q8(a). Briefly explain the two basic approaches used to minimize register-memory operations on RISC machines.202216m

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

    Briefly explain the two basic approaches used to minimize register-memory operations on RISC machines.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    RISC instruction set keeps only load/store accessing memory to simplify pipeline. Yet stack frames, parameter passing and spills cause many register↔memory moves. Two approaches to minimize:

    1. Hardware Approach - Large Register File with Register Windows (Berkeley RISC I)

    Provide very large register file (e.g., 32-128 registers) and partition into overlapping windows per procedure.

    • Registers divided into: Global (G0-Gn) - shared by all procedures, Local, In, Out.
    • On call, CPU switches to new window: Out registers of caller become In registers of callee (overlap) - parameters passed without memory store/load.
    • Only window pointer changes, no memory traffic for save/restore on call/return unless window overflows/underflows.
    • Example: RISC I has 8 windows ×16 registers + 10 globals = 138 registers, but only 32 visible at a time. Sun SPARC implements this.
    • Effectively caches procedure context in registers, cutting memory operations by 50%+.

    Alternative hardware: Register Stack with renaming.

    2. Software/Compiler Approach - Optimized Register Allocation

    • Efficient graph-coloring register allocator keeps most-used variables (loop indices, temporaries) in registers for entire lifetime, minimizing loads/stores.
    • Compiler optimizations: keep variables in registers across basic blocks, common subexpression elimination, loop invariant movement, leaf-procedure optimization.
    • Instruction scheduling and delayed load handling: compiler inserts independent instructions after load to avoid stall, reducing load interlocks.
    • Stanford MIPS approach: Use compiler rather than hardware windows - relies on large but flat register file (32 registers) and smart allocation.

    Both aim to exploit locality: hardware caches context via windows; software keeps working set in registers. Combined, RISC achieves CPI ≈1 while CISC spends many cycles on register-memory traffic.

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. Q8(b). A computer has 16 registers, an ALU with 32 operations, and a shifter with 8 operations, all connected to a common bus system. (i) Formulate a control word for micro-operation. (ii) Show the bits of the control word that specify the micro-operation R4 \leftarrow R5 + R6.20227m

    Module 1: Functional Block of computer and Data representaion

    A computer has 16 registers, an ALU with 32 operations, and a shifter with 8 operations, all connected to a common bus system.

    (i) Formulate a control word for micro-operation.

    (ii) Show the bits of the control word that specify the micro-operation R4 $\leftarrow$ R5 + R6.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Given: 16 registers → $4$ bits to address, 32 ALU ops → $5$ bits, 8 shifter ops → $3$ bits. Common bus system: any register can drive bus (SEL A, SEL B), any register can be destination.

    (i) Control Word Format

    For register-to-register micro-operation via two bus passes or one ALU+shifter path:

    Field	Bits	Function
    SELA	4	Select source register A to bus → ALU A input
    SELB	4	Select source register B to bus → ALU B input
    SELD	4	Select destination register to receive result
    ALUF	5	ALU operation select
    SHF	3	Shifter operation select
    Total	20

    Format: SELA (4) | SELB (4) | SELD (4) | ALUF (5) | SHF (3) = 20-bit control word. If including control bits for bus enable, memory, etc., additional bits may be added, but core is 20 bits.

    Encoding: Registers: $R0=0000, R1=0001, R2=0010, R3=0011, R4=0100, R5=0101, R6=0110,\dots,R15=1111$.
    ALU ops example: $ADD=00010$, $SUB=00011$, etc. Shifter: $No\_shift/Pass=000$, $SHL=001$, etc.

    (ii) Bits for $R4 \leftarrow R5 + R6$

    • SELA = $R5 = 0101$
    • SELB = $R6 = 0110$
    • SELD = $R4 = 0100$
    • ALUF = $ADD = 00010$ (assuming code 00010 for ADD)
    • SHF = $No\ shift = 000$

    Control word = 0101 0110 0100 00010 000

    In hex grouping: 0x5 6 4 02 0 → binary 01010110010000010000 = 0x56410 (20 bits).

    If shifter field considered at LSB side, full 20-bit word: SELA SELB SELD ALUF SHF = 0101 0110 0100 00010 000.

    Micro-operation execution: Bus: $R5 \rightarrow ALU.A$, $R6 \rightarrow ALU.B$, ALU performs $A+B$, result through shifter (unshifted) → bus → $R4$ latch via SELD decode.

    If microinstruction also contains SEQ bits for next-address, additional bits for carry-in etc. would extend word, but core operation bits as above.

24. Q9. Let a be the percentage of a program code that can be executed simultaneously by n processors in a computer system. Assume that the remaining code must be executed sequentially by a single processor. Each processor has an execution rate of x MIPS. (a) Derive an expression for the effective MIPS rate when using the system for exclusive execution of this program, in terms of n, \alpha, and x. (b) If n=16 and x=4 MIPS, determine the value of that will yield a system performance of 40 MIPS.202214m

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

    Let a be the percentage of a program code that can be executed simultaneously by $n$ processors in a computer system. Assume that the remaining code must be executed sequentially by a single processor. Each processor has an execution rate of $x$ MIPS.

    (a) Derive an expression for the effective MIPS rate when using the system for exclusive execution of this program, in terms of $n$, $\alpha$, and $x$.

    (b) If $n=16$ and $x=4$ MIPS, determine the value of that will yield a system performance of 40 MIPS.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Amdahl's Law – Effective MIPS with n Processors (14 Marks)

    Let $\alpha$ = fraction of code parallelizable (executable on $n$ processors simultaneously), so $(1-\alpha)$ is strictly sequential. Each processor rate = $x$ MIPS.

    Let total instructions = $I$.

    (a) Derivation:

    Time if executed on single processor: $T_1 = \frac{I}{x}$ (in $\mu s$ if $x$ in MIPS, i.e., $10^6$ instr/sec)

    With $n$ processors:

    • Sequential part: $(1-\alpha)I$ instructions at rate $x$ → $T_{seq}= \frac{(1-\alpha)I}{x}$
    • Parallel part: $\alpha I$ instructions shared among $n$ processors, effective rate $n\cdot x$ → $T_{par}= \frac{\alpha I}{n x}$

    Total parallel time: $T_n = T_{seq}+T_{par}= \frac{I}{x}\left[(1-\alpha)+\frac{\alpha}{n}\right]$

    Effective MIPS $M_{eff}= \frac{I}{T_n} = \frac{I}{\frac{I}{x}[(1-\alpha)+\alpha/n]} = \frac{x}{(1-\alpha)+\alpha/n}$

    So $M_{eff}= \frac{x}{(1-\alpha)+\frac{\alpha}{n}} = \frac{n x}{n(1-\alpha)+\alpha}$

    This is Amdahl's law: Speedup $S = \frac{T_1}{T_n}= \frac{1}{(1-\alpha)+\alpha/n}$, and $M_{eff}=x\cdot S$.

    Checks: If $\alpha=0$ → $M_{eff}=x$ (no gain). If $\alpha=1$ → $M_{eff}=n x$ (linear). If $n\to\infty$ → $M_{eff}\to \frac{x}{1-\alpha}$ (bottleneck by sequential part).

    (b) Numerical:

    Given $n=16$, $x=4$ MIPS, $M_{eff}=40$ MIPS. Find $\alpha$.

    $40 = \frac{4}{(1-\alpha)+\alpha/16}$

    $(1-\alpha)+\alpha/16 = \frac{4}{40}=0.1$

    $1-\alpha+0.0625\alpha =0.1$

    $1-0.9375\alpha =0.1$

    $0.9375\alpha =0.9$

    $\alpha = \frac{0.9}{0.9375}=0.96$

    $\alpha = 96\%$

    Interpretation: 96% of code must be parallelizable to achieve 40 MIPS (≈10× speedup) with 16×4 MIPS processors. If $\alpha$ lower, cannot reach 40 MIPS even with infinite processors (max would be $x/(1-\alpha)$).