Content deleted Content added
m Reverted 1 edit by 154.74.127.182 (talk) to last revision by Kvng |
m Disambiguating links to General-purpose computing on graphics processing units (link changed to General-purpose computing on graphics processing units (software)) using DisamAssist. |
||
| (19 intermediate revisions by 11 users not shown) | |||
Line 7:
In [[computing]], a '''cache''' ({{IPAc-en|audio=LL-Q1860 (eng)-Back ache-cache.wav|k|æ|ʃ}} {{respell|KASH}})<ref>
{{cite web|url=http://www.oxforddictionaries.com/definition/english/cache|archive-url=https://web.archive.org/web/20120818122040/http://oxforddictionaries.com/definition/english/cache|url-status=dead|archive-date=18 August 2012|title=Cache|work=Oxford Dictionaries|access-date=2 August 2016}}</ref> is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewhere. A '''cache hit''' occurs when the requested data can be found in a cache, while a '''cache miss''' occurs when it cannot. Cache hits are served by reading data from the cache, which is faster than recomputing a result or reading from a slower data store; thus, the more requests that can be served from the cache, the faster the system performs.<ref>{{Cite journal|last1=Zhong|first1=Liang|last2=Zheng|first2=Xueqian|last3=Liu|first3=Yong|last4=Wang|first4=Mengting|last5=Cao|first5=Yang|date=February 2020|title=Cache hit ratio maximization in device-to-device communications overlaying cellular networks|url=http://dx.doi.org/10.23919/jcc.2020.02.018|journal=China Communications|volume=17|issue=2|pages=232–238|doi=10.23919/jcc.2020.02.018|s2cid=212649328|issn=1673-5447|url-access=subscription}}</ref>
To be cost-effective, caches must be relatively small. Nevertheless, caches are effective in many areas of computing because typical [[Application software|computer applications]] access data with a high degree of [[locality of reference]]. Such access patterns exhibit temporal locality, where data is requested that has been recently requested, and spatial locality, where data is requested that is stored near data that has already been requested.
Line 31:
During a cache miss, some other previously existing cache entry is typically removed in order to make room for the newly retrieved data. The [[Heuristic (computer science)|heuristic]] used to select the entry to replace is known as the [[Cache replacement policies|replacement policy]]. One popular replacement policy, least recently used (LRU), replaces the oldest entry, the entry that was accessed less recently than any other entry. More sophisticated caching algorithms also take into account the frequency of use of entries.
==={{Anchor|Dirty|WRITEPOLICIES|WRITE-BACK|WRITE-BEHIND|WRITE-THROUGH|WRITE-AROUND}}
[[File:Write-through with no-write-allocation.svg|thumb|380px|A write-through cache without write allocation]]
[[File:Write-back with write-allocation.svg|thumb|500px|A write-back cache with write allocation]]
* ''Write-through'':
* ''Write-back'':
A write-back cache is more complex to implement since it needs to track which of its locations have been written over and mark them as ''dirty'' for later writing to the backing store. The data in these locations are written back to the backing store only when they are evicted from the cache, a process referred to as a ''lazy write''. For this reason, a read miss in a write-back cache
* ''Write allocate'' (also called ''fetch on write''):
* ''No-write allocate'' (also called ''write-no-allocate'' or ''write around''):
* A write-back cache
* A write-through cache uses no-write allocate. Here, subsequent writes have no advantage, since they still need to be written directly to the backing store.
Entities other than the cache may change the data in the backing store, in which case the copy in the cache may become out-of-date or ''stale''. Alternatively, when the client updates the data in the cache, copies of
===Prefetch===
Line 69:
Earlier [[graphics processing unit]]s (GPUs) often had limited read-only [[texture cache]]s and used [[swizzling (computer graphics)|swizzling]] to improve 2D [[locality of reference]]. [[Cache miss]]es would drastically affect performance, e.g. if [[mipmapping]] was not used. Caching was important to leverage 32-bit (and wider) transfers for texture data that was often as little as 4 bits per pixel.
As GPUs advanced, supporting [[General-purpose computing on graphics processing units (software)|general-purpose computing on graphics processing units]] and [[compute kernel]]s, they have developed progressively larger and increasingly general caches, including [[instruction cache]]s for [[shader]]s, exhibiting functionality commonly found in CPU caches. These caches have grown to handle [[synchronization primitive]]s between threads and [[atomic operation]]s, and interface with a CPU-style MMU.
===DSPs===
Line 88:
The time aware least recently used (TLRU) is a variant of LRU designed for the situation where the stored contents in cache have a valid lifetime. The algorithm is suitable in network cache applications, such as ICN, [[content delivery network]]s (CDNs) and distributed networks in general. TLRU introduces a new term: time to use (TTU). TTU is a time stamp on content which stipulates the usability time for the content based on the locality of the content and information from the content publisher. Owing to this locality-based time stamp, TTU provides more control to the local administrator to regulate in-network storage.
In the TLRU algorithm, when a piece of content arrives, a cache node calculates the local TTU value based on the TTU value assigned by the content publisher. The local TTU value is calculated by using a locally
=====Least frequent recently used=====
The least frequent recently used (LFRU) cache replacement scheme combines the benefits of LFU and LRU schemes. LFRU is suitable for network cache applications, such as ICN, CDNs and distributed networks in general. In LFRU, the cache is divided into two partitions called privileged and unprivileged partitions. The privileged partition can be seen as a protected partition. If content is highly popular, it is pushed into the privileged partition. Replacement of the privileged partition is done by first evicting content from the unprivileged partition, then pushing content from the privileged partition to the unprivileged partition, and finally inserting new content into the privileged partition. In the above procedure, the LRU is used for the privileged partition and an approximated LFU (ALFU) scheme is used for the unprivileged partition. The basic idea is to cache the locally popular content with the ALFU scheme and push the popular content to the privileged partition.<ref>{{cite journal|author=Bilal, Muhammad|display-authors=etal|title=A Cache Management Scheme for Efficient Content Eviction and Replication in Cache Networks|journal=IEEE Access|volume=5|pages=1692–1701|arxiv=1702.04078|bibcode=2017arXiv170204078B|year=2017|doi=10.1109/ACCESS.2017.2669344|s2cid=14517299}}</ref
====Weather forecast====
In 2011, the use of smartphones with weather forecasting options was overly taxing [[AccuWeather]] servers; two requests
==Software caches==
===Disk cache===
While CPU caches are generally managed entirely by hardware, a variety of software manages other caches. The [[page cache]] in main memory
▲While CPU caches are generally managed entirely by hardware, a variety of software manages other caches. The [[page cache]] in main memory, which is an example of disk cache, is managed by the operating system [[Kernel (operating system)|kernel]].
While the [[disk buffer]], which is an integrated part of the hard disk drive or solid state drive, is sometimes misleadingly referred to as
Finally, a fast local hard disk drive can also cache information held on even slower data storage devices, such as remote servers ([[web cache]]) or local [[tape drive]]s or [[optical jukebox]]es; such a scheme is the main concept of [[hierarchical storage management]]. Also, fast flash-based solid-state drives (SSDs) can be used as caches for slower rotational-media hard disk drives, working together as [[hybrid drive]]s
===Web cache===
{{Main|Web cache}}
Web browsers and [[
Another form of cache is [[P2P caching]], where the files most sought for by [[peer-to-peer]] applications are stored in an ISP cache to accelerate P2P transfers. Similarly, decentralised equivalents exist, which allow communities to perform the same task for P2P traffic, for example, Corelli.<ref>{{cite conference|last1=Tyson|first1=Gareth|last2=Mauthe|first2=Andreas|last3=Kaune|first3=Sebastian|last4=Mu|first4=Mu|last5=Plagemann|first5=Thomas|title=Corelli: A Dynamic Replication Service for Supporting Latency-Dependent Content in Community Networks|url=http://comp.eprints.lancs.ac.uk/2044/1/MMCN09.pdf|conference=MMCN'09|archive-url=https://web.archive.org/web/20150618193018/http://comp.eprints.lancs.ac.uk/2044/1/MMCN09.pdf|archive-date=2015-06-18}}</ref>
Line 118 ⟶ 115:
===Content delivery network===
{{
A [[content delivery network]] (CDN) is a network of distributed servers that deliver pages and other
CDNs
===Cloud storage gateway===
{{Main|Cloud storage gateway}}
A [[cloud storage gateway
===Other caches===
The
Write-through operation is common when operating over [[unreliable
[[Web search
[[Database caching]] can substantially improve the throughput of [[database]] applications, for example in the processing of [[Database index|indexes]], [[Data dictionary|data dictionaries]], and frequently used subsets of data.
A [[distributed cache]]<ref>{{cite journal|last1=Paul|first1=S.|last2=Fei|first2=Z.|date=1 February 2001|title=Distributed caching with centralized control|journal=Computer Communications|volume=24|issue=2|pages=256–268|citeseerx=10.1.1.38.1094|doi=10.1016/S0140-3664(00)00322-4}}
=={{anchor|The difference between buffer and cache}}<!--Former section name used in external links-->Buffer vs. cache==
| |||