Data-movement-intensive Problems

Résumé du livre

Abstract: "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. We show that these two theorems are not true in general. Specifically, we exhibit for each theorem a problem to which the theorem does not apply.