Devrais-je utiliser le filetage et la récursion ensemble?

Question

Je bricole des arbres BSP depuis un moment et je joue également avec des threads. Lors de l'ajout d'un triangle à une arborescence BSP, il est possible de créer un nouveau thread pour le traitement parallèle des données.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    insert(frontpiece, bspnode.front)
    insert(backpiece, bspnode.back)
  }
  ....
}

Les deux opérations d'insertion ci-dessus peuvent être exécutées par deux threads et, comme elles ne modifient pas les mêmes données, une synchronisation peu coûteuse peut être utilisée.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    handle = beginthread(insert(backpiece, bspnode.front))
    insert(frontpiece, bspnode.back)
    if(handle)
    {
      waitforthread(handle)
    }
    else
    {
      insert(backpiece, bspnode.front)
    }
  }
  ....
}

Cette nouvelle méthode tente de créer un thread pour terminer l'opération en parallèle, mais ne devrait pas échouer si le thread ne peut pas être créé (elle reviendra simplement à l'algorithme d'origine).

S'agit-il d'une bonne pratique de programmation ou j'utilise les threads de manière incorrecte? Je n'ai pas pu trouver de littérature sur cette technique. J'aime le fait qu'il utilise mon processeur au maximum (2 cœurs) et qu'il soit théoriquement adapté à un nombre quelconque de processeurs disponibles. Je n'aime pas que cela puisse être terriblement inutile en termes de processeur et de mémoire.

Answer 1

Les threads sont parfaits si une partie du traitement attend quelque chose d'extérieur (entrée utilisateur, E / S, autre traitement) - le thread en attente peut continuer d'attendre, alors qu'un thread qui n'attend pas se met en avance .

Toutefois, pour les tâches gourmandes en temps de traitement, plus de threads que de processeurs créent réellement une surcharge. Il semble que vos threads effectuent tout le "travail sur le processeur", alors je m'en tiens à un thread par cœur - testez pour trouver le nombre optimal, cependant.

La surcharge la plus importante créée provient du changement de contexte (geler un thread et charger le contexte d'exécution du suivant), ainsi que des erreurs de cache lorsque les threads effectuent des tâches avec une mémoire différente (si votre thread peut utiliser efficacement le cache du processeur) .

Answer 2

votre meilleur choix serait de créer un pool de threads, puis de l'utiliser "de manière transparente" pour ajouter des nœuds.

Par exemple, créez 2 threads au démarrage du programme, faites-les attendre sur un sémaphore ou un événement. Lorsque vous avez des nœuds à ajouter, vous insérez les données dans une file d'attente, puis vous déclenchez le sémaphore. Cela réveille l'un des threads qui extrait les données de la file d'attente et effectue le traitement. (assurez-vous que l'accès à la file d'attente est threadsafe - la meilleure synchronisation avec une section critique est préférable).

Les performances globales de votre application sont plus lentes car vous avez plus de temps, copiez des données dans la file d'attente et exécutez des threads supplémentaires, mais si vous utilisiez un seul cœur, vous exécuterez désormais le processus 2. Cela fonctionne mieux si le traitement par thread est coûteux.

Answer 3

Bien sûr, par exemple, Quicksort peut être programmé multithread très facilement et permet d’obtenir des gains de performances importants sur les systèmes multicœurs, ainsi que de légères pertes de performances sur les systèmes non multithread. Rappelez-vous simplement que vous ajoutez deux fois plus de temps système - une fois pour la pile, sur la récursivité et une fois sur le thread, donc si vous effectuez un grand nombre de récursions, le système risque de surcharger un système plus rapidement qu'une approche non multithread.