On the parallel decomposability of geometric problems

ABSTRACT

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 &Ogr;(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.

REFERENCES

• 1: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 2: M. J. Atallah , G. N. Frederickson , S. R. Kosaraju, Sorting with efficient use of special-purpose sorters, Information Processing Letters, v.27 n.1, p.13-15, February 1988 [doi>10.1016/0020-0190(88)90075-0]
• 3: R. Beige1 and J. Gill, Sorting tt Objects with a k-sorter, TRCS, The Johns Hopkins University, Apr. 1987.
• 4: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• 5: B. Chazelle, Computational Geometry on a Systolic Chip, IEEE Trans. on Computers, pp. 774- 785, Sept. 1984.
• 6: G.N. Frederickson and D.B. Johnson, The Complexity of Selection and Ranking in X + Y and Matrices with Sorted Columns, JCSS, pp. 197- 208, 1982.
• 7: Michael Truman Goodrich , Mikhail J. Atallah, Efficient parallel techniques for computational geometry, 1987
• 8: R.H. Giiting, Optimal Divide-and-Conquer to Compute Measure and Contour for a Set of Iso- Rectangles, Acta Informatica, pp. 271-291, 1984.
• 9: C. S. Jeong and D. T. Lee, Parallel Geometric Algorithms on a Mesh Connected Computer, TR, 87-0%FC-01, Dept. EE/CS, Northwestern Univ., 1987. To appear in Algorithmica.
• 10: S. Rao Kosaraju , Mikhail J. Atallah, Optimal simulations between mesh-connected arrays of processors, Journal of the ACM (JACM), v.35 n.3, p.635-650, July 1988 [doi>10.1145/44483.44494]
• 11: D.T. Lee and H. Chang and C.K. Wong, An onchip compare steer bubble sorter, IEEE Trans. Computers, pp. 396-405, 1981.
• 12: D.T. Lee and F.P. Preparata, Computational Geometry-A Survey, IEEE Trans. on Computers, pp. 872-1101, 1984.
• 13: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 14: R. Miller and Q. F. Stout, Mesh Computer Algorithms for Computational Geometry, TR 86-18, Dept. of CS, SUNY at Buffalo, 1986.
• 15: Heinrich Müller, Sorting numbers using limited systolic coprocessors, Information Processing Letters, v.24 n.6, p.351-354, 6 April 1987 [doi>10.1016/0020-0190(87)90109-8]
• 16: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 17: Zen-Cheung Shih , Gen-Huey Chen , R. C. T. Lee, Systolic algorithms to examine all pairs of elements, Communications of the ACM, v.30 n.2, p.161-167, Feb. 1987 [doi>10.1145/12527.12532]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Theory