Memory Structure and Cache Management

Memory Structures: Cache and Primary Memory

• Understanding how smaller memory structures are mapped from primary memory to secondary memory through the cache.
• The primary purpose of cache is to enhance speed:
  • Cache allows the processor to access instructions and data rapidly.
  • Cache effectively condenses the primary memory space into a smaller, quicker-access area.

Principles of Locality of Reference

• The principle of locality of reference suggests:
  • When data or instructions are accessed, it is likely that the next collection of data or instructions will be in the vicinity of the current data.
  • Based on this principle, data is brought into cache in blocks instead of singular items from the primary memory.

Memory Mapping Overview

• Primary Memory is large, while Cache Memory is smaller:
  • Data blocks are transferred from primary memory to cache memory to facilitate easy access.
  • Once cache memory is exhausted or certain data is no longer needed, data is overwritten or moved back to primary memory.

Replacement Strategy

• The need for a replacement strategy arises out of the necessity to efficiently manage cache resources:
  • Data and instructions will occupy cache memory by overwriting less necessary elements.
  • There are different strategies for replacement, which determine how blocks are chosen to be replaced:
  1. Associative Mapping:
     • Blocks from primary memory can move into any location in the cache.
     • A Cache Block Table is maintained to track which blocks from primary memory are currently in cache.
     • Example of cache mapping: Block 24 from primary memory is currently in cache location zero.
  2. Least Recently Used (LRU) Strategy:
     • The management system tracks usage activity within blocks.
     • Blocks not accessed recently are prioritized for removal from cache.
  3. First In First Out (FIFO) Strategy:
     • Blocks that have remained in cache the longest are removed first, under the assumption that older data is less likely to be needed.
  4. Random Replacement:
     • A block is chosen randomly for removal, irrespective of usage.

Calculation of Cache and Primary Memory Blocks

• Example scenario details:
  • Primary Memory Size: 64k
  • Divided into blocks of 32 bytes:
  • Calculation: $64k / 32 = 2048$ blocks in primary memory.
  • Cache Size: 4k
  • Divided into blocks of 32 bytes:
  • Calculation: $4k / 32 = 128$ blocks in cache.

Structure of Cache Block Table

• Each entry in the cache block table corresponds to a block within the cache, tracking which block from primary memory is residing there.
• Example entry check:
  • If Block 24 is replaced in cache, the cache block table would reflect that block 0 now holds block 24.
• The size of cache block table for this scenario is 128 entries, indexed from 0 to 127.

Address Generation and Memory Management

• When a CPU generates a address (16-bit) for memory access:

  • The memary management system interprets the address:
  • Divides it into two parts:
  • Identifies the block containing the desired byte (11 bits).
  • Identifies the byte's position within that block (5 bits).

• In an example calculation:

  • 11 bits determine the block (total of $2^{11}$ blocks).
  • 5 bits represent the byte offset within that block.

Accessing Cache and Primary Memory

• Example Process:
  • Generating Address: For instance, if a CPU generates an address referencing block 23 and byte 6:
  • Check the Cache Block Table for block 23:
    • If found (a cache hit), directly access that byte in cache memory.
    • If not (a cache miss), bring block 23 from primary memory into cache, replacing another block based on the replacement strategy.

Limitations of Associative Mapping

• As memory sizes increase, particularly cache sizes, the cache block table becomes larger:
  • Searching through a larger cache block table becomes slower, impacting overall speed.
  • This necessitates exploration of alternative strategies to improve search and management responsiveness within cache.

Future Directions and Alternative Methods

• Exploration of different methodologies to enhance cache efficiency and speed relinquished by the traditional associative mapping.
• Techniques for reducing search time in cache management as cache sizes continuously grow.

Conclusion

• Overview of managing memory structures is critical for understanding performance implications in computer architecture.
• High cache hit ratios promote processing efficiency and can dramatically reduce load times for applications and operations.