cs431

KAIST CS431: Concurrent Programming

Logistics

• Instructor: Jeehoon Kang

• Time: Mon & Wed 13:00-14:15 (2024 Spring)

• Place

  • Rm. 1101, Bldg. E3-1. YOUR PHYSICAL ATTENDANCE IS REQUIRED unless announced otherwise.
  • Zoom room (if remote participation is absolutely necessary). The passcode is announced at KLMS.
  • Youtube channel. Turn on English subtitles on YouTube, if necessary.

• Websites: https://github.com/kaist-cp/cs431, https://gg.kaist.ac.kr/course/19

• Announcements: in the issue tracker

  • We assume that you will read each announcement within 24 hours.
  • We strongly recommend you watch the repository.

• TA: Sunho Park (Head TA), Janggun Lee.

  • Office Hours: Fri 9:15-10:15, Rm. 4432, Bldg. E3-1. If you want to come, do so by 9:30. See below for the office hour policy.

• IMPORTANT: you should not expose your work to others. In particular, you should not fork the upstream and push there.

Course description

Context

I anticipate that in the next 700 years, computers will be massively parallel. Humankind seeks to enhance computer performance in the era of big data. This goal has become increasingly challenging following the breakdown of Dennard scaling around 2005, indicating that the performance of sequential computers is unlikely to improve further. Consequently, both servers and personal computers have adopted multi-core systems. This challenge is compounded by the end of Moore's Law, which signifies our diminishing ability to benefit from denser electronic circuits. It appears that the primary pathway to optimizing performance now lies in specialization, focusing on exploiting the parallelism in workloads. Due to these technological trends, I foresee that future computers will be massively parallel.

However, we are not yet fully equipped for the era of massive parallelism. The principal challenge is managing shared mutable states, a key aspect of concurrency. Coordinating multiple cores and resources requires their inputs and outputs to be synchronized through shared mutable states like memory. Yet, managing these states is inherently difficult, both in theory and practice. For instance, with thousands or millions of cores, how can we efficiently synchronize concurrent access to shared memory? In the face of nondeterministic thread execution interleaving, how can we ensure the safety of a concurrent program? And considering compiler and hardware optimizations, what constitutes the correct specification of a concurrent data structure?

Fortunately, in the past ten years, the theory of shared mutable states has made significant advances, greatly facilitating the design and analysis of practical systems utilizing these states. Therefore, in this course, we will explore recent theories of shared mutable states and their application in real-world systems.

Goal

This course is designed for senior undergraduate or graduate students in computer science and related disciplines who have an interest in the contemporary theory and practice of parallel computer systems. The course aims to equip students with the ability to:

• Understand the motivations and challenges of concurrent programming.
• Learn design patterns and principles for reasoning in concurrent programming.
• Design, implement, and evaluate concurrent programs.
• Apply their knowledge to real-world parallel systems.

Textbook

• Slides
• Code Documentation
• References
  • The Art of Multiprocessor Programming
  • The Crossbeam Library Documentation
  • Concurrent reference counting algorithm (TBA)
  • Behaviour-Oriented Concurrency
  • C++ Concurrency in Action
  • Rust Atomics and Locks

Prerequisites

• It is strongly recommended that students have completed courses in:

  • Mathematics (MAS101): Propositional logic and proof techniques.
  • Data Structures (CS206): Understanding of linked lists, stacks, and queues.
  • Systems Programming (CS230) or Operating Systems (CS330): Familiarity with memory layout, caching, and locking mechanisms.
  • Programming Principles (CS220) or Programming Languages (CS320): Knowledge of lambda calculus and interpreters.

  A solid foundation in these areas is crucial for success in this course.

• Other recommended knowledge that will be beneficial:

  • Basic understanding of Computer Architecture (CS311).
  • Programming experience in Rust.

Schedule

• week 1: CS230/CS330 review on concurrent programming
• week 2: Rust
• week 3: lock-based concurrency (API)
• week 4: lock-based concurrency (implementation 1)
• week 5: lock-based concurrency (implementation 2)
• week 6: lock-based concurrency (application)
• week 7: behavior-oriented concurrency (API)
• week 8: midterm exam
• week 9: lock-free concurrency (concept)
• week 10: lock-free concurrency (data structures 1)
• week 11: lock-free concurrency (data structures 2)
• week 12: lock-free concurrency (data structures 3)
• week 13: lock-free concurrency (specification)
• week 14: lock-free concurrency (garbage collection)
• week 15: behavior-oriented concurrency (implementation)
• week 16: final exam

