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:
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.
Since there are 16 bytes in a cache block, the OFFSET field must contain 4 bits (24 = 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 (210 = 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.
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.
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.
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.
A more complete diagram can be found in Patterson and Hennessey, Figure 5.17.