Unit 5: Memory Unit - Subjective Questions

Memory Hierarchy refers to the arrangement of different types of memory in a computer system according to their speed, cost per bit, and access time, so as to achieve a balance between performance and cost.

Levels of Memory Hierarchy (top to bottom):

• CPU Registers – Fastest, smallest, most expensive, located inside the CPU.
• Cache Memory – Very fast SRAM, holds frequently used data.
• Main Memory (RAM) – Moderate speed and cost, holds active programs.
• Auxiliary/Secondary Memory – Magnetic disks, SSDs; large capacity, slower, cheaper.
• Tertiary/Backup Storage – Magnetic tapes, optical disks; largest, slowest, cheapest.

Diagram (conceptual pyramid):

    Registers      (fastest, costliest, smallest)
     Cache
  Main Memory

Auxiliary Memory
Tertiary Storage (slowest, cheapest, largest)

Characteristics as we move down:

• Access time increases
• Cost per bit decreases
• Storage capacity increases
• Frequency of access by CPU decreases

Justification for hierarchy:

• A single memory technology cannot be simultaneously fast, large, and cheap.
• The principle of locality of reference ensures that keeping frequently used data in faster memory gives near-fast-memory performance at near-cheap-memory cost.
• It provides an economical yet high-performance memory system.

Cache Memory is a small, high-speed memory placed between the CPU and main memory. It stores copies of frequently accessed instructions and data to reduce the average time to access memory.

Principle of Locality of Reference:
Programs tend to access a relatively small portion of the address space at any given time. This behavior is called locality of reference and has two forms:

• Temporal Locality (locality in time): If a memory location is referenced, it is likely to be referenced again soon (e.g., loops, repeated instructions).
• Spatial Locality (locality in space): If a location is referenced, nearby locations are likely to be referenced soon (e.g., array traversal, sequential instructions).

How locality makes cache effective:

• Because of temporal locality, recently used data kept in cache is reused, giving cache hits.
• Because of spatial locality, transferring a block of neighboring words into cache satisfies future references.
• A high hit ratio results, so most references are served at cache speed rather than slow main memory speed.

Performance measure – Hit Ratio:

Average access time:

where is cache access time and is main memory access time.

Mapping techniques determine how main memory blocks are placed into cache lines.

1. Direct Mapping:

• Each main memory block maps to exactly one cache line.
• Cache line = (Block number) mod (Number of cache lines).
• Address is divided into: Tag | Line (Index) | Word (Offset).

| Tag | Line | Word |

• Advantage: Simple and cheap hardware.
• Disadvantage: High conflict misses; two blocks mapping to same line evict each other.

2. Associative Mapping (Fully Associative):

• A block can be placed in any cache line.
• Address divided into: Tag | Word.

| Tag | Word |

• Requires comparing the tag with all cache lines using associative (CAM) memory.
• Advantage: Most flexible, fewest conflict misses.
• Disadvantage: Expensive due to parallel tag comparison hardware.

3. Set-Associative Mapping:

• Cache divided into sets, each set containing lines (k-way set associative).
• A block maps to one set but can occupy any line within that set.
• Address divided into: Tag | Set | Word.

| Tag | Set | Word |

• Advantage: Compromise between direct and associative; reduces conflict misses at moderate cost.

Summary Table:

When the CPU writes data, the cache and main memory must be kept consistent. Two policies handle this.

1. Write-Through:

• Data is written simultaneously to both the cache and main memory on every write.
• Main memory always holds the most up-to-date data.

Advantages:

• Simple to implement.
• Memory is always consistent (good for multiprocessor / I/O coherence).

Disadvantages:

• Every write accesses slow main memory, increasing write traffic and slowing performance.

2. Write-Back (Copy-Back):

• Data is written only to the cache. The modified block is marked with a dirty bit.
• Main memory is updated only when the block is replaced/evicted.

Advantages:

• Faster writes; reduces memory traffic (multiple writes to same block updated once).

Disadvantages:

• More complex; requires a dirty bit.
• Memory temporarily inconsistent → coherence problems in multiprocessors and I/O.

Comparison Table:

