A performance study of data layout techniques for improving data locality in refinement-based pathfinding
- 31 December 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
Abstract
The widening gap between processor speed and memory latency increases the importance of crafting data structures and algorithms to exploit temporal and spatial locality. Refinement-based pathfinding algorithms, such as Classic Refinement (CR), find quality paths in very large sparse graphs where traditional search techniques fail to generate paths in acceptable time. In this paper, we present a performance evaluation study of three simple data structure transformations aimed at improving the data reference locality of CR. These transformations are robust to changes in computer architecture and the degree of compiler optimization. We test our alternative designs on four contemporary architectures, using two compilers for each machine. In our experiments, the application of these techniques results in performance improvements of up to 67% with consistent improvements above 15%. Analysis reveals that these improvements stem from improved data reference locality at the page level and to a lesser extent at the cache line level.Keywords
This publication has 10 references indexed in Scilit:
- A survey of graph layout problemsACM Computing Surveys, 2002
- Dynamic hot data stream prefetching for general-purpose programsACM SIGPLAN Notices, 2002
- Theory and Practice of Time-Space Trade-Offs in Memory Limited SearchLecture Notes in Computer Science, 2001
- External memory algorithms and data structuresACM Computing Surveys, 2001
- On External-Memory MST, SSSP, and Multi-way Planar Graph SeparationLecture Notes in Computer Science, 2000
- Cache-conscious structure layoutACM SIGPLAN Notices, 1999
- Cache-conscious data placementPublished by Association for Computing Machinery (ACM) ,1998
- Cache-conscious data placementACM SIGOPS Operating Systems Review, 1998
- Speeding up problem solving by abstraction: a graph oriented approachArtificial Intelligence, 1996
- A Comparison of Several Bandwidth and Profile Reduction AlgorithmsACM Transactions on Mathematical Software, 1976