Computer Organization & Architecture 2023

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

Solution: A pipeline stage consists of both sequential and combinational circuits. The combinational logic performs the actual computation, while sequential elements (registers/latches) hold the intermediate results between stages.

Answer: (ii) 1-way set associative

Solution: A direct mapped cache is equivalent to a 1-way set associative cache. In direct mapping, each memory block can only go to one specific cache line, meaning each set has only one block (1-way).

Answer: (iv) All of these

Solution: Pipeline performance suffers due to: (i) Different stage delays cause the slowest stage to become the bottleneck, (ii) Data dependencies cause pipeline stalls (hazards), (iii) Shared resources cause structural hazards when multiple stages need the same resource simultaneously.

Answer: (ii) 200 ns

Solution: Average Access Time = Hit Ratio × Cache Time + (1 - Hit Ratio) × (Cache Time + Memory Time) = 0.9 × 100 + 0.1 × (100 + 1000) = 90 + 0.1 × 1100 = 90 + 110 = 200 ns

Answer: (iii) MISD

Solution: MISD (Multiple Instruction, Single Data) has no practical usage as it's difficult to find applications where multiple different instructions need to operate on the same data simultaneously. SISD (single processor), SIMD (vector processors), and MIMD (multiprocessors) all have practical applications.

Answer: (ii) Facilitates easy implementation of new instructions

Solution: Microprogrammed control units store control signals in a control memory (microprogram), making it easy to modify or add new instructions by simply updating the microprogram. While slower than hardwired control, they offer greater flexibility.

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

Solution: In memory-mapped I/O, I/O devices are assigned addresses within the same address space as memory. This allows the processor to use the same instructions for both memory and I/O operations.

Answer: (iii) 1024

Solution: Required memory: 32K × 32 bits = 32768 × 32 bits Available chip: 128 × 8 bits

For width: 32/8 = 4 chips needed in parallel For depth: 32768/128 = 256 chips needed

Total chips = 4 × 256 = 1024 RAMs

Answer: (ii) Structural hazard

Solution: When the processor stalls because a required hardware resource (like instruction memory or ALU) is not available, it's called a structural hazard. This occurs when multiple instructions need the same resource at the same time.

Answer: (i) Immediate

Solution: In immediate addressing mode, the operand value itself is specified directly in the instruction. For example, ADD R1, #5 adds the immediate value 5 to register R1.

Answer:

Pipeline Hazards:

Pipeline hazards are situations that prevent the next instruction from executing during its designated clock cycle. There are three types:

1. Structural Hazards: Occur when hardware cannot support all possible combinations of instructions in simultaneous execution.

Example: Single memory for both instruction fetch and data access causes conflict when both stages need memory access.

2. Data Hazards: Occur when an instruction depends on the result of a previous instruction still in the pipeline.

Example:

ADD R1, R2, R3
SUB R4, R1, R5  // SUB needs R1's value before ADD completes

Types: RAW (Read After Write), WAR (Write After Read), WAW (Write After Write)

3. Control Hazards: Occur due to branch instructions that change the program counter.

Example: A conditional branch instruction - the pipeline doesn't know which instruction to fetch next until the branch condition is evaluated.

Answer:

Addressing Modes:

Addressing mode specifies how to interpret the address field of an instruction to get the effective operand address.

Why computers use addressing modes:

• Provide flexibility in accessing operands
• Support different data structures (arrays, stacks)
• Reduce program size
• Enable position-independent code

Modes without address fields:

1. Implied/Implicit Mode: The operand is implicitly specified by the opcode itself. Example: CMA (Complement Accumulator) - operand is always the accumulator

2. Register Mode: The operand is in a processor register specified by the instruction. Example: ADD R1, R2 - operands are in registers R1 and R2

Answer:

Given:

• Cache capacity = 16 KB = 16 × 1024 = 16384 bytes
• Block size = 8 words = 8 × 4 = 32 bytes (since word = 32 bits = 4 bytes)
• Physical address space = 4 GB = 2³² bytes
• 4-way set associative

Calculations:

Number of blocks in cache = 16384 / 32 = 512 blocks

Number of sets = Number of blocks / Associativity = 512 / 4 = 128 sets

Address breakdown (32 bits total for 4GB space):

• WORD/Block Offset bits = log₂(Block size in bytes) = log₂(32) = 5 bits
• SET/Index bits = log₂(Number of sets) = log₂(128) = 7 bits
• TAG bits = Total address bits - SET bits - WORD bits = 32 - 7 - 5 = 20 bits

