Introduction aux "Ranges" des TBB

Bonjour à tous,

Je vais vous présenter une fonctionnalité de la bibliothèque TBB que j'ai eu l'occasion de découvrir durant le concours Acceler8.
Pour rappel, TBB qui est l'acronyme de "Threading Building Blocks" est une bibliothèque développée par Intel qui vise à faciliter le parallélisme.

Rappel sur les TBB



L'une des fonctionnalités très appréciée est le parallel_for, et ses dérivées tels que le parallel_reduce.
Ils permettent de paralléliser une boucle très facilement, voici un exemple de code qui parallélise une fonction d'affichage simple, qui pourrait être remplacée par un traitement long et coûteux.

Ainsi le code suivant affiche les entiers de 1 à 41 :
Code source brut.
Code source avec coloration syntaxique.

Peut être parallélisé ainsi :
Code source brut.
Code source avec coloration syntaxique.

L'ordre d'affichage est parallélisé, et donc, les nombres ne sont pas dans l'ordre.

Le "range" utilisé ici est le "tbb::blocked_range", qui permet de reproduire les itérations de la boucle. Il suffit de spécifier le "range" et la classe qui effectue le travail, le parallel_for fait tout le reste du travail. La simplicité d'écriture est vite perçue.

Enfin, il est important de noter que le type du range se retrouve dans la méthode de la classe qui surcharge l'opérateur ().

Rendre notre classe Compute plus modulaire



Avant d'aller plus, modifions notre classe Compute pour lui faire accepter un "range" de type différent plus facilement. Pour cela, rien de plus simple, il suffit de templater la classe, ce qui nous donne :
Code source brut.
Code source avec coloration syntaxique.

Avec ce template, il nous suffira de modifier les 2 lignes du main pour changer de "range".

L'utilité des ranges



Mais finalement, quelle est l'utilité des ranges ?
C'est simple, ils servent à découper votre problème en sous-problèmes, et permettent après découpage, de lancer les threads sur ces sous-problèmes.

Dans notre cas, nous voulons paralléliser une boucle, et le "tbb::blocked_range" est la méthode parfaite pour faire cela, il découpe l'intervalle demandé (de 1 à 42) en deux, et cela récursivement tant que jugé utile.

Bien sûr, pour des problèmes plus complexes, pour des problèmes entraînant des appels récursifs par exemple, vous ne pourrez pas utiliser bêtement le parallel_for, et il vous faudra chercher du côté de "ranges" ou des "tasks". Nous n'aborderons pas ici les tasks néanmoins.

Les méthodes à implémenter pour faire une classe "range"



En parcourant la documentation, on s'aperçoit que notre classe "range" n'a pas besoin d'hériter d'une classe abstraite, mais doit implémenter certaines méthodes :

    • Un constructeur par copie : R( const R& )

    • Un constructeur qui découpe le problème en deux : R( R& r, split )

    • Un destructeur : ~R()

    • Une méthode qui spécifie si on peut découper le "range" en deux : is_divisible

    • Une méthode qui spécifie si le "range" courant est vide ou non : empty



Définir son propre range



Ce qui nous donne le code suivant dans notre cas :
Code source brut.
Code source avec coloration syntaxique.

Les méthodes très importantes sont :

    • empty : permet de ne pas lancer de calcul sur une morceau vide du problème (après découpage, cela peut arriver).

    • is_divisible : cela permet de donner une taille minimale à un problème, et de s'assurer qu'il sera effectué par un seul thread. Cela évite le surcoût du lancement de trop de threads. Le paramètre "grain_size" est ainsi utilisé pour limiter s'assurer que le problème envoyé à un thread fait au minium 5 lignes (car pour 11 lignes, on découpe en 5 et 6 lignes).

    • do_split : qui est introduite dans le code mais n'est pas nécessaire, et qui se charge d'effectuer le découpage du problème en deux sous problèmes. C'est là que toute l'intelligence du découpage doit se faire.




Et en intégrant notre "range" personnalisé à notre code précédent cela donne :
Code source brut.
Code source avec coloration syntaxique.

Vous noterez que la liste d'initialisation du constructeur définit end avant begin, ce qui est impératif à cause du constructeur qui découpe un problème, et de la fonction "do_split", qui modifie "r.end_".

Remarques sur les performances



Le découpage en sous-problèmes peut être appelé un nombre conséquent de fois, il est donc important que la fonction de découpage ne soit pas trop longue à s'exécuter.
Pour l'anecdote, sur le concours Acceler8, en voulant découper un problème très équitablement, j'ai utilisé la fonction de calcul de racine carré (sqrt), qui a eu pour conséquence d’augmenter drastiquement le temps de calcul. Ce que je gagnais en répartissant plus équitablement le travail sur les cœurs de la machine, je le perdais en calcul de racine carré. Attention donc à ne pas vous faire avoir.

Conclusion



Vous avez vu ici un petit aperçu des "ranges" personnalisés, à vous d'adapter le code à vos besoin : ajouter des paramètres au constructeur, ainsi que découper intelligemment et efficacement.

Sources :



Para obter informações mais completas sobre otimizações do compilador, consulte nosso aviso de otimização.