Homework 7 – Chapter 7

Computer Organization – Fall 2002

Due: December 3, 2002 – beginning of class

1. We studied three types of memory hierarchy in chapter 7, one-word-wide, wide (4-word), and interleaved (4-way) memory organizations. Assume cache block size of 32-bytes. It takes 2 clock cycles to send the address to memory. Each word is 32-bits wide. Further assume main memory latency is 9 cycles for each access and that the transfer time is 2 cycles. For each of the organizations, calculate the miss penalties. Which give the best time? (17 points)

2. Cache are built out of SRAM chips which come in standard sizes. If you have a processor with 32-bit addresses and data words, what is the largest size of data storage in bytes that can be built, given the following information. The cache is 2-way set associative with 2-word blocks. Each SRAM is 32Kx8-bits. You have been given 42 such SRAMs. Create the largest cache possible noting that each cache has overhead. How many SRAM chips will be unused if any? How many bits for tag, index, and offset fields in each address? Sketch the arrangement. (33 points)

3. For the following set of hex addresses, show the hits and misses. Also show the final cache contents after the various accesses. You may want to start with an empty cache and modify it with each access. The cache is direct mapped and has 16 blocks, each consisting of one 32-bit word. Make a table showing, for each hex address, the significant bits of the tag, the index field, offset field, and whether it is a hit or miss. Show the final contents (hex addresses) of the cache in a second table. (30 points)

0x2c, 0x100, 0xd0, 0xe0, 0x104, 0xd0, 0x6c, 0x100, 0xd4, 0x88, 0x10c, 0x68, 0x2c, 0x6c

4. For the addresses given in problem 3, assume a 2-way set associative cache with 2-word blocks with a total of 4 sets. Again create two tables, one with tag, index, offset fields and whether a hit or a miss, and a second table with the final contents of the cache. Replacement is by LRU. (30 points)

5. For the addresses given in problem 3, assume a direct-mapped cache with 4-word blocks and 4 blocks. Give the tables as above. Replacement is by LRU. (20 points)

6. Consider a virtual byte address machine with 40-bit virtual addresses. Each page is 32KB. The physical addresses however are only 32 bits. For this virtual memory system, how many entries are there in the page table? In contrast, how many physical pages exist? There is a direct mapped 8KB cache with 16-byte blocks associated with the physical memory. How many bits are in the tag, index and offset fields? Sketch the organization showing a virtual address, the page table, and the physical address. Show the number of bits in the VPN field, page offset field in a virtual address, and the tag, index, and offset fields in the physical address. (35 points)

7. To make a virtual memory system more efficient, a TLB can be added. Assume in the above question there is a fully associative TLB of 128 entries. And, rather than a direct-mapped cache, a 4-way set associative cache is used with 2K sets and each block has 2 words. For this organization, how many data bytes are in the cache? How many bits are in the tag, index and offset fields of the physical address? Sketch the organization, labeling all the fields of the virtual address, VPN, page offset, TLB, valid bit, dirty bit, physical address, tag, index, and offset fields, and cache. If MUXs are required show this also. (45 points)