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 named activities/activity1.ipynb
  • 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.

(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

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

(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.

(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.

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

(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.

(16 December) Final Exam. 9am-12pm.