Exercises

1.  Hints and Answers    Suppose a computer using direct mapped cache has 2²⁰ words of main memory and a cache of 32 blocks, where each cache block contains 16 words.

   1.  Hints and Answers    How many blocks of main memory are there?

   2.  Hints and Answers    What is the format of a memory address as seen by the cache, that is, what are the sizes of the tag, block, and word fields?

   3.  Hints and Answers    To which cache block will the memory reference 0DB63₁₆ map?

2. Suppose a computer using direct mapped cache has 2³² words of main memory and a cache of 1024 blocks, where each cache block contains 32 words.

   1. How many blocks of main memory are there?

   2. What is the format of a memory address as seen by the cache, that is, what are the sizes of the tag, block, and word fields?

   3. To which cache block will the memory reference 000063FA₁₆ map?

3.  Hints and Answers    Suppose a computer using fully associative cache has 2¹⁶ words of main memory and a cache of 64 blocks, where each cache block contains 32 words.

   1.  Hints and Answers    How many blocks of main memory are there?

   2.  Hints and Answers    What is the format of a memory address as seen by the cache, that is, what are the sizes of the tag and word fields?

   3.  Hints and Answers    To which cache block will the memory reference F8C9₁₆ map?

4. Suppose a computer using fully associative cache has 2²⁴ words of main memory and a cache of 128 blocks, where each cache block contains 64 words.

   1. How many blocks of main memory are there?

   2. What is the format of a memory address as seen by the cache, that is, what are the sizes of the tag and word fields?

   3. To which cache block will the memory reference 01D872₁₆ map?

5.  Hints and Answers    Assume a system's memory has 128M words. Blocks are 64 words in length and the cache consists of 32K blocks. Show the format for a main memory address assuming a 2-way set associative cache mapping scheme. Be sure to include the fields as well as their sizes.

6. A 2-way set associative cache consists of four sets. Main memory contains 2K blocks of eight words each.

   1. 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.

   2. Compute the hit ratio for a program that loops 3 times from locations 8 to 51 in main memory. You may leave the hit ratio in terms of a fraction.

7. Suppose a computer using set associative cache has 2¹⁶ words of main memory and a cache of 32 blocks, and each cache block contains 8 words.

   1. If this cache is 2-way set associative, what is the format of a memory address as seen by the cache, that is, what are the sizes of the tag, set, and word fields?

   2. If this cache is 4-way set associative, what is the format of a memory address as seen by the cache?

8. Suppose a computer using set associative cache has 2²¹ words of main memory and a cache of 64 blocks, where each cache block contains 4 words.

   1. If this cache is 2-way set associative, what is the format of a memory address as seen by the cache, that is, what are the sizes of the tag, set, and word fields?

   2. If this cache is 4-way set associative, what is the format of a memory address as seen by the cache?

9.  *   Suppose we have a computer that uses a memory address word size of 8 bits. This computer has a 16-byte cache with 4 bytes per block. The computer accesses a number of memory locations throughout the course of running a program.

   Suppose this computer uses direct-mapped cache. The format of a memory address as seen by the cache is shown here:

   

   The system accesses memory addresses (in hex) in this exact order: 6E, B9, 17, E0, 4E, 4F, 50, 91, A8, A9, AB, AD, 93, and 94. The memory addresses of the first four accesses have been loaded into the cache blocks as shown below. (The contents of the tag are shown in binary and the cache "contents" are simply the address stored at that cache location.)

   

   1. What is the hit ratio for the entire memory reference sequence given above?

   2. What memory blocks will be in the cache after the last address has been accessed?

10. A direct-mapped cache consists of eight blocks. Main memory contains 4K blocks of eight words each. Access time for the cache is 22ns and the time required to fill a cache slot from main memory is 300ns. (This time allows us to determine the block is missing and bring it into cache.) Assume a request is always started in parallel to both cache and to main memory (so if it is not found in cache, we do not have to add this cache search time to the memory access). If a block is missing from cache, the entire block is brought into the cache and the access is restarted. Initially, the cache is empty.

    1. 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.

    2. Compute the hit ratio for a program that loops 4 times from locations 0 to 67₁₀ in memory.

    3. Compute the effective access time for this program.

