Memory Hierarchy Exercises

Approach: Name the four levels from the fastest to the slowest, give the two or three characteristics that distinguish each, and close with the property that the hierarchy as a whole buys.

Steps:

1. Registers:
   • The fastest and the smallest in capacity (a few dozen)
   • Integrated with the CPU, the most expensive
   • Stores the data of the current operation
2. Cache:
   • Very fast, relatively small in capacity (KB-MB)
   • Stores recently accessed data
   • Exploits the principle of locality to raise the hit rate
3. Main memory:
   • Relatively fast, relatively large in capacity (GB)
   • Stores programs and data
   • Exchanges data directly with the CPU
4. Auxiliary memory:
   • Relatively slow, the largest in capacity (TB)
   • Stores data permanently
   • The cheapest
5. The property the hierarchy buys:
   • The levels balance speed against capacity against cost
   • The principle of locality raises the overall performance

Answer: The memory hierarchy consists of the registers, the cache, the main memory, and the auxiliary memory. The registers are the fastest and the smallest and are integrated with the CPU; the cache is very fast but relatively small and holds recently accessed data; the main memory is relatively fast and relatively large and holds the programs and data; the auxiliary memory is relatively slow but the largest and holds the data permanently at the lowest cost. Through the hierarchical design the levels balance speed, capacity, and cost, and the principle of locality raises the overall performance.

Approach: Compare the two memories on the six axes that separate them — working principle, speed, power consumption, cost, capacity, and application — and then summarise the trade-off.

Steps:

1. Working principle:
   • SRAM: based on flip-flop circuits, needs no refresh
   • DRAM: based on capacitive storage, needs a periodic refresh
2. Speed:
   • SRAM: fast, with a short access time
   • DRAM: relatively slow, and it takes time to refresh
3. Power consumption:
   • SRAM: low power consumption, small static power
   • DRAM: relatively high power consumption, large dynamic power
4. Cost:
   • SRAM: expensive, the circuit is complex
   • DRAM: cheap, the circuit is simple
5. Capacity:
   • SRAM: small capacity, low integration density
   • DRAM: large capacity, high integration density
6. Applications:
   • SRAM: used as the cache and the registers
   • DRAM: used as the main memory

Answer: SRAM is built from flip-flops and needs no refresh, which makes it fast, low-power, and expensive but small in capacity, so it is used for the cache and the registers. DRAM is built from capacitors and needs a periodic refresh, which makes it slower and more power-hungry but cheap and large in capacity, so it is used for the main memory. The choice is a straight trade-off between speed and cost per bit.

Approach: Take the three schemes in turn, giving for each how a main memory block is placed, the mapping relation, and the trade-off between the conflict rate and the hardware cost.

Steps:

1. Direct mapping:
   • A main memory block maps to a fixed position in the cache
   • The mapping relation: cache line number = main memory block number mod the number of cache lines
   • Advantages: simple to implement, fast to access
   • Disadvantages: a high conflict rate and a low hit rate
2. Fully associative mapping:
   • A main memory block can map to any position in the cache
   • The tags of all the cache lines have to be compared
   • Advantages: a low conflict rate and a high hit rate
   • Disadvantages: complex to implement, slow to access
3. Set associative mapping:
   • A main memory block maps to any line within a fixed set
   • Combines the advantages of direct mapping and full associativity
   • Advantages: a moderate conflict rate and a fairly high hit rate
   • Disadvantages: moderate implementation complexity

Answer: The three mapping schemes are direct mapping, in which each main memory block maps to a fixed cache line according to cache line number = main memory block number mod the number of cache lines, which is the simplest and the fastest but suffers from a high conflict rate; full associative mapping, in which a block may map anywhere and all the tags have to be compared, which gives the lowest conflict rate and the highest hit rate at the cost of slow access; and set associative mapping, in which a block maps to any line of a fixed set, which combines the advantages of the two and is what most caches use.

Approach: Answer the two halves of the question separately: first the principle, in three layers — the concept, the working mechanism, and the advantages — and then the four replacement algorithms with the rule each one uses and the trade-off it makes.

