M4: Concurrent Data Structures

This fourth module provides an introduction to building higher-level concurrent objects. We will first start with learning about how we can build a concurrent linked list and then move on to other common data structures such as hash tables, queues and stacks.

Pre-recorded Lectures

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

The pre-recorded lectures are available here: M4 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 4

  • 4.1 - Concurrent Objects and Concurrent Linked Lists Introduction

  • 4.2 - Coarse Grain Linked Lists

  • 4.3 - Fine Grain Synchronization

  • 4.4 - Optimistic Synchronization

Week 5

  • 4.5: Introduction to Concurrent Pools

  • 4.6: Bounded & Lock-Free Queue

  • 4.7: Lock-Free Stack

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

Resources/Readings

  • The Art of Multiprocessor Programming readings:

    • Ch. 3.1, 3.2,3.4,3.5

    • Ch. 7.5, 7.6

    • Ch. 8.1, 8.2.1, 8.5

    • Ch. 9.1, 9.2, 9.3, 9.4

Synchronous Session (In-person Lecture)

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

Week 4

  • Dates/Times

    • Wednesday April 10th @ 5:30pm-7:20pm

  • Session Outline

    • Q&A on the pre-recorded lectures

    • Synchronization primitives: semaphores, and condition variables

    • Implementations of Concurrent Linked-Lists

Week 5

  • Dates/Times

    • Wednesday April 17th @ 5:30pm-7:20pm

  • Session Outline

    • Q&A on the pre-recorded lectures

    • Lock-free lists

    • Concurrent hash tables

    • Concurrent pools [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.

  • Project #1, due Thursday April 18th at 11:59pm CDT

  • Project #2, due Thursday May 2nd at 11:59pm CDT