Parallel Computing: Theory and Practice (15-897)

Instructor: Umut Acar (Office hours: by appointment)

TA: Stefan Muller (Office hours: TBD)

Communications: Piazza

Meeting times: Tuesday and Thursday, 1:30-2:50pm.

Course location: GHC 4201

Books: We will use material from the following two books

• Parallel Computing: Theory and practice (TAPP)

• Parallel algorithms book (PA)

Course Schedule

• Week 1: Multithreading, DAGs, Scheduling

  • Jan 12:

    • Introduction

    • Processors, precesses, threads

    • Multithreading: DAGs, work and span, scheduling, coding, parallelism versus concurrency

    • Preliminaries for the PA book: PA: SPARC

  • Jan 14:

    • Multithreading: scheduling, coding, parallelism versus concurrency

    • Fork-join parallelism

    • Critical sections, atomic instructions

    • Maximum-subsequence-sum problem

• Week 2: Algorithm Design for Sequences

  • Jan 19:

    • Sequences: PA: Sequences

    • Parallel-Algorithm Design Techniques:

      • PA: Divide and conquer

      • PA: Contraction

  • Jan 21:

    • Introduction to PASL

    • Work efficiency and granularity control

• Week 3: Parallel Arrays, Searching, and Sorting

  • Jan 26:

    • Parallel arrays: sequences in practice

  • Jan 28

    • Parallel quicksort

• Week 4: Sorting

  • Feb 2:

    • PA: Partitioning

    • Parallel mergesort

  • Feb 4:

    • No class

• Week 5: Online Scheduling and Work Stealing

  • Feb 9:

    • Background Reading: PA: Probabilities and expectations

    • Online scheduling

    • Example: scheduling fork-join programs

    • Work stealing

  • Feb 11:

    • Work stealing and its structural lemma

    • Balls and Bins Lemma

• Week 6: Trees and Parallel Tree Contraction

  • Feb 16: Work stealing analysis

  • Feb 18:

    • Basic graph terminology

    • Trees and tree contraction

• Week 7: Trees and Parallel Tree Contraction

  • Feb 23: Applications of tree contraction

  • Feb 25: Analysis of tree contraction

• Week 8: Parallel Sets and Tables

  • March 1:

    • PA: Binary search trees

  • March 3:

    • PA: Sets and Tables

• Week 9: Spring Break

• Week 12:

  • March 29: Models of Parallel Computation

    • Async-Finish

    • Futures

    • PRAM

  • March 31: Graphs and Parallel BFS

• Week 13: Parallel BFS and DFS

  • April 5: Parallel Unordered Depth-First Search

  • April 7: Parallel Unordered Depth-First Search

• Week 14: Graph Contraction

  • April 12: Graph Contraction

  • April 14: Carnival

• Week 15:

  • April 19: Graph Contraction

  • April 21: Project Presentations

• Week 16:

  • April 26: Project Presentations

  • April 28: Project Presentations

• Week 17:

  • May 5: Project Presentations (NSH 4201)

Administration

There will be several assignments, one midterm exam, and one final. Participation in class accounts for 25% of your grade. Participation includes actual participation in class + discussions on piazza + feedback on the TAPP notes (submitted via github). For example, if you participate less in class, you can make up for that by submitting feedback on the book.