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.      S. Chatterjee and S. Sen, Cache-Efficient Matrix Transposition slides

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  SIAM Journal on Scientific Computing, 22(6):2113-2134, 2001. Larry Carter and Kang Su Gatlin, Towards an Optimal Bit-Reversal Permutation Algorithm.slides

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.  N. Manjikian and T. Abdelrahman, Array Data Layout for the Reduction of Cache Conflicts