Problem Set: Cache

 

  1. Suppose we have a main memory of 16MB and a direct mapped cache of 16KB, and suppose the size of a memory block is 32 bytes.
    1. What is 1K represented in hex?
    2. What is 1M represented in hex?
    3. How many lines are in the cache? Give your answer both as a base 10 number (you can represent the number using K or M) and as a power of two.
    4. How many blocks are in main memory? Give your answer both as a base 10 number (you can represent the number using K or M) and as a power of two.
    5. How many bits are in a memory address?
    6. How many bits of the memory address are needed to identify the position of a byte within a block (the offset)?
    7. How many bits of the memory address are needed to identify the block?
    8. How many bits of the memory address are needed for the tag?
  2. Suppose a computer using direct mapped cache has 232 words of word-addressable main memory, and a cache of 1024 lines, where each cache line contains 64 words.
    1. How many blocks of main memory are there?
    2. How many bits are needed for the tag, block, and offset fields?
    3. To which cache line will the memory address 0x63FA16 map?
  3. Suppose a computer using direct mapped cache has 232 bytes of byte-addressable main memory and a cache size of 512 bytes, and each cache block contains 64 bytes.
    1. How many blocks of main memory are there?
    2. How many bits are needed for the tag, block, and offset fields?
    3. To which cache block will the memory address 0x13A4498A map?
  4. Suppose a computer using fully associative cache has 224 bytes of byte-addressable main memory and a cache of 128 blocks, where each cache block contains 64 bytes.
    1. How many blocks of main memory are there?
    2. What is the format of a memory address as seen by the cache, i.e., what are the sizes of the tag and offset fields?
    3. To which cache block will the memory address 0xD87216 map?
  5. A 2-way set-associative cache consists of four sets. Main memory contains 2K blocks of eight words each and word addressing is used.
    1. How many lines are in the cache?
    2. Show the main memory address format that allows us to map addresses from main memory to cache. Be sure to include the fields as well as their sizes.
  6. The following 2-way set-associative cache consists of four sets. Main memory contains 64K blocks of 64 bytes each.
    1. How many lines are in the cache?
    2. How many bits are in an address?
    3. Show the main memory address format that allows us to map addresses from main memory to cache. Be sure to include the fields as well as their sizes.
    4. Given the address 0x4AE7, which set does it map to? Is it in the cache? If so, in which line of the set?
    5. Given the address 0x10592B, which set does it map to? Is it in the cache? If so, in which line of the set?
    6. Given the address 0xCA86, which set does it map to? Is it in the cache? If so, in which line of the set?

      7. Terms

      Be familiar with the meaning of the following terms.


      cache hit   cache miss
      hit rate   miss time
      hit time   miss penalty
      direct mapped cache   fully associative cache
      set associative cache   levels of cache

    Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

    © Copyright Emmi Schatz 2021