Answer:

Virtual to Physical Address Mapping:

Virtual addresses are mapped to physical addresses using a Page Table:

1. Virtual address is divided into Virtual Page Number (VPN) and Page Offset
2. VPN is used as an index into the page table
3. Page table entry contains the Physical Frame Number (PFN)
4. Physical address = PFN concatenated with Page Offset

The TLB (Translation Lookaside Buffer) caches recent translations for faster access.

Methods of Writing into Cache:

1. Write-Through: Data is written to both cache and main memory simultaneously.

• Advantage: Memory always has consistent data
• Disadvantage: Slower write operations

2. Write-Back: Data is written only to cache. Memory is updated when the block is replaced.

• Advantage: Faster writes
• Disadvantage: Memory may have stale data; requires dirty bit

3. Write-Around: Data is written directly to memory, bypassing cache.

• Used when data won't be read again soon

Answer:

Types of Instruction Formats:

1. Three-Address Format:

• Format: OP A, B, C (Result ← A op B, store in C)
• Example: ADD R1, R2, R3
• Advantage: Flexible, preserves operands
• Disadvantage: Longer instructions

2. Two-Address Format:

• Format: OP A, B (A ← A op B)
• Example: ADD R1, R2 (R1 = R1 + R2)
• Advantage: Shorter than 3-address
• Disadvantage: One operand is overwritten

3. One-Address Format:

• Format: OP A (ACC ← ACC op A)
• Uses accumulator implicitly
• Example: ADD X (ACC = ACC + X)
• Advantage: Short instructions
• Disadvantage: Limited flexibility

4. Zero-Address Format:

• Format: OP (uses stack)
• Example: ADD (pops two operands, pushes result)
• Used in stack-based architectures
• Advantage: Very short instructions
• Disadvantage: Stack management overhead

Answer:

Cache Mapping Techniques:

Answer:

The CLA adder eliminates the ripple carry delay by computing all carries in parallel.

Define Generate (G) and Propagate (P):

• Gᵢ = Aᵢ · Bᵢ (Generate: carry is generated if both inputs are 1)
• Pᵢ = Aᵢ ⊕ Bᵢ (Propagate: carry is propagated if exactly one input is 1)

Carry equations:

• C₁ = G₀ + P₀·C₀
• C₂ = G₁ + P₁·G₀ + P₁·P₀·C₀
• C₃ = G₂ + P₂·G₁ + P₂·P₁·G₀ + P₂·P₁·P₀·C₀
• C₄ = G₃ + P₃·G₂ + P₃·P₂·G₁ + P₃·P₂·P₁·G₀ + P₃·P₂·P₁·P₀·C₀

Sum: Sᵢ = Pᵢ ⊕ Cᵢ

Example: Add A = 1011 and B = 0110 with C₀ = 0

C₁ = 0 + 1·0 = 0 C₂ = 1 + 0·0 + 0·1·0 = 1 C₃ = 0 + 1·1 + 1·0·0 + 1·0·1·0 = 1 C₄ = 0 + 1·0 + 1·1·1 + 1·1·0·0 + 1·1·0·1·0 = 1

Sum = 10001 ✓

Answer:

Cache block number = Memory block mod 8

Final Cache Status: [24, 17, 82, 3, 20, 5, 30, 63]

Answer:

DMA (Direct Memory Access):

DMA is a technique that allows peripheral devices to transfer data directly to/from memory without CPU intervention.

DMA Transfer Process:

1. Initialization: CPU programs the DMA controller with:

   • Starting memory address
   • Number of bytes to transfer
   • Direction (read/write)
   • I/O device address

2. Request: When device is ready, it sends DMA request (DRQ) to DMA controller.

3. Bus Request: DMA controller sends bus request (BR) to CPU.

4. Bus Grant: CPU completes current operation and sends bus grant (BG), releasing the bus.

5. Transfer: DMA controller takes control of bus and transfers data directly between device and memory.

6. Completion: After transfer, DMA controller releases bus and sends interrupt to CPU.

DMA Modes:

• Burst Mode: Entire block transferred at once
• Cycle Stealing: One word at a time between CPU operations
• Transparent Mode: Transfer when CPU not using bus

Answer:

Hardwired Control Unit Components:

1. Instruction Register (IR): Holds the current instruction being executed.

