Files: Description File size Format
Fulltext PDF (requires Acrobat Reader)
Fulltext PostScript (requires a PostScript Reader)
   
Author: Per-Olof Fjällström
Article title: Parallel Algorithms for Batched Range Searching on Coarse-Grained Multicomputers
Publ. type: Article
Volume: 2
Article No: 3
Language: English
Abstract [en]:

We defne the batched range-searching problem as follows: given a set S of n points and a set Q of m hyperrectangles, report for each hyperrect; angle which points it contains. This problem has applications in, for ex ample, computer-aided design and engineering. We present several parallel algorithms for this problem on coarse-grained multicomputers. Our algorithms are based on well-known average- and worst-case effcient sequential algorithms. One of our algorithms solves the d-dimensional batched range-searching problem in O(Ts(n logd-1p,p) + Ts(m logd-1p,p) + ((m +n)logd-1(n/p) + m logd-1p log(n/p) + k)/p) time on a p-processor coarse-grained multicomputer. (Ts(n,p) denotes the time globally to sort n numbers on a p-processor multicomputer, and k is the total number of reported points.

The work presented here is funded by CENIIT (the Center for Industrial Information Technology) at Link oping University.

Keywords: Parallel algorithms, coarse,grained multicomputers, range searching
PDF
Publisher: Linköping University Electronic Press
Year: 1997
Available: 1997-04-01
No. of pages: 14
Series: Linköping Electronic Articles in Computer and Information Science
ISSN: 1401-9841
REFERENCE TO THIS PAGE:
Fjällström, Per-Olof (1997). Parallel Algorithms for Batched Range Searching on Coarse-Grained Multicomputers in Linköping Electronic Articles in Computer and Information Science, Vol. 2. http://www.ep.liu.se/ea/cis/1997/003/. ()