CS-343 Assignment 8
Solutions

Answers

  1. What are the three parameters that vary along the various levels of the memory hierarchy.
    Speed, Capacity, and Cost. The closer to the CPU a memory element is, the lower the access time (faster), the smaller the capacity, and the larger the cost per bit of memory.
  2. If rotational delay were the only factor affecting disk access time, how much faster would a 7200 RPM disk be compared to a 5400 RPM disk?
    7200 ÷ 5400 = 1.33 times faster.
  3. What is the rotational period of a 10,000 RPM disk, in milliseconds?
    10,000 RPM = 166.67 revolutions per second. 1/166.67 = 0.006 seconds = 6 msec.
  4. Define the terms track and sector for magnetic disks.
    A track is the circular path traced as the disk rotates under the read/write head at a given position of the head. A sector is the smallest amount of information that can be read or written on a track; on PC systems a sector is typically 512 bytes.
  5. Use the web to define areal density in the context of disk drives. Search for the highest areal density of a currently available disk. What is it? Cite the sources for both of your answers to this question.
    Computer storage density (Wikipedia). That is, the number of bits that can be stored in a unit-sized square of recording material. Seagate announced disks that store 625 gigabits (78.13GB) per square inch of disk surface earlier this month. (Source: Engadget.)
  6. How amazing is the answer to the second part of the previous question?
    It’s “way” amazing.
  7. Why doesn’t anyone build a computer with a a terabye of registers in the CPU and just skip the main meory and disk levels of the memory hierarchy all together?
    It would be prohibitively expensive.
  8. A computer has 16 GB of main memory and 1 MB of cache. Once the cache has filled, what is the probability of a cache hit if the processor accesses main memory in a totally random fashion?
    1M ÷ 16G = 220 - 34 = 2-14 = 0.0000610...
  9. The previous question specified “once the cache has filled.” Would the probability of a hit be higher or lower than your answer before the cache has filled?
    Before the cache fills, there will be more cold start misses (Section 5.5 of the text), so there would be more misses: the probability of a hit would be lower.
  10. For a certain computer, main memory access time is 50 nsec, and cache access time is 750 psec. What is the average access time if p(hit) is 0.90?
    0.9 × 750 + 0.1 × 50,000 = 5,675 psec = 5.675 nsec.
  11. If the average access time for the computer in the previous example was observed to be 900 psec, what must the probability of a hit have been?
    900 = phit × 750 + (1 - phit) × 50,000 900 = 750 × phit + 50,000 - (50,000 × phit) -49,100 = -49,250 × phit -49,100 ÷ 49,250 = -phit phit = 0.99695... No calculators on the exam!
  12. The text differentiates between spatial and temporal locality (page 452). In class, I glossed over the difference. In light of the last word of both definitions in the text, discuss why my approach makes sense. Then explain what feature of cache designs applies to spatial locality but not necessarily to temporal locality, thus making the distinction meaningful after all.
    The last word of both definitions is “soon,” indicating that temporal locality is operating in both cases. But when there is a cache miss, an entire block of memory is brought into cache, not just the individual location referenced by the processor. Because of spatial locality, the extra information brought into cache is highly likely to be accessed, not “again,” but “soon.”
  13. Explain why programs tend to exhibit locality with respect to instruction accesses.
    Loops cause relatively small sets of instruction words to be accessed repeatedly.
  14. Explain why programs tend to exhibit locality with respect to data accesses.
    Properly designed code that operates on arrays tends to access all the elements of a row one after another, assuming the data are stored in row-major order.
  15. Explain the effect of locality on the probability of a cache hit.
    Because the information that will be accessed again “soon” is already in the cache, the probability of a hit increases.
  16. A computer with byte-addressable memory uses 48-bit addresses.
    1. How many bytes of memory could be attached to the computer?
      248
    2. How many 8-byte words would that be?
      245
    3. How many 128-byte blocks would that be?
      241
    4. How many address bits would select a byte within a word?
      log2(8) = 3 bits
    5. How many address bits would select a byte within a block?
      log2(128) = 7 bits
    6. How many address bits would select a word within a block?
      log2(128 ÷ 8) = 4 bits
    Assume this computer has 220 cache lines.
    1. What is the capacity, in bytes, of this cache?
      220 × 27 = 227 bytes. (Remember, the size of cache lines is always the same size as main memory blocks, which was given in the previoius question.)
    2. How many sets would there be using a direct mapped design?
      One line per set, same as the number of lines: 220.
    3. How many sets would there be using an 8-way set associative design?
      23 lines per set, so: 220 - 3 = 217 sets.
    4. How many sets would there be using a fully associative design?
      Just one set that includes all the lines.
    5. How many address bits would the index field have for the direct mapped design?
      20
    6. How many address bits would the index field have for an 8-way set associative design?
      17
    7. How many address bits would the index field have for a fully associative design?
      0
    8. How large would the tag field be for the direct mapped design?
      48 - (20 + 7) = 21
    9. How large would the tag field be for an 8-way set associative design?
      48 - (17 + 7) = 24
    10. How large would the tag field be for a fully associative design?
      48 - (0 + 7) = 41
  17. What is the purpose of the v-bit in a cache memory?
    To indicate whether a cache line contains valid data from main memory or not. All the v-bits get set to 0 when a program starts running, resulting in many cold-start misses.
  18. Define cold-start, capacity, and conflict misses.
    cold-start
    When a requested block has not been loaded into cache yet.
    capacity
    When the cache is full and a line has to be overwritten with a block.
    conflict
    When there are empty lines, but not within the set to which a block is mapped.