M6: Advanced Parallel Scheduling Techniques

In this sixth module, we will begin to look at more ways to dynamically distribute work to threads in a parallel program. Specifically, we will look at the futures, work dealing and stealing algorithms.

Pre-recorded Lectures

Note: The pre-recorded videos for M6 will be posted after Wednesday’s lecture.

The pre-recorded lectures are available here: M6 Videos. You can also find the videos under the “Panopto” tab on the MPCS 52060 canvas site.

The lectures are a series of approx 20-30 minute videos divided into the following sections:

Week 7

No videos this week. Study for your exam.

Week 8

  • 6.1: Work Distribution (Dealing & Stealing)

  • 6.2: Work-Stealing and ABA Problem

  • 6.3: Work Stealing Algorithm

Week 9

  • 6.4: Bulk synchronous parallel (BSP) model

  • 6.5: Parallel computation in Python and C

The slides/code presented in these videos are accessible in the upstream repository under the m6/resources directory. Please reachout to me if you do not have access to this repository.

Resources/Readings

  • The Art of Multiprocessor Programming readings:

    • Ch. 16.1, 16.4, 16.5

Synchronous Session (In-person Lecture)

As a reminder here are the dates and times for the synchronous session for this module:

Week 7

  • Dates/Times

    • Wednesday May 1st @ 5:30pm-7:20pm

  • Session Outline

    • Thread Pools and Futures

    • Work Distribution (Dealing & Stealing)

    • Work Stealing and ABA Problem [if time permits]

Week 9

  • Dates/Times

    • Wednesday May 15th @ 5:30pm-7:20pm

  • Session Outline

    • Work Balancing

    • Data Parallelism (Map/Reduce)

    • Barriers [if time permits]

Check the upstream repository at the start of class to retrieve the code snippets that will be discussed in the synchronous session.

Assignment

Assignments are always due on Thursday evenings.