| dbo: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)
- 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. Optimal cache-oblivious algorithms are known for matrix multiplication, matrix transposition, sorting, and several other problems. Some more general algorithms, such as Cooley–Tukey FFT, are optimally cache-oblivious under certain choices of parameters. As these algorithms are only optimal in an asymptotic sense (ignoring constant factors), further machine-specific tuning may be required to obtain nearly optimal performance in an absolute sense. The goal of cache-oblivious algorithms is to reduce the amount of such tuning that is required. Typically, a cache-oblivious algorithm works by a recursive divide-and-conquer algorithm, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into the cache, regardless of the cache size. For example, an optimal cache-oblivious matrix multiplication is obtained by recursively dividing each matrix into four sub-matrices to be multiplied, multiplying the submatrices in a depth-first fashion. In tuning for a specific machine, one may use a hybrid algorithm which uses loop tiling tuned for the specific cache sizes at the bottom level but otherwise uses the cache-oblivious algorithm. (en)
- 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 bloques que están óptimamente dimensionados para una caché dada. Los algoritmos de caché ajeno óptimos son conocidos por el , la multiplicación de matrices, el ordenamiento, la transposición de matrices, y otros problemas. Debido a que estos algoritmos son solamente óptimos en un sentido asintótico (ignorando factores constantes), un ajuste más específico de la máquina puede ser necesario para obtener un rendimiento casi óptimo en un sentido absoluto. El objetivo de los algoritmos de caché ajeno es reducir la cantidad de tales ajustes requeridos. Típicamente, un algoritmo de caché ajeno trabaja por un algoritmo recursivo divide y vencerás, donde el problema se divide en subproblemas más pequeños y más pequeños. Finalmente, se llega a un tamaño de subproblema que encaja en caché, independientemente del tamaño de la caché. Por ejemplo, una matriz de multiplicación óptima caché-ajeno se obtiene de forma recursiva dividiendo cada matriz en cuatro sub-matrices para ser multiplicada, multiplicando las submatrices de un modo primero en profundidad. En sintonía para una máquina específica, se puede utilizar un algoritmo híbrido que utiliza bloques ajustados para los tamaños de caché específicos en el nivel inferior, pero por lo demás utiliza el algoritmo de caché ajeno. (es)
|
| 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)
|
