A parallel sorting algorithm for a novel model of computation |
| |
Authors: | Amitabha Das Louise E Moser P M Melliar-Smith |
| |
Affiliation: | (1) Department of Electrical and Computer Engineering, University of California, Santa, 93106 Barbara, California |
| |
Abstract: | The computational complexity of a parallel algorithm depends critically on the model of computation. We describe a simple and elegant rule-based model of computation in which processors apply rules asynchronously to pairs of objects from a global object space. Application of a rule to a pair of objects results in the creation of a new object if the objects satisfy the guard of the rule. The model can be efficiently implemented as a novel MIMD array processor architecture, the Intersecting Broadcast Machine. For this model of computation, we describe an efficient parallel sorting algorithm based on mergesort. The computational complexity of the sorting algorithm isO(nlog2
n), comparable to that for specialized sorting networks and an improvement on theO(n
1.5) complexity of conventional mesh-connected array processors. |
| |
Keywords: | Parallel sorting algorithm rule-based model of computation MIMD array processor architecture |
本文献已被 SpringerLink 等数据库收录! |