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\left(\frac{n}{p} + \log p \right).

Kategorie:Informatika