Computer Architecture
The Anatomy of Modern Processors

Cache operation

The most basic cache is a direct-mapped cache. It is a small table of fast memory (modern processors will store 16-256kbytes of data in a first-level cache and access a cache word in 2 cycles). There are two parts to each entry in the cache, the data and a tag.

If memory addresses have p bits (allowing 2^p bytes of memory to be addressed) and the cache can store 2^k words of memory. Then the least significant m bits of the address address a byte within a word. (Each word contains 2^m bytes.)

The next k bits of the address select one of the 2^k entries in the cache. The p-k-m bits of the tag in this entry are compared with the most significant p-k-m bits of the memory address: if they match, then the data "belongs" to the required memory address and is used instead of data from the main memory. When the cache tag matches the high bits of the address, we say that we've got a cache hit. Thus a request for data from the CPU may be supplied in 2 cycles rather than the 20-100 cycles that is necessary to fetch the same data from the main memory.