Experimental study on cache-performance optimization for graph storage
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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project |
| Language: | English |
| Published: |
Nanyang Technological University
2024
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/175373 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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. |
|---|