Overview

In this reading we will begin our exploration of various organizations of hardware caches. The first organization we will look at is the direct-mapped cache. This type of cache is simple and fast to access but with some serious drawbacks that you will read about.

Required Reading

Sections 6.4.0 - 6.4.2 (pp. 614-624) from the course textbook.

Learning Objectives

BASIC Learning Objectives

Each student will be responsible for learning and demonstrating proficiency in the following objectives PRIOR to the class meeting. The reading quiz will test these objectives.

1. Describe the contents of a cache line.
2. Given the fundamental cache parameters (S, E, B, and m), calculate the following: maximum number of unique memory addresses, the cache size (excluding overhead), and the number of set index, block offset, and tag bits.
3. Describe the defining characteristic of a direct-mapped cache.
4. Given the contents of a direct-mapped cache and a specific memory address, determine whether there an access to that memory address will be a hit or a miss.
5. Summarize what causes thrashing in a direct-mapped cache.

ADVANCED Learning Objectives

The following objectives should be mastered by each student DURING and FOLLOWING the class session through active work and practice.

1. Simulate the operation of a direct-mapped cache on a stream of memory accesses, classifying each miss.
2. Identify parts of a C program that are prone to trashing in a direct-mapped cache and modify the code to help avoid the problem.

Pre-class Exercises

These exercises are geared towards mastering the BASIC learning objectives listed above. You are expected to submit them before class and it is highly recommended that you complete them before attempting the reading quiz.

1. Assume you have a cache with the following set of parameters: (S, E, B, m) = (64, 4, 8, 32). Calculate the following parameters:

   • The size of memory, given in bytes.
   • The capacity of the cache, given in bytes.
   • The number of bits used for the set index.
   • The number of bits used for the block offset.
   • The number of bits used for the tag.

2. Assume you have the following direct-mapped cache.

   Set	Valid	Tag	Block Contents
   000	1	110100	0x0000000000FFA01F
   001	0	000000	0x0000000000000000
   010	1	110100	0xA1B2C3D4E5F60011
   011	1	110101	0xFFAABBDD01234567
   100	1	000011	0x1122334455667788
   101	0	000000	0x0000000000000000
   110	0	000000	0x0000000000000000
   111	1	110100	0x0000F1BDC3D8910A

   For each of the following 12-bit addresses, indicate whether they are a hit or miss in the cache. For simplicity, assume that you are accessing only a single byte and that the contents of the cache never change.

   • 0xD26
   • 0xD08
   • 0xA08
   • 0xCE6