Français
Menu

Qu'est-ce que Tableau ?

Structure de données qui range à la suite des valeurs de même type et désigne chaque élément par un indice. Comme les éléments sont stockés de façon contiguë en mémoire, la position de n'importe quel élément se calcule à partir de son indice : chaque élément peut donc être lu ou écrit en temps constant. Certains langages font commencer les indices à 0, certaines notations à 1.

Nom japonais: 配列

« Tableau » apparaît dans 74 questions d'entraînement réparties sur 15 thèmes, dont Bases de la programmation (trace de pseudo-code), Structures de données et algorithmes, Programmation GPU.

Domaine: Bases de la programmation (trace de pseudo-code)

S'entraîner : questions sur Tableau

Dans un cache à correspondance directe, les éléments de deux tableaux correspondent au même emplacement du cache et s’évincent mutuellement à chaque accès alterné. Dans quelle catégorie se classe ce défaut ?

  1. ADéfaut obligatoire
  2. BDéfaut de capacité
  3. CDéfaut de conflit
Afficher la réponse et l'explication

Réponse : C. Défaut de conflit

Lorsque le cache dans son ensemble dispose de place mais que deux données se disputent le même ensemble et s’évincent mutuellement, il s’agit d’un défaut de conflit. On le réduit en augmentant l’associativité pour loger au moins deux données dans le même ensemble, ou en décalant le début d’un tableau pour qu’il corresponde à un autre ensemble. Le défaut de capacité provient d’un ensemble de travail plus grand que le cache entier et ne diminue pas même en totalement associatif. Le défaut obligatoire survient au premier accès et ne concerne pas les accès répétés.

Lorsqu’une ligne d’un tableau à deux dimensions mesure 4096 octets (une puissance de 2), le parcours des éléments par colonne peut provoquer de nombreux défauts même si la capacité du cache est suffisante. Quelle mesure est efficace ?

  1. AAjouter un remplissage en fin de chaque ligne pour que la taille de ligne ne soit plus une puissance de 2
  2. BRemplacer le type du tableau par un autre type de même taille
  3. CRéaligner le tableau entier sur une grande frontière d’adresse en puissance de 2
Afficher la réponse et l'explication

Réponse : A. Ajouter un remplissage en fin de chaque ligne pour que la taille de ligne ne soit plus une puissance de 2

Si une ligne mesure exactement 4096 octets, les éléments parcourus par colonne sont espacés de multiples de 4096 : leurs bits d’index situés dans les 12 bits de poids faible sont identiques et ils se concentrent dans très peu d’ensembles (tous dans le même ensemble pour un cache L1 d’au plus 4 KB par voie). Dès que le nombre de lignes tombant dans un même ensemble dépasse l’associativité, des défauts de conflit apparaissent malgré une capacité suffisante. Ajouter à chaque ligne un remplissage (padding) d’environ une ligne de cache décale l’ensemble associé à chaque élément et répartit les accès. Un alignement sur une puissance de 2 ne change rien, et un type de même taille n’a aucun effet.

« Tableau » dans les explications

Questions mentionnant « Tableau » (74)

  1. a0 contient l'adresse de début d'un tableau a de type int (4 octets), et a1 l'indice i. Que charge le code ci-dessus dans a2 ?
  2. Parcourir le tableau à deux dimensions a[i][j] du langage C avec j dans la boucle interne, comme ci-dessus, est généralement plus rapide qu’avec i dans la boucle interne. Pour quelle raison ?
  3. Dans un cache à correspondance directe, les éléments de deux tableaux correspondent au même emplacement du cache et s’évincent mutuellement à chaque accès alterné. Dans quelle catégorie se classe ce défaut ?
  4. Dans la boucle ci-dessus, avec un int de 4 octets, des lignes de cache de 64 octets et un tableau absent du cache aligné sur une frontière de ligne, quel est le taux de défauts de la lecture du tableau en l’absence de préchargement ?
  5. Pourquoi le traitement ci-dessus, qui additionne uniquement les coordonnées x, devient-il généralement plus rapide une fois réécrit sous forme de structure de tableaux (chaque composante dans un tableau séparé) ?
  6. Lorsqu’une ligne d’un tableau à deux dimensions mesure 4096 octets (une puissance de 2), le parcours des éléments par colonne peut provoquer de nombreux défauts même si la capacité du cache est suffisante. Quelle mesure est efficace ?
  7. Pourquoi le parcours de la liste chaînée ci-dessus est-il généralement bien plus lent que la lecture séquentielle d’un tableau comportant le même nombre d’éléments ?
  8. Un faux partage se produit dans un tableau de compteurs par thread déclaré « long cnt[8]; ». Quelle est la mesure la plus appropriée ?
  9. Pour calculer avec plusieurs threads la somme de tous les éléments d’un tableau, quelle méthode convient du point de vue des performances ?
  10. On veut traiter un tableau de 1000 éléments à raison d'un élément par thread, avec 256 threads par bloc. Combien de blocs faut-il lancer ?
  11. Avec i l'indice de chaque thread, lire le tableau tous les 32 éléments comme ci-dessus est plus lent que lire a[i]. Quelle en est la raison principale ?
  12. Un tableau de 32×32 float est placé en mémoire partagée ; sa lecture par colonne (verticalement) par les 32 threads d'un warp provoque des conflits de banc. Quelle contre-mesure est couramment utilisée ?
  13. Envoyer des données au GPU pour un traitement léger, comme une seule addition par élément d'un tableau, peut être plus lent qu'un calcul sur CPU. Quelle en est la raison principale ?
  14. Lors de l'addition élément par élément de deux grands tableaux sur GPU (c[i] = a[i] + b[i]), qu'est-ce qui détermine principalement les performances ?
  15. Sur GPU, on veut extraire d'un tableau les seuls éléments satisfaisant une condition et les écrire de façon compacte dans un autre tableau (chaque thread produit 0 ou 1 sortie). Quel calcul parallèle est couramment utilisé pour déterminer l'adresse d'écriture de chaque thread ?

Termes associés

Variable Pointeur GPU Ligne de cache Liste chaînée (linked list) Pile (stack) Préchargement (prefetch) struct (structure C) SIMD Complexité temporelle (notation grand O)

Retour au glossaire