@inproceedings{412798258f2142ab8e7ae1ddb585bddd,
title = "Locality behavior of parallel and sequential algorithms for irregular graph problems",
abstract = "Large-scale graph problems are becoming increasingly important in science and engineering. The irregular, sparse instances are especially challenging to solve on cache-based architectures as they are known to incur erratic memory access patterns. Yet many of the algorithms also exhibit some degree of regularity with memory accesses. It is important to characterize the locality behavior in order to bridge the gap between algorithm and architecture. In our study we quantify the locality of several fundamental graph algorithms, both sequential and parallel, and correlate our observations with the algorithmic design. Our study of locality behavior brings insight into the impact of different cache architectures on the performance of both sequential and parallel graph algorithms.",
keywords = "Graph problems, Parallel algorithms, Spatial locality, Temporal locality",
author = "Guojing Cong and Tong Wen",
year = "2007",
language = "English",
isbn = "9780889867048",
series = "Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems",
pages = "391--397",
booktitle = "Proceedings of the 19th IASTED International Conference on Parallel and Distributed Computing and Systems",
note = "19th IASTED International Conference on Parallel and Distributed Computing and Systems ; Conference date: 19-11-2007 Through 21-11-2007",
}