Revisiting parallel speedup complexity
Selim G. Akl, Michel Cosnard, A. Ferreira · 2003
Two 'folk theorems' that permeate the parallel computation literature are reconsidered in this paper. The first of these, known as the speedup theorem, states that the maximum speedup a sequential computation can undergo when p processors are used is p. The second theorem, known as Brent's Theorem, states that a computation requiring one step and n processors can be executed by p processors in at most (n/p) steps. The authors exhibit for each theorem a problem to which the theorem does not apply. Their approach is purely theoretical and uses only abstract models of computation, namely the RAM and PRAM. Practical issues pertaining to the applicability of their results to specific existing computers, whether sequential or parallel, are not addressed.>