Related handling of write miss: Write-Allocate (load block then write) is typically used with Write-Back, while No-Write-Allocate is common with Write-Through.

Virtual Memory is a memory management technique that gives an application the illusion of a very large (main) memory by using disk storage as an extension of RAM. It allows execution of programs larger than physical memory and provides isolation between processes.

Key Idea:
The logical (virtual) address space used by programs is separated from the physical address space of main memory. The mapping is done by hardware (MMU) and OS.

Paging Mechanism:

• Virtual address space is divided into fixed-size blocks called pages.
• Physical memory is divided into equally sized blocks called page frames.
• Any page can be loaded into any free frame.

Address Translation:
A virtual address is split into:

• The Page Number indexes the Page Table, which gives the corresponding Frame Number.
• The Offset is combined with the frame number to form the physical address:
  

Page Table: Maintained per process; each entry contains the frame number, a valid/present bit, and control bits (dirty, reference, protection).

Page Fault: If the required page is not in main memory (valid bit = 0), a page fault occurs; the OS loads the page from disk, possibly replacing another page using a replacement algorithm (FIFO, LRU, etc.).

TLB: A Translation Lookaside Buffer is a small cache of recent page-table entries used to speed up address translation.

Benefits:

• Programs larger than RAM can run.
• Efficient multiprogramming and memory protection.

Main Memory (primary memory) is the memory directly accessible by the CPU and holds programs and data currently in execution. Auxiliary Memory (secondary/backup storage) provides large, non-volatile, long-term storage.

Comparison Table:

Main Memory Details:

• Consists of RAM (read/write, volatile) and ROM (read-only, non-volatile, holds bootstrap/firmware).
• Organized as an array of words with an address decoder, read/write control, and data lines.

Auxiliary Memory Details:

• Examples: Hard disks (magnetic), Solid State Drives, magnetic tapes, CD/DVD.
• Characterized by access time = seek time + rotational latency + transfer time (for disks).
• Used for storing the OS, files, and programs when not in use.

Role: The CPU works with main memory; auxiliary memory supplies data to main memory as needed (via virtual memory / swapping).

Main Memory Organization:
Main memory is organized as a collection of words, each identified by a unique address. A memory chip has:

• Address lines – select the word ( address lines → locations).
• Data lines – carry data in/out ( data lines → word size of bits).
• Control lines – Read/Write (R/W), Chip Select (CS).

A chip of capacity stores words of bits each.

Building Larger Memory:

1. Increasing Word Size (horizontal expansion):

• Place chips side by side; same address lines drive all chips, data lines are concatenated.
• Example: Two chips → one memory.

2. Increasing Number of Words (vertical expansion):

• Use additional high-order address bits with a decoder to select the correct chip via Chip Select.
• Example: Two chips → one memory. One extra address line (A8) chosen by a decoder selects chip 0 or chip 1.

Example (Combined):
To build a memory using chips:

Arranged as 4 rows (for 1024/256 words) × 2 columns (for 8/4 bits).

Address Decoding: A decoder uses high-order address bits to enable the correct chip/row, while low-order bits address the word within the chip.

Parallel Processing is a method of performing multiple operations or instructions simultaneously to increase computational speed and throughput. The idea is to divide work among multiple processing elements that operate concurrently.

Flynn's Classification categorizes computers based on the number of instruction streams and data streams:

1. SISD (Single Instruction, Single Data):

• One instruction stream operates on one data stream.
• Conventional uniprocessor (von Neumann) machines.
• Example: Traditional single-core CPUs.

2. SIMD (Single Instruction, Multiple Data):

• One instruction operates on multiple data elements simultaneously.
• Multiple processing units controlled by a single control unit.
• Example: Vector/array processors, GPUs.

3. MISD (Multiple Instruction, Single Data):

• Multiple instruction streams operate on a single data stream.
• Rare/theoretical; example: fault-tolerant systolic arrays.

4. MIMD (Multiple Instruction, Multiple Data):

• Multiple processors execute different instructions on different data independently.
• Example: Multiprocessors, multicomputers, modern multicore systems.

Summary Table:

