TY - GEN
T1 - A study on the locality behavior of minimum spanning tree algorithms
AU - Cong, Guojing
AU - Sbaraglia, Simone
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
KW - Graph algorithm
KW - Memory locality
KW - Minimum spanning tree
UR - http://www.scopus.com/inward/record.url?scp=77049085734&partnerID=8YFLogxK
U2 - 10.1007/11945918_55
DO - 10.1007/11945918_55
M3 - Conference contribution
AN - SCOPUS:77049085734
SN - 354068039X
SN - 9783540680390
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 583
EP - 594
BT - High Performance Computing - HiPC 2006 - 13th International Conference Proceedings
T2 - 13th International Conference on High Performance Computing, HiPC 2006
Y2 - 18 December 2006 through 21 December 2006
ER -