A simple yet effective graph partition model for GPU computing

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

1 Scopus citations


Graph edge partition models have recently become an appealing alternative to graph vertex partition models for parallel and distributed computing due to their flexibility in balancing loads and their performance in reducing communication cost [1, 3]. In this paper, we introduce a simple yet effective graph edge partitioning model for GPU computing. In practice, our model yields high partition quality (better than or the same as the state-of-the-art edge partition approaches, at least for power-law graphs) with low partition overhead. In theory, previous work [1] showed that an approximation factor of O(dmax √log n log k) apply to the graphs with m = Ω(k2) edges (k is the number of partitions). Our model extends this result to all graphs. We demonstrate how graph edge partition model can be applied to GPU computing. We draw our examples from GPU program for locality enhancement both over time and (processor) space. For the first time, we demonstrate the effectiveness of edge partition for modeling data reuse in a many-core processors, both in theory and in practice.

Original languageEnglish (US)
Title of host publication47th International Conference on Parallel Processing, ICPP 2018
Subtitle of host publicationWorkshop Proceedings
PublisherAssociation for Computing Machinery
ISBN (Print)9781450365239
StatePublished - Aug 13 2018
Event47th International Conference on Parallel Processing, ICPP 2018 - Eugene, United States
Duration: Aug 14 2018Aug 16 2018

Publication series

NameACM International Conference Proceeding Series


Other47th International Conference on Parallel Processing, ICPP 2018
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


  • Data reuse
  • GPU
  • Graph partition model
  • Locality


Dive into the research topics of 'A simple yet effective graph partition model for GPU computing'. Together they form a unique fingerprint.

Cite this