Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Algorithmes en ligne: ratio concurrentiel

Dans cours

CS-450: Algorithms II

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many ...

Description

Cette séance de cours par l'instructeur couvre les algorithmes en ligne où l'entrée est révélée progressivement. Il discute du concept de ratio concurrentiel dans les algorithmes de mise en cache, explorant des stratégies pour minimiser les erreurs de cache et optimiser l'utilisation de la mémoire.

Enseignant·e·s (3)

Mikhail Kapralov

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Source officielle

Concepts associés (32)

Mémoire cache

Une mémoire cache ou antémémoire est, en informatique, une mémoire qui enregistre temporairement des copies de données provenant d'une source, afin de diminuer le temps d'un accès ultérieur (en lecture) d'un matériel informatique (en général, un processeur) à ces données. Le principe du cache est également utilisable en écriture, et existe alors en trois modes possibles : write-through, write-back et write-around.

Algorithmes de remplacement des lignes de cache

Article principal : mémoire cache Les mémoires caches dans les matériels informatiques sont le plus souvent partiellement associatives : une ligne de la mémoire principale ne peut être rangée que dans une partie bien définie de la mémoire cache. Dans le cas d'une mémoire cache logicielle, il est possible qu'elle soit totalement associative et gérée globalement. Dans les deux cas, se pose le problème de devoir dégager une place dans la mémoire cache, ou dans la partie de celle-ci concernée, lorsque celle-ci est pleine et qu'on veut y charger des données de la mémoire principale.

Cache de processeur

Un cache de processeur est une antémémoire matérielle utilisée par l'unité centrale de traitement (CPU) d'un ordinateur pour réduire le coût moyen (temps ou énergie) de l’accès aux données de la mémoire principale. Un cache de processeur est une mémoire plus petite et plus rapide, située au plus près d'une unité centrale de traitement (ou d'un cœur de microprocesseur), qui stocke des copies des données à partir d'emplacements de la mémoire principale qui sont fréquemment utilisés avant leurs transmissions aux registres du processeur.

Cache hierarchy

Cache hierarchy, or multi-level caches, refers to a memory architecture that uses a hierarchy of memory stores based on varying access speeds to cache data. Highly requested data is cached in high-speed access memory stores, allowing swifter access by central processing unit (CPU) cores. Cache hierarchy is a form and part of memory hierarchy and can be considered a form of tiered storage. This design was intended to allow CPU cores to process faster despite the memory latency of main memory access.

Competitive analysis (online algorithm)

Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance. An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded.

Afficher plus

Séances de cours associées (58)

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.

Algorithmes d'approximation

Couvre les algorithmes d'approximation pour les problèmes d'optimisation, la relaxation LP et les techniques d'arrondi aléatoire.

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.

Produit cartésien et induction

Présente le produit cartésien et l'induction pour les épreuves utilisant des entiers et des ensembles.

Hiérarchie de la mémoire et performance de cache

Explore la mémoire virtuelle, les tables de pages, le TLB et la mémoire cache dans les systèmes informatiques.

Afficher plus

Concepts associés (32)

Mémoire cache

Algorithmes de remplacement des lignes de cache

Cache de processeur

Cache hierarchy

Competitive analysis (online algorithm)

Afficher plus