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.
Type de document :
[Research Report] RR-1819, INRIA. 1992
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:34:42
Dernière modification le : samedi 27 janvier 2018 - 01:31:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:52:21



  • HAL Id : inria-00074853, version 1



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



Consultations de la notice


Téléchargements de fichiers