Analysis of parallel algorithms

cosmos 4th April 2017 at 11:00am
Analysis of algorithms Parallel computing

Brent's theorem

parallelizing reduce for binary/associative operators

parallelizing scan

Amdahl's law states that in parallelization, if P is the proportion of a system or program that can be made parallel, and 1-P is the proportion that remains serial, then the maximum speedup that can be achieved using N number of processors is 1/((1-P)+(P/N).