# Homework 3: Cache Organization and Indexing

Assigned Friday, May 6, 2016 Friday, May 13, 2016 at 11:59pm Submit a PDF file of your solutions using the course's Assignment Drop Box.

## Introduction

The purpose of written homework assignments is to get you thinking about the topics being covered in lecture and in readings in the textbook which are not represented in the hands-on, programming lab assignments. These written assignments also better prepare you for exams. It is worth noting that the book contains many practice problems similar to the problems we ask on these written assignments! The solutions for those practice problems are located at the end of each chapter and should give you a feel for the kind of answers we expect you to turn in for these kind of assignments.

## Logistics

We will provide solutions to all of the problems in the written homework assignments in a timely fashion after the assignment is due. This may be around 4 or 5 days after the due date, because some students may use late days.

Make sure you are using the 3rd edition of Computer Systems: A Programmer's Perspective. If you're not using the right book, you might be doing the wrong problems!

## Questions

1. Structs: Practice Problem 3.41, p. 268.
• How would you change the assembly code generated if we inserted another line into the C function at the end (just before the }) as ` sp->s.y = 18;`?
2. Cache structure: Practice Problem 6.9, p. 616.
Repeat this problem for the following two real caches:
• Intel Xeon L1 data cache: m = 38, C = 32768, B = 64, E = 8
• AMD Opteron 6168 L2 unified cache: m = 48, C = 524288, B = 64, E = 16
3. Miss rates: Practice Problem 6.10, p. 624.
Assume that instead our cache is 2-way set associative. That is, C=64, S=2, E=2, B=16. So our cache is twice as big, and each set now contains two lines. Please give a separate answer for each of these two scenarios:
• a) What will the overall miss rate be for the original layout of the two arrays in this cache (include all accesses to array x and array y)?
• b) What will the overall miss rate be for the padded version?
4. Cache operation: Practice Problems 6.12-6.16, p. 628-630. (Nothing required for turn-in.)
5. Cache optimization: Practice Problem 6.18, p. 637.
• Repeat for an algae struct that has 4 integer fields instead of 2. Execute the same code as shown (only access the original first two fields, do not access the two new fields). You can assume that the new struct looks something like:
`struct algae_position { int x; int y; int z; int w; };`
6. Cache operation: Homework Problem 6.28, p. 650.
• Be sure to review and completely understand Practice Problems 6.12 - 6.16 before working on this problem.
• Don't forget to take block size into account!
7. Cache operation: Homework Problem 6.29, p. 651.
• Be sure to review and completely understand Practice Problems 6.12 - 6.16 before working on this problem.
• Note: Part A has a typo (picto?). The picture showing the bits shows 13 bits instead of 12 bits. You can just cross out bit number 12, leaving only 12 bits total.
• Note: For part B, you only need to give the “read value” for the two read operations, there is no read value for the write.