Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Cache-oblivious algorithm
Résumé
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.
The idea (and name) for cache-oblivious algorithms was conceived by Charles E.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (9)
CS-307: Introduction to multiprocessor architecture
Multiprocessors are a core component in all types of computing infrastructure, from phones to datacenters. This course will build on the prerequisites of processor design and concurrency to introduce
CS-471: Advanced multiprocessor architecture
Multiprocessors are now the defacto building blocks for all computer systems. This course will build upon the basic concepts offered in Computer Architecture I to cover the architecture and organizati
CS-550: Formal verification
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
Séances de cours associées (48)
Mémoire cache
Explore la conception de mémoire cache, les succès, les ratés et les politiques d'expulsion dans les systèmes informatiques, en mettant l'accent sur la localité spatiale et temporelle.
Programmes de vérification avec l'inox: Partie 2
Se concentre sur l'utilisation d'Inox pour la vérification des programmes, en démontrant le processus de vérification des programmes et en assurant l'exactitude.
Caches - Performance
Explore l'évaluation des performances de la mémoire cache, couvrant les points de repère, la loi d'Amdahl, les performances du processeur, la hiérarchie de la mémoire, les optimisations de cache et les caches multiniveaux.
Publications associées (91)
Intermediate Address Space: virtual memory optimization of heterogeneous architectures for cache-resident workloads
David Atienza Alonso, Marina Zapater Sancho, Luis Maria Costero Valero, Darong Huang, Qunyou Liu
The increasing demand for computing power and the emergence of heterogeneous computing architectures have driven the exploration of innovative techniques to address current limitations in both the compute and memory subsystems. One such solution is the use ...
2024TiC-SAT: Tightly-coupled Systolic Accelerator for Transformers
David Atienza Alonso, Giovanni Ansaloni, Alireza Amirshahi, Joshua Alexander Harrison Klein
Transformer models have achieved impressive results in various AI scenarios, ranging from vision to natural language processing. However, their computational complexity and their vast number of parameters hinder their implementations on resource-constraine ...
2023uKharon: A Membership Service for Microsecond Applications
Rachid Guerraoui, Antoine Murat, Javier Picorel Obando, Athanasios Xygkis
Modern data center fabrics open the possibility of microsecond distributed applications, such as data stores and message queues. A challenging aspect of their development is to ensure that, besides being fast in the common case, these applications react fa ...
USENIX Association2023Personnes associées (29)
Unités associées (10)
Concepts associés (6)
Tri rapide
En informatique, le tri rapide ou tri pivot (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. Dans le cas des tableaux, c'est un tri en place mais non stable. La complexité moyenne du tri rapide pour n éléments est proportionnelle à n log n, ce qui est optimal pour un tri par comparaison, mais la complexité dans le pire des cas est quadratique.
Diviser pour régner (informatique)
thumb|652x652px|Trois étapes (diviser, régner, combiner) illustrées avec l'algorithme du tri fusion En informatique, diviser pour régner (du latin , divide and conquer en anglais) est une technique algorithmique consistant à : Diviser : découper un problème initial en sous-problèmes ; Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ; Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.
Principe de localité (informatique)
Le principe de localité est un terme générique en informatique, qui correspond à une observation des programmes actuels et regroupe différents types de localités. Les programmes possèdent deux caractéristiques intéressantes : ils tendent à utiliser les instructions et les données qui sont situées dans la zone mémoire proche des données et instructions accédées récemment: il s'agit du principe de localité spatiale. Alors que les programmes suivent fréquemment des boucles et des sauts pour les instructions, la localité spatiale est encore plus marquée pour les données.