A Study of Integer Sorting on Multicores

Research output: Contribution to journalArticlepeer-review

Abstract

Integer sorting on multicores and GPUs can be realized by a variety of approaches that include variants of distribution-based methods such as radix-sort, comparison-oriented algorithms such as deterministic regular sampling and random sampling parallel sorting, and network-based algorithms such as Batcher's bitonic sorting algorithm. In this work we present an experimental study of integer sorting on multicore processors. We have implemented serial and parallel radix-sort for various radixes, deterministic regular oversampling, and random oversampling parallel sorting, including new variants of ours, and also some previously little explored or unexplored variants of bitonic-sort and odd-even transposition sort. The study uses multithreading and multiprocessing parallel programming libraries with the same C language code working under Open MPI, MulticoreBSP, and BSPlib. We first provide some general high-level observations on the performance of these implementations. If we can conclude anything is that accurate prediction of performance by taking into consideration architecture dependent features such as the structure and characteristics of multiple memory hierarchies is difficult and more often than not untenable. To some degree this is affected by the overhead imposed by the high-level library used in the programming effort. Another objective is to model the performance of these algorithms and their implementations under the MBSP (Multi-memory BSP) model. Despite the limitations mentioned above, we can still draw some reliable conclusions and reason about the performance of these implementations using the MBSP model, thus making MBSP useful and usable.

Original languageEnglish (US)
Article number1850014
JournalParallel processing letters
Volume28
Issue number4
DOIs
StatePublished - Dec 1 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • MBSP model
  • Parallel computing
  • integer sorting
  • multicore
  • performance evaluation

Fingerprint

Dive into the research topics of 'A Study of Integer Sorting on Multicores'. Together they form a unique fingerprint.

Cite this