Question 1

Do the same thing as in Part A, except for a 4-way set associative cache. Assume 00110 and 11011 were the last two addresses to be accessed. Use the Least Recently Used replacement policy.

Accepted Answer

The answer of Do the same thing as in Part...

Question 2

Rather than a two-level page table, what other page table architecture could be used to reduce the memory foot print of page tables for the 64-bit address space from the last question? Assume that you do not need to map the full address space, but some small fraction (people typically do not have 264 bytes of physical memory). However, you should assume that the virtual pages that are mapped are uniformly distributed across the virtual address space (i.e. it is not only the low addresses or high addresses that are mapped, but rather a few pages from all ranges of memory).

Accepted Answer

The answer of Rather than a two-level page table, what...

Question 3

Caching. "One of the keys to happiness is a bad memory." -Rita Mae Brown Consider the following piece of code:
int x = 0, y = 0; // The compiler puts x in r1 and y in r2. int i; // The compiler put i in r3.
int A[4096]; // A is in memory at address 0x10000
...
for (i=0;i<1024;i++) { x += A[i];
}
for (i=0;i<1024;i++) { y += A[i+2048];
}
(a) Assume that the system has a 8192-byte, direct-mapped data cache with 16-byte blocks. Assuming that the cache starts out empty, what is the series of data cache hits and misses for this snippet of code. Assume that ints are 32-bits.
(b) Assume that an iteration of a loop in which the load hits takes 10 cycles but that an iteration of a loop in which the load misses takes 100 cycles. What is the execution time of this snippet with the aforementioned cache?
(c) Repeat part A except assume that the cache is 2-way set associative with an LRU replacement policy and 16-byte sets (8-byte blocks).
(d) Repeat part B using the cache described in part C. Is the direct-mapped or the set-associative cache better?

Accepted Answer

The answer of Caching. "One of the keys to happiness...

Question 4

You are given an empty 16K 2-way set-associative LRU-replacement cache with 32 byte blocks on a machine with 4 byte words and 32-bit addresses. Describe in mathematical terms a memory read address sequence which yields the following Hit/Miss patterns. If such a sequence is impossible, state why. Sample sequences:
address(N) = N mod 232 (= 0, 1, 2, 3, 4...)
address = (7, 12, 14)
(a) Miss, Hit, Hit, Miss
(b) Miss, (Hit)*
(c) (Hit)*
(d) (Miss)*
(e) (Miss, Hit)*

Accepted Answer

The answer of You are given an empty 16K 2-way...

Question 5

Assume an instruction cache miss rate for gcc of 2% and a data cache miss rate of 4%. If a machine has a CPI of 2 without any memory stalls and the miss penalty is 40 cycles for all misses, determine how much faster a machine would run with a perfect cache that never missed. Assume 36% of instructions are loads/stores.

Accepted Answer

The answer of Assume an instruction cache miss rate for...

Question 6

Invalidation vs. Update-based Protocols.
(a) As miss latencies increase, does an update protocol become more or less preferable to an invalidation-based protocol? Explain.
(b) In a multilevel cache hierarchy, would you propagate updates all the way to the first-level cache or only to the second-level cache? Explain the trade-offs.

Accepted Answer

The answer of Invalidation vs. Update-based Protocols.
(a) As miss latencies...

Question 7

Caches: Misses and Hits
int i;
int a[1024*1024]; int x=0;
for(i=0;i<1024;i++)
{
x+=a[i]+a[1024*i];
}
Consider the code snippet in code above. Suppose that it is executed on a system with a 2-way set associative 16KB data cache with 32-byte blocks, 32-bit words, and an LRU replacement policy. Assume that int is word-sized. Also assume that the address of a is 0x0, that i and x are in registers, and that the cache is initially empty. How many data cache misses are there? How many hits are there?

Accepted Answer

The answer of Caches: Misses and Hits
int i;
int a[1024*1024]; int...

Question 8

Virtual Memory
(a) 32-bit Virtual Address Spaces. Consider a machine with 32-bit virtual addresses, 32-bit physical addresses, and a 4KB page size. Consider a two-level page table system where each table occupies one full page. Assume each page table entry is 32 bits long. To map the full virtual address space, how much memory will be used by the page tables?
(b) 64-bit Virtual Address Spaces. A two-part question.
Consider a machine with a 64-bit virtual addresses, 64-bit physical addresses, and a 4MB page size. Consider a two-level page table system where each table occupies one full page. Assume each page table entry is 64 bits long. To map the full virtual address space, how much memory will be used by the page tables? (Hint: you will need more than 1 top-level page table. For this question this is okay.)

Accepted Answer

The answer of Virtual Memory
(a) 32-bit Virtual Address Spaces. Consider...

Question 9

Consider an architecture that uses virtual memory, a two-level page table for address translation, as well as a TLB to speed up address translations. Further assume that this machine uses caches to speed up memory accesses. Recall that all addresses used by a program are virtual addresses. Further recall that main memory in the microarchitecture is indexed using physical addresses. The virtual memory subsystem and cache memories could interact in several ways. In particular, the cache memories could be accessed using virtual addresses. We will refer to this scheme as a virtually indexed, virtually tagged cache. The cache could be indexed using virtual addresses, but the tag compare could happen with physical addresses (virtually indexed, physically tagged). Finally, the cache could be accessed using only the physical address. Describe the virtues and drawbacks for each of these systems. Be sure to consider the case where two virtual addresses map to the same physical address.

Accepted Answer

The answer of Consider an architecture that uses virtual memory,...

Question 10

How many total SRAM bits will be required to implement a 256KB four-way set associative cache. The cache is physically-indexed cache, and has 64-byte blocks. Assume that there are 4 extra bits per entry: 1 valid bit, 1 dirty bit, and 2 LRU bits for the replacement policy. Assume that the physical address is 50 bits wide.

Accepted Answer

The answer of How many total SRAM bits will be...

Question 11

TLB's are typically built to be fully-associative or highly set-associative. In contrast, first-level data caches are more likely to be direct-mapped or 2 or 4-way set associative. Give two good reasons why this is so.

Accepted Answer

The answer of TLB's are typically built to be fully-associative...

Question 12

Describe the general characteristics of a program that would exhibit very little temporal and spatial locality with regard to instruction fetches. Provide an example of such a program (pseudo- code is fine). Also, describe the cache effects of excessive unrolling. Use the terms static instructions and dynamic instructions in your description.

Accepted Answer

The answer of Describe the general characteristics of a program...

Question 13

(a) What is the hit and miss rate of the direct-mapped cache in Part A?
(b) What is the hit and miss rate of the 4-way set associative cache in Part B?
(c) Assume a machine with a CPI of 4 and a miss penalty of 10 cycles. Ignoring writes, calculate the ratio of the performance of the 4-way set associative cache to the direct-mapped cache. In other words, what is the speedup when using the machine with the 4-way cache?

Accepted Answer

The answer of (a) What is the hit and miss...

Quiz 5: Large and Fast

Do the same thing as in Part A, except for a 4-way set associative cache. Assume 00110 and 11011 were the last two addresses to be accessed. Use the Least Recently Used replacement policy.

TLB's are typically built to be fully-associative or highly set-associative. In contrast, first-level data caches are more likely to be direct-mapped or 2 or 4-way set associative. Give two good reasons why this is so.