Rechercher un shuffle efficace en SIMD
Les instructions SIMD sont des extensions des jeux d'instruction standard, qui effectuent la même opération sur des registres de plusieurs mots. Il s'agit d'un moyen de paralléliser les programmes à bas-niveau. Parmi les instructions SIMD, certaines servent à décaler les mots au sein d'un registre, ou à mélanger des mots venant de deux registres différents. Ces instructions sont dites de "shuffle".Parmi les utilisations du shuffle, un motif fréquemment utilisé en SIMD consiste à prendre le mot le plus à gauche d'un registre, et de le concaténer avec les mots les plus à droite d'un autre registre, comme montré sur la figure ci-dessous.
Un collègue spécialiste du SIMD m'a posé le défi de trouver le nombre minimum d'instructions pour réaliser ce motif avec le jeu d'instructions AVX (spécifié ici). L'approche que j'ai choisi d'adopter est une approche énumérative.
Je suis passé par un certain nombre d'étapes avant d'arriver à la dernière solution, qui minimise le temps de calcul et l'utilisation de la mémoire. Je vais essayer de décrire ici les différentes étapes.
L'idée de base est de représenter un mot par une valeur, qui sera unique car on ne considère pas d'opération arithmétique ou logique. Ainsi, initialement, on considère que le premier registre de 8 mots contient les valeurs 0 à 7, et le deuxième registre les valeurs 8 à 15. On peut déjà noter qu'il y a au maximum 168 = 232 valeurs possibles pour le registre résultat. La structure de donnée stockant les résultats atteignables parait naturellement être un arbre, dans lequel chaque profondeur de l'arbre correspond à l'index du mot du résultat. Chaque noeud contient un tableau de pointeurs vers les noeuds fils, indexé par la valeur du noeud fils. Ainsi, sur des registres de 4 mots, la valeur du résultat [ 2, 0, 3, 2 ] est stockée par un noeud dans l'arbre atteint en prenant successivement les pointeurs aux indexes 2, 0, 3 et 2 des noeuds rencontrés (voir figure ci-dessous).
En plus de cela, il faut stocker la manière dont ce résultat a été atteint, ce qui est fait dans les noeuds feuilles en gardant des pointeurs vers les noeuds opérandes, l'instruction utilisée ainsi que le potentiel immédiat de l'instruction.
Le premier algorithme auquel j'ai pensé est le suivant :
Current = [ src0, src1 ] (liste)
Processed = { } (set)
Results = { src0, src1 } (set)
while (!Current.empty()):
c = Current.head()
for each instruction [single op] and each immediate imm:
g = inst(c, imm)
if (g ∉ Results):
Results.add(g)
for each p in processed:
for each instruction [double op] and each immediate imm:
g = inst(c, p, imm)
if (g ∉ Results):
Results.add(g)
Current.add(g) # add to tail
Current.pop()
Processed.add(c)
Processed = { } (set)
Results = { src0, src1 } (set)
while (!Current.empty()):
c = Current.head()
for each instruction [single op] and each immediate imm:
g = inst(c, imm)
if (g ∉ Results):
Results.add(g)
for each p in processed:
for each instruction [double op] and each immediate imm:
g = inst(c, p, imm)
if (g ∉ Results):
Results.add(g)
Current.add(g) # add to tail
Current.pop()
Processed.add(c)
Le problème de cet algorithme est que les résultats ne sont pas stockés en fonction de leur ordre, c'est-à-dire du nombre d'instructions nécessaires pour les obtenir. Si l'ordre est stocké dans une feuille (et calculé à partir de l'ordre des parents), il n'est pas facile de faire la mise à jour des noeuds pour lesquels le noeud courant intervient comme opérande. En effet, lors du parcourt de l'ensemble Processed, les noeuds ne sont pas parcourus par ordre croissant, et il est donc possible d'obtenir un même résultat d'un ordre inférieur plus tard dans le temps. L'autre problème que cela pose est qu'il est plus difficile de déterminer une condition d'arrêt garantissant un résultat optimal, c'est-à-dire un moment à partir duquel on est sûrs que l'on ne peut plus produire de résultat d'un ordre inférieur à un ordre donné.
Une autre idée, survenue après discussion avec un collègue, consiste donc à stocker les valeurs à traiter en fonction de leur ordre, dans une liste (il y a donc une liste par ordre). Un arbre est gardé pour tester rapidement si un résultat a déjà été obtenu, ainsi que stocker sa construction. Le but est donc de parcourir les listes contenant les valeurs à traiter de manière à produire tous les résultats d'un ordre donné en une seule fois. L'algorithme devient le suivant :
order[0] = [ src0, src1 ] (liste)
Results = { src0, src1 } (set)
target_order = 1
while (target_order < MAX_ORDER):
for elem in order[target_order - 1]:
for each instruction [single op] and each immediate imm:
g = inst(c, imm)
if (g ∉ Results):
Results.add(g)
order[target_order].add(g)
for all combinations (i, j) with i < j such that i + j == target_order - 1:
for each elem0 in order[i]:
for each elem1 in order[j]:
for each instruction [double op] and each immediate imm:
g = inst(c, p, imm)
if (g ∉ Results):
Results.add(g)
order[target_order].add(g) # add to tail
if Results.contains(target):
print target stack
target_order += 1
Results = { src0, src1 } (set)
target_order = 1
while (target_order < MAX_ORDER):
for elem in order[target_order - 1]:
for each instruction [single op] and each immediate imm:
g = inst(c, imm)
if (g ∉ Results):
Results.add(g)
order[target_order].add(g)
for all combinations (i, j) with i < j such that i + j == target_order - 1:
for each elem0 in order[i]:
for each elem1 in order[j]:
for each instruction [double op] and each immediate imm:
g = inst(c, p, imm)
if (g ∉ Results):
Results.add(g)
order[target_order].add(g) # add to tail
if Results.contains(target):
print target stack
target_order += 1
D'autres optimisation ont ensuite successivement été apportées :
- La suppression des champs val, index et order dans les noeuds pour réduire l'empreinte mémoire:
- La valeur de index peut être retrouvé avec un paramètre en plus dans les fonctions.
- Le champ val n'est utile que pour passer d'un noeud au suivant ou pour retrouver la valeur correspondant à un noeud donné ; dans chacun de ces cas, val évite d'avoir à parcourir le tableau de pointeurs du noeud parent pour comparer ses éléments avec lui-même. Or, dans cet algorithme, il n'y a pas de parcours de l'arbre, et retrouver la valeur correspondant à un noeud n'est fait que dans l'affichage du résultat.
- Le champ order n'est plus utile dans cet algorithme.
- L'utilisation de tableaux plutôt que de listes, puisque qu'il n'y a pas d'insertion ni de suppression en tête. Les tableaux sont redimensionnés à cout amorti constant.
- Le "packing" des valeurs codées dans le tableau pour utiliser tous les bits (8 valeurs par mot).
- L'utilisation de noeuds différents pour les feuilles pour ne pas payer inutilement le cout mémoire des champs propres à chaque type de noeud (tableau de pointeurs pour les noeuds intermédiaires ; fonction, opérandes parents et immédiat pour les noeuds feuille).
Le code final se trouve ici.