Goals

This assignment will cover caches and floating point numbers.

Setup

You should writeup your solutions as hw6.txt in gradebot. Please use the provided format in hw6.txt.

Exercises

Problem 1: Cache Block Size, Associativity, and AMAT (15 pts)

Suppose we have 16 bit byte-addresses and the clock frequency is 2GHz. We have the cache parameters as follows:

• Cache size: 4KiB
• Block size: 1 word (4 bytes)
• Cache hit time: 2 cycles
• Cache miss time: 100 cycles

Now suppose we access the following addresses, in order:

0x0000, 0x0008, 0x000c, 0x1004, 0x1008, 0x100c, 0x0000, 0x0008, 0x000c

1. First, we start with a direct-mapped cache.

1. What are the widths of the tag, set index, and block offset fields?
2. Is each memory access a cache hit or a miss? Also, identify the cache miss type if it's a miss, and fill in the following table.

Address	Cache Hit / Miss?	Miss Type(Compulsory, Capacity, or Conflict)
0x0000
0x0008
0x000c
0x1004
0x1008
0x100c
0x0000
0x0008
0x000c

3. Calculate the miss rate and the AMAT in ns. How much does it decrease or increase the memory access time compared to having no cache?



2. Next, we increase the block size to 2 words. The overall cache size remains unchanged.

1. Repeat (a.1) for a cache with a block size of 2 words.
2. Repeat (a.2) for a cache with a block size of 2 words.
3. Calculate the miss rate. Note that we have different hit or miss times (or both) with the increased block size. Choose the valid one among the following timing parameters, and calculate the AMAT in ns. How much does it decrease or increase the memory access time compared to having no cache?
• Cache hit time: 1, 2, 3 cycles
• Cache miss time: 90, 100, 110 cycles



3. Lastly, we increase the associativity of the cache in (b) whose block size is two words. The overall cache size remains unchanged.

1. Repeat (a.1) for a two-way set associative cache.
2. Repeat (a.2) for a two-way set associative cache.
3. Repeat (b.3) for a two-way set associative cache.

Problem 2: Cache Friendly Programming (5 pts)

The following C program is run (with no optimization) on a processor with a direct-mapped data cache with a size of 1KiB and a block size of 32 bytes.

int i, j, array[256*256];

/* ... */

for (i = 0 ; i < 255 ; i++) {
  for (j = 0 ; j < 256 ; j++) {
    array[256*j] += array[256*j + i + 1];
  }
}

Assume sizeof(int) == 4 and array == 0x4000.

1. Calculate the miss rate.
2. Rewrite the code to improve the performance (don't use cache blocking). What is the miss rate in this case? Give a fraction or three significant digits for the percentage.
3. Will a write-back cache be helpful with the code in (b)? Explain briefly, in one or two sentences.

Problem 3: Floating Point Numbers (10 pts)

1. Convert -32.588 to floating point format. Write your answer in hexadecimal.
2. Convert the floating point number 0xC1102000, which follows the 7 bit exponent representation as described above, to decimal. Please specify infinities as +inf or -inf, and not a number as NaN.
3. What's the smallest non-infinite positive integer (an integer has nothing to the right of the decimal) it CANNOT represent? Leave your answer in decimal (ex: 12).
4. What's the smallest positive value it can represent that is not a denorm? Leave your answer as a power of 2 (ex: 2^x).
5. What's the smallest positive value it can represent? Leave your answer as a power of 2 (ex: 2^x).