Improving Memory Access Locality for Large-Scale Graph Analysis Applications

Guojing Cong, Konstantin Makarychev

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

1 Scopus citations

Abstract

Large-scale graph analysis on irregular instances is challenging due to the erratic memory access pattern. Although various techniques have been proposed to improve cache performance, in general they do not apply to algorithms with fine-grained parallelism. Most parallel graph algorithms exhibit poor locality behavior and thus poor cache performance on current architectures. In this paper we present our study of improving spatial locality for graph analysis applications. Our approach is to lay out the graph in a fashion that matches the frequently occurred patterns in parallel graph algorithms. We manipulate the graph layout by permuting the labelings of vertices. We show that the graph layout problem is NP-hard for the traversal pattern, and present performance comparisons of different labeling approaches. We further discuss the impact of labeling on fundamental building blocks of parallel algorithms such as pointer jumping and Euler-tour tree computation. Experimental results show that the labeling technique improves the scalability of the algorithms as a result of more efficient use of memory bandwidth.

Original languageEnglish (US)
Title of host publication22nd ISCA International Conference on Parallel and Distributed Computing and Communication Systems 2009, PDCCS 2009
PublisherInternational Society for Computers and Their Applications (ISCA)
Pages121-127
Number of pages7
ISBN (Electronic)9781615675777
StatePublished - 2009
Externally publishedYes
Event22nd International Conference on Parallel and Distributed Computing and Communication Systems, PDCCS 2009 - Louisville, United States
Duration: Sep 24 2009Sep 26 2009

Publication series

Name22nd ISCA International Conference on Parallel and Distributed Computing and Communication Systems 2009, PDCCS 2009

Conference

Conference22nd International Conference on Parallel and Distributed Computing and Communication Systems, PDCCS 2009
Country/TerritoryUnited States
CityLouisville
Period9/24/099/26/09

Keywords

  • Breadth-first Search
  • Depth-first Search
  • Locality
  • Parallel Graph Algorithms

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Fingerprint

Dive into the research topics of 'Improving Memory Access Locality for Large-Scale Graph Analysis Applications'. Together they form a unique fingerprint.

Cite this