Combien d'étapes faut-il pour sommer 1024 valeurs par une réduction en arbre ?

Réponse : A. 10

Le nombre de valeurs étant divisé par deux à chaque étape, 1024→512→256→…→1, il faut 10 divisions par deux pour arriver à 1. Le nombre d'étapes vaut donc log2 1024=10. Le nombre total d'additions, 512+256+…+1=1023, est le même qu'avec un seul thread additionnant séquentiellement, mais avec seulement 10 étapes, le calcul est très rapide si les threads sont suffisamment nombreux.