Benefits of parallel processing: Higher speed, throughput, reliability, and better resource utilization.

Pipelining is a technique of decomposing a sequential process into sub-operations, each executed in a dedicated segment (stage) that operates concurrently with other segments, like an assembly line.

Instruction Pipeline (typical stages):

1. IF – Instruction Fetch: Fetch instruction from memory.
2. ID – Instruction Decode: Decode and read registers.
3. EX – Execute: Perform ALU operation.
4. MEM – Memory Access: Read/write memory if needed.
5. WB – Write Back: Write result to register.

While one instruction is being executed, the next can be decoded and another fetched — increasing throughput.

Speedup Derivation:
Let:

• = number of tasks (instructions)
• = number of pipeline stages
• = clock cycle time (time per stage)

Time without pipeline (sequential):

Time with pipeline:
The first task takes cycles to fill the pipeline; each subsequent task completes in 1 cycle:

Speedup:

Maximum speedup (as ):

Thus an ideal -stage pipeline can be up to times faster.

Pipeline Hazards (limit speedup): Structural, Data, and Control (branch) hazards.

Pipeline Hazards are situations that prevent the next instruction in the pipeline from executing in its designated clock cycle, reducing pipeline performance.

1. Structural Hazards:

• Arise when two instructions require the same hardware resource simultaneously (e.g., single memory for instruction fetch and data access).
• Solutions: Provide separate instruction and data memories/caches (Harvard architecture), duplicate resources, or stall.

2. Data Hazards:

• Occur when an instruction depends on the result of a previous instruction still in the pipeline.
• Types: RAW (Read After Write), WAR (Write After Read), WAW (Write After Write).
• Solutions:
  • Forwarding/Bypassing: Route the ALU result directly to the dependent instruction.
  • Pipeline stalls / bubbles.
  • Compiler instruction reordering.

3. Control (Branch) Hazards:

• Arise from branch/jump instructions since the next instruction address is unknown until the branch is resolved.
• Solutions:
  • Branch prediction (static/dynamic).
  • Delayed branch (fill delay slots with useful instructions).
  • Branch target buffer.
  • Flushing wrongly fetched instructions.

Summary Table:

Proper handling of hazards is essential to keep the pipeline efficient and close to its ideal speedup.

A Multiprocessor is a system with two or more CPUs (processors) sharing common resources such as memory and I/O, working together under an integrated operating system.

Characteristics of Multiprocessors:

• Multiple processors operating in parallel.
• Shared resources – memory, I/O devices, and a common bus/interconnect.
• Single integrated OS controlling all processors.
• Improved performance and throughput via parallel execution.
• Increased reliability/fault tolerance – failure of one processor need not stop the system (graceful degradation).
• Inter-processor communication and synchronization mechanisms.

Benefits: Higher performance, better cost/performance than a single powerful CPU, reliability, and flexibility.

Classification based on memory coupling:

1. Tightly Coupled (Shared-Memory) Multiprocessors:

• Processors share a common main memory.
• Communication through shared memory (fast).
• Requires cache coherence and memory access arbitration.
• Example: Symmetric Multiprocessors (SMP).

2. Loosely Coupled (Distributed-Memory) Multiprocessors:

• Each processor has its own local memory.
• Communication via message passing over an interconnection network.
• More scalable, less memory contention.
• Example: Multicomputers, clusters.

Comparison Table:

Interconnection Structures define how processors, memory modules, and I/O units are connected and communicate in a multiprocessor system. The main structures are:

1. Time-Shared / Common Bus:

• All processors and memory share a single common bus.
• Only one transfer at a time; a bus controller arbitrates access.
• Advantage: Simple, low cost.
• Disadvantage: Bus becomes a bottleneck; limited scalability.

2. Multiport Memory:

• Each memory module has multiple ports, one for each processor.
• Memory itself resolves conflicts using fixed priorities per port.
• Advantage: High transfer rate, parallel access.
• Disadvantage: Expensive; requires much control logic and cabling.

3. Crossbar Switch:

