ECE 637: Advanced Cache-Aware Algorithms

Tuesday, 2-4:30PM, ECE Room 237

Instructor: Dr. David A. Bader

Office: ECE 230B

Office Hours: Tuesday/Thursday 10:00 - 10:45 AM, or by appointment.

• Course Description: Design and analysis of advanced cache-oblivious and cache-aware models, algorithms, and data structures; experimental algorithmics; emphasis on combinatorial problems. Prerequisites: (CS&E 509 -- Parallel Algorithms) and (ECE 537 or CS 500), or by permission of the instructor.
• Grading: 20% Class participation, 30% Comprehension of discussion topics, 50% Final Project
• Please join the "ParAlg" Class Discussion List
• Paper Assignments
• Discussion Papers:

  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.
  2. Sandeep Sen, Siddhartha Chatterjee, Neeraj Dumir, Towards a theory of cache-efficient algorithms, Journal of the ACM, 49(6):828-858, 2002.

     Parallel Architectures

  3. Sun: A. Charlesworth, Starfire: extending the SMP envelope, IEEE Micro, 1(18):39-49, 1998.
  4. SGI: G. Haff, Latency Matters!, SGI Research Note, September 2002.
  5. IBM: J.M. Tendler, J.S. Dodson, J.S. Fields, Jr., H. Le, and B. Sinharoy, POWER4 System Microarchitecture, IBM Journal of Research and Development, 46(1):5-25, 2002.

     Cache Performance of Algorithms

  6. A. LaMarca and R.E. Ladner, The Influence of Caches on the Performance of Heaps, Journal of Experimental Algorithmics, Vol 1, 1996.
  7. A. LaMarca and R.E. Ladner, The Influence of Caches on the Performance of Sorting, Journal of Algorithms, 31:66-104, 1999.
  8. 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.
  9. Li Xiao, Xiaodong Zhang, Stefan A. Kubricht, Improving Memory Performance of Sorting Algorithms, ACM Journal on Experimental Algorithmics, 5:1-23, 2000.
     • Zhao Zhang and Xiaodong Zhang, Fast Bit-Reversals on Uniprocessors and Shared-Memory Multiprocessors, SIAM Journal on Scientific Computing, 22(6):2113-2134, 2001.

     Cache Aware

  10. John W. Romein, Jaap Heringa, Henri E. Bal, A Million-Fold Speed Improvement in Genomic Repeats Detection, 2003 (submitted).
  11. 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.
  12. 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.
  13. Naila Rahman, Richard Cole, and Rajeev Raman, Optimised Predecessor Data Structures for Internal Memory, Workshop on Algorithm Engineering, 2001.
  14. Markus Kowarschik, Ulrich Rüde, Christian Weiß, and Wolfgang Karl, Cache-Aware Multigrid Methods for Solving Poisson's Equation in Two Dimensions, Computing, 64:381-399, 2000.
  15. Markus Kowarschik and Christian Weiß, An Overview of Cache Optimization Techniques and Cache-Aware Numerical Algorithms, Proceedings of the GI-Dagstuhl Forschungseminar: Algorithms for Memory Hierarchies, Lecture Notes in Computer Science (LNCS), Vol. 2625, 2003.

      Cache Oblivious

  16. M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, Cache-Oblivious Algorithms, IEEE Symposium on Foundations of Computer Science, 1999.
  17. Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, Cache-Oblivious B-Trees, IEEE Symposium on Foundations of Computer Science, 2000.
  18. Michael A. Bender, Ziyang Duan, John Iacono, Jing Wu, A Locality Preserving Cache-Oblivious Dynamic Dictionary, extended version of SODA 2002 paper.
  19. 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.
  20. Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, Cache Oblivious Search Trees via Binary Trees of Small Height,October 2001.
  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.
  22. Richard E. Ladner, Ray Fortna, Bao-Hoang Nguyen, A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentations, April 2002.