On the parallel decomposability of geometric problems
Mikhail J. Atallah, J.-J. Tsay · 1989
There is a large and growing body of literature concerning the solution of geometric problems on mesh-connected arrays of processors [5,9,14,17]. Most of these algorithms are optimal (i.e., run in time Ο(n1/d) on a d-dimensional n-processor array), and they all assume that the parallel machine is trying to solve a problem of size n on an n-processor array. What happens when we have parallel machine for efficiently solving a problem of size p, and we are interested in using it to solve a problem of size n < p? The answer to that question has to do with a fundamental, and yet (at least so far) little-studied property of geometric problems: their parallel-decomposability. More specifically, given that a problem of size p can be solved on a parallel machine P faster by a factor of (say) s(p) than on a RAM alone, then that problem is fully parallel-decomposable for P if a RAM to which the parallel machine P is attached can solve arbitrarily large problems with a speedup of also s(p) when compared to a RAM alone. The issue has been settled for the sorting problem when P is a linear systolic array [1,2,3,11]. Here we show that many geometric problems are fully parallel-decomposable for (multidimensional) mesh-connected arrays of processors.