A Performance Study of Data Layout Techniques for Improving Data Locality in Refinement-Based Pathfinding
- Robert Niewiadomski, Department of Computing Sciences, University of Alberta
- Jose Nelson Amaral, Department of Computing Sciences, University of Alberta
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.
Citation
R. Niewiadomski, J. Amaral. "A Performance Study of Data Layout Techniques for Improving Data Locality in Refinement-Based Pathfinding". Journal of Experimental Algorithms (JEA), 1.2(9), pp 1-28, January 2004.| Keywords: | performance, improving, refinement-based, machine learning |
| Category: | In Journal |
BibTeX
@article{Niewiadomski+Amaral:JEA04,
author = {Robert Niewiadomski and Jose Nelson Amaral},
title = {A Performance Study of Data Layout Techniques for Improving Data
Locality in Refinement-Based Pathfinding},
Volume = "1.2",
Number = "9",
Pages = {1-28},
journal = {Journal of Experimental Algorithms (JEA)},
year = 2004,
}Last Updated: June 04, 2007Submitted by Staurt H. Johnson