Steps:

1. The basic principle of virtual memory:
   1. The basic concept:
      • Extends the external storage space into main memory space
      • A program can address a space larger than the physical memory
      • Automates the memory management
   2. The working principle:
      • The program uses virtual addresses
      • The physical address is obtained by address translation
      • The pages are brought into memory on demand
   3. The advantages:
      • Enlarges the address space
      • Raises the memory utilisation
      • Simplifies program development
2. The common page replacement algorithms:
   1. OPT (the optimal algorithm):
      • Chooses the page that will not be used for the longest time in the future
      • Theoretically optimal, but impossible to implement in practice
   2. FIFO (first in first out):
      • Chooses the page that entered the memory first
      • Simple to implement, with a mediocre effect
   3. LRU (least recently used):
      • Chooses the page that has not been accessed for the longest time
      • A good effect, but complex to implement
   4. The CLOCK algorithm:
      • Combines the advantages of LRU and FIFO
      • Uses a reference bit and scans in a circle
      • Comparatively simple to implement, with a good effect

Answer: Virtual memory extends the external storage into the main memory space, so a program can address more than the physical memory holds, the virtual addresses are translated into physical addresses through a page or segment table, and the pages are brought in on demand; the result is a larger address space, better memory utilisation, and simpler program development. The common page replacement algorithms are OPT, which evicts the page that will not be used for the longest time and is theoretically optimal but unrealisable; FIFO, which evicts the page that entered first and is simple but only moderately effective; LRU, which evicts the page that has not been used for the longest time and works well but is complex; and CLOCK, which uses a reference bit and a circular scan to combine the strengths of LRU and FIFO at a comparatively low implementation cost.

Approach: Answer in five layers — what the TLB accelerates, what memory accesses it saves, what access pattern it exploits, how it fits into the hierarchy, and what it saves in power — and close with a summary sentence.

Steps:

1. Accelerating the address translation:
   • Caches the address translations that are used often
   • Reduces the number of page table lookups
   • Raises the speed of the address translation
2. Reducing the memory accesses:
   • Avoids a page table access on every translation
   • Reduces the memory access latency
   • Raises the overall performance of the system
3. Optimising the access pattern:
   • Exploits the spatial locality of the program
   • Caches the translations of the recently accessed addresses
   • Raises the TLB hit rate
4. Supporting the multilevel caching:
   • Acts as a cache of the address translations
   • Works together with the data cache
   • Forms a complete memory hierarchy
5. Lowering the power consumption:
   • Reduces the number of page table accesses
   • Lowers the power of the memory accesses
   • Raises the energy efficiency

Answer: The TLB (Translation Lookaside Buffer) is a cache of the address translations. It accelerates the translation by caching the results that are used often, which reduces the number of page table lookups and the memory access latency and therefore raises the overall performance. It optimises the access pattern by exploiting the spatial locality of the program and caching the recently used translations, so its hit rate goes up. It also completes the memory hierarchy, sitting alongside the data cache as the cache of the address translations, and it lowers the power consumption by cutting the number of page table accesses.

Approach: Compare the two schemes on the seven axes that separate them — the basic unit, the address structure, the management method, the address translation, the memory allocation, the protection mechanism, and the application scenario.

Steps:

1. The basic unit:
   • Paged: the page, of a fixed size
   • Segmented: the segment, of a variable size
2. The address structure:
   • Paged: page number + the offset within the page
   • Segmented: segment number + the offset within the segment
3. The management method:
   • Paged: managed page by page, which supports the page replacement
   • Segmented: managed segment by segment, which supports the segment swapping
4. The address translation:
   • Paged: a page table lookup, then the physical address is computed
   • Segmented: a segment table lookup, then the offset within the segment is checked
5. The memory allocation:
   • Paged: allocated page by page, which may produce internal fragmentation
   • Segmented: allocated segment by segment, which may produce external fragmentation
6. The protection mechanism:
   • Paged: protection at the page level
   • Segmented: protection at the segment level, which is more flexible
