(c'est une question pour un rappor de tp, y'a pas de code a écrire, juste des idées)
 
je travaille avec des arbres binaires presque parfaits ( comme ca on travaille sur des tableaux)
 
 
 
 

arbre applati dans 1 tableau)
 
je construis mon tas en parcourant les noeuds linéairement en partant du bas, de droite a gauche (dans le cas ou la racine serait en haut)  et en rétablissant l'arbre a chaque fois ( c'est a dire que l'on a tjrs un arbre en dessous du noeud, et pas encore forcément au dessus)
 

(ordre de parcours de l'arbre, qui est en fait applati dans un tableau)
 
la ca me fait mon arbre presque parfait, puis je peux trier en prenant mon plus grand élément et en rétablissant l'arbre
 
bref juste la rien de nouvo
 
mais...
 
dans le cas d'une machine multiprocesseur, quel serait le meilleur moyen de paralleliser le tri et avec combien de procs ?
 
moi je pense "simplement" que l'on peut y gagner dans la construction initiale de l'arbre binaire presque parfait = tas  
donc fatalement donnant pour un noeud chacune des deux branches à un processeur  
 
donc soit on est pauvre et on parallelise uniquement les deux fils de la racine avec 2 procs
 
soit on est mégalo et on parallelise toute la derniere rangée de noeuds soit a peu pres log(2) N processeurs, si N est la taille de l'arbre / tableau a trier
 
 
 
 
voila, si vous aves des idées pour completer les miennes....

bah l'idée pour rentabiliser c'est que chaque cpu soit chargé pour à peu près la même durée, donc à priori oui si l'arbre est équilibré, dans la mesure ou on a du bi proc faire faire le parcours à partir de chaque fils de la racine...
 
mais attention, pour que ce soit rentable, comme ça sa marche, mais si jamais tu prends une autre approche, il ne faut pas que les N cpu mettent à jour le tableau de manière entrelacée, sinon il va y avoir du trashing de mémoire cache...
 
admettons que ton tableau final fasse 1 mo, dans le cas d'un bi-proc et ta solution des 2 fils, chaque cpu à peu près mettre à jour 512 ko.
 
mais si tu prends une autre approche et que chaque cpu tape dans une zone en mémoire cache de l'autre, tu seras plus lent qu'en mono-cpu.

en fait la je me disais : on peut essayer de touver un compromis avevc plsu de 2 cpus, mais a chaque fois  on ne pourrait avoir tous les cpus qui tournent en même temps, 2 c le minimum, utilisé a 100%, mais on "pourrait" faire avec 16 procos, sachant que lorsque l'on travaille sur des noeuds supérieure a la couche 4 (16=2^4) et bien on aurait des cpus qui feraient dodo

On peut aussi répondre à la demande, en créant un pool de n threads où n correspond au nombre de tes processeurs.
 
Chacun de ces threads écoute le thread principal qui va leur donner des ordres (trie, ceci, trie cela). Lorsqu'ils ont fini, ils informent le thread principal de leur inactivité, et ce dernier pourra les "réactiver" en leur affectant une nouvelle tâche.