A cache in the primary storage hierarchy contains cache lines that are grouped into sets. If each set contains k lines then we say that the cache is k-way associative.

A data request has an address specifying the location of the requested data. Each cache-line sized chunk of data from the lower level can only be placed into one set. The set that it can be placed into depends on its address.

This mapping between addresses and sets must have an easy, fast implementation. The fastest implementation involves using just a portion of the address to select the set. When this is done, a request address is broken up into three parts:

• An offset part identifies a particular location within a cache line.
• A set part identifies the set that contains the requested data.
• A tag part must be saved in each cache line along with its data to distinguish different addresses that could be placed in the set.

A computer uses 32-bit byte addressing. The computer uses a 2-way associative cache with a capacity of 32KB. Each cache block contains 16 bytes. Calculate the number of bits in the TAG, SET, and OFFSET fields of a main memory address.

Answer

Since there are 16 bytes in a cache block, the OFFSET field must contain 4 bits (2⁴ = 16). To determine the number of bits in the SET field, we need to determine the number of sets. Each set contains 2 cache blocks (2-way associative) so a set contains 32 bytes. There are 32KB bytes in the entire cache, so there are 32KB/32B = 1K sets. Thus the set field contains 10 bits (2¹⁰ = 1K).

Finally, the TAG field contains the remaining 18 bits (32 - 4 - 10). Thus a main memory address is decomposed as shown below.

    if the requested data is in the local store
        return the requested data
    else
        get the requested and nearby data from the lower level
        save it in the local store
        return the requested data
      

Parts of this operation are explained further below. The address decomposition is provided for easy reference.

if the requested data is in the local store

• Use the set part of the request address to select a set.
• For each line in the selected set
  • test its valid bit, and
  • test if its tag matches the tag part of the request address.

You have a cache hit if any line passes both tests. The line that passes the tests is called the matching cache line. It contains the requested data.

If no cache line passes both tests you have a cache miss. The local store does not contain the requested data.

return the requested data

• Use the offset part of the request address to select a portion of the matching cache line and return it.

save it in the local store

• Use a replacement algorithm to select a victim line from the selected set. The replacement algorithm is trivial if the degree of associativity is 1 (a direct-mapped cache) - then there is only one choice for the victim.
• Overwrite the victim with data from the lower level.

A cache whose local store contains m lines is k-way associative for some k that divides m. Usually both m and k are powers of 2. There is special terminology for the extremes of associativity.

• When k equals 1, the cached is called direct mapped.
• When k equals m, the cached is called fully associative. In this case there is only one set so there are no set bits in the address decomposition.

Cache Addressing Diagrammed

A 4-way associative cache with 64 cache lines is diagrammed below. The rectangular array should be viewed as a register bank in which a register selector input selects an entire row for output.

Each row in this diagram is a set. For a 4-way associative cache each set contains 4 cache lines. Each cache line consists of a "tag" and a "data" field. There is also a "valid" bit, which is not shown.

The tag portion of the request address is compared to all of the tag fields in the selected set. If one the tag fields is a match the the corresponding data field is selected - it contains the requested data. If there is no match, the cache controller must go to the lower-level store for the requested data.

Whether the requested line comes from the local store or the lower-level store, the offset bits of the request address drive a multiplexer to select the desired data.

set 0	tag	data	tag	data	tag	data	tag	data
set 1	tag	data	tag	data	tag	data	tag	data
set 2	tag	data	tag	data	tag	data	tag	data
set 3	tag	data	tag	data	tag	data	tag	data
set 4	tag	data	tag	data	tag	data	tag	data
set 5	tag	data	tag	data	tag	data	tag	data
set 6	tag	data	tag	data	tag	data	tag	data
set 7	tag	data	tag	data	tag	data	tag	data
set 8	tag	data	tag	data	tag	data	tag	data
set 9	tag	data	tag	data	tag	data	tag	data
set 10	tag	data	tag	data	tag	data	tag	data
set 11	tag	data	tag	data	tag	data	tag	data
set 12	tag	data	tag	data	tag	data	tag	data
set 13	tag	data	tag	data	tag	data	tag	data
set 14	tag	data	tag	data	tag	data	tag	data
set 15	tag	data	tag	data	tag	data	tag	data

A more complete diagram can be found in Patterson and Hennessey, Figure 5.17.