Page 172 - A Practical Guide from Design Planning to Manufacturing

Microarchitecture 145

Memory Cache Cache
1 A Tag Data Tag Data
array array array array
2 B
3 C 2 B 2 B
4 D 4 D 3 C
Get new
5 E 5 E 5 E
cache line
6 F
Load addr(3) Load addr(3)
Addr data Miss! Hit!
Figure 5-10 Cache data and tag arrays.

Each cache is actually made up of two separate arrays, the data array
and the tag array. The data array contains the actual values being
stored. When describing the size of the cache it is the data array size
that is quoted. The tag array contains the addresses of the values cur-
rently stored in the data array. The tag array is effectively an index for
the contents of the data array.
Each portion of the data array that has its own tag is called a cache line.
When a cache miss causes new data to be fetched, the entire cache line
is replaced and the matching tag array entry is updated. In Fig. 5-10, a
load from address 3 misses in the cache initially. This triggers the data
from that address to be loaded, replacing the value stored in the cache
for address 4.
This could cause a conflict miss if the data from address 4 is needed
again in the near future. In order to reduce conflict misses and make
better use of limited size, some caches allow a particular memory loca-
tion to be stored in more than one location in the cache. In these designs,
when new data is loaded, the cache chooses which value is replaced
based on which values have been used most recently. The number of loca-
tions in which a value can be stored is called the associativity of the cache
(Fig. 5-11).

Tag Tag Tag
array array array
Each 1 or 2 Each 1–4 Each 1–6
address address address
has 1 3 or 4 has 2 3–6 can go 1–6
possible possible to any
location 5 or 6 locations 1–2, 5–6 location 1–6
Assoc = 1 Assoc = 2 Assoc = 3
Direct mapped Associative cache Fully associative
Figure 5-11 Cache associativity.