Complexity analysis and algorithm design for reorganizing data to minimize non-coalesced memory accesses on GPU

Bo Wu, Zhijia Zhao, Eddy Z. Zhang, Yunlian Jiang, Xipeng Shen

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


The performance of Graphic Processing Units (GPU) is sensitive to irregular memory references. Some recent work shows the promise of data reorganization for eliminating non-coalesced memory accesses that are caused by irregular references. However, all previous studies have employed simple, heuristic methods to determine the new data layouts to create. As a result, they either do not provide any performance guarantee or are effective to only some limited scenarios. This paper contributes a fundamental study to the problem. It systematically analyzes the inherent complexity of the problem in various settings, and for the first time, proves that the problem is NP-complete. It then points out the limitations of existing techniques and reveals that in practice, the essence for designing an appropriate data reorganization algorithm can be reduced to a tradeoff among space, time, and complexity. Based on that insight, it develops two new data reorganization algorithms to overcome the limitations of previous methods. Experiments show that an assembly composed of the new algorithms and a previous algorithm can circumvent the inherent complexity in finding optimal data layouts, making it feasible to minimize non-coalesced memory accesses for a variety of irregular applications and settings that are beyond the reach of existing techniques.

Original languageEnglish (US)
Pages (from-to)57-67
Number of pages11
JournalACM SIGPLAN Notices
Issue number8
StatePublished - Aug 2013

All Science Journal Classification (ASJC) codes

  • Computer Science(all)


  • Computational complexity
  • Data transformation
  • Memory coalescing
  • Runtime optimizations
  • Thread-data remapping

Fingerprint Dive into the research topics of 'Complexity analysis and algorithm design for reorganizing data to minimize non-coalesced memory accesses on GPU'. Together they form a unique fingerprint.

Cite this