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.

Principes de localité

modifier

Les programmes possèdent deux caractéristiques intéressantes :

  1. 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.
  2. ils tendent à réutiliser les données et instructions utilisées dans le passé: il s'agit du principe de localité temporelle.

La raison pour laquelle ces principes sont vérifiés est la manière dont sont créés les programmes et les processeurs. En effet, des données ou instructions qui sont reliées entre elles (par exemple les données d'un tableau) sont enregistrées dans des endroits proches les uns des autres de la mémoire principale. Or, les programmes traitent habituellement les données de manière séquentielle. Ainsi, si un élément est accédé, son voisin sera très probablement accédé, créant ainsi la localité spatiale. Les boucles étant des caractéristiques courantes des programmes modernes, un élément accédé récemment sera également accédé dans le futur, créant ainsi la localité temporelle.

Utilité

modifier

Ces principes de localité sont notamment utilisés pour les techniques de paging. Les mémoires cache tirent également profit du principe de localité pour tenter de prédire les données et instructions qui seront accédées dans le futur proche. Les algorithmes de remplacement de lignes de cache tentent d'utiliser ce principe pour être aussi près que possible de la politique de remplacement optimal.