2. Instruction Decoder: Decodes opcode and generates signals indicating operation type.

3. Timing Generator/Sequencer: Generates timing signals (T0, T1, T2...) for sequential control.

4. Control Logic (Combinational Circuit): Generates control signals based on:

   • Decoded instruction
   • Current timing state
   • Status flags

5. Control Signals: Output signals that control ALU, registers, memory, buses.

Control Signal = f(Opcode, Timing State, Flags)

Answer:

Asynchronous Data Transfer:

In asynchronous transfer, data transfer occurs without a common clock. The sender and receiver coordinate using control signals.

Strobe Control:

A single control line (strobe) indicates data validity.

Source-initiated strobe:

1. Source places data on bus
2. Source activates strobe signal
3. Destination reads data
4. Source deactivates strobe

Destination-initiated strobe:

1. Destination activates strobe (requesting data)
2. Source places data on bus
3. Destination reads data
4. Destination deactivates strobe

Handshaking Mechanism:

Uses two control lines for reliable transfer:

• Data Valid (from source)
• Data Accepted (from destination)

Process:

1. Source places data, asserts Data Valid
2. Destination reads data, asserts Data Accepted
3. Source sees acknowledgment, removes data, deasserts Data Valid
4. Destination deasserts Data Accepted
5. Ready for next transfer

Advantage: More reliable, handles speed differences between devices.

Answer:

Multiplicand M = 20 = 00010100 (8 bits) Multiplier Q = -19 = 11101101 (8 bits, 2's complement)

After completing Booth's algorithm iterations:

Result: -380 in 2's complement

Verification: 20 × (-19) = -380 ✓

Answer:

Original 4-stage pipeline:

• Stage delays: 800, 500, 400, 300 ps
• Clock period = max(800, 500, 400, 300) = 800 ps
• Throughput₁ = 1/800 ps

New 5-stage pipeline:

• Stage delays: 600, 350, 500, 400, 300 ps
• Clock period = max(600, 350, 500, 400, 300) = 600 ps
• Throughput₂ = 1/600 ps

Throughput Increase: = ((1/600 - 1/800) / (1/800)) × 100 = ((800 - 600) / 600) × 100 = (200/600) × 100 = 33.33%

Answer:

IEEE 754 Floating Point Standard:

Single Precision (32 bits):

Format: (-1)^S × 1.M × 2^(E-Bias)

• S = Sign bit (0 = positive, 1 = negative)
• E = Biased exponent (Bias = 127 for single precision)
• M = Mantissa (fractional part, leading 1 is implicit)

Example: Represent -13.625 in IEEE 754 single precision

1. Sign: S = 1 (negative)

2. Convert to binary:

   • 13 = 1101₂
   • 0.625 = 0.101₂ (0.5 + 0.125)
   • 13.625 = 1101.101₂

3. Normalize: 1.101101 × 2³

4. Exponent: E = 3 + 127 = 130 = 10000010₂

5. Mantissa: 10110100000000000000000 (23 bits)

Result: 1 10000010 10110100000000000000000

Answer:

Paging is a memory management scheme that eliminates the need for contiguous memory allocation.

Key Concepts:

• Physical memory divided into fixed-size frames
• Logical memory divided into same-size pages
• Page size = Frame size (typically 4KB)

Page Table:

• Maps logical page numbers to physical frame numbers
• Each process has its own page table
• Page table entry contains: Frame number, Valid bit, Protection bits

Advantages:

• Eliminates external fragmentation
• Simplifies memory allocation
• Enables virtual memory

Answer:

Technique to increase memory bandwidth by dividing memory into multiple banks that can be accessed simultaneously.

Types:

1. High-Order Interleaving: Most significant bits select bank
2. Low-Order Interleaving: Least significant bits select bank

Advantage: Effective memory bandwidth = Number of banks × Single bank bandwidth

Answer:

Privileged Instructions:

• Can only be executed in kernel/supervisor mode
• Direct hardware control
• Examples: I/O instructions, halt, interrupt control

Non-Privileged Instructions:

• Can be executed in user mode
• Normal computational operations
• Examples: ADD, SUB, LOAD, STORE

Answer:

Principle that programs tend to access a relatively small portion of their address space at any time.

Types:

1. Temporal Locality: Recently accessed items likely to be accessed again soon
2. Spatial Locality: Items near recently accessed items likely to be accessed soon

Applications:

• Cache Design
• Virtual Memory
• Prefetching
• Branch Prediction