Cache

• Small amount of fast memory


• Sits between normal main memory and CPU


• May be located on CPU chip or module

Cache operation

• CPU requests contents of memory location


• Check cache for this data


• If present, get from cache (fast)


• If not present, read required block from main memory to cache


• Then deliver from cache to CPU


• Cache includes tags to identify which block of main memory is in each cache slot

Cache Design

• Size


• Mapping Function


• Replacement Algorithm


• Write Policy


• Block Size


• Number of Caches

Typical Cache Organization

Mapping Function

• Cache of 64kByte


• Cache block of 4 bytes

—   i.e. cache is 16k (214) lines of 4 bytes

• 16MBytes main memory


• 24 bit address

—   (224=16M)

Direct Mapping

• Each block of main memory maps to only one cache line

—   i.e. if a block is in cache, it must be in one specific place

• Address is in two parts


• Least Significant w bits identify unique word


• Most Significant s bits specify one memory block


• The MSBs are split into a cache line field r and a tag of s-r (most significant)


•   Address length = (s + w) bits


• Number of addressable units = 2s+w words or bytes


• Block size = line size = 2w words or bytes


• Number of blocks in main memory = 2s+ w/2w = 2s


• Number of lines in cache = m = 2r


• Size of tag = (s – r) bits

Associative Mapping

• A main memory block can load into any line of cache


• Memory address is interpreted as tag and word


• Tag uniquely identifies block of memory


• Every line’s tag is examined for a match


• Cache searching gets expensive


• Address length = (s + w) bits


• Number of addressable units = 2s+w words or bytes


• Block size = line size = 2w words or bytes


• Number of blocks in main memory = 2s+ w/2w = 2s


• Number of lines in cache = undetermined


• Size of tag = s bits

Set Associative Mapping

• Cache is divided into a number of sets


• Each set contains a number of lines


• A given block maps to any line in a given set

—   e.g. Block B can be in any line of set i

• e.g. 2 lines per set

—   2 way associative mapping

—   A given block can be in one of 2 lines in only one set

• Address length = (s + w) bits


• Number of addressable units = 2s+w words or bytes


• Block size = line size = 2w words or bytes


• Number of blocks in main memory = 2d


• Number of lines in set = k


• Number of sets = v = 2d


• Number of lines in cache = kv = k * 2d


• Size of tag = (s – d) bits