Comment implémenter le tri Radix sur multi-GPU - de la même manière que sur un seul GPU, en divisant les données puis en construisant des histogrammes sur des GPU séparés, puis réutiliser les données de fusion (comme un paquet de cartes)?Comment implémenter le tri Radix sur multi-GPU?
Cette méthode fonctionnerait, mais je ne pense pas que ce serait l'approche la plus rapide. Spécifiquement, la fusion d'histogrammes pour chaque K bits (K = 4 est actuellement le meilleur) nécessiterait que les clés soient échangées entre les GPU 32/K = 8 fois pour trier les entiers de 32 bits. Étant donné que la bande passante mémoire entre les GPU (~ 5 Go/s) est beaucoup plus faible que la bande passante mémoire sur un GPU (~ 150 Go/s), cela va tuer les performances.
Une meilleure stratégie serait de diviser les données en plusieurs parties, de trier chaque partie en parallèle sur un GPU différent, puis de fusionner les parties une fois à la fin. Cette approche nécessite seulement un transfert inter-GPU (vs 8 ci-dessus), donc il sera considérablement plus rapide.
Malheureusement, cette question n'est pas correctement posée. Cela dépend de la taille de l'élément, où les éléments commencent leur vie en mémoire et où vous voulez que les éléments triés finissent par résider.
Parfois, il est possible de compresser la liste triée en stockant des éléments dans des groupes partageant le même préfixe commun, ou des éléments uniques à la volée, en stockant chaque élément une fois dans la liste triée avec un nombre associé. Par exemple, vous pouvez trier une énorme liste d'entiers 32 bits en 64K listes distinctes de valeurs 16 bits, réduisant de moitié vos besoins en mémoire.
Le principe général est que vous voulez réduire le plus possible le nombre de passages sur les données et que votre débit correspondra presque toujours aux contraintes de bande passante associées à votre politique de stockage.
Si votre ensemble de données dépasse la taille de la mémoire rapide, vous souhaiterez probablement terminer avec une passe de fusion plutôt que de continuer à trier la base, car une autre personne a déjà répondu. Je viens d'entrer dans l'architecture GPU et je ne comprends pas le commentaire K = 4 ci-dessus. Je n'ai jamais vu une architecture où un si petit K serait optimal.
Je pense que fusionner des histogrammes est également une mauvaise approche. Je laisserais probablement les éléments se fragmenter en mémoire plutôt que de fusionner des histogrammes. Est-ce si difficile de gérer les listes de dispersion/collecte à l'échelle méso dans le tissu GPU? J'espère bien que non. Enfin, il est difficile de concevoir une raison pour laquelle vous voudriez impliquer plusieurs GPUs pour cette tâche. Supposons que votre carte dispose de 2 Go de mémoire et de bande passante d'écriture de 60 Go/s (c'est ce que montre ma carte de milieu de gamme). Un tri radix à trois passes (histogrammes 11 bits) nécessite 6 Go de bande passante d'écriture (probablement votre facteur de limitation de débit) ou environ 100 ms pour trier une liste de 2 Go d'entiers 32 bits. Super, ils sont triés, maintenant quoi? Si vous devez les expédier ailleurs sans prétraitement ni compression, le temps de tri sera petit.
Dans tous les cas, juste compilé mes premiers exemples de programmes aujourd'hui. Il y a encore beaucoup à apprendre. Mon application cible est la permutation intensive, qui est étroitement liée au tri. Je suis sûr que je vais revenir sur ce sujet à l'avenir.
Ce type de fusion externe n'est-il pas disponible? –