Tools

Ensure you are proficient with the following development tools:

• Git: Essential for downloading homework templates and managing your development process. If you're new to Git, please complete this tutorial.

  • Follow these steps to set up your repository:

    • Clone the upstream repository directly without forking it:

      $ git clone --origin upstream [email protected]:kaist-cp/cs431.git
      $ cd cs431
      $ git remote -v
      upstream    [email protected]:kaist-cp/cs431.git (fetch)
      upstream    [email protected]:kaist-cp/cs431.git (push)
      

    • To receive updates from the upstream, fetch and merge upstream/main:

      $ git fetch upstream
      $ git merge upstream/main
      

  • For managing your development on a Git server, create a private repository:

    • Upgrade to a "PRO" GitHub account, available at no cost. See the documentation.
    • Configure your repository as a remote:

      $ git remote add origin [email protected]:<github-id>/cs431.git
      $ git remote -v
      origin     [email protected]:<github-id>/cs431.git (fetch)
      origin     [email protected]:<github-id>/cs431.git (push)
      upstream [email protected]:kaist-cp/cs431.git (fetch)
      upstream [email protected]:kaist-cp/cs431.git (push)
      

    • Push your work to your repository:

      $ git push -u origin main
      

• Rust: The programming language for homework assignments. Rust's ownership type system significantly simplifies the development of large-scale system software.

• ChatGPT or other Large Language Models (LLMs) (optional): Useful for completing your homework.

  • In an AI-driven era, learning to effectively utilize AI in programming is crucial. Homework difficulty is adjusted assuming the use of ChatGPT 3.5 or an equivalent tool.

• Visual Studio Code (optional): Recommended for developing your homework, although you may use any editor of your preference.

• Single Sign On (SSO): Use the following SSO credentials to access gg and the development server:

  • id: KAIST student id (8-digit number)
  • email: KAIST email address (@kaist.ac.kr)
  • password: Reset it here: https://auth.fearless.systems/if/flow/default-recovery-flow/
  • Log in to gg using the "kaist-cp-class" option, and to the development server using the "OpenID Connect" option.

• Development Server:

  • IMPORTANT: Do not attempt to hack or overload the server. Please use it responsibly.
  • Create and connect to a workspace to use the terminal or VSCode (after installation).
  • We recommend using VSCode with the "Rust Analyzer" and "CodeLLDB" plugins.

Grading & Honor Code

Cheating

IMPORTANT: READ CAREFULLY. THIS IS A SERIOUS MATTER.

• Sign the KAIST CS Honor Code for this semester. Failure to do so may lead to expulsion from the course.

• We will employ sophisticated tools to detect code plagiarism.

  • Search for "code plagiarism detector" on Google Images to understand how these tools can identify advanced forms of plagiarism. Do not attempt plagiarism in any form.

Programming Assignments (60%)

• All assignments will be announced at the start of the semester.
• Submit your solutions to https://gg.kaist.ac.kr/course/19.
• Refer to the documentation at https://kaist-cp.github.io/cs431/cs431_homework/.
• You are permitted to use ChatGPT or other LLMs.

Midterm and Final Exams (40%)

• Dates & Times: April 15th (Mon), June 10th (Mon), 13:00-15:00

• Location: Room 2443, Building E3-1, KAIST

• Physical attendance is required. If necessary, online participation via Zoom will be accommodated.

• You are expected to bring your own laptop. Laptops can also be borrowed from the School of Computing Administration Team.

Attendance (?%)

• A quiz must be completed on the Course Management website for each session (if any). Quizzes should be completed by the end of the day.

• Failing to attend a significant number of sessions will result in an automatic grade of F.

Communication

Registration

• Ensure your ability to log into the lab submission website.
  • Use your kaist-cp-class account for login.
  • Your ID is your @kaist.ac.kr email address.
  • Reset your password here: https://auth.fearless.systems/if/flow/default-recovery-flow/
  • Contact the instructor if login issues arise.

Rules

• Course-related announcements and information will be posted on the course website and the GitHub issue tracker. It is expected that you read all announcements within 24 hours of their posting. Watching the repository is highly recommended for automatic email notifications of new announcements.

• Questions about course materials and assignments should be posted in the course repository's issue tracker.

  • Avoid sending emails to the instructor or TAs regarding course materials and assignments.
  • Research your question using Google and Stack Overflow before posting.
  • Describe your question in detail, including:
    • Environment (OS, gcc, g++ version, and other relevant program information).