Selection on rectangular meshes with multiple broadcasting |
| |
Authors: | D Bhagavathi P J Looges S Olariu J L Schwing J Zhang |
| |
Institution: | (1) Department of Computer Science, Old Dominion University, 23529-0162 Norfolk, VA, USA;(2) Department of Math. and Computer Science, Elizabeth City State University, 27909 Elizabeth City, NC, USA |
| |
Abstract: | One of the fundamental algorithmic problems in computer science involves selecting thekth smallest element in a setS ofn elements. In this paper we present a fast selection algorithm which runs inO(n
1/8 logn) time on a mesh with multiple broadcasting of sizen
3/8 ×n
5/8. Our result shows that, just like semigroup computations, selection can be done much faster on a suitably chosen rectangular mesh than on square meshes. We also show that if every processor can storen
1/9 items, then our selection algorithm runs inO(n
1/9 logn) time on a mesh with multiple broadcasting of sizen
1/3 ×n
5/9.Work supported by NASA under grant NCC1-99.This author was partly supported by NSF grant CCR-8009996. |
| |
Keywords: | C 1 2 E 1 F 1 2 F 2 2 |
本文献已被 SpringerLink 等数据库收录! |
|