Cache placement policies: Difference between revisions

Revision as of 21:23, 5 March 2023

Revision as of 18:50, 8 May 2023

Line 1:

{{Short description|Design decisions affecting processor cache speeds and sizes}}

{{Distinguish|cache replacement policies}}

[[File:Dual Core Generic.svg|thumb|190px|Diagram of a generic dual-core processor with CPU-local level-1 caches and a shared, on-die level-2 cache]]

A [[CPU cache]] is a memory which holds the recently utilized data by the processor. A block of memory cannot necessarily be placed randomly in the cache and may be restricted to a single [[CPU cache#Cache entries|cache line]] or a set of cache lines<ref name=":0">{{Cite web|url=https://cseweb.ucsd.edu/classes/su07/cse141/cache-handout.pdf|title=The Basics of Cache}}</ref> by the '''cache placement policy'''.<ref>{{Cite web|url=http://web.cs.iastate.edu/~prabhu/Tutorial/CACHE/bl_place.html|title=Cache Placement Policies}}</ref><ref>{{Cite web|url=http://fourier.eng.hmc.edu/e85_old/lectures/memory/node4.html|title=Placement Policies|archive-url=https://web.archive.org/web/20200814000302/http://fourier.eng.hmc.edu/e85_old/lectures/memory/node4.html|archive-date=August 14, 2020|url-status=dead}}</ref> In other words, the cache placement policy determines where a particular memory block can be placed when it goes into the cache.

'''Cache placement policies''' are programmable approaches to holding data that is to be utilized by the [[general processing unit]] (CPU) in the [[CPU cache]].

==Performance==

There are three different policies available for placement of a memory block in the cache: direct-mapped, fully associative, and set-associative. Originally this space of cache organizations was described using the term "congruence mapping".<ref>{{Cite journal|last=Mattson|first=R.L.|author1-link=Richard Mattson|last2=Gecsei|first2=J.|last3=Slutz|first3=D. R.|last4=Traiger|first4=I|date=1970|title= Evaluation Techniques for Storage Hierarchies|journal=IBM Systems Journal|volume=9|issue=2|pages=78–117|doi=10.1147/sj.92.0078}}</ref>

[[CPU cache]] plays a significant role in the overall performance of a computer system and the speed at which a [[general processing unit]] (CPU) can process data. CPU cache is very fast [[computer memory]], usually using [[static random-access memory]] (SRAM). SRAM is [[volatile memory]], it can only store data when supplied with electricity. The CPU cache sits between the CPU core and the [[random-access memory]] (RAM). The CPU cache isolates the super fast CPU cores from the much slower RAM, which is usually [[direct random access memory]] (DRAM).<ref>{{Cite book|title= Fundamentals of Computer Organization and Design | author1= Sivarama P. Dandamudi |publisher= Springer New York |year=2006 |isbn= 9780387215662 | pages=731}}</ref>

Cache placement policies can enhance the performance of data processing by the CPU cores, because computer programs may access data in the RAM sequentially, also known as sequential execution or spatial locality behavior. Alternatively computer programs may execute a part of the code or data repeatedly for some time, also known as sequential code execution or [[Infinite loop|loop structure]].<ref>{{Cite book|title= Fundamentals of Computer Organization and Design | author1= Sivarama P. Dandamudi |publisher= Springer New York |year=2006 |isbn= 9780387215662 | pages=731}}</ref>

== Direct-mapped cache ==

In a direct-mapped cache structure, the cache is organized into multiple sets<ref name=":0" /> with a single cache line per set. Based on the address of the memory block, it can only occupy a single cache line. The cache can be framed as a {{math| ''n'' × 1}} column matrix.<ref name=":1">{{Cite book|title=Fundamentals of Parallel Multi-core Architecture|last=Solihin|first=Yan|publisher=Taylor & Francis|year=2015|isbn=978-1482211184|pages=136–141}}</ref>

=== ToApproaches place a block in theto cache =placement==

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

* The set is determined by the [[CPU cache#Cache entry structure|index]]<ref name=":0" /> bits derived from the address of the memory block.

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

* The memory block is placed in the set identified and the [[CPU cache#Cache entry structure|tag]]<ref name=":0" /> is stored in the tag field associated with the set.

There are three different policies available for placement of data the CPU cache: direct-mapped, fully associative, and set-associative. Originally this space of cache organizations was described using the term "congruence mapping".<ref>{{Cite journal| last=Mattson| first=R.L.| author1-link=Richard Mattson| last2=Gecsei| first2=J.| last3=Slutz| first3=D. R.| last4=Traiger| first4=I| date=1970| title= Evaluation Techniques for Storage Hierarchies|journal=IBM Systems Journal| volume=9| issue=2| pages=78–117| doi=10.1147/sj.92.0078}}</ref>

* If the cache line is previously occupied, then the new data replaces the memory block in the cache.

=== To search a word in the cache ===

* The set is identified by the index bits of the address.

* The tag bits derived from the memory block address are compared with the tag bits associated with the set. If the tag matches, then there is a [[CPU cache#Cache entries|cache hit]] and the cache block is returned to the processor. Else there is a [[CPU cache#Cache miss|cache miss]] and the memory block is fetched from the lower memory ([[Computer data storage#Primary storage|main memory]], [[Computer data storage#Secondary storage|disk]]).

=== Advantages ===

* This placement policy is power efficient as it avoids the search through all the cache lines.

* The placement policy and the [[CPU cache#Replacement policies|replacement policy]] is simple.

* It requires cheap hardware as only one tag needs to be checked at a time.

=== Disadvantage ===

* It has lower cache hit rate, as there is only one cache line available in a set. Every time a new memory is referenced to the same set, the cache line is replaced, which causes conflict miss.<ref>{{Cite web|url=http://meseec.ce.rit.edu/eecc551-winter2001/551-1-30-2002.pdf|title=Cache Miss Types}}</ref>

=== 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.

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.''

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

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

# Address <code>0x0000</code> (tag - <code>0b00_0000</code>, index – <code>0b00_0000</code>, offset – <code>0b00</code>) corresponds to block 0 of the memory and maps to the set 0 of 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.

# 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 {{math|1 × ''m''}} row matrix.<ref name=":1" />

=== To place a block in the cache ===

* The cache line is selected based on the valid bit<ref name=":0" /> associated with it. If the valid bit is 0, the new memory block can be placed in the cache line, else it has to be placed in another cache line with valid bit 0.

* If the cache is completely occupied then a block is evicted and the memory block is placed in that cache line.

* The eviction of memory block from the cache is decided by the replacement policy.<ref>{{Cite web|url=http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Memory/fully.html|title=Fully Associative Cache|archive-url=https://web.archive.org/web/20171224054857/http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Memory/fully.html|archive-date=December 24, 2017|url-status=dead}}</ref>

=== To search a word in the cache ===

* 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

=== Disadvantages ===

* The placement policy is slow as it takes time to iterate through all the lines.{{Disputed inline|talk=Talk:Cache placement policies#Advantages/disadvantages of the fully associative cache wrong?|date=June 2022}}

* 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.

The total number of sets in the cache is 1, and the set contains 256/4=64 cache lines, as the cache block is of size 4 bytes.

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.

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.

== Set-associative cache ==

Set-associative cache is a trade-off between direct-mapped cache and fully associative cache.

A set-associative cache can be imagined as a {{math|''n'' × ''m''}} matrix. The cache is divided into ‘n’ sets and each set contains ‘m’ cache lines. A memory block is first mapped onto a set and then placed into any cache line of the set.

The range of caches from direct-mapped to fully associative is a continuum of levels of set associativity. (A direct-mapped cache is one-way set-associative and a fully associative cache with ''m'' cache lines is ''m''-way set-associative.)

Many processor caches in today's designs are either direct-mapped, two-way set-associative, or four-way set-associative.<ref name=":1" />

=== To place a block in the cache ===

* The set is determined by the index bits derived from the address of the memory block.

* The memory block is placed in an available cache line in the set identified, and the tag is stored in the tag field associated with the line. If all the cache lines in the set are occupied, then the new data replaces the block identified through the [[CPU cache#Replacement policies|replacement policy]].

=== To locate a word in the cache ===

* The set is determined by the index bits derived from the address of the memory block.

* The tag bits are compared with the tags of all cache lines present in selected set. If the tag matches any of the cache lines, it is a cache hit and the appropriate line is returned. If the tag doesn't match any of the lines, then it is a cache miss and the data is requested from next level in the memory hierarchy.

=== Advantages ===

* The placement policy is a trade-off between direct-mapped and fully associative cache.

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

=== Disadvantages ===

* The placement policy will not effectively use all the available cache lines in the cache and suffers from [[Cache performance measurement and metric#Conflict misses|conflict miss]].

=== 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.

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''.

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

* ''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.

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

# Address <code>0x0000</code> (tag - <code>0b000_0000</code>, index – <code>0b0_0000</code>, offset – <code>0b00</code>) corresponds to block 0 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.

# Address <code>0x0004</code> (tag - <code>0b000_0000</code>, index – <code>0b0_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 1, determined by the replacement policy for the cache.

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

# Address <code>0x0100</code> (tag – <code>0b000_0010</code>, index – <code>0b0_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 ==

Other schemes have been suggested, such as the ''skewed cache'',<ref name="Seznec">{{cite journal|author=André Seznec|year=1993|title=A Case for Two-Way Skewed-Associative Caches|journal=ACM SIGARCH Computer Architecture News|volume=21|issue=2|pages=169–178|doi=10.1145/173682.165152|doi-access=free}}</ref> where the index for way 0 is direct, as above, but the index for way 1 is formed with a [[hash function]]. A good hash function has the property that addresses which conflict with the direct mapping tend not to conflict when mapped with the hash function, and so it is less likely that a program will suffer from an unexpectedly large number of conflict misses due to a pathological access pattern. The downside is extra latency from computing the hash function.<ref name="CK">{{cite web|url=http://www.stanford.edu/class/ee282/08_handouts/L03-Cache.pdf|title=Lecture 3: Advanced Caching Techniques|author=C. Kozyrakis|archive-url=https://web.archive.org/web/20120907012034/http://www.stanford.edu/class/ee282/08_handouts/L03-Cache.pdf|archive-date=September 7, 2012|url-status=dead}}</ref> Additionally, when it comes time to load a new line and evict an old line, it may be difficult to determine which existing line was least recently used, because the new line conflicts with data at different indexes in each way; [[Cache algorithms|LRU]] tracking for non-skewed caches is usually done on a per-set basis. Nevertheless, skewed-associative caches have major advantages over conventional set-associative ones.<ref>

[http://www.irisa.fr/caps/PROJECTS/Architecture/ Micro-Architecture] "Skewed-associative caches have ... major advantages over conventional set-associative caches."

</ref>

== Pseudo-associative cache ==

A true set-associative cache tests all the possible ways simultaneously, using something like a [[content-addressable memory]]. A pseudo-associative cache tests each possible way one at a time. A hash-rehash cache and a column-associative cache are examples of a pseudo-associative cache.

In the common case of finding a hit in the first way tested, a pseudo-associative cache is as fast as a direct-mapped cache, but it has a much lower conflict miss rate than a direct-mapped cache, closer to the miss rate of a fully associative cache.<ref name="CK" />

== See also ==

* [[Cache algorithms]]

* [[CPU cache#Associativity|Associativity]]

* [[Cache algorithms|Cache replacement policy]]

* [[Cache hierarchy]]

* [[Cache (computing)#Writing policies|Writing Policies]]

* [[Cache coloring]]