Fractal MultiThread

De Wiki LOGre
Aller à : navigation, rechercher


Principe

Le but de ce projet est d effectuer un calcul de fractal en multithead afin d utiliser l API de gestion de thread introduites avec le standard C++11 et observer comment la repartition des calculs entre threads impacte les performances.

Technos utilisées


Code source

Application

L'appli calcule l'de Mandelbrot de maniere multithreadee
Par default l appli utilise l API C++ pour déterminer le nombre de thread a instancier

std::thread::hardware_concurrency()

parametres

  • --width : largeur de l image a calculer
  • --height : hauteur de l image a calculer
  • --nb : nombre de threads
  • --type : type de repartition entre threads
  • --slot-size : taille d un slot de calcul pour les threads de type shared
Usage is :
        fractal.exe [OPTIONS]
OPTIONS : --<parameter_name>=<parameter_value>
        --height=...
        --nb=...
        --slot-size=...
        --type=...
        --width=...

Repartition entre thread

J ai defini trois types :

  • horizontal : chaque thread va calculer les lignes de l image pour lesquelles numero_de_ligne modulo nombre_de_threads == thread_id
  • h_block : chaque thread va calculer les lignes de l image pour lesquelles thread_id * (height / nb_thread) <= numero_de_ligne <= (thread_id + 1) * (height / nb_thread)
  • Shared : les threads se disputent un index representant un pixel de coordonnes ( index % width, index / width) . Lorsqu un thread obtient l index il va l incrementer de la taille de slot,le remettre a dispo des autres threads et calculer tous les pixels du slot. L acces a l index se fait via des operations lockless de type compare_exchamge_strong fournie par les types std:;atomic

Les images suivantes representent la repartition entre threads avec la couleur du pixel indiquant quel thread l a calcule.

Résultats obtenus

Threads de type horizontal

Chaque thread travaille exactement sur la meme quantite de pixel que les autres threads.
Certains pixels demandent plus de calculs que d autres mais cette manière de repartir les lignes de pixel entre les threads permet quand même d avoir une assez bonne répartition des itérations comme le montrent les statistiques calculées par l application:

horizontal[0] : 163840 pixels and 21584025 iterations representing 12.5% in 2.63s
horizontal[1] : 163840 pixels and 21587069 iterations representing 12.5% in 2.68s
horizontal[2] : 163840 pixels and 21604929 iterations representing 12.5% in 2.96s
horizontal[3] : 163840 pixels and 21602285 iterations representing 12.5% in 2.9s
horizontal[4] : 163840 pixels and 21602285 iterations representing 12.5% in 2.74s
horizontal[5] : 163840 pixels and 21604929 iterations representing 12.5% in 3.12s
horizontal[6] : 163840 pixels and 21587069 iterations representing 12.5% in 2.76s
horizontal[7] : 163840 pixels and 21584025 iterations representing 12.5% in 3.09s

On note cependant un certain déséquilibre entre les temps d exécution des différents threads

Threads de type h_block

Chaque thread travaille exactement sur la meme quantite de pixel que les autres threads.
Certains pixels demandent plus de calculs que d autres et cette manière de repartir les lignes de pixel entre les threads est clairement avantageuse pour les threads calculant les lignes eloignes du centre de l image et desavantageuse pour les threads calculant les lignes au centre de l'image
Cela s observe tres clairement dans le nombre d iterations prises en charge par chaque thread:

h_block[0] : 163840 pixels and 2463014 iterations representing 1.43% in 0.368s
h_block[1] : 163840 pixels and 13307499 iterations representing  7.7% in 1.85s
h_block[2] : 163840 pixels and 28085659 iterations representing 16.3% in 3.24s
h_block[3] : 163840 pixels and 42522136 iterations representing 24.6% in 4.89s
h_block[4] : 163840 pixels and 42522136 iterations representing 24.6% in 4.95s
h_block[5] : 163840 pixels and 28085659 iterations representing 16.3% in 3.57s
h_block[6] : 163840 pixels and 13307499 iterations representing  7.7% in 1.81s
h_block[7] : 163840 pixels and 2463014 iterations representing 1.43% in 0.543s

et se reflète logiquement dans les temps d exécution des threads: le plus lent met quasiment 5 fois plus de temps a s exécuter que le plus rapide

Threads de type shared

Le fait de partager l index entre les threads permet de ne pas se poser la question de la répartition des taches entre threads
En effet des qu un thread a exécuté les calcules nécessaires au traitement de son slot il retourne piocher un autre slot dans l index partage
Les threads devraient donc se repartir equitablement la tache et s arreter lorsqu il n y plus de slots disponibles
C est ce que l on observe dans les statistiques ( slot de taille 1 ci dessous) ou l on voit que le nombre d iteration est reparti plutot equitablement et que les temps d executions de chaque thread sont identiques:

