Instructor: Umut Acar (Office hours: by appointment)TA: Stefan Muller (Office hours: TBD)Communications: PiazzaMeeting times: Tuesday and Thursday, 1:30-2:50pm.Course location: GHC 4201Books: We will use material from the following two booksCourse 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:
**Week 2: Algorithm Design for Sequences**- Jan 19:
- Sequences: PA: Sequences
- Parallel-Algorithm Design Techniques:
- Jan 21:
**Week 3: Parallel Arrays, Searching, and Sorting****Week 4: Sorting**- Feb 2:
- 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:
**Week 6: Trees and Parallel 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:
- March 3:
**Week 9: Spring Break****Week 12:**- March 29: Models of Parallel Computation
- March 31: Graphs and Parallel BFS
**Week 13: Parallel BFS and DFS****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)
AdministrationThere 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. |