Editing CPU cache (section)

==Cache entry structure==
Cache row entries usually have the following structure:

{| style="width:30%; text-align:center" border="1"
|-
| tag || data block || flag bits
|}

The ''data block'' (cache line) contains the actual data fetched from the main memory. The ''tag'' contains (part of) the address of the actual data fetched from the main memory. The flag bits are [[#Flag_bits|discussed below]].

The "size" of the cache is the amount of main memory data it can hold. This size can be calculated as the number of bytes stored in each data block times the number of blocks stored in the cache. (The tag, flag and [[ECC memory#Cache|error correction code]] bits are not included in the size,<ref>{{cite web |author=Sadler |first1=Nathan N. |last2=Sorin |first2=Daniel L. |year=2006 |title=Choosing an Error Protection Scheme for a Microprocessor's L1 Data Cache |url=https://people.ee.duke.edu/~sorin/papers/iccd06_perc.pdf |page=4}}</ref> although they do affect the physical area of a cache.)

An effective memory address which goes along with the cache line (memory block) is split ([[Most significant bit|MSB]] to [[Least significant bit|LSB]]) into the tag, the index and the block offset.<ref>{{cite book |last1=Hennessy |first1=John L. |url=https://books.google.com/books?id=v3-1hVwHnHwC&q=Hennessey+%22block+offset%22&pg=PA120 |title=Computer Architecture: A Quantitative Approach |last2=Patterson |first2=David A. |publisher=Elsevier |year=2011 |isbn=978-0-12-383872-8 |page=B-9 |language=en}}</ref><ref>{{cite book |last1=Patterson |first1=David A. |url=https://books.google.com/books?id=3b63x-0P3_UC&q=Hennessey+%22block+offset%22&pg=PA484 |title=Computer Organization and Design: The Hardware/Software Interface |last2=Hennessy |first2=John L. |publisher=Morgan Kaufmann |year=2009 |isbn=978-0-12-374493-7 |page=484 |language=en}}</ref>

{| style="width:30%; text-align:center" border="1"
|-
| tag || index || block offset
|}

The index describes which cache set that the data has been put in. The index length is <math>\lceil \log_2(s) \rceil</math> bits for {{mvar|s}} cache sets.

The block offset specifies the desired data within the stored data block within the cache row. Typically the effective address is in bytes, so the block offset length is <math>\lceil \log_2(b) \rceil</math> bits, where {{mvar|b}} is the number of bytes per data block.
The tag contains the most significant bits of the address, which are checked against all rows in the current set (the set has been retrieved by index) to see if this set contains the requested address. If it does, a cache hit occurs. The tag length in bits is as follows:

::<code>tag_length = address_length - index_length - block_offset_length</code>

Some authors refer to the block offset as simply the "offset"<ref name="ccs.neu.edu">{{cite web |author=Cooperman |first=Gene |year=2003 |title=Cache Basics |url=http://www.ccs.neu.edu/course/com3200/parent/NOTES/cache-basics.html}}</ref> or the "displacement".<ref>{{cite web |author=Dugan |first=Ben |year=2002 |title=Concerning Cache |url=http://www.cs.washington.edu/education/courses/cse378/02sp/sections/section9-1.html}}</ref><ref>{{Cite book |last=Cragon |first=Harvey G. |url=https://books.google.com/books?id=q2w3JSFD7l4C&dq=displacement+tag+cache&pg=PA209 |title=Memory Systems and Pipelined Processors |date=1996 |publisher=Jones & Bartlett Learning |isbn=978-0-86720-474-2 |page=209 |language=en}}
</ref>

===Example===
The original [[Pentium 4]] processor had a four-way set associative L1 data cache of 8&nbsp;[[Kibibyte|KiB]] in size, with 64-byte cache blocks. Hence, there are 8&nbsp;KiB&nbsp;/&nbsp;64&nbsp;=&nbsp;128 cache blocks. The number of sets is equal to the number of cache blocks divided by the number of ways of associativity, what leads to 128&nbsp;/&nbsp;4&nbsp;=&nbsp;32 sets, and hence 2<sup>5</sup>&nbsp;=&nbsp;32 different indices. There are 2<sup>6</sup>&nbsp;=&nbsp;64 possible offsets. Since the CPU address is 32 bits wide, this implies 32&nbsp;&minus;&nbsp;5&nbsp;&minus;&nbsp;6&nbsp;=&nbsp;21 bits for the tag field.

The original Pentium&nbsp;4 processor also had an eight-way set associative L2 integrated cache 256&nbsp;KiB in size, with 128-byte cache blocks. This implies 32&nbsp;&minus;&nbsp;8&nbsp;&minus;&nbsp;7&nbsp;=&nbsp;17 bits for the tag field.<ref name="ccs.neu.edu" />

==={{Anchor|Flag bits}} Flag bits===
An instruction cache requires only one flag bit per cache row entry: a valid bit. The valid bit indicates whether or not a cache block has been loaded with valid data.

On power-up, the hardware sets all the valid bits in all the caches to "invalid". Some systems also set a valid bit to "invalid" at other times, such as when multi-master [[bus snooping]] hardware in the cache of one processor hears an address broadcast from some other processor, and realizes that certain data blocks in the local cache are now stale and should be marked invalid.

A data cache typically requires two flag bits per cache line{{snd}}a valid bit and a [[dirty bit]]. Having a dirty bit set indicates that the associated cache line has been changed since it was read from main memory ("dirty"), meaning that the processor has written data to that line and the new value has not propagated all the way to main memory.