Introduction
1. Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, Dave Lomet AlphaSort: A Cache-Sensitive Parallel External Sort
Models
1. Alok Aggarwal and Jeffrey Scott Vitter, The Input/Output Complexity of Sorting and Related Problems, Communications of the ACM, 31:1116-1127, 1988. slides of talk
2. Sandeep Sen, Siddhartha Chatterjee, Neeraj Dumir, Towards a theory of cache-efficient algorithms, Journal of the ACM, 49(6):828-858, 2002. slides
3.
Cache Performance of Algorithms
4. A. LaMarca and R.E. Ladner, The Influence of Caches on the Performance of Heaps, Journal of Experimental Algorithmics, Vol 1, 1996. slides
5. A. LaMarca and R.E. Ladner, The Influence of Caches on the Performance of Sorting, Journal of Algorithms, 31:66-104, 1999. slides
6. R.E. Ladner, J.D. Fix, and A. LaMarca, Cache Performance Analysis of Traversals and Random Accesses, Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999.slides
7. Y. Gil and A. Itai, How to pack trees. J. Algorithms 32, 108-132, (1999).
8. N. Park, W. Liu, V. Prasanna, C Rahavendra, Efficient Matrix Multiplication Using Cache Concious Data Layouts
9.
10. R. Hankins and J. Patel, Effect of Node Size on the Performance of Cache-Conscious B+ Trees slides
11. Li Xiao, Xiaodong Zhang, Stefan A. Kubricht, Improving Memory Performance of Sorting Algorithms, ACM Journal on Experimental Algorithmics, 5:1-23, 2000.slides
12. Zhao Zhang and Xiaodong Zhang, Cache-Optimal
Methods for Bit-Reversals
13. Michael Penner, Viktor K Prasanna, Cache-Friendly Implementations of Transitive Closure, International Conference on Parallel Architectures and Compilation Techniques (PACT'01), Barcelona, Spain, September 2001.
14. Joon-Sang Park, Michael Penner, Viktor K Prasanna, Optimizing Graph Algorithms for Improved Cache Performance, International Parallel and Distributed Processing Symposium, Fort Lauderdale, FL, April 2002. slides
Cache Oblivious
15. M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, Cache-Oblivious Algorithms, IEEE Symposium on Foundations of Computer Science, 1999.
16. Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, Cache-Oblivious B-Trees, IEEE Symposium on Foundations of Computer Science, 2000. slides
17. Michael A. Bender, Ziyang Duan, John Iacono, Jing Wu, A Locality Preserving Cache-Oblivious Dynamic Dictionary, extended version of SODA 2002 paper.
18. Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, J. Ian Munro, Theis Rauhe, Mikkel Thorup, Efficient Tree Layout in a Multilevel Memory Hierarchy, Extended version of ESA 2002 paper, November 2002.
19. Gerth Stolting Brodal, Rolf Fagerberg, Riko Jacob, Cache Oblivious Search Trees via Binary Trees of Small Height,October 2001. slides auxilliary notes
20. Pankaj Agarwal, Lars Arge, Andrew Danner and Brian Holland-Mikley Cache-oblivious data structures for orthogonal range searching
21. Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro, Cache-Oblivious Priority Queue and Graph Algorithm Applications, 34th ACM Symposium on Theory of Computing (STOC), 2002. slides
Hardware
22. Alexander Gaysinsky, Alon Itai and Hadas Shachnai. Strongly Competitive Algorithms for Caching with Pipelined Prefetching. ESA 2001. Compressed postscript. IPL version pdf.
23. J. Hallberg, T. Palm and M. Brorsson, Cache-conscious Allocation of Pointer-Based Data Structures Revisited with HW/SW Prefetching slides
24.