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:
| 主要作者: | |
|---|---|
| 其他作者: | |
| 格式: | Final Year Project |
| 語言: | English |
| 出版: |
Nanyang Technological University
2024
|
| 主題: | |
| 在線閱讀: | https://hdl.handle.net/10356/175373 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 總結: | 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. |
|---|