Thumbnail
Access Restriction
Subscribed

Author Gavril, Fănică
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Parallel binary insertion ♦ Parallel merging ♦ Parallel processing
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⌈log2(2m + 1)⌉ + ⌊3m/p⌋ + [m/p][log2(n/m)] steps. If n = 2βm (β an integer), the algorithm requires at most 2[log2(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[log2(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)/2p)log2m steps in the general case and km/p + ((k + 1)/2)(m/p)log2m in the special case where n = km.
Description Affiliation: Univ. of Illinois, Urbana (Gavril, Fănică)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 18
Issue Number 10
Page Count 4
Starting Page 588
Ending Page 591


Open content in new tab

   Open content in new tab
Source: ACM Digital Library