11.3.3.1.2 : Données alignées


Lorsqu'on manipule de petits tableaux, en plus d'être contiguës, les données sur lesquelles on effectue un calcul vectoriel doivent aussi être convenablement alignées.

En effet, les registres vectoriels du processeur se comportent de manière similaire aux types scalaires (float, int,~etc.), à cette différence près qu'ils sont composés de $N$ types scalaires contigus.

Or, un processeur ne peut lire des données efficacement qu'à des adresses mémoires qui sont multiples de leur taille. Par exemple, pour un vecteur de $N$ entiers 32-bits (4 octets chacun), l'adresse mémoire du vecteur doit être multiple de $4N$ . Selon les processeurs, violer cette règle aura pour effet soit d'empêcher totalement la vectorisation, soit de la rendre moins efficace noteIl existe des instructions intrinsèques (voirsection 11.3.4.2) qui permettent d'initialiser des registres vectoriels avec des données non alignées. Cependant elles sont plus lentes que leurs équivalentes alignées et le sont pas utilisées par le compilateur lorsqu'il vectorise..

Malheureusement, les allocateurs mémoires comme malloc alignent les tableaux sur $16$ octets, ce qui convient pour des vecteurs SSE4, mais pas pour des vecteurs AVX ($32$ octets) ou AVX 512 ($64$ octets).

Dans ces conditions un autre allocateur est nécessaire : memalign (ou posix_memalign sur MacOS).

Il est également possible d'utiliser des bibliothèques comme mallocproxy[70]Automatically Replacing malloc and Other C/C++ Functions for Dynamic Memory Allocation, Intel, qui change les propriétés de la fonction malloc dynamiquement. Dans tous les cas les formats de données doivent donc s'adapter.



Pour illustrer ces problématiques d'alignement, considérons un calcul sur un tableau de $23$ éléments (voir figure 39).

Un traitement scalaire de ce tableau aurait besoin de $23$ calculs. Nous allons supposer dans la suite que la vectorisation permet $8$ calculs simultanés (AVX pour des float ou AVX 512 pour des double).

Si le tableau n'est pas aligné, deux calculs vectoriels peuvent être effectués sur des sous-ensembles alignés des données au centre du tableau. Mais les premiers et les derniers éléments du tableau, qui ne peuvent pas remplir un registre vectoriel complet du fait de leurs adresses mémoire, sont traités séparément.

Les premiers éléments du tableau sont traités un par un avec des calculs scalaires : c'est le peel. Les derniers éléments du tableau sont également traités un par un avec des calculs scalaires, car il n'y a pas assez de données pour remplir un vecteur : c'est le tail. Dans notre exemple, le peel est constitué de $4$ calculs, et le tail de $3$ . Ce qui implique un nombre de calculs total de $9$ dans le cas non-aligné.

Lorsque le tableau est aligné, il n'y a plus de peel, $2$ calculs vectorisés et $7$ calculs de tail. Ce qui revient toujours à $9$ calculs au total. Dans ces deux cas, l'accélération n'est donc que de $2,56$ alors qu'elle devrait idéalement tendre vers $8$ .



L'utilisation d'un padding noteLe padding est nommé zero-padding dans la bibliothèque MKL. consiste à ajouter des valeurs supplémentaires à l'allocation du tableau de données pour que le nombre total d'éléments soit un multiple de la taille des registres vectoriels (dans note cas : $8$ ). Les valeurs des éléments qui composent le padding dépendent du calcul à effectuer. S'il s'agit de multiplication, d'addition ou de soustraction, le padding vaudra $0$ mais s'il s'agit d'une division le padding devra valoir $1$ noteLes calculs vectorisés ne se limitent pas aux seules opérations de base, mais peuvent utiliser toute sorte de fonctions trigonométriques, exponentielles,~etc. Dans tous les cas, la valeur du padding doit être une valeur neutre pour ces calculs..

Dans notre cas, comme le tableau contient $23$ valeurs, une seule valeur de padding est nécessaire. Cette astuce permettra, au prix d'une allocation légèrement plus grande, de n'utiliser que des calculs vectorisés. Dans notre cas, $3$ instructions suffisent désormais, ce qui représente un facteur d'accélération de $7,67$ .



Certains générateurs de formats de données permettent de créer des tableaux, des matrices ou des tenseurs qui sont alignés en mémoire avec un padding si l'utilisateur le demande [69]Data format generator, Pierre Aubert.

nothing

Figure 39 : Différence d'accélération attendues en fonction de l'alignement des données utilisées et de l'utilisation d'un padding sur un tableau de $23$ éléments.