J'ai réussi à mettre au point une implémentation d'un histogramme à utiliser dans un environnement basé sur CUDA. Ce que j'ai de la difficulté à comprendre, c'est ce que serait la complexité du travail de l'algorithme.Complexité de la mise en œuvre parallèle de l'histogramme
Je peux dire que la complexité d'implémentation en série serait linéaire - O (n) où n = nombre d'entrées basé sur le fait que nous devons faire une boucle sur toutes les entrées au moins une fois.
La mise en oeuvre serait:
diviser les mesures en groupes
passer chaque groupe de mesures à un fil séparé
Compute Un histogramme local dans chaque fil
Réduit-les à un histogramme global
Aurais-je à travailler sur la complexité de chaque étape et fusionner?
Votre histogramme est-il lié par calcul ou lié à l'E/S? (en général, c'est le dernier) ... À moins d'avoir une bande passante d'E/S supérieure à celle d'un seul noyau, vous pouvez obtenir des performances décentes sur un seul cœur en utilisant simplement SIMD. Il n'est pas rare d'avoir un IO de moins de 1600 Mo/seconde dans les E/S brutes, et d'ajouter l'histogramme à environ 900 Mo/seconde. Le transfert de données vers le GPU est généralement le goulot d'étranglement sur un GPU, et dans ce cas, les opérations sont minimes, donc cela peut être un cas sous-optimal pour sélectionner un GPU. – Holmz