SA
메인 내용으로 이동

Cache Mapping

  • While with logical operators, it is possible to check if a value exists or not, if a block can be anywhere, we need to search everywhere.
  • Where is the block we are looking for?
  • Fully Associative Mapping
    • Any block from memory can be put in any cache block (i.e., no restriction)
    • S=1S=1, K=NK=N
    • Byte offset bits b=log2Bb = \log_2B bits where BB is the block size
    • No set index because there is one set.
    • Most flexible (fewer evictions)
    • Longest search time O(N)O(N)
  • Direct Mapping
    • Each block from memory can only be put in one location
    • S=NS=N, K=1K=1
    • Each set has one block.
    • Least flexible (more evictions)
    • Shortest search time O(1)O(1)
  • K-Way Set-Associative Mapping
    • Given S sets, block ii of main memory maps to set imodSi\mod S
    • Within the set, the block can be put anywhere.
    • Byte offset bits b=log2Bb = \log_2B bits where BB is the block size
    • Set bits s=log2Ss = \log_2S bits where SS is the number of cache sets
    • Tag bits tt = remaining bits
    • Compromised
      • 1-way set associative = Direct
      • N-way set associative = Fully Associative
    • Search Time is O(K)O(K)
    • For small KK Parallel Search with Hardware Optimization: O(1)O(1)

이 문서를 언급한 문서들