About: Cache-oblivious algorithm

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Cache-oblivious algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Whole100003553, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FCache-oblivious_algorithm&graph=http%3A%2F%2Fdbpedia.org&graph=http%3A%2F%2Fdbpedia.org

In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An optimal cache-oblivious algorithm is a cache-oblivious algorithm that uses the cache optimally (in an asymptotic sense, ignoring constant factors). Thus, a cache-oblivious algorithm is designed to perform well, without modification, on multiple machines with different cache sizes, or for a memory hierarchy with different levels of cache having different sizes. Cache-oblivious algorithms are contrasted with explicit loop tiling, which explicitly breaks a problem into blocks that are optimally sized for a given cache.

Attributes	Values
rdf:type	software yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553
rdfs:label	Cache-oblivious algoritmus (cs) Cache-Oblivious Algorithmus (de) Algoritmo de caché ajeno (es) Cache-oblivious algorithm (en)
rdfs:comment	V informatice, cache-oblivious algoritmus, česky asi kešově průhledný algoritmus, je algoritmus navržený tak, aby využil výhod CPU cache, aniž by znal její velikost a charakteristiky. Algoritmus je navržený tak, aby se choval dobře na strojích s různou velikostí keše nebo když má paměťová hierarchie různý počet úrovní. Cache-oblivious algoritmy jsou dávány do protikladu k algoritmům s dělením na bloky, které problém dělí na bloky vhodné pro danou velikost keše. (cs) In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An optimal cache-oblivious algorithm is a cache-oblivious algorithm that uses the cache optimally (in an asymptotic sense, ignoring constant factors). Thus, a cache-oblivious algorithm is designed to perform well, without modification, on multiple machines with different cache sizes, or for a memory hierarchy with different levels of cache having different sizes. Cache-oblivious algorithms are contrasted with explicit loop tiling, which explicitly breaks a problem into blocks that are optimally sized for a given cache. (en) Ein cache-oblivious Algorithmus ist ein Algorithmus, der effizient auf Architekturen mit mehrstufiger Speicherhierarchie arbeitet, ohne deren genaue Parameter zu kennen.Diese Parameter sind zum Beispiel die Anzahl der Caches, die Größe der jeweiligen Cachezeilen oder deren Zugriffszeiten.Die Performance wird im sogenannten Idealized Cache Modell analysiert, in dem das Kostenmaß die Cache-Misses sind. Ein cache-oblivious Algorithmus ist optimal, wenn er die Caches asymptotisch optimal benutzt, also eine bis auf konstante Faktoren minimale Anzahl an Cache-Misses erzeugt. (de) En computación, un algoritmo de caché-ajeno (o algoritmo caché-trascendente) es un algoritmo diseñado para tomar ventaja de un caché de la CPU sin tener el tamaño de la memoria caché (o la longitud de las líneas de caché, etc.) como un parámetro explícito. Un algoritmo óptimo caché-ajeno es un algoritmo de caché ajeno que utiliza el caché de forma óptima (en un sentido asintótico haciendo caso omiso de factores constantes). Por lo tanto, un algoritmo caché-ajeno está diseñado para funcionar bien, sin modificaciones, en varias máquinas con diferentes tamaños de caché, o para una jerarquía de memoria con diferentes niveles de caché que tienen diferentes tamaños. Los algoritmos de caché ajeno se contrastan con bloques explícitos, como en la , que separa de forma explícita un problema en bloqu (es)
foaf:depiction
dcterms:subject	Analysis of algorithms Models of computation Cache (computing)
Wikipage page ID	1773377 (xsd:integer)
Wikipage revision ID	1120865123 (xsd:integer)
Link from a Wikipage to another Wikipage	Cache-oblivious distribution sort Cache line Cache miss Quicksort Memory address Blitz++ Algorithm Massachusetts Institute of Technology Funnelsort Cooley–Tukey FFT algorithm Lower bound Cache (computing) Computer program Computing Performance tuning Priority queue B-tree CPU cache Divide-and-conquer algorithm Locality of reference Amortized analysis Harald Prokop Recursion Hash table Hybrid algorithm Abstract machine Analysis of algorithms Models of computation Charles E. Leiserson Cache (computing) Least Recently Used Block (data storage) Loop tiling In-place matrix transposition Mergesort Random-access memory Cache-oblivious matrix multiplication Memory hierarchy Model of computation Turing machine External memory algorithm External sorting RAM model Running time Asymptotic notation Asymptotically optimal Matrix transpose Matrix transposition Main memory Depth-first External memory model dbr:Todd_Veldhuizen
sameAs	Cache-oblivious algorithm Cache-oblivious algorithm Cache-oblivious algorithm Cache-oblivious algorithm Cache-oblivious algorithm Cache-oblivious algorithm Cache-oblivious algorithm
dbp:wikiPageUsesTemplate	dbt:Cn dbt:Mvar dbt:Not_a_typo dbt:Reflist dbt:Short_description
thumbnail	wiki-commons:Special:FilePath/External_memory.svg?width=300
has abstract	V informatice, cache-oblivious algoritmus, česky asi kešově průhledný algoritmus, je algoritmus navržený tak, aby využil výhod CPU cache, aniž by znal její velikost a charakteristiky. Algoritmus je navržený tak, aby se choval dobře na strojích s různou velikostí keše nebo když má paměťová hierarchie různý počet úrovní. Cache-oblivious algoritmy jsou dávány do protikladu k algoritmům s dělením na bloky, které problém dělí na bloky vhodné pro danou velikost keše. Tyto algoritmy jsou obvykle navrhovány pomocí rekurzivního dělení (rozděl a panuj). Na určité úrovni se celý vstup vejde do keše a výpočet probíhá v ní. Jako optimální cache-oblivious byly navrženy například algoritmy: rychlá Fourierova transformace, násobení matic, třídicí algoritmus, transpozice matice a další. (cs) Ein cache-oblivious Algorithmus ist ein Algorithmus, der effizient auf Architekturen mit mehrstufiger Speicherhierarchie arbeitet, ohne deren genaue Parameter zu kennen.Diese Parameter sind zum Beispiel die Anzahl der Caches, die Größe der jeweiligen Cachezeilen oder deren Zugriffszeiten.Die Performance wird im sogenannten Idealized Cache Modell analysiert, in dem das Kostenmaß die Cache-Misses sind. Ein cache-oblivious Algorithmus ist optimal, wenn er die Caches asymptotisch optimal benutzt, also eine bis auf konstante Faktoren minimale Anzahl an Cache-Misses erzeugt. Entwurfsziel ist eine gute Performance des gleichen Codes auf verschiedenen Maschinen mit vielen Speicherebenen, ohne dass Anpassungen an die Architektur gemacht werden müssen.(Für eine optimale Performance müssen allerdings noch Anpassungen an die jeweilige Hardware vorgenommen werden, die über die Speicherhierarchie hinausgehen.) Cache-oblivious Algorithmen sind verwandt mit External Memory Algorithmen, bei denen im Gegensatz aber nur von einer zweistufigen Speicherhierarchie ausgegangen wird und bei denen die Größe des kleineren/schnelleren sowie die Blockgröße des größeren/langsameren Speichers dem Algorithmus als Eingabeparameter zur Verfügung stehen.Ein optimaler cache-oblivious Algorithmus für zwei Speicherebenen ist auch optimal für beliebig viele Speicherebenen. (de)

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 43 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software