In-place data sliding algorithms for many-core architectures

Juan Gómez Luna, Li Wen Chang, I. Jui Sung, Wen-Mei W Hwu, Nicolás Guil

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In-place data manipulation is very desirable in many-core architectures with limited on-board memory. This paper deals with the in-place implementation of a class of primitives that perform data movements in one direction. We call these primitives Data Sliding (DS) algorithms. Notable among them are relational algebra primitives (such as select and unique), padding to insert empty elements in a data structure, and stream compaction to reduce memory requirements. Their in-place implementation in a bulk synchronous parallel model, such as GPUs, is specially challenging due to the difficulties in synchronizing threads executing on different compute units. Using a novel adjacent work-group synchronization technique, we propose two algorithmic schemes for regular and irregular DS algorithms. With a set of 5 benchmarks, we validate our approaches and compare them to the state-of-the-art implementations of these benchmarks. Our regular DS algorithms demonstrate up to 9.11x and 73.25x on NVIDIA and AMD GPUs, respectively, the throughput of their competitors. Our irregular DS algorithms outperform NVIDIA Thrust library by up to 3.24x on the three most recent generations of NVIDIA GPUs.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 44th International Annual Conference on Parallel Processing, ICPP 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)9781467375870
StatePublished - Dec 8 2015
Event44th International Conference on Parallel Processing, ICPP 2015 - Beijing, China
Duration: Sep 1 2015Sep 4 2015

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918


Other44th International Conference on Parallel Processing, ICPP 2015


  • In-place
  • Relational algebra
  • Stream compaction

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Hardware and Architecture


Dive into the research topics of 'In-place data sliding algorithms for many-core architectures'. Together they form a unique fingerprint.

Cite this