7. The application scenario:
   • Paged: general-purpose systems, which support multitasking
   • Segmented: specialised systems, which support modular programs

Answer: In paged virtual memory the unit is the fixed-size page, the address is a page number plus an offset within the page, the memory is managed page by page with page replacement, the translation goes through a page table lookup, the allocation is page-granular and may leave internal fragmentation, and the protection is at the page level. In segmented virtual memory the unit is the variable-size segment, the address is a segment number plus an offset within the segment, the memory is managed segment by segment with segment swapping, the translation goes through a segment table lookup and checks the offset, the allocation is segment-granular and may leave external fragmentation, and the protection is at the segment level and is more flexible. Paging fits general-purpose multitasking systems, while segmentation fits specialised systems with modular programs.

Approach: First derive the number of cache lines from the capacity and the line size, then split a 32-bit address into the offset, the line number, and the tag fields according to the powers of two, and finally state the mapping relation.

Steps:

1. The number of cache lines:
   • Total cache capacity = 32KB = 32 × 1024 = 32768 bytes
   • Size of each line = 64 bytes
   • Number of cache lines = 32768 ÷ 64 = 512 lines
2. The address structure:
   • Width of the virtual address: assume 32 bits
   • Width of the block offset: log₂64 = 6 bits
   • Width of the line number: log₂512 = 9 bits
   • Width of the tag: 32 - 6 - 9 = 17 bits
3. The address structure:

   [Tag bits (17 bits)] [Line number (9 bits)] [Block offset (6 bits)]

4. The mapping relation:
   • Main memory block number = virtual address ÷ 64
   • Cache line number = main memory block number mod 512

Answer: The total cache capacity is 32KB = 32 × 1024 = 32768 bytes and each line is 64 bytes, so the number of cache lines = 32768 ÷ 64 = 512 lines. Assuming a 32-bit virtual address, the block offset is log₂64 = 6 bits, the line number is log₂512 = 9 bits, and the tag is 32 - 6 - 9 = 17 bits, so the address structure is [Tag bits (17 bits)] [Line number (9 bits)] [Block offset (6 bits)]. The mapping relation is main memory block number = virtual address ÷ 64 and cache line number = main memory block number mod 512.

Approach: Take the four policies in turn, giving the advantage, the disadvantage, and the performance consequence of each, and then close with the advice on how to choose and combine them.

Steps:

1. Write-through:
   • Advantages: good data consistency, the main memory always holds the most recent data
   • Disadvantages: the write operation is slow and it increases the bus load
   • Performance impact: lowers the write performance, but guarantees the data consistency
2. Write-back:
   • Advantages: the write operation is fast and it reduces the bus load
   • Disadvantages: the data consistency is complex and the dirty bits have to be managed
   • Performance impact: raises the write performance, but increases the complexity of the system
3. Write-allocate:
   • Advantages: raises the hit rate of the later accesses
   • Disadvantages: adds the overhead of the write miss
   • Performance impact: suits the programs with good spatial locality
4. Write-no-allocate:
   • Advantages: reduces cache pollution
   • Disadvantages: may lower the hit rate
   • Performance impact: suits the programs with random write accesses
5. Optimisation advice:
   • Choose the write policy that suits the characteristics of the program
   • Combine the multilevel cache to optimise the overall performance
   • Balance the hardware cost against the performance requirement

Answer: Write-through keeps the main memory up to date at all times, so the consistency is excellent, but every write also hits the main memory, which slows the writes down and loads the bus. Write-back only writes the cache and defers the main memory update to the replacement, so the writes are fast and the bus load is low, at the cost of a more complex consistency story that has to be managed with the dirty bits. Write-allocate fetches the block on a write miss, which raises the hit rate of the later accesses but adds the overhead of the miss, and it suits programs with good spatial locality, while write-no-allocate writes straight through to the main memory, which keeps the cache free of pollution but may lower the hit rate and suits random write patterns. The policy is therefore chosen according to the program, combined with a multilevel cache, and balanced against the hardware cost.