Announcements

  • Lab 3 focus is understanding locality+hierarchy in programming and execution model of Sequoia and Cell.
    • Don’t waste a lot of time on doing superficial things.
    • Ask me if you’re not sure if something is superficial
  • Performance modeling is really important bit, but we’re looking for back of the envelope stuff.
  • Seriously, be minimalistic in this lab
  • Come see me about project updates!
  • Lab 2 grades will be uploaded today.
  • Next week is going to be wrap up and loose ends (and a bit about future directions)
    • I will quickly go over all current scribe notes
      • please let me know if you’re done with yours
    • I’ll also link one nice paper that I would like to discuss a little bit.

Lab 2

Things that people did well

  • Allocated histogram bins to avoid bank conflicts
  • Experimented with number of bins/blocks
  • Experimented with bin/pixel partitioning
  • Tried out some shared memory to reduce BW when partitioning bins
  • Ran into 16KB problem, some tried allocating a few bins in registers
  • Ran into image not fitting in device memory
    • My bad on that one, I really apologize.
  • Different ways of doing reductions.

Common problems

  • A lot of people had divides all over the place. Make constants constant and use >> to divide by powers of 2.
  • Sorry about the image not fitting in GPU memory.
  • Didn’t think about what the expected performance might be (makes optimizing really hard).
  • BW was the issue and other than coalescing, very little discussion of it. Could have tried to maximize both BW and reuse by having many threads gather, but only a few threads compute. Should have also spread out the gather across all memory banks (ROPs).

estimating performance

  1. LD pixel
  2. bin = pixel >> BIN_SHIFT (BIN_SHIFT==log2(MAX_VAL/NUM_BINS)
  3. LD hist[bin]
  4. hist[bin]++
  5. ST hist[bin]
  6. perhaps test branch condition
  7. branch

So 7 cycles for every pixel load, and can do 128 “cycles” at 1.35GHz:

~25 GW/sec == 100GB/s of ints or 50GB/s for shorts

Desktop can sustain ~8GB/s so best speedup should be about 5 - 10x

Conclusion — maximize locality to reduce BW. Minimize re-reading of pixels and always coalesce (even when doing shorts). Also need to make sure all memory banks are being used.

Also need to hide latency of course and deal with reductions.

Tools to Increase Locality

  • Increase locality by blocking for reuse.
    • matrix multiply
    • histogram
    • what about unstructured data?
  • Unstructured representation
    • Geometry
    • Mesh
    • Graphs
    • Adjacency matrix
    • This is why sparse matrices are so important
  • Partitioning or Domain Decomposition
    • First used to divide parallel work
      • Load balance
      • Minimize communication
    • Can also be used just to minimize comm — increase

locality

  • Geometric partitioning
    • Kernighan-Lynn
    • Cuthill-McGee
  • Graph partitioning
    • Spectral methods
    • Approximate
      • METIS / ParMETIS
      • Jostle
      • Chaco
      • Zoltan
      • PARTY
      • PARTI
  • Space Filling Curves
  • Search based
  • Connection to streaming
    • Streaming recap
    • Streaming algorithms
    • Spatial locality
    • Sparse matrix formats, mesh formats, and more