Cache replacement policies (original) (raw)

About DBpedia

In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize in order to manage a cache of information stored on the computer. Caching improves performance by keeping recent or often-used data items in memory locations that are faster or computationally cheaper to access than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for the new ones.

thumbnail

Property Value
dbo:abstract Ein Cache-Algorithmus ist ein Algorithmus zur Steuerung eines Cache, mit dem Speicherzugriffe zwischen einer CPU und dem Arbeitsspeicher optimiert und Inkonsistenzprobleme verhindert werden sollen. Caches im weiteren Sinne werden aber auch in Software verwendet, wo die Cache-Algorithmen entsprechend gelten. Es wird unterschieden zwischen cache write policy (dt. Schreibregel) und cache replacement policy (dt. Ersetzungsregel). Der Begriff Cache-Algorithmus wird im Englischen aber in der Regel nur auf replacement policy bezogen. Bei der Betrachtung der Algorithmen unterscheidet man zudem zwischen Cache Hit (angeforderte Daten liegen im Cache) und Cache Miss (angeforderte Daten liegen nicht im Cache). Entsprechend heißen diese Situationen beim Lesen/Schreiben Write Hit/Read Hit und Write Miss/Read Miss. (de) In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize in order to manage a cache of information stored on the computer. Caching improves performance by keeping recent or often-used data items in memory locations that are faster or computationally cheaper to access than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for the new ones. (en) En computación, los algoritmos de caché (referidos también como algoritmos de reemplazo o políticas de reemplazo) son programas que optimizan la gestión de la información en la memoria caché del ordenador. Cuando el caché está lleno, el algoritmo elige qué elementos elimina para liberar espacio y poder añadir nuevos elementos. El tiempo medio de acceso en memoria es​ donde: = tiempo medio de acceso al elemento = probabilidad de fallo = 1 - (probabilidad de acierto) = tiempo para hacer un acceso a memoria cuando ha habido un fallo (o, con caché multinivel, tiempo medio entre accesos al elemento en memoria para el siguiente nivel de caché)= latencia: tiempo para acceder al elemento en caché cuando ha habido un acierto = efectos secundarios, como colas mantenidas por los multiprocesadores Hay dos cifras principales al evaluar un caché:latencia y tasa de aciertos.Hay también otros factores secundarios que afectan a la prestación del caché.​ La tasa de aciertos en el caché describe cuántas veces que se busca un elemento este está en el caché. La latencia del caché describe lo que tarda en devolver un elemento solicitado (implica que ha habido un acierto). Las estrategia de reemplazo más rápidas llevan en cuenta los elementos menos usados para reducir la cantidad de tiempo utilizado en actualizarlos. Cada estrategia de reemplazo supone un compromiso entre la tasa de aciertos y la latencia. Medidas de la tasa de acierto se hacen empíricamente mediante aplicaciones de estrés. La tasa de acierto varía ampliamente de una aplicación a otra. En particular, las aplicaciones de streaming de video y audio generalmente tienen una tasa de acierto cercana a cero, dado que cada bit del stream se lee la primera vez -una omisión obligada- y luego no es leído o escrito nunca más. Incluso peor, muchos algoritmos de caché -especialmente LRU- permiten que estos datos de streaming entren en el caché, sacando fuera otros datos que sí se usarán pronto (contaminación del caché).​ (es) キャッシュアルゴリズム（英: Cache algorithm）は、コンピュータ上で情報を格納するキャッシュを管理するプログラムまたはハードウェア構造を最適化するアルゴリズム群。キャッシュが一杯になったとき、このアルゴリズムで新たな情報を格納するための場所を選択し確保する。置換アルゴリズムあるいは置換ポリシーとも。 キャッシュのヒット率（hit rate）とは、探しているデータがキャッシュ上で見つかる率（頻度）である。キャッシュサイズを増やさずにヒット率を向上させるには、キャッシュアルゴリズムはより多くの使用（usage）情報を必要とする。 キャッシュのレイテンシとは、あるデータを要求してからキャッシュがそれを返すまでにかかる時間である。より高速な置換戦略は一般に、より少ない使用情報を使用していて、情報の更新にかかる時間が少ない（ダイレクトマップ式なら全く情報を持たない）。 それぞれのキャッシュアルゴリズムは、ヒット率とレイテンシの兼ね合いを考慮している。 (ja) Алгори́тмы кэши́рования (алгоритмы вытеснения, политики вытеснения, а также «алгоритмы/политики замещения») — в информатике это оптимизация инструкций: особая компьютерная программа или аппаратно поддерживаемая структура, способная управлять кэшем информации, хранимой в компьютере. Когда кэш заполнен, алгоритм должен выбрать, что именно нужно удалить из него, чтобы иметь возможность записи (в кэш) новой, более актуальной информации. Аппаратная реализация данных алгоритмов предполагает использование таймера, счётчика или их комбинации. «Уровень попаданий» в кэш означает то, насколько часто искомые данные обнаруживаются в кэше. Более эффективные политики вытеснения отслеживают обращения к наиболее используемой информации, чтобы улучшить уровень попаданий (при том же размере кэша). «Латентность» кэша означает, насколько быстро кэш может вернуть запрошенные данные непосредственно после запроса (в случае, если происходит «попадание»). Более быстрые стратегии вытеснения обычно отслеживают наименее используемую информацию — или, в случае кэша прямого отображения (direct-mapped cache), отсутствие информации, чтобы снизить затраты времени на обновление информации. Каждая стратегия вытеснения является компромиссом между уровнем попаданий и латентностью. (ru)
dbo:thumbnail wiki-commons:Special:FilePath/Beladysalgoworking.png?width=300
dbo:wikiPageExternalLink http://dl.acm.org/citation.cfm%3Fid=2814734 http://www.usenix.org/events/usenix01/full_papers/zhou/zhou_html/node3.html
dbo:wikiPageID 954281 (xsd:integer)
dbo:wikiPageInterLanguageLink dbpedia-fr:Algorithmes_de_remplacement_des_lignes_de_cache dbpedia-zh:快取文件置換機制
dbo:wikiPageLength 39816 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1114056358 (xsd:integer)
dbo:wikiPageWikiLink dbr:László_Bélády dbr:Benchmark_(computing) dbr:Algorithm dbr:Perceptron dbr:VLDB_conference dbr:Information-centric_networking dbr:Optimization_(computer_science) dbr:Content_delivery_network dbr:Cache-oblivious_algorithm dbr:Cache_(computing) dbr:Cache_pollution dbr:Cache_thrashing dbr:Computer_program dbr:Computing dbr:Page_fault dbr:CPU_cache dbc:Memory_management_algorithms dbr:Distributed_cache dbr:Learning_augmented_algorithm dbr:Locality_of_reference dbr:ARM_architecture dbr:File:LIRSalgoworking.png dbr:File:Mruexample.png dbr:File:Plruexample.png dbr:Page_replacement_algorithm dbc:Cache_(computing) dbr:Content_Delivery_Network dbr:Intel dbr:Operating_system dbr:Cache_algorithms dbr:Markov_chain dbr:FIFO_(computing_and_electronics) dbr:CPU_caches dbr:Cache_coherency dbr:File:Beladysalgoworking.png dbr:File:Lruexample.png dbr:File:Mockingjay_Description.svg dbr:File:MultiQueueReplacementAlgortithm.jpg
dbp:wikiPageUsesTemplate dbt:About dbt:Anchor dbt:Cleanup_reorganize dbt:Confusing dbt:Distinguish dbt:Further dbt:Multiple_issues dbt:Reflist dbt:Short_description dbt:Use_dmy_dates dbt:Copy_edit
dcterms:subject dbc:Memory_management_algorithms dbc:Cache_(computing)
rdf:type owl:Thing
rdfs:comment In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize in order to manage a cache of information stored on the computer. Caching improves performance by keeping recent or often-used data items in memory locations that are faster or computationally cheaper to access than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for the new ones. (en) キャッシュアルゴリズム（英: Cache algorithm）は、コンピュータ上で情報を格納するキャッシュを管理するプログラムまたはハードウェア構造を最適化するアルゴリズム群。キャッシュが一杯になったとき、このアルゴリズムで新たな情報を格納するための場所を選択し確保する。置換アルゴリズムあるいは置換ポリシーとも。 キャッシュのヒット率（hit rate）とは、探しているデータがキャッシュ上で見つかる率（頻度）である。キャッシュサイズを増やさずにヒット率を向上させるには、キャッシュアルゴリズムはより多くの使用（usage）情報を必要とする。 キャッシュのレイテンシとは、あるデータを要求してからキャッシュがそれを返すまでにかかる時間である。より高速な置換戦略は一般に、より少ない使用情報を使用していて、情報の更新にかかる時間が少ない（ダイレクトマップ式なら全く情報を持たない）。 それぞれのキャッシュアルゴリズムは、ヒット率とレイテンシの兼ね合いを考慮している。 (ja) Ein Cache-Algorithmus ist ein Algorithmus zur Steuerung eines Cache, mit dem Speicherzugriffe zwischen einer CPU und dem Arbeitsspeicher optimiert und Inkonsistenzprobleme verhindert werden sollen. Caches im weiteren Sinne werden aber auch in Software verwendet, wo die Cache-Algorithmen entsprechend gelten. Es wird unterschieden zwischen cache write policy (dt. Schreibregel) und cache replacement policy (dt. Ersetzungsregel). Der Begriff Cache-Algorithmus wird im Englischen aber in der Regel nur auf replacement policy bezogen. (de) En computación, los algoritmos de caché (referidos también como algoritmos de reemplazo o políticas de reemplazo) son programas que optimizan la gestión de la información en la memoria caché del ordenador. Cuando el caché está lleno, el algoritmo elige qué elementos elimina para liberar espacio y poder añadir nuevos elementos. El tiempo medio de acceso en memoria es​ donde: Hay dos cifras principales al evaluar un caché:latencia y tasa de aciertos.Hay también otros factores secundarios que afectan a la prestación del caché.​ (es) Алгори́тмы кэши́рования (алгоритмы вытеснения, политики вытеснения, а также «алгоритмы/политики замещения») — в информатике это оптимизация инструкций: особая компьютерная программа или аппаратно поддерживаемая структура, способная управлять кэшем информации, хранимой в компьютере. Когда кэш заполнен, алгоритм должен выбрать, что именно нужно удалить из него, чтобы иметь возможность записи (в кэш) новой, более актуальной информации. Аппаратная реализация данных алгоритмов предполагает использование таймера, счётчика или их комбинации. (ru)
rdfs:label Cache-Algorithmus (de) Cache replacement policies (en) Algoritmo de caché (es) キャッシュアルゴリズム (ja) Алгоритмы кэширования (ru)
owl:differentFrom dbr:Cache_placement_policies
owl:sameAs yago-res:Cache replacement policies wikidata:Cache replacement policies dbpedia-de:Cache replacement policies dbpedia-es:Cache replacement policies dbpedia-fa:Cache replacement policies dbpedia-ja:Cache replacement policies dbpedia-ru:Cache replacement policies dbpedia-simple:Cache replacement policies dbpedia-sr:Cache replacement policies dbpedia-tr:Cache replacement policies https://global.dbpedia.org/id/MWij
prov:wasDerivedFrom wikipedia-en:Cache_replacement_policies?oldid=1114056358&ns=0
foaf:depiction wiki-commons:Special:FilePath/Beladysalgoworking.png wiki-commons:Special:FilePath/LIRSalgoworking.png wiki-commons:Special:FilePath/Lruexample.png wiki-commons:Special:FilePath/Mockingjay_Description.svg wiki-commons:Special:FilePath/Mruexample.png wiki-commons:Special:FilePath/MultiQueueReplacementAlgortithm.jpg wiki-commons:Special:FilePath/Plruexample.png
foaf:isPrimaryTopicOf wikipedia-en:Cache_replacement_policies
is dbo:wikiPageRedirects of dbr:Bélády's_Min dbr:Least_Recently_Used dbr:Cache_Replacement_Policies dbr:Cache_algorithms dbr:Least_recently_used dbr:Least-recently_used dbr:LRU_algorithm dbr:LRU_cache dbr:Belady's_Min dbr:Cache_algorithm dbr:Cache_replacement_algorithm dbr:Cache_replacement_policy dbr:Caching_algorithm dbr:MRU_cache
is dbo:wikiPageWikiLink of dbr:Mockingjay_(disambiguation) dbr:László_Bélády dbr:Bélády's_Min dbr:Algorithmic_efficiency dbr:Consistent_hashing dbr:Computer_performance dbr:Thrashing_(computer_science) dbr:ABA_problem dbr:Least_Recently_Used dbr:THE_multiprogramming_system dbr:Bélády's_anomaly dbr:Cache_Replacement_Policies dbr:Cache_algorithms dbr:MRU dbr:Virtual_memory dbr:Least_recently_used dbr:Least-recently_used dbr:LRU_algorithm dbr:LRU_cache dbr:Belady's_Min dbr:Cache_algorithm dbr:Cache_replacement_algorithm dbr:Cache_replacement_policy dbr:Caching_algorithm dbr:MRU_cache
is owl:differentFrom of dbr:Cache_placement_policies
is foaf:primaryTopic of wikipedia-en:Cache_replacement_policies