Cache-oblivious algorithms and data structures are a rather new thing, introduced by Frigo et al. in Cache-oblivious algorithms, 1999. Prokop's thesis from the same year introduces the early ideas as well.
The paper by Frigo et al. present some experimental results showing the potential of the theory and of the cache-oblivious algorithms and data structures. Many cache-oblivious data structures are based on static search trees. Methods of storing and navigating these trees have been developed quite a bit, perhaps most notably by Bender et al. and also by Brodal et al. Demaine gives a nice overview.
The experimental work of investigating the cache behaviour in practice was done at least by Ladner et al. in A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation, 2002. Ladner et al. benchmarked the cache behaviour of algorithms solving the binary search problem, using the classic algorithm, cache-oblivious algorithm and cache-aware algorithm. Each algorithm was benchmarked with both implicit and explicit navigation methods. In addition to this, the thesis by Rønn, 2003 analyzed the same algorithms to quite high detail and also performed even more thorough testing of the same algorithms as Ladner et al.
My question is
Has there been any newer research on benchmarking the cache behaviour of cache-oblivious algorithms in practice since? I'm especially interested in the performance of the static search trees, but I would also be happy with any other cache-oblivious algorithms and data structures.
Asked By : Juho
Answered By : pad
You've already covered background research on cache-oblivious algorithms quite well. In terms of benchmarking and practical results, I see this recent paper by Intel as an interesting read:
A Synergetic Approach to Throughput Computing on x86-based Multicore Desktops
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/740
0 comments:
Post a Comment
Let us know your responses and feedback