Overview

In this reading you will learn about two new cache organizations: set associative and fully associative. These organizations usually improve the cache hit rate when compared to direct-mapped caches. However, this improvement to hit rate is a trade-off, as other performance metrics are worse for these new types of caches.

Required Reading

Sections 6.4.3 - 6.4.4 (pp. 624-630) 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. Compare and contrast set associative and fully associative caches.
  2. Contrast the line matching process in direct-mapped caches with that in a set associative cache.
  3. Given the contents of a set or fully associative cache and a specific memory address, determine whether an access to that memory address will be a hit or a miss.

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 set (or fully) associative cache with an LRU replacement policy on a stream of memory accesses, classifying each miss.
  2. Determine whether a C program will be prone to conflict misses in an associative cache.

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 the following cache.

    Set Line Valid Tag Block Contents
    00 0 1 1101001 0x0000000000FFA01F
    00 1 1 1100111 0x0000000000000000
    01 0 1 1101000 0xA1B2C3D4E5F60011
    01 1 1 1101011 0xFFAABBDD01234567
    10 0 1 0000110 0x1122334455667788
    10 1 0 0000000 0x0000000000000000
    11 0 0 0000000 0x0000000000000000
    11 1 1 1101000 0x0000F1BDC3D8910A

    Part A: This is an N-way set associative cache. What is N?

    Part B: 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.

    Part C: Redo the table above, assuming that the only thing that changes it that the cache becomes fully associative. Hint: Some of the columns will no longer be needed.