• A grid of switches connects every processor to every memory module.
• Multiple simultaneous transfers possible (as long as different memory modules).
• Advantage: High throughput, supports parallel access.
• Disadvantage: Hardware complexity grows as switches.

4. Multistage Switching Network:

• Uses small switching elements (e.g., switches) arranged in multiple stages (e.g., Omega network).
• Routing done using the binary destination address.
• Advantage: Cost-effective compromise between bus and crossbar.
• Disadvantage: Possible blocking; longer latency.

5. Hypercube (Binary n-cube):

• Each node is a processor with local memory; nodes connected as an n-dimensional cube.
• Each node connects to neighbors; routing by comparing address bits.
• Advantage: Scalable, short communication paths ().

Summary: Choice depends on cost, performance, and scalability requirements — from simple common bus to complex crossbar and hypercube networks.

Given:

• Cache access time, ns
• Main memory access time, ns
• Hit ratio,

Formula for average memory access time:

Calculation:

Result: The average memory access time is 38 ns.

Effect of increasing hit ratio:

• As increases, more references are served at the fast cache speed, so approaches .
• For example, if :
  
• If :
  

Conclusion: A higher hit ratio significantly reduces average access time, improving overall system performance. Even small increases near high hit ratios yield large gains because misses (costly memory accesses) become rarer.

Cache Coherence Problem:
In a multiprocessor system where each processor has its own private cache, multiple copies of the same memory block may exist in different caches. If one processor modifies its cached copy, other copies (and possibly main memory) become stale/inconsistent. Ensuring all processors see a consistent view of memory is the cache coherence problem.

Why it arises:

• Sharing of writable data among multiple caches.
• Process migration – a process moving between processors carries data.
• I/O activity bypassing caches.

Example: Processors P1 and P2 both cache variable X = 5. P1 writes X = 10 to its cache. P2's cached X is now stale.

Solutions:

1. Software Approaches:

• Mark shared writable data as non-cacheable.
• Compiler/OS-managed cache flushing.

2. Hardware Approaches (Cache Coherence Protocols):

• Snoopy Protocols (bus-based): Each cache controller monitors (snoops) the bus for transactions on addresses it holds.

  • Write-Invalidate: On a write, invalidate all other copies (e.g., MESI protocol with Modified, Exclusive, Shared, Invalid states).
  • Write-Update (Broadcast): On a write, update all other copies.

• Directory-Based Protocols: A central directory tracks which caches hold each block; used in scalable (non-bus) systems.

Goal: Maintain consistency while minimizing performance overhead, so all processors observe writes correctly and in a proper order.

Magnetic Disk is a widely used auxiliary (secondary) storage device that stores data magnetically on rotating platters. It is non-volatile and offers large capacity at low cost per bit.

Structure:

• Platters: Circular disks coated with magnetic material; may be stacked.
• Tracks: Concentric circles on each platter surface where data is stored.
• Sectors: Each track is divided into fixed-size arcs called sectors (smallest addressable unit).
• Cylinder: Set of tracks at the same radius across all platter surfaces.
• Read/Write Head: One per surface, mounted on an actuator arm; reads/writes data.
• Spindle: Rotates platters at a constant speed (RPM).

Working:

• Data is accessed by moving the head to the correct track and waiting for the sector to rotate under it, then transferring data.

Disk Access Time Components:

1. Seek Time (): Time for the head to move to the desired track.
2. Rotational Latency (): Time for the required sector to rotate under the head. On average, half a rotation:
   
3. Transfer Time (): Time to read/write the data:
   

Total Access Time:

Example: For a disk at 6000 RPM, average rotational latency:

SRAM (Static RAM) and DRAM (Dynamic RAM) are the two main types of semiconductor read/write memory, differing in structure, speed, and cost.

SRAM:

• Stores each bit using a flip-flop (4–6 transistors).
• Does not require refreshing (retains data as long as power is on).
• Fast access, but low density and expensive.

DRAM:

• Stores each bit as charge on a capacitor (1 transistor + 1 capacitor).
• Charge leaks, so it needs periodic refreshing.
• Slower but high density and cheap.

Comparison Table:

Why SRAM for Cache:

