G. Cong and T. Wen (USA)
Parallel Algorithms, Graph Problems, Temporal Locality, Spatial Locality
Large-scale graph problems are becoming increasingly im portant in science and engineering. The irregular, sparse in stances are especially challenging to solve on cache-based architectures as they are known to incur erratic memory ac cess patterns. Yet many of the algorithms also exhibit some degree of regularity with memory accesses. It is impor tant 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 al gorithms, both sequential and parallel, and correlate our observations with the algorithmic design. Our study of lo cality behavior brings insight into the impact of different cache architectures on the performance of both sequential and parallel graph algorithms.
Important Links:
Go Back
