Cache placement policies: Difference between revisions

Revision as of 18:31, 19 January 2021

Revision as of 19:59, 19 January 2021

Line 45:

# Address <code>0x00FF</code> (tag – <code>0b00_0000</code>, index – <code>0b11_1111</code>, offset – <code>0b11</code>) corresponds to block 63 of the memory and maps to the set 63 of the cache.

# Address <code>0x0100</code> (tag – <code>0b00_0001</code>, index – <code>0b00_0000</code>, offset – <code>0b00</code>) corresponds to block 64 of the memory and maps to the set 0 of the cache.

== Fully associative cache ==

In a fully associative cache, the cache is organized into a single cache set with multiple cache lines. A memory block can occupy any of the cache lines. The cache organization can be framed as (1*m) row matrix.<ref name=":1" />

Line 58 ⟶ 56:

* The Tag field of the memory address is compared with tag bits associated with all the cache lines. If it matches, the block is present in the cache and is a cache hit. If it doesn't match, then it's a cache miss and has to be fetched from the lower memory.

* Based on the Offset, a byte is selected and returned to the processor.

[[File:Fully-Associative Cache Snehal Img.png|thumb|513x513px|Fully associative cache]]

=== Advantages ===

* Fully associative cache structure provides us the flexibility of placing memory block in any of the cache lines and hence full utilization of the cache.

* The placement policy provides better cache hit rate.

* It offers the flexibility of utilizing a wide variety of [[CPU cache#Replacement policies|replacement algorithms]] if a cache miss occurs.

=== Disadvantage ===

* The placement policy is slow as it takes time to iterate through all the lines.

* The placement policy is power hungry as it has to iterate over entire cache set to locate a block.

* The most expensive of all methods, due to the high cost of associative-comparison hardware.

=== Example ===

Consider a main memory of 16 kilobytes, which is organized as 4-byte blocks, and a fully associative cache of 256 bytes and 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.

[[File:Fully-Associative Cache Snehal Img.png|thumb|513x513px|Fully associative cache]]

Consider a main memory of 16 kilobytes, which is organized as 4-byte blocks, and a fully associative cache of 256 bytes and a block size of 4 bytes.

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

Line 77 ⟶ 74:

The incoming address to the cache is divided into bits for offset and tag.

* ''Offset'' corresponds to the bits used to determine the byte to be accessed from the cache line. In the example, there are 2 offset bits, which are used to address the 4 bytes of the cache line

* ''Tag'' corresponds to the remaining bits. This means there are 14 – (2) = ''12 tag bits'', which are stored in tag field to match the address on cache request.

In the example, there are 2 offset bits, which are used to address the 4 bytes of the cache line and the remaining 12 bits form the tag.

The tag bits are stored in the tag field of the cache line to match the address on cache request.

Since any block of memory can be mapped to any cache line, the memory block can occupy one of the cache lines based on the replacement policy.

Line 110 ⟶ 104:

=== Example ===

Consider a main memory of 16 kilobytes, which is organized as 4-byte blocks, and a 2-way set-associative 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.

[[File:Set-Associative Cache Snehal Img.png|thumb|578x578px|Set-Associative Cache]]

Consider a main memory of 16 kilobytes, which is organized as 4-byte blocks, and a 2-way set-associative cache of 256 bytes with a block size of 4 bytes.

Since each cache block is of size 4 bytes and is 2-way set-associative, the total number of sets in the cache is 256/(4 * 2), which equals 32 sets.[[File:Set-Associative Cache Snehal Img.png|thumb|578x578px|Set-Associative Cache]]The incoming address to the cache is divided into bits for Offset, Index and 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''.

In this example, there are 2 offset bits, which are used to address the 4 bytes of a cache line; there are 5 index bits, which are used to address the 32 sets of the cache; and there are 7 = (14 – (5+2)) tag bits, which are stored in tag to match against addresses from cache requests.

Address* 0x0000(tag''Index'' –corresponds 000_0000, index – 0_0000, offset –to 00)bits mapsused to block 0 of the memory and occupiesdetermine the set 0 of the cacheCache. TheThere blockare occupies32 onesets ofin the cache lines of the set 0, and isbecause determined2^5 by= the32, replacementthere policyare for''5 theindex cachebits.''

* ''Tag'' corresponds to the remaining bits. This means there are 14 – (5+2) = ''7 bits'', which are stored in tag field to match the address on cache request.

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

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

Similarly, address 0x00FF(tag – 000_0001, index – 1_1111, offset – 11) maps to block 63 of the memory and occupies one of the cache lines of the set 31 of the cache.

# Address 0x0100<code>0x0000</code> (tag –- 000_0010<code>0b00_0000</code>, index – 0_0000<code>0b00_0000</code>, offset – 00<code>0b00</code>) mapscorresponds to block 640 of the memory and occupiesmaps oneto the set 0 of the cache. linesThe ofblock theoccupies a cache line in set 0, ofdetermined by the replacement policy for the cache.

# Address <code>0x0004</code> (tag - <code>0b00_0000</code>, index – <code>0b00_0001</code>, offset – <code>0b00</code>) corresponds to block 1 of the memory and maps to the set 1 of the cache. The block occupies a cache line in set 0, determined by the replacement policy for the cache.

# Address <code>0x00FF</code> (tag – <code>0b00_0000</code>, index – <code>0b11_1111</code>, offset – <code>0b11</code>) corresponds to block 63 of the memory and maps to the set 63 of the cache. The block occupies a cache line in set 63, determined by the replacement policy for the cache.

# Address <code>0x0100</code> (tag – <code>0b00_0001</code>, index – <code>0b00_0000</code>, offset – <code>0b00</code>) corresponds to block 64 of the memory and maps to the set 0 of the cache. The block occupies a cache line in set 0, determined by the replacement policy for the cache.

==Two-way skewed associative cache==