Paralelní redukce

Paralelní redukce je druh výpočetní operace na paralelních počítačích, která soubor n vstupních hodnot redukuje na jedinou výslednou hodnotu. Jedná se o způsob, jakým lze paralelně vypočítat výraz typu

$a_1*a_2*\cdots *a_n$.

Aby byl výpočet takového výrazu paralelizovatelný, musí být operace * asociativní.

Příkladem paralelní redukce je součet pole – zde je operací * sčítání, které asociativní je.

Paralelní redukce n prvků na p-procesorovém počítači má časovou náročnost $O(\frac{n}{p}+\log p)$.