Access Restriction

Author Niewiadomski, Robert ♦ Amaral, Jos Nelson ♦ Holte, Robert C.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2004
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Cache-conscious algorithms ♦ Classical refinement ♦ Pathfinding
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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2004-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 9

Open content in new tab

   Open content in new tab
Source: ACM Digital Library