Waarom wordt bij het berekenen van de som van veel waarden op een GPU een reductie in boomvorm gebruikt (herhaaldelijk naburige waarden optellen en zo halveren)?

Antwoord: B. Omdat in elke stap veel threads tegelijk kunnen optellen en n waarden in log2 n stappen kunnen worden gesommeerd

Als één thread achter elkaar optelt, zijn n-1 stappen nodig, maar in boomvorm tellen in stap 1 n/2 threads naburige waarden op, in stap 2 n/4 threads, enzovoort, en is het klaar na log2 n stappen. Het totale aantal optellingen verandert niet, maar door het kleine aantal stappen verloopt de parallelle berekening snel. Binnen een block worden de stappen met shared memory uitgevoerd, en de resultaten per block worden ten slotte samengevoegd.