Merging with parallel processors

Publisher Website
Google Scholar
Abstract
Consider two linearly ordered sets A, B , | A | = m , | B | = n, m ≤ n , and p, p ≤ m , parallel processors working synchronously. The paper presents an algorithm for merging A and B with the p parallel processors, which requires at most 2⌈log 2 (2 m + 1)⌉ + ⌊3 m / p ⌋ + [ m / p ][log 2 ( n / m )] steps. If n = 2 β m ( β an integer), the algorithm requires at most 2[log 2 ( m + 1)] + [ m / p ](2 + β ) steps. In the case where m and n are of the same order of magnitude, i.e. n = km with k being a constant, the algorithm requires 2[log 2 ( m + 1)] + [ m / p ](3 + k ) steps. These performances compare very favorably with the previous best parallel merging algorithm, Batcher's algorithm, which requires n / p + (( m + n )/2 p )log 2 m steps in the general case and km / p + (( k + 1)/2)( m / p )log 2 m in the special case where n = km .

This publication has 4 references indexed in Scilit: