L’entrelacement, ou comment le désordre peut être efficace
L’entrelacement : explications
L’entrelacement est une technique de stockage des données qui permet d’augmenter les performances d’accès sur un disque, en arrangeant lesdites données dans un ordre prédéfini. Quand on a commencé à utiliser massivement des disques pour stocker les données informatiques, on s’est vite rendu compte qu’il fallait agencer les données sur le disque de manière à optimiser les vitesses de lecture et d’écriture. La manière la plus logique serait de ranger physiquement les données qui vont ensemble au même endroit et dans le bon ordre sur le disque, mais on voit à l’utilisation que ce n’est pas la manière la plus rapide pour l’accès à ces données. On va lui préférer une technique de « désordre intelligent », plus souvent appelé entrelacement.
Donc je vais mélanger mes données et ça va aller plus vite ?
Exactement ! Quand on stocke des données sur un disque, ce dernier est divisé en « secteurs » ou « blocs » qui regroupent un nombre fini de bytes (512 bytes sur les disques durs communs, 2048 pour les CD et les DVD).
Imaginons maintenant qu’on veut accéder à un fichier de 4,5 ko sur notre disque dur, et donc lire successivement 9 secteurs. On pourrait penser que le moyen le plus rapide est de placer nos secteurs dans l’ordre, de 1 à 9 : la tête de lecture lirait donc d’abord le secteur 1, puis passerait directement au 2, au 3 et ainsi de suite. Malheureusement, lire des données, ce n’est pas instantané ! Si on place les secteurs 1 et 2 l’un à côté de l’autre, il faut que l’unité de lecture du disque dur ait fini d’analyser les données du secteur 1 immédiatement, pour pouvoir commencer à lire le secteur 2 quand celui-ci arrive sous la tête de lecture. Comme le disque tourne en continu, si jamais la lecture du secteur 1 prend un peu trop de temps, le disque va sauter le secteur deux et se retrouver au secteur 3, qu’il ne veut pas lire ! Dans ce cas, pour retourner au secteur 2, le disque doit effectuer une rotation complète pour se replacer au début du secteur 2. Cette perte de temps est critique puisqu’elle arrive à chaque fois qu’on veut lire un secteur.
Mince, mais alors comment je les range, mes données ?
Il y a donc une corrélation entre le temps de lecture d’un secteur et la vitesse de rotation du disque, qui va nous permettre de déterminer quelle distance il doit y avoir entre les secteurs 1 et 2 pour optimiser la lecture. Imaginons que la lecture du secteur 1 finisse alors que la tête de lecture se trouve au-dessus du secteur 4 : on va entrelacer les données avec un rapport de 1:4. Les secteurs seront alors placés de la manière suivante :
1 8 6 4 2 9 7 5 3
Et la lecture s’effectuera comme ça :
- Lecture du secteur 1
- Calcul le temps que 3 secteurs passent
- Lecture disponible
- Reprise de la lecture au secteur 2
- Etc..
Ça marche exactement pareil pour l’écriture ! Sur les ordinateurs des années 1990, c’était même à l’utilisateur de choisir la valeur de l’entrelacement avec laquelle il voulait formater son disque !
L’entrelacement dans la mémoire RAM
Mais mélanger les données, ce n’est pas utile seulement sur les disques durs traditionnels, on s’est rendu compte rapidement qu’un système un peu similaire pouvait s’appliquer au sein de la mémoire du processeur, pour les Dynamic Random Access Memory (DRAM). L’idée est de séparer la mémoire principale en plusieurs « bancs » de mémoire. Comme le CPU peut accéder facilement à ces différents bancs de mémoire, on peut améliorer les performances d’accès et donc compenser la relative lenteur des DRAM. L’idée est la même que sur un disque dur, comme chaque banc de mémoire a un temps d’attente minimum entre chaque lecture ou écriture, on essaye d’optimiser notre temps pour que le CPU ne soit jamais inactif. Ainsi, on augmente significativement le débit de notre mémoire, en écriture et en lecture. Ici on discerne généralement 2 méthodes différentes :
- « 2 way interleaving »
- « 4 way interleaving »
Le processeur accède dans la première méthode à 2 bancs de mémoire simultanément, à la fois pour lire et écrire, et à 4 bancs de mémoire dans la deuxième méthode.
Conclusion
L’entrelacement est une technique utilisée dans tous les supports de stockage de nos jours, car elle augmente beaucoup les caractéristiques de débit en lecture et en écriture. Avec le « big data » dont tout le monde parle, le stockage des données étant l’un des grands défis numériques du 21ème siècle, les techniques d’optimisation comme l’entrelacement ne doivent pas être négligées, et les chercheurs du monde entier cherchent encore comment améliorer nos techniques de stockage de l’information.