Perfectly load-balanced, stable, synchronization-free parallel merge

DOI10.1142/S0129626414500054zbMATH Open1327.68328arXiv1303.4312OpenAlexW1971297816MaRDI QIDQ3458205FDOQ3458205

Authors: Christian Siebert, Jesper Larsson Träff 

Publication date: 18 December 2015

Published in: Parallel Processing Letters (Search for Journal in Brave)

Abstract: We present a simple, work-optimal and synchronization-free solution to the problem of stably merging in parallel two given, ordered arrays of m and n elements into an ordered array of m+n elements. The main contribution is a new, simple, fast and direct algorithm that determines, for any prefix of the stably merged output sequence, the exact prefixes of each of the two input sequences needed to produce this output prefix. More precisely, for any given index (rank) in the resulting, but not yet constructed output array representing an output prefix, the algorithm computes the indices (co-ranks) in each of the two input arrays representing the required input prefixes without having to merge the input arrays. The co-ranking algorithm takes O(log min(m,n)) time steps. The algorithm is used to devise a perfectly load-balanced, stable, parallel merge algorithm where each of p processing elements has exactly the same number of input elements to merge. Compared to other approaches to the parallel merge problem, our algorithm is considerably simpler and can be faster up to a factor of two. Compared to previous algorithms for solving the co-ranking problem, the algorithm given here is direct and maintains stability in the presence of repeated elements at no extra space or time cost. When the number of processing elements p does not exceed (m+n)/log min(m,n), the parallel merge algorithm has optimal speedup. It is easy to implement on both shared and distributed memory parallel systems.

Full work available at URL: https://arxiv.org/abs/1303.4312

Recommendations

• Space-efficient parallel merging
• On parallel integer merging
• Fast integer merging on the EREW PRAM
• A benchmark parallel sort for shared memory multiprocessors
• Parallel merging with restriction

zbMATH Keywords

parallel mergingstable mergingmerge problem

Mathematics Subject Classification ID

Data structures (68P05) Parallel algorithms in computer science (68W10)

Cites Work

• Finding the maximum, merging, and sorting in a parallel computation model
• Title not available (Why is that?)
• Merging multiple lists on hierarchical-memory multiprocessors
• Optimal merging and sorting on the EREW PRAM
• An optimal parallel algorithm for merging using multiselection
• Merging on the BSP model
• Parallel merging: Algorithm and implementation results
• Space-efficient parallel merging
• Parallel algorithms for merging and sorting
• Asymptotically efficient in-place merging

Cited In (3)

• Title not available (Why is that?)
• Parallel merge sort with load balancing
• Title not available (Why is that?)

This page was built for publication: Perfectly load-balanced, stable, synchronization-free parallel merge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3458205)