Lectures
Lectures are designed for synchronous delivery. It is not expected that the recorded version is an adequate substitute for attending.
Recorded lectures are available through Canvas on the Panopto tab.
Jupyter notebooks for lectures are available on github (https://github.com/randalburns/pplectures2022
). It is encouraged that you clone this repo, pull before each lecture and run.
Announcments (week of August 29 2022)
Projects
Past
- Activity 1: All possible regressions (due Friday September, 16 2022 5:00 pm EDT)
- complete the notebook in
randalburns/pplectures2022
namedactivities/activity1.ipynb
- complete the notebook in
- Activity 2: OpenMP Filter (due September, 30 2022 5:00 pm EDT)
- Activity 3: Java BlockingQueue (due Tuesday October 18, 2022 11:59:59 pm EDT)
- Activity 4:
dask
notebooks (due November 8, 2022 5:00 pm EDT) - Activity 5: k-means in Spark (due December 2, 2022 5:00 pm EST)
- Activity 6: cancelled Ray Deadlock (no due date)
I have included activity 6 for your reference. It is the assignment that was described in Lecture 22. You should review and run the notebooks to see what’s going on.
Upcoming
Late Hours
A total of 48 late hours are permitted per semester to use as needed for activities. Late hours will be rounded up to the nearest hour, e.g. a project submitted 2.1 hours late will count as using 3 late hours.
Examinations:
- Midterm 1: October 5, 2022. (during class period)
- Midterm 2: November 2, 2022. (during class period)
- Final Exam: Friday December 16, 2022. 9am–12pm.
Examinations will be conducted in class. Students are allowed to bring one page (letter-size or A4) of handwritten notes. THe notes page must be turned in with the exam.
Course Schedule
(29 August) Introduction to Parallel Programming (zoom lecture)
Syllabus review. Academic ethics. Parallelism in modern computer architectures. Performance beyond computational complexity. An introduction to course tools for lectures and homework: conda/python/github/jupyter.
- Lecture:
Lec01.Intro.ipynb
- Reading:
- Mattson, Patterns for Parallel Programming, Chapter 1.
(31 August) A First Parallel Program
Parallelization with joblib
in Python. The Global Interpreter Lock. Python packages for data science. Performance timing.
- Lecture:
Lec02.FirstParallel.ipynb
- Reading:
- Matloff, Parallel Computing for Data Science, Chapter 1.
Activity #1: Joblib – All Pairs Regression
- due September, 16 2022 5:00 pm EDT.
- complete the notebook in
pplectures2022/activities/activity1.ipynb
(5 September) Labor day.
(7 September) Amdahl’s Law and Strong Scaling
Amdahl’s law is the fundamental principle behind strong scaling in parallel computing. Strong scaling is the process of solving a problem of the fixed size faster with parallel resources.
- Lecture:
Lec03.Amdahls.ipynb
- Reading:
- Mattson, Patterns for Parallel Programming, Ch. 2.4-2.6
(7 and 12 September) Factors Against Parallelism
A visual introduction to how parallelism is lost in programs.
- Lecture:
Lec03.5.Factors.ipynb
(12 September) OpenMP in C/C++
Lecture 4: An introduction to parallelizing serial programs based on compiler directives. Serial equivalence.
- Reading:
- Mattson, Patterns for Parallel Programming, Appendix A.
- Reference Materials:
- LLNL Tutorial (ignore Fortran stuff): https://computing.llnl.gov/tutorials/openMP/
- Specification (it’s actually really useful): http://www.openmp.org/mp-documents/spec30.pdf
(14 September) Cache Hierarchy
Lecture 5: Memory hierarchy and latency. Caching concepts: size, lines, associativity, and inclusion/exclusion. False sharing.
(19 September) Loop Optimization
Lecture 6: Loop Optimizations
- Reading:
- Performance tutorial (this is good!): http://www.akira.ruc.dk/~keld/teaching/IPDC_f10/Slides/pdf4x/4_Performance.4x.pdf
Activity #2: OpenMP Filter
- due September, 30 2022 5:00 pm EDT.
(21 September) Loop Dependency Analysis
Lecture 7a: Loop Dependencies
- This recorded lecture also contains Loop Unrolling which we did not finish in the previous lecture.
- Reading:
- https://en.wikipedia.org/wiki/Loop_dependence_analysis
(21 September) Moore’s Law and Parallelism.
Lecture 7b: Moore’s law.
- Reading:
- Chapter 2, Patterns for Parallel Programming
(26 September) Vectorization.
(28 September) Python JIT compilation. Parallel Efficiency
Two short lectures to revist python, JobLib and scaleup.
NO MATERIAL past this point is on the Midterm 1.
(3 October) Java Threads and Java Concurrency Control
Lecture 10a: Java Threads, Lecture 10b: Java Synchronization: Asynchrony, waiting on threads, volatile variables, and synchronized functions.
- Reading:
- Appendix C: Patterns for Parallel Programming
(5 October) Midterm 1
(10 October) Processess, Threads, Virtual Memory, Simultaneous Multithreading
Activity #3: Java Blocking Queue
- due October, 18 2022 11:59:59 pm EDT.
(12 October) Mutual Exclusion
Lecture 12: Critical sections, Peterson’s algorithm and fast mutual exclusion.
- Reading:
- Chapter 1 and 2-2.6: Herlihy and Shavat
(17 October) Roofline
Lecture 13: The roofline performance model and off-chip bandwidth
- Reading: Understand operational intensity and the memory-limited and processing limited portions of the chart. This will be on the final as described in class!
- Williams et al. Roofline: An Insightful Visual Performance Model for Floating-Point Programs and Multicore Architectures, CACM, 52(4), 2009.
(19 October) Distributed Memory Systems, Flynn’s Taxonomy
- Reading:
- MPI Tutorial, Lawrence Livermore National Lab
- Mattson, Appendix B, Patterns for Parallel Programming.
NO MATERIAL past this point is on the Midterm 2.
(24 October) Dask
Lecture 15: Dask Arrays. Data parallel and declarative programming. Execution graphs and lazy evaluation.
Activity 4: dask
notebooks. (due November 8, 2022 5:00 pm EST)
(31 October) Dask Dataframes
Lecture 16: Parallel Pandas. Slicing and Aggregation. Indexing.
(2 November) Midterm 2
(7 November) Introduction to Map/Reduce
Lecture 17: The Google Parallel computing environment, functional programming concepts applied to large-scale parallelism, text processing.
- Reading:
- J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters, OSDI, 2004
(9 November) Hadoop!
Lecture 18: Hadoop! programming, the WordCount tutorial, and the Hadoop! toolchain. Triangle counting example.
(14 November) Introduction to Spark
Lecture 19: Spark and Resilient Distributed Datasets.
- Reading:
- Zaharia et al. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing, NSDI, 2012
Activity 5: k-means in Spark (due 2 December)
(16 November) Ray: Task Programming with Remote Functions
Lecture 20: Remote functions, distributed objects, distributed memory management
- Reading: P. Moritz et al. Ray: A Distributed Framework for Emerging AI Applications. OSDI, 2018.
(21 and 23 November) No class.
(28 November) BSP, Barriers, and Ray Actors
Lecture 21: Bulk synchronous parallel, barrier synchronization, stateful distributed objects, service centers, ray.get()
as a synchronization primitive.
(5 December) Deadlock in Ray
Reading: Just for fun. Mars Pathfinder
(7 December) The Google TPU
Lecture 24: Reading: Jouppi et al. In-Datacenter Performance Analysis of a Tensor Processing Unit. ISCA, 2017.