-
Notifications
You must be signed in to change notification settings - Fork 0
What we can use from the book
Here I focus on labs. The most useful section of the book for lectures is probably chapter 2 which develops some performance theory, and chapter 1 which has some about architecture.
Chapters 1 to 3. Appendix B,,C, and D
The SAXPY example (chapter 4) is conceptually simple and could be a good lab for experimenting with measuring performance.
Chapter 3 section 3.2. Chapter 4. Chapter 8 section 3.
Mandelbrot is probably the best lab.
Chapter 3 section 3.4 and 3.5. Chapter 5. Chapter 8 sections 10 and 11. Chapter 11.
I think it would be a good idea to produce some supplementary materials or an extra session on the mathematical foundations for the collective operations. 8.10 has a rough introduction to monoids, but more would probably be helpful--I’m not sure we can expect our undergrads to know what “associative” means or to have an intuition about how common monoids are and how many operations can be expressed in terms of them.
The books coverage of scan/prefix sum is pretty limited. It is pointed out that many seemingly sequential algorithms can be expressed in terms of scans, but few examples are provided.
- Lookahead carry addition
- Array partition (as in quicksort)
The integration example (chapter 5) is okay and could be used for a lab.
The k-means example in chapter 11 is great and would make a very good lab.
Chapter 3 section 5. Chapter 6.
I don’t think this chapter has a great example. It might make sense to use a map/reduce example (such as k-means).
Another possibility is the sample sort from chapter 14.
Chapter 7. Chapter 8 section 12.
Chapter 10 “Forward Seismic Simulation” is the main stencil example in the book. Which is a problem if we are not assuming knowledge of PDEs. Their might be a way to recast this example without the math.
Chapter 8--this is the densest chapter in the book, and I have tried to show how it could be split up.
Cache Oblivious Matrix Multiplication (Chapter 8) Katsuba Multiplication (Chapter 8) Quicksort (Chapter 8) Mergesort (Chapter 13) Cholesky Factorization (Chapter 15)
Any of those would make good labs, although my recommendation would be mergesort as it is self contained
Chapter 9.
The best example in the book is chapter 12/Bzip2. Unfortunately, making a lab out of this would be a lot of work as the code set for the book does not include it and bzip2 is a large program.