shared[0] : 159293 pixels and 21734795 iterations representing 12.6% in 2.8s and 138537 compare exchange_fails for 159293 slots ie 87%
shared[1] : 170059 pixels and 21064122 iterations representing 12.2% in 2.8s and 109521 compare exchange_fails for 170059 slots ie 64.4%
shared[2] : 168221 pixels and 22720654 iterations representing 13.2% in 2.8s and 144829 compare exchange_fails for 168221 slots ie 86.1%
shared[3] : 184001 pixels and 23009697 iterations representing 13.3% in 2.8s and 117624 compare exchange_fails for 184001 slots ie 63.9%
shared[4] : 163287 pixels and 22501099 iterations representing   13% in 2.8s and 141098 compare exchange_fails for 163287 slots ie 86.4%
shared[5] : 140855 pixels and 20520503 iterations representing 11.9% in 2.8s and 122732 compare exchange_fails for 140855 slots ie 87.1%
shared[6] : 153843 pixels and 19643361 iterations representing 11.4% in 2.8s and 100982 compare exchange_fails for 153843 slots ie 65.6%
shared[7] : 171161 pixels and 21562385 iterations representing 12.5% in 2.8s and 110908 compare exchange_fails for 171162 slots ie 64.8%

Avec un slot de petite taille on voit cependant que les opérations atomiques ont un nombre d échec non négligeable meme si il est peu perceptible sur les performances etant donne qu il n y a pas de cout d acquisitions en comparaison d un mutex et qu il s agit d opérations atomiques.
En augmentant la taille du slot on voit que le nombre d échec diminue nettement ce qui améliore les performances tout en conservant une bonne répartition du temps d exécution sur les threads
En revanche on voit un certain déséquilibre sur le nombre de pixels traites ( logique étant donne que certains pixels sont plus couteux que d autres) et le nombre d itérations par thread. Statistiques pour un slot de taille 100 :

shared[0] : 184300 pixels and 23155402 iterations representing 13.4% in 2.7s and 2 compare exchange_fails for 1843 slots ie 0.109%
shared[1] : 151200 pixels and 20477570 iterations representing 11.9% in 2.7s and 1 compare exchange_fails for 1512 slots ie 0.0661%
shared[2] : 169300 pixels and 22567794 iterations representing 13.1% in 2.7s and 3 compare exchange_fails for 1693 slots ie 0.177%
shared[3] : 168200 pixels and 22025636 iterations representing 12.7% in 2.7s and 1 compare exchange_fails for 1682 slots ie 0.0595%
shared[4] : 164220 pixels and 22402198 iterations representing   13% in 2.7s and 3 compare exchange_fails for 1643 slots ie 0.183%
shared[5] : 162100 pixels and 21738892 iterations representing 12.6% in 2.7s and 2 compare exchange_fails for 1621 slots ie 0.123%
shared[6] : 150400 pixels and 19328125 iterations representing 11.2% in 2.7s and 3 compare exchange_fails for 1504 slots ie 0.199%
shared[7] : 161000 pixels and 21060999 iterations representing 12.2% in 2.7s and 3 compare exchange_fails for 1610 slots ie 0.186%

A partir d une certain taille de slot on voit que des dispartites apparaissent dans les temps d executions car certains threads n ont plus de slots a traiter tandis que d autres n ont pas termine de traiter leur slot
Par exemple avec un slot de taille 100000:

shared[0] : 184300 pixels and 23155402 iterations representing 13.4% in 2.7s and 2 compare exchange_fails for 1843 slots ie 0.109%
shared[1] : 151200 pixels and 20477570 iterations representing 11.9% in 2.7s and 1 compare exchange_fails for 1512 slots ie 0.0661%
shared[2] : 169300 pixels and 22567794 iterations representing 13.1% in 2.7s and 3 compare exchange_fails for 1693 slots ie 0.177%
shared[3] : 168200 pixels and 22025636 iterations representing 12.7% in 2.7s and 1 compare exchange_fails for 1682 slots ie 0.0595%
shared[4] : 164220 pixels and 22402198 iterations representing   13% in 2.7s and 3 compare exchange_fails for 1643 slots ie 0.183%
shared[5] : 162100 pixels and 21738892 iterations representing 12.6% in 2.7s and 2 compare exchange_fails for 1621 slots ie 0.123%
shared[6] : 150400 pixels and 19328125 iterations representing 11.2% in 2.7s and 3 compare exchange_fails for 1504 slots ie 0.199%
shared[7] : 161000 pixels and 21060999 iterations representing 12.2% in 2.7s and 3 compare exchange_fails for 1610 slots ie 0.186%

Conclusion

Les algorithmes lockless sont vraiment tres interessants en terme de performance et de repartition de tache entre thread mais demande neamoins de choisir une taille de slot suffisant pour minimiser les collisions lors des operations atomiques
L'API des threads de C++11 simplifie nettement le code de gestion des threads par rapport a l API Posix