Cache behaviour analysis for graph algorithms

Abstract: Graph processing is an ever-increasing significant area of research in the wake of the demand for efficient tools that process data such as graphs, which can describe sets of objects (vertices) and their relations to each other (edges). Graph algorithms traverse these graphs by visiting their vertices or additionally calculating some properties about them such as how significant a specific vertex is in the context of the greater graph. This thesis describes a set of popular graph algorithms and provides respective pseudocodes for them to profile their cache behaviour. Particularly, each algorithm is characterised by each respective pseudocode line's cache misses, a known performance bottleneck. As a major field of research in graph processing concerns accommodating the graph algorithms for the memory hierarchy, this thesis provides a comprehensive overview of how the algorithm interacts with the cache. It is demonstrated which parts of each algorithm exhibit the worst cache behaviour, accompanied bya possible explanation. Lastly, the algorithms' performance is measured to illustrate how they compare and the effect of the choice of the input graph. This work aims to provide an overview of the subject so that people, whose foundations lie in computer architecture, may be better equipped to research graph processing.