|Fulltext||PDF (requires Acrobat Reader)|
|Fulltext||PostScript (requires a PostScript Reader)|
|Article title:||Parallel Algorithms for Batched Range Searching on Coarse-Grained Multicomputers|
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 Linkoping University.
|Keywords:||Parallel algorithms, coarse,grained multicomputers, range searching|
|Publisher:||Linköping University Electronic Press|
|No. of pages:||14|
|Series:||Linköping Electronic Articles in Computer and Information Science|
|REFERENCE TO THIS PAGE: