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

Les limites des registres

Description

Cette séance de cours couvre les limites des registres dans la mise en œuvre du consensus entre les processus, en se concentrant sur les algorithmes utilisant Fetch&Inc, Test&Set et Compare&Swap objets. Il discute de l'impossibilité de parvenir à un consensus avec seulement des registres, présentant des preuves et des lemmes pour soutenir les arguments.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Source officielle

Concepts associés (17)

Compare-and-swap

Compare-and-swap (CAS) est une instruction atomique utilisée dans les systèmes multiprocesseurs ou multi-cœurs utilisant une mémoire partagée. Elle compare la valeur stockée à une adresse mémoire donnée à l'un de ses arguments et, en cas d'égalité, écrit une nouvelle valeur à cette adresse. Selon les implémentations, elle signale si l'écriture a réussi soit en renvoyant une valeur booléenne, soit en renvoyant la valeur lue en mémoire.

Fetch-and-add

Fetch And Add en informatique, désigne l'instruction d'extraction et d'ajout de processeur (FAA pour Fetch-And-Add) incrémentant atomiquement le contenu d'un emplacement de mémoire par une valeur spécifiée. Autrement dit, l'instruction d'extraction et d'ajout effectue l'opération incrémentant la valeur à l'adresse x par a (où x est une adresse de mémoire et a est une valeur quelconque), puis retourne la valeur d'origine de l'adresse x, de telle sorte que si cette opération est exécutée par un processus dans un système simultané, aucun autre processus ne verra jamais un résultat intermédiaire.

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.

Registre de processeur

Un registre est un emplacement de mémoire interne à un processeur. Les registres se situent au sommet de la hiérarchie mémoire : il s'agit de la mémoire la plus rapide d'un ordinateur, mais dont le coût de fabrication est le plus élevé, car la place dans un microprocesseur est limitée. Une architecture externe de processeur définit un ensemble de registres, dits architecturaux, qui sont accessibles par son jeu d'instructions. Ils constituent l'état externe (architectural) du processeur.

Algorithme de recherche

En informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au problème. Supposons que l'ensemble de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une relation d'ordre. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.

Afficher plus

Séances de cours associées (29)

Architecture informatique : Algorithmes aux programmes (Compilation)

Explore la transition des algorithmes aux programmes par la compilation, en mettant l'accent sur les contraintes et les pratiques de codage compréhensibles par la machine.

Résoudre les jeux de parité dans la pratique

Explore les aspects pratiques de la résolution des jeux de parité, y compris les stratégies gagnantes, les algorithmes, la complexité, le déterminisme et les approches heuristiques.

Optimisation quasi-newton

Couvre les méthodes de recherche de ligne de gradient et les techniques d'optimisation en mettant l'accent sur les conditions Wolfe et la définition positive.

Complexité et induction: Algorithmes et preuves

Couvre la complexité, les algorithmes et les preuves du pire cas, y compris l'induction mathématique et la récursion.

Architecture informatique: résumé

Explore l'architecture informatique, la mémoire, les registres, les circuits VLSI, les algorithmes et l'interaction logiciel-matériel.

Afficher plus

Concepts associés (17)

Compare-and-swap

Fetch-and-add

Algorithme

Registre de processeur

Algorithme de recherche

Afficher plus