• Cache demands very high speed to match the CPU. SRAM's fast, refresh-free access makes it ideal despite higher cost, since cache is small.

Why DRAM for Main Memory:

• Main memory needs large capacity at low cost. DRAM's high density and low cost per bit make it suitable, and its slower speed is acceptable because caches hide much of the latency.

Conclusion: The choice reflects the memory hierarchy trade-off — speed (SRAM/cache) vs. capacity and cost (DRAM/main memory).

When a page fault occurs and main memory is full, a page replacement algorithm decides which page to evict to make room for the new page. A good algorithm minimizes the number of page faults.

1. FIFO (First-In, First-Out):

• Replaces the oldest page (the one loaded first).
• Implemented with a queue.
• Advantage: Simple.
• Disadvantage: May remove frequently used pages; suffers from Belady's anomaly (more frames can increase faults).

2. LRU (Least Recently Used):

• Replaces the page that has not been used for the longest time.
• Based on the assumption that recently used pages will be used again (temporal locality).
• Advantage: Good performance, close to optimal.
• Disadvantage: Expensive to implement (needs counters or stacks to track usage).

3. Optimal (OPT / MIN):

• Replaces the page that will not be used for the longest time in the future.
• Gives the minimum number of page faults.
• Disadvantage: Requires future knowledge — not implementable in practice, used only as a benchmark.

Comparison Table:

Note: Other algorithms include LFU, Second-Chance (Clock), and NRU. LRU is the most practical approximation to Optimal.

Arithmetic Pipeline divides an arithmetic operation into sub-operations executed in successive pipeline segments, allowing multiple operations to overlap. It is commonly used for floating-point arithmetic and vector operations in scientific computers.

Floating-Point Addition Example:
Consider adding two normalized floating-point numbers:

The addition is divided into four segments:

Segment 1 – Compare Exponents:

• Compare the two exponents by subtraction to find the difference and the larger exponent.

Segment 2 – Align Mantissas:

• Shift the mantissa of the number with the smaller exponent to the right until exponents are equal.

Segment 3 – Add/Subtract Mantissas:

• Add the two aligned mantissas to form the result mantissa.

Segment 4 – Normalize the Result:

• Normalize the result mantissa and adjust the exponent accordingly (shift and update exponent).

Diagram (pipeline flow):

Input → [Compare Exp] → [Align Mantissa] → [Add Mantissa] → [Normalize] → Output
R R R R

(R = registers between segments)

Example:

• Align:
• Add mantissas: , result
• Normalize:

Benefit: Each segment works on different operations simultaneously, greatly increasing throughput for a stream of floating-point additions.

Both cache memory and virtual memory are part of the memory hierarchy and rely on locality of reference, but they solve different problems.

Cache Memory:

• Sits between CPU and main memory.
• Purpose: Increase speed by keeping frequently used data close to the CPU.
• Managed primarily by hardware.
• Transfers small units called blocks/lines.
• Miss penalty is small (main memory access).

Virtual Memory:

• Sits between main memory and secondary storage (disk).
• Purpose: Increase apparent memory size and enable multiprogramming and protection.
• Managed by OS with hardware (MMU) support.
• Transfers larger units called pages.
• Miss (page fault) penalty is large (disk access).

Comparison Table:

Use of Locality:

• Cache exploits temporal & spatial locality to keep hot data near the CPU.
• Virtual memory exploits locality to keep the actively used working set of pages in main memory, so most references avoid slow disk access.

Conclusion: Both use locality to give the illusion of a memory that is simultaneously fast (cache) and large (virtual memory).

Given:

• Number of segments,
• Number of tasks,
• Time per segment, ns

1. Time without pipelining (sequential):
Each task passes through all segments sequentially:

2. Time with pipelining:
First task fills the pipeline in cycles; remaining tasks complete one per cycle:

3. Speedup:

4. Efficiency:
Efficiency is the ratio of actual speedup to the maximum possible speedup ():

Alternatively:

Results Summary:

Conclusion: Pipelining reduces total time from 8000 ns to 2060 ns, achieving nearly the maximum theoretical speedup of 4, with high efficiency because .