Experimental study on cache-performance optimization for graph storage

• Main Author: Foo, Wei Ling
• Other Authors: Luo Siqiang
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2024
• Subjects: Computer and Information Science
• Online Access: https://hdl.handle.net/10356/175373
• Institution: Nanyang Technological University

Cache systems are designed to enhance data access speed by keeping it close to the processor, allowing faster access than retrieving data from the main memory. This advantage is beneficial and applicable to graph traversal algorithms when closely related nodes are stored in a cache line. Hao Wei et al. [1] introduced a graph ordering algorithm, Gorder, a greedy procedure to reorder graph nodes in such a way that optimises their placement on a cache line. In a replication work, Fabrice Lecuyer et al. implemented ten different graph ordering algorithms and nine graph traversal algorithms and measured the execution time on nine graph datasets. In this extension, I have collected ten types of large graph datasets to measure the execution time using five graph ordering algorithms and five graph traversal algorithms as benchmarks from Fabrice Lecuyer et al. [2]. My findings show that Gorder results in the overall fastest execution time among the other graph-ordering algorithms, which validates the two initial results but highlights that Gorder is not the best performer on some types of graph datasets.