Cache placement policies: Difference between revisions

Revision as of 01:37, 22 December 2020

Revision as of 18:31, 19 January 2021

Line 27:

=== Example ===

[[File:Direct-Mapped Cache Snehal Img.png|thumb|500x500px|Direct-Mapped Cache]]

Consider a main memory of 16 kilobytes, which is organized as 4-byte blocks, and a direct-mapped cache of 256 bytes with a block size of 4 bytes. Because the main memory is 16kB, we need a minimum of 14 bits to uniquely represent a memory address.

Since each cache block is of size 4 bytes, the total number of sets in the cache is 256/4, which equals 64 sets.

Line 33:

The incoming address to the cache is divided into bits for [[CPU cache#Cache entry structure|Offset]], [[CPU cache#Cache entry structure|Index]] and [[CPU cache#Cache entry structure|Tag]].

* ''Offset'' corresponds to the bits used to determine the byte to be accessed from the cache line. Because the cache lines are 4 bytes long, there are ''2 offset bits''.

* ''Index'' corresponds to bits used to determine the set of the Cache. There are 64 sets in the cache, and because 2^6 = 64, there are ''6 index bits.''

In the example, there are 2 offset bits, which are used to address the 4 bytes of the cache line.

Index* ''Tag'' corresponds to the remaining bits. usedThis means there are 14 – (6+2) = ''6 tag bits'', which are stored in tag field to determinematch the setaddress ofon thecache Cacherequest.

Below are memory addresses and an explanation of which cache line they map to:

In the example, there are 6 index bits, which are used to address the 64 sets of the cache.

# Address <code>0x0000</code> (tag - 00_0000<code>0b00_0000</code>, index – 00_0000<code>0b00_0000</code>, offset – 00<code>0b00</code>) mapscorresponds to block 0 of the memory and occupiesmaps to the set 0 of the cache.

Tag corresponds to the remaining bits.

# Address <code>0x0004</code> (tag - 00_0000<code>0b00_0000</code>, index – 00_0001<code>0b00_0001</code>, offset – 00<code>0b00</code>) mapscorresponds to block 1 of the memory and occupiesmaps to the set 1 of the cache.

# Address 0x0100<code>0x00FF</code> (tag – 00_0001<code>0b00_0000</code>, index – 00_0000<code>0b11_1111</code>, offset – 00<code>0b11</code>) mapscorresponds to block 6463 of the memory and occupiesmaps to the set 063 of the cache.

Similarly,# Address address<code>0x0100</code> 0x00FF(tag – 00_0000<code>0b00_0001</code>, index – 11_1111<code>0b00_0000</code>, offset – 11<code>0b00</code>) mapscorresponds to block 6364 of the memory and occupiesmaps to the set 630 of the cache.

In the example, there are 14 – (6+2) = 6 tag bits, which are stored in tag field to match the address on cache request.

Address 0x0000(tag - 00_0000, index – 00_0000, offset – 00) maps to block 0 of the memory and occupies the set 0 of the cache.

Address 0x0004(tag - 00_0000, index – 00_0001, offset – 00) maps to block 1 of the memory and occupies the set 1 of the cache.

Similarly, address 0x00FF(tag – 00_0000, index – 11_1111, offset – 11) maps to block 63 of the memory and occupies the set 63 of the cache.

Address 0x0100(tag – 00_0001, index – 00_0000, offset – 00) maps to block 64 of the memory and occupies the set 0 of the cache.

== Fully associative cache ==