Editing CPU cache (section)

===Multicolumn cache===
Comparing with a direct-mapped cache, a set associative cache has a reduced number of bits for its cache set index that maps to a cache set, where multiple ways or blocks stays, such as 2 blocks for a 2-way set associative cache and 4 blocks for a 4-way set associative cache. Comparing with a direct mapped cache, the unused cache index bits become a part of the tag bits. For example, a 2-way set associative cache contributes 1 bit to the tag and a 4-way set associative cache contributes 2 bits to the tag. The basic idea of the multicolumn cache<ref name="Two-fast">{{Cite journal |last1=Zhang |first1=Chenxi |last2=Zhang |first2=Xiaodong |last3=Yan |first3=Yong |date=September–October 1997 |title=Two fast and high-associativity cache schemes |journal=IEEE Micro |volume=17 |issue=5 |pages=40–49 |doi=10.1109/40.621212}}</ref> is to use the set index to map to a cache set as a conventional set associative cache does, and to use the added tag bits to index a way in the set. For example, in a 4-way set associative cache, the two bits are used to index way 00, way 01, way 10, and way 11, respectively. This double cache indexing is called a "major location mapping", and its latency is equivalent to a direct-mapped access. Extensive experiments in multicolumn cache design<ref name="Two-fast" /> shows that the hit ratio to major locations is as high as 90%. If cache mapping conflicts with a cache block in the major location, the existing cache block will be moved to another cache way in the same set, which is called "selected location". Because the newly indexed cache block is a most recently used (MRU) block, it is placed in the major location in multicolumn cache with a consideration of temporal locality. Since multicolumn cache is designed for a cache with a high associativity, the number of ways in each set is high; thus, it is easy find a selected location in the set. A selected location index by an additional hardware is maintained for the major location in a cache block.{{Citation needed|date=May 2023}}

Multicolumn cache remains a high hit ratio due to its high associativity, and has a comparable low latency to a direct-mapped cache due to its high percentage of hits in major locations. The concepts of major locations and selected locations in multicolumn cache have been used in several cache designs in ARM Cortex R chip,<ref>{{Cite web |date=2014 |title=ARM Cortex-R Series Programmer's Guide |url=https://developer.arm.com/documentation/den0042/latest |access-date=2023-05-04 |website=developer.arm.com}}</ref> Intel's way-predicting cache memory,<ref>{{Cite web|url=https://patents.google.com/patent/US6425055B1/en|title=Way-predicting cache memory}}</ref> IBM's reconfigurable multi-way associative cache memory<ref>{{Cite web |date=November 22, 1994 |title=Reconfigurable multi-way associative cache memory |url=https://patents.google.com/patent/US5367653A/en |access-date=2024-01-19}}</ref> and Oracle's dynamic cache replacement way selection based on address tab bits.<ref>{{Cite web |title=US Patent Application for DYNAMIC CACHE REPLACEMENT WAY SELECTION BASED ON ADDRESS TAG BITS Patent Application (Application #20160350229 issued December 1, 2016) – Justia Patents Search |url=https://patents.justia.com/patent/20160350229 |website=patents.justia.com}}</ref>