A study on the locality behavior of minimum spanning tree algorithms

Guojing Cong, Simone Sbaraglia

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

Locality behavior study is crucial for achieving good performance for irregular problems. Graph algorithms with large, sparse inputs, for example, oftentimes achieve only a tiny fraction of the potential peak performance on current architectures. Compared with most numerical algorithms graph algorithms lay higher pressure on the memory system. In this paper, using the minimum spanning tree problem as an example, we study the locality behavior of graph algorithms, both sequential and parallel, for arbitrary, sparse instances. We show that the inherent locality of graph algorithms may not be favored by the current architecture, and parallel graph algorithms tend to have significantly poorer locality behaviors than their sequential counterparts. As memory hierarchy gets deeper and processors start to contain multi-cores, our study suggests that architectural support and new parallel algorithm designs are necessary for achieving good performance for irregular graph problems.

Original languageEnglish
Title of host publicationHigh Performance Computing - HiPC 2006 - 13th International Conference Proceedings
Pages583-594
Number of pages12
DOIs
StatePublished - 2006
Externally publishedYes
Event13th International Conference on High Performance Computing, HiPC 2006 - Bangalore, India
Duration: Dec 18 2006Dec 21 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4297 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on High Performance Computing, HiPC 2006
Country/TerritoryIndia
CityBangalore
Period12/18/0612/21/06

Keywords

  • Graph algorithm
  • Memory locality
  • Minimum spanning tree

Fingerprint

Dive into the research topics of 'A study on the locality behavior of minimum spanning tree algorithms'. Together they form a unique fingerprint.

Cite this