11. Consider a byte-addressable computer with 24-bit addresses, a cache capable of storing a total of 64KB of data, and blocks of 32 bytes. Show the format of a 24-bit memory address for:

    1. direct mapped

    2. associative

    3. 4-way set associative

12. Suppose a process page table contains the entries shown below. Using the format shown in Figure 6.15a, indicate where the process pages are located in memory.

    

13.  Hints and Answers    Suppose a process page table contains the entries shown below. Using the format shown in Figure 6.15a, indicate where the process pages are located in memory.

    

14.  *   You have a virtual memory system with a two-entry TLB, a 2-way set associative cache, and a page table for a process P. Assume cache blocks of 8 words and page size of 16 words. In the system below, main memory is divided into blocks, where each block is represented by a letter. Two blocks equal one frame.

    

    Given the system state as depicted above, answer the following questions:

    1. How many bits are in a virtual address for process P? Explain.

    2. How many bits are in a physical address? Explain.

    3. Show the address format for virtual address 18₁₀ (specify field name and size) that would be used by the system to translate to a physical address and then translate this virtual address into the corresponding physical address. (Hint: convert 18 to its binary equivalent and divide it into the appropriate fields.) Explain how these fields are used to translate to the corresponding physical address.

15. Given a virtual memory system with a TLB, a cache, and a page table, assume the following:

    • A TLB hit requires 5ns.

    • A cache hit requires 12ns.

    • A memory reference requires 25ns.

    • A disk reference requires 200ms (this includes updating the page table, cache, and TLB).

    • The TLB hit ratio is 90%.

    • The cache hit rate is 98%.

    • The page fault rate is .001%.

    • On a TLB or cache miss, the time required for access includes a TLB and/or cache update, but the access is not restarted.

    • On a page fault, the page is fetched from disk, all updates are performed, but the access is restarted.

    • All references are sequential (no overlap, nothing done in parallel).

    For each of the following, indicate whether or not it is possible. If it is possible, specify the time required for accessing the requested data.

    1. TLB hit, cache hit

    2. TLB miss, page table hit, cache hit

    3. TLB miss, page table hit, cache miss

    4. TLB miss, page table miss, cache hit

    5. TLB miss, page table miss

    Write down the equation to calculate the effective access time.

16. A system implements a paged virtual address space for each process using a one-level page table. The maximum size of virtual address space is 16MB. The page table for the running process includes the following valid entries (the ® notation indicates that a virtual page maps to the given page frame, that is, it is located in that frame):

    Virtual page 2 ® Page frame 4    Virtual page 4 ® Page frame 9

    Virtual page 1 ® Page frame 2    Virtual page 3 ® Page frame 16

    Virtual page 0 ® Page frame 1

    The page size is 1024 bytes and the maximum physical memory size of the machine is 2MB.

    1. How many bits are required for each virtual address?

    2. How many bits are required for each physical address?

    3. What is the maximum number of entries in a page table?

    4. To which physical address will the virtual address 1524₁₀ translate?

    5. Which virtual address will translate to physical address 1024₁₀?

17. 1. If you are a computer builder trying to make your system as price-competitive as possible, what features and organization would you select for its memory hierarchy?

    2. If you are a computer buyer trying to get the best performance from a system, what features would you look for in its memory hierarchy?

18.  *   Consider a system that has multiple processors where each processor has its own cache, but main memory is shared among all processors.

    1. Which cache write policy would you use?

    2. The Cache Coherency Problem. With regard to the system just described, what problems are caused if a processor has a copy of memory block A in its cache and a second processor, also having a copy of A in its cache, then updates main memory block A? Can you think of a way (perhaps more than one) of preventing this situation, or lessening its effects?

19.  *   Pick a specific architecture (other than the one covered in this chapter). Do research to find out how your architecture approaches the concepts introduced in this chapter, as was done for Intel's Pentium.