CS 498 Program Optimization

Fall 2006

Lecture Notes

Introduction

Compiler Challenges (first chapter of the book "Optimizing Compilers for Modern Architectures", by Randy Allen and Ken Kennedy, Morgan and Kaufmann Publishers, 2002)

Compiler Optimizations (chapters 12-19 of the book "Advanced Compiler Design Implementation", by S. Muchnick, Morgan and Kaufmann Publishers, 1997)

Vtune, by Paul Petersen from INTEL

Threading Tools, by Paul Petersen from INTEL

Locality/Tiling-I

• Reading Assignment: Tile Selection Using Cache Organization and Data Layout, by S. Coleman and K. S. McKinley, in PLDI 1995.

Locality for non-numerical codes

• Reading Assignments:
  Cache-conscious Structure Definition, by T. Chilimbi, B. Davidson and J. Larus, in PLDI 1999
  Cache-conscious Structure Layout, by T. Chilimbi, M. Hill, and J. Larus, in PLDI 1999.

Parallel Programming, by Arch Robison from INTEL

• Episodes I + II

• Episodes III + IV

• Episodes V + VI

Introduction to OpenMP

Introduction to Pthreads

Instruction Level Parallelism

Hierarchically Tiled Arrays: A Programming Paradigm for Parallelism and Locality , by Ganesh Bikshandi

Introduction to Library Generators

The Atlas System

• Example of the scheduling in ATLAS
• Reading Assignment:
  Is Search Really Necessary to Generate High Performance BLAS?, by K. Yotov et al., in Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Platform Adaptation", Volume 23, Number 2, pages 358-386, Februrary 2005.

Iterative Compilation with Kernel Exploration, by Denis Barthou

• Reading Assignmnet:
  Automatic Tuning Matrix Multiplication Performance on Graphics Hardware, by Chanhao Jian and Marc Snir, in PACT 2004.

• Reading Assignmnet:
  SPARSITY:" An Optimization Framework for Sparse Matrix Kernels", by E-J. Im, K. A. Yelick, and R. Vuduc, in Int'l Journal of High Performance Computing App., 18(1), pages 135-158, 2004.

• Reading Assignment:
  A Dynamically Tuned Sorting Library, by X. Li, M.J. Garzaran, and D. Padua, in Proc. of the International Symposium on Code Generation and Optimization, pages 111-124, March 2004

• Reading Assignment:
  Optimizing Sorting with Genetic Algorithms, by X. Li, M.J. Garzaran, and D. Padua, in Proc. of the International Symposium on Code Generation and Optimization, pages 99-110, March 2005

• Reading Assignment:
  A Sampling-based Framework For Parallel Data Mining, by S. Cong, J. Han, J. Hoeflinger, and David Padua, in PPoPP 2005