Reduction: And minimizing divergence

Wen mei W. Hwu, David B. Kirk, Izzat El Hajj

Research output: Chapter in Book/Report/Conference proceedingChapter


This chapter introduces the parallel reduction pattern that plays an important role in many data-processing applications. Reduction operators that are associative and commutative allow the reduction computation to be parallelized into a reduction tree and optimized aggressively with several optimization techniques, such as thread index assignment for reduced control and memory divergence, using shared memory for reduced global memory accesses, thread coarsening, and segmented reduction, that are needed to achieve high performance for large inputs.

Original languageEnglish (US)
Title of host publicationProgramming Massively Parallel Processors
Subtitle of host publicationa Hands-on Approach, Fourth Edition
Number of pages23
ISBN (Electronic)9780323912310
ISBN (Print)9780323984638
StatePublished - Jan 1 2022


  • Reduction trees
  • associative operators
  • barrier synchronization
  • commutative operators
  • control divergence
  • execution resource utilization efficiency
  • identity value
  • memory coalescing
  • memory divergence
  • segmented reduction
  • speedup
  • thread coarsening
  • thread index to data index mapping

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Reduction: And minimizing divergence'. Together they form a unique fingerprint.

Cite this