On The Limits To Speed Up Parallel Machines By Large Hardware And Unbounded Communication
Friedhelm Meyer auf der Heide, Rüdiger Reischuk · 2005
Lower bounds for sequential and parallel random access machines (RAM's, WRAM's) and distributed systems of RAM's (DRAM's) are proved. We show that, when p processors instead of one are available, the computation of certain functions cannot be speeded up by a factor p but only by a factor 0 (log(p)). For DRAM's with communication graph of degree c a maximal speedup 0 (log(c)) can be achieved for these problems. We apply these results to testing the solvability of linear diophantine equations. This generalizes a lower bond of Yao for parallel computation trees. Improving results of Dobkin/Lipton and Klein/Meyer auf der Heide, we establish large lower bounds for the above problem on RAM's. Finnaly we prove that at least log (n) + 1 steps are necessary for computing the sum of n integers by a WRAM regardless of the number of processors and the solution of write conflicts.