- 1.M. J. Atallah and J.-J. Ts~y. On the paralleldecomposability of geometric problems. Proc. 5th Annu.' ACM Sympos. Comput. Geom., pages 104-113, 1989. Google ScholarDigital Library
- 2.K.E. Batcher. Sorting networks and their applications. Proc. A FIPS Spring Joint Computer Co~ference, pages 307-314, 1968.Google ScholarDigital Library
- 3.J. L. Bentley. Algorithms for Klee's rectangle problems. Carnegie-Mellon Unix,., Penn., Dept. of (~Jomp. Sci. Unpublished notes, 1977.Google Scholar
- 4.D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice Hall, Englewood Cliffs, N J, 1989. Google ScholarDigital Library
- 5.R. Cypher and C. G. Plaxton. Deterministic sorting in nearly logarithmic time on the hypercube and related computers. A CM Symposium on Theory of Computing, 193-203. ACM, 1990. Google ScholarDigital Library
- 6.Grand Challenges: High Performance Computing a'nd Communications. The FY 1992 U.S. Research and Development. Program. A Report by the Committee on Physical, Mathematical, and Engineering Sciences. Federal Council for Science, Engineering, and Technology. To Supplement the U.S. President's Fiscal Year 1992 Budget.Google Scholar
- 7.R. I. Greenberg and C. E. Leiserson. Randomized Routing on Fat-trees. Advances in Computing Research, 5:345-374, 1989.Google Scholar
- 8.F. Dehne and J.-R. Sack. Translation separability of sets of polygons. The Visual Computer .3: 227-235, 1987.Google Scholar
- 9.F. Dehne and A. Fabri and A. Rau-Chaplin. Data structure decomposition./'or Coarse Grained Multicomputers. Manuscript.Google Scholar
- 10.S. Hart and M. Sharir. Nonlinearity of Davenport- Schinzel sequences and of generalized path compression schemes. Combinatorica, 6:151-177, 1986. Google ScholarDigital Library
- 11.J. Hershberger Finding the upper envelope of n line segments i'n O(nlog n) time Inf. Proc. Letters 33, 169- 174, 1989. Google ScholarDigital Library
- 12.F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan I(aufmann Publishers, San Mateo, CA, 1992. Google ScholarDigital Library
- 13.M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci. 23:166-2(.t4, 1981.Google ScholarCross Ref
- 14.F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, NY, 1985. Google ScholarDigital Library
- 15.J. H. Reif and L. G. Valiant. A logarithmic time sort for linear size networks. J. A CM, Vol.34, 1:60-76, 1987. Google ScholarDigital Library
- 16.J. van Leeuwen and D. Wood. The measure problem for rectangular ranges in d-space. J. Algorithms, 2:282-300, 1981.Google ScholarCross Ref
Index Terms
- Scalable parallel geometric algorithms for coarse grained multicomputers
Recommendations
Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms
External memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. Typical EM algorithms are specially crafted for the EM situation. ...
Coarse grained parallel algorithms for graph matching
Parallel graph algorithm design is a very well studied topic. Many results have been presented for the PRAM model. However, these algorithms are inherently fine grained and experiments show that PRAM algorithms do often not achieve the expected speedup ...
Comments