返回Google圖書搜尋

Data-movement-intensive Problems

Selim G. AklMichel CosnardAfonso G. Ferreira

其他書名	Two Folk Theorems in Parallel Computation Revisited
出版	Ecole Normale Supérieure de Lyon. Laboratoire de l'Informatique du Parallélisme [LIP], 1990
URL	http://books.google.com.hk/books?id=6S-_GwAACAAJ&hl=&source=gbs_api

註釋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.