Skip to Main content Skip to Navigation
Reports

Scalable parallel geometric algorithms for coarse grained multicomputers

Abstract : Whereas most of the literature assumes that the number of processors p is a function of the problem size n, in scalable algorithms p becomes a parameter of the time complexity. This is a more realistic modelisation of real parallel machines and yields optimal algorithms, for the case that n H p, where H is a function depending on the architecture of the interconnexion network. In this paper we present scalable algorithms for a number of geometric problems, namely lower envelope of line segments, 2D-nearest neighbour, 3D-maxima, 2D-weighted dominance counting area of the union of rectangles, 2D-convex hull. The main idea of these algorithms is to decompose the problem in p subproblems of size 0(F(n;p) + f(p)), with f(p) 2 F(n;p) , which can be solved independently using optimal sequential algorithms. For each problem we present a spatial decomposition scheme based on some geometric observations. The decomposition schemes have in common that they can be computed by globally sorting the entire data set at most twice. The data redundancy of f(p) duplicates of data elements per processor does not increase the asymptotic time complexity and ranges for the algorithms presented in this paper, from p to p2. The algorithms do not depend on a specific architecture,they are easy to implement and in practice efficient as experiments show.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074853
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 4:34:42 PM
Last modification on : Saturday, January 27, 2018 - 1:31:04 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:52:21 PM

Identifiers

  • HAL Id : inria-00074853, version 1

Collections

Citation

Franck Dehne, Andreas Fabri, Andrew Rau-Chaplin. Scalable parallel geometric algorithms for coarse grained multicomputers. [Research Report] RR-1819, INRIA. 1992. ⟨inria-00074853⟩

Share

Metrics

Record views

244

Files downloads

251