BeBOP Readings for 2001

Bibliographies

Some bibliographies (in BibTeX format) of relevant readings as we collect them:

Since we didn't get a chance to discuss the Yi, Adve, and Kennedy paper last week, we'll take a look at it this week.

"Transforming loops to recursion for multi-level memory hierarchies." [PostScript] [PDF] (PLDI 2000)
Q. Yi, V. Adve, K. Kennedy.
This paper is a follow-up to the readings on cache-oblivious algorithms. The authors examine compiler source transformation for generating cache-oblivious recursive algorithms from a loop-based implementation, and show experimental results with some linear algebra kernels (e.g., Cholesky factorization).
(Note: The fonts in the PostScript version display a little more clearly than those in the PDF version.)

The focus for this week is on techniques for compilation. There are two readings, one of a practical nature and one with a more theoretical flavor.

"Efficient exploitation of parallelism on Pentium III and Pentium 4 processor-based systems." [PDF]. (Intel Technology Journal, Q1 2001)
A. Bik and M. Girkar and P. Grey and X. Tian.
This article is a high-level overview of vectorization in the Intel C/C++ and Fortran compilers (icc/ifc).

This week we take a closer look at the Intel Pentium family of processors.

"Performance characterization of the Pentium Pro processor." (HPCA 1997)
D. Bhandarkar, J. Ding.
"Implementing the streaming SIMD extensions on the Pentium III processor." (IEEE Micro, 20:4, 2000, 47--57).
S. Raman, V. Pentkovski, J. Keshava.
"The microarchitecture of the Pentium 4 processor." (Intel Technology Journal, Q1, 2000).
G. Hinton, D. Sager, M. Upton, D. Boggs, D. Carmean, A. Kyker, P. Roussel.
Chapter 3 of Computer Architecture: A Quantitative Approach (3rd edition)
Patterson and Hennessey.
Section 3.7 covers the Pentium Pro and is a digestable summary of the key results in the first reading by Bhandarkar and Ding. The rest of the chapter reviews basic register renaming and out-of-order execution techniques. (This is a preprint of their new book, so see me about obtaining a copy of this chapter.)

"Cache-Oblivious Algorithms." (FOCS 1999)
M. Frigo, C. Leiserson, H. Prokop, S. Ramachandran.
This paper discusses, in the context of a particular machine/cache model, algorithms for matrix transpose, FFT, and sorting that are asymptotically optimal with respect to the amount of data movement in a system with multi-level caches. These algorithms are interesting because they do not have any cache-dependent tuning parameters (like block sizes).

You say you have too much time on your hands and crave more details? Then check out:

"Portable High-Performance Programs" and "Cache-Oblivious Algorithms", theses by Frigo and Prokop, respectively, replete with all the gory details.
"Cache-Oblivious B-Trees" (Bender, Demaine, and Farach-Colton in FOCS 2000).
... and more.

XBLAS Home Page
This web page contains a short, high-level description of this new software standard. This is a good place to start.
BLAS Technical Forum
This page contains the full formal software standard of which the XBLAS is a part. The XBLAS in particular are defined in Chapter 4. You should read Chapter 1, the introduction, and pages 132--144 of Chapter 4. The rest of the very lengthy Chapter 4 is a list of subroutine interfaces, and just reading the first few will give you a flavor of what we are doing. Also, we are not currently working on the Fortran versions of this code---just C.
"Design, Implementation, and Testing of Extended and Mixed Precision BLAS." (UTK Tech Report CS--00--451; submitted to ACM TOMS)
X. Li, J. Demmel, D. Bailey, G. Henry, Y. Hida, J. Iskandar, W. Kahan, A. Kapur, M. C. Martin, T. Tung, D. J. Yoo.
Read this paper next. It gives a more complete explanation of the motivation and background of the standard (Chapter 4 of the standard is a bit brief on this).
"Algorithms for Quad-Double Precision Floating Point Arithmetic."
Yozo Hida, Xiaoye Li, David Bailey. (ARITH-15, 2001)
Read this paper on the different implementations of high precision arithmetic.

"Optimizing Sparse Matrix-Vector Multiplication for Register Reuse." (ICCS 2001)
Eun-Jin Im, Katherine A. Yelick.
Read this first for a summary of the latest Sparsity-related research results.
"Optimizing Sparse Matrix Kernels for Data Mining." (SIAM ICDM 2001)
Eun-Jin Im, Katherine Yelick.
Read this next.
"Optimizing the Performance of Sparse Matrix-Vector Multiplication." (UCB PhD thesis)
[Appendix (24 MB)]
Eun-Jin Im.
This thesis has the full details. Note: The appendix is a separate download.

Titanium Project
"Towards an Accurate Model of Collective Communications." (ICCS 2001)
Sathish S. Vadhiyar, Graham E. Fagg, Jack J. Dongarra.
Read first.
"On Global Combine Operations." (J. Par. Dist. Comp.)
Robert van de Geijn.
Another useful starting-point.

A Media-Enhanced Vector Architecture for Embedded Memory Systems." (UCB Masters' Thesis)
Christoforos Kozyrakis.
Take a look at this paper first.
IRAM Project
See this page for an overview of the project.

Get your hands dirty with the following exercise on optimizing matrix multiply.

Broken links or other comments? Mail me.