notes and shit for inf3380

introduction: 3 design, 4 communication, 5 modeling.

paradigms: 6 message passing, 7 shared memory.

algorithms: 8 matrices, 9 sorting, 10 graphs.

• ch3 parallel algorithm design
  • 3.1 preliminaries
  • 3.2 decomposition
  • 3.3 tasks and interactions
  • 3.4 mapping for load balancing
  • 3.5 interaction overhead
  • 3.6 parallel algorithm models
• ch4 communication operations
  • 4.1 one-to-all broadcast and all-to-one reduction
  • 4.2 all-to-all broadcast and reduction
  • 4.3 all-reduce and prefix-sum
  • 4.4 scatter and gather
  • 4.5 all-to-all personalized communication
  • 4.6 circular shift
  • 4.7 improving communication speed
• ch5 analytical modeling
  • 5.1 sources of overhead
  • 5.2 performance metrics
  • 5.3 granularity
  • 5.4 scalability
  • 5.5 cost-optimal execution time
  • 5.6 asymptotic analysis
  • 5.7 other scalability metrics
• ch6 the message-passing paradigm
  • 6.1 message-passing
  • 6.2 send and receive
  • 6.3 mpi
  • 6.4 topologies and embedding
  • 6.5 overlapping communication with computation? TODO
  • 6.6 collective communication and computation
  • 6.7 groups and communicators
• ch7 shared address space
  • 7.10 openmp
• ch8 dense matrix algorithms
  • 8.1 matrix-vector multiplication
  • 8.2 matrix-matrix multiplication
  • 8.3 linear equations
• ch9 sorting
  • 9.1 issues
  • 9.3 bubble sort
  • 9.4 quicksort
• ch10 graph algorithms
  • 10.1 definitions and representations
  • 10.2 minimum spanning tree: prim's TODO
  • 10.3 single-source shortest paths: dijkstra's TODO
  • 10.4 all-pairs shortest paths