Merging on the BSP model

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


The design of complex parallel algorithms relies heavily on a set of primitive operations. In this work, we examine the problem of merging two sorted sequences in an architecture independent setting. We derive parallel algorithms that can be used on a variety of parallel machines and whose performance can be reliably predicted if these algorithms are analyzed under the bulk-synchronous parallel (BSP) model. While our algorithms are fairly simple themselves, description of their performance in terms of the BSP parameters is somewhat complicated. The main reward for quantifying these complications, is that it enables parallel software to be written once and for all that can be migrated efficiently among a variety of parallel platforms. The optimal merging algorithm presented in this work achieves asymptotically optimal parallel efficiency compared to any optimal sequential merging algorithm.

Original languageEnglish (US)
Pages (from-to)809-822
Number of pages14
JournalParallel Computing
Issue number6
StatePublished - May 2001

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


  • Architecture independent
  • BSP algorithms
  • Merging
  • Parallel algorithms


Dive into the research topics of 'Merging on the BSP model'. Together they form a unique fingerprint.

Cite this