Cache Organization

Typically, the formula for finding the number of index bits is given only for set associative organizations, because most authors assume that everyone can remember that fully associative caches have no index bits and direct mapped enough to reference all slots in the cache. However, few students seem to get that part.

Block Size:

number of bytes per block (in byte-addressable memory). Used to determine byte offset.

Cache Size:

number of bytes in this level of memory hierarchy. Used with block size to determine number of cache lines, where each line is associated with one block in cache. We use the termlines to emphasize the fact that regardless of the number of bytes in the block, only one tag and validity bit represents the block.

Associativity:

types are direct mapped, set associative, and fully associative. Used to restrict access to cache lines.

Name	set size	# sets	Associativity
Direct	1 line	r= # lines per cache	1-way
Set	s lines	$\frac{r} {s}$	s-way
Fully	r lines	1 (one)	r-way

Address bits:

# bits in address comprising tag + index + block offset.

Validity Bit:

useful info or junk?

Block Offset:

location of info in block.

Index bits:

$2^{\rm index}= \frac{\rm cache size}{\rm (block size) * (associativity)}$

Dirty bits:

indicate whether or not valid blocks have been modified in systems that use a write-back strategy. If the dirty bit is clear (has value 0), then the block is unchanged in this level of the hierarchy, and can be replaced directly on a miss. If the dirty bit is set (has value 1), then the block needs to be written to the next lower level in the hierarchy before that space in the cache can be reused.