KAIST CS431: Concurrent Programming

Logistics

• Instructor: Jeehoon Kang
• Time: Mon & Wed 1:00pm-2:15pm
• Place
  • Rm. 102, Bldg. N1. 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 subtitle at YouTube, if necessary.
• Websites: https://github.com/kaist-cp/cs431, https://gg.kaist.ac.kr/course/11
• Announcements: in issue tracker
  • We assume you read each announcement within 24 hours.
  • We strongly recommend you to watch the repository.
• TA: Janggun Lee
  • Office Hour: Fri 9:00am-10:00am, Zoom room (The passcode is same as the class). It is not required, but if you want to come, do so by 9:15am. See below for 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 expect computers in the next 700 years will be massively parallel. We the humankind want to improve the performance of computers in the era of big data. But it is becoming more and more challenging after the breakdown of Dennard scaling around 2005, which means the performance of sequential computers will not be improved. Thus not only servers but also personal computers have been multi-core systems since then. The problem is only worsened by the ending of the Moore's law, which means we are no longer able to benefit from denser electrical circuit. It seems the only remaining way to optimize performance is specialization, which aims to better exploit parallelism of workloads. Because of these technology trends, I expect computers in the future will be massively parallel.

But we are not ready yet for the era of massive parallelism. The main difficulty lies on handling shared mutable states, which is the main topic of concurrency. To coordinate multiple cores and other resources, their inputs and outputs should be somehow properly synchronized with each other via shared mutable states like memory. But handling shared mutable states is inherently challenging, both theoretically and practically. For example, in the presence of thousands and millions of cores, how to efficiently synchronize concurrent accesses to shared memory? In the presence of nondeterministic interleaving of thread executions, how to make sure the safety of a concurrent program? In the presence of compiler and hardware optimizations, what is the right specification of a concurrent data structure?

Fortunately, the theory of shared mutable states has advanced quite impressively in the past ten years, which makes it greatly more comfortable in designing and analyzing practical systems with shared mutable states. So in this course, we will discuss the recent theory of shared mutable states and its application to real-world practical systems.

Goal

This course is geared towards senior undergraduate (or graduate) students in computer science (or related disciplines) who are interested in the modern theory and practice of parallel computer systems. This course aims to help such students to:

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

Textbook

• Slides

• Classical papers and libraries

  • Promising semantics: programming language & architecture semantics for shared-memory concurrency
  • Crossbeam: concurrent data structure library written in Rust

Prerequisites

• It is strongly recommended that students already took courses on:

  • Mathematics (MAS101): proposition statement and proof
  • Data structures (CS206): linked list, stack, queue
  • Systems programming (CS230) or Operating systems (CS330): memory layout, cache, lock
  • Programming principles (CS220) or Programming languages (CS320): lambda calculus, interpreter

  Without a proper understanding of these topics, you will likely struggle in this course.

• Other recommendations which would help you in this course:

  • Basic understanding of computer architecture (CS311)
  • Programming experience in Rust

Tools

Make sure you're capable of using the following development tools:

• Git: for downloading the homework skeleton and version-controlling your development. If you're not familiar with Git, walk through this tutorial.

  • Please do the following steps to set up your repository:

    • Directly clone the upstream 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 get updates from the upstream, fetch and merge upstream/main.

      $ git fetch upstream
      $ git merge upstream/main

  • If you want to manage your development in a Git server, please create your own private repository.

    • You may upgrade your GitHub account to "PRO", which is free of charge. Refer to the documentation.

    • Set up 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 to your repository.

      $ git push -u origin main

• Rust: as the language of homework implementation. We chose Rust because its ownership type system greatly simplifies the development of large-scale system software.

  We recommend you to read this page that describes how to study Rust.

• Visual Studio Code (optional): for developing your homework. If you prefer other editors, you're good to go.

• You can connect to server by ssh s<student-id>@cp-service.kaist.ac.kr -p13002, e.g., ssh [email protected] -p13002.

  • IMPORTANT: Don't try to hack. Don't try to freeze the server. Please be nice.

  • Your initial password will be announced at https://gg.kaist.ac.kr.

  • I require you to register public SSH keys to the server. (In September, we'll expire your password so that you can log in only via SSH keys.) See this tutorial for more information on SSH public key authentication. Use ed25519.

  • In your client, you may want to set your ~/.ssh/config as follows for easier SSH access:

    Host cs431
      Hostname cp-service.kaist.ac.kr
      Port 13002
      User s20071163
    

    Then you can connect to the server by ssh cs431.

  • Now you can use it as a VSCode remote server as in the video.

  • Install rustup in the server to begin working on Rust!

  • NOTE: We recommend the rust-analyzer plugin instead of rls.

  • NOTE: If permission denied error occurs when trying to install CodeLLDB Extension into the remote server, please follow the steps:

    1. Download this file at the remote server.
    2. Follow the instructions to install it.

  • NOTE: If you cannot connect to the remote server via VSCode with fail to create hard link error message, please follow the steps:

    1. Close VSCode window and try to connect to the remote server via terminal(or cmd). If you encounter Connection timed out error message, try again after a few minutes.
    2. Delete all the files in ~/.vscode-server/bin/.

Grading & honor code

Cheating

IMPORTANT: PAY CLOSE ATTENTION. VERY SERIOUS.

• Please sign the KAIST CS Honor Code for this semester. Otherwise, you may be expelled from the course.

• We will use sophisticated tools for detecting code plagiarism​.

  • Google "code plagiarism detector" for images and see how these tools can detect "sophisticated" plagiarisms. You really cannot escape my catch. Just don't try plagiarism in any form.

Programming assignments (60%)

For details, see https://gg.kaist.ac.kr/course/11.

Midterm and final exams (40%)

• Date & Time: TBA (midterm) and TBA (final), 13:00pm-15:45pm (or shorter, TBA)

• Place: Rm. 102, Bldg. N1, KAIST

  • If online participation is absolutely necessary, we'll use Zoom.

Attendance (?%)

• You should solve a quiz on the Course Management](https://gg.kaist.ac.kr/course/11) website for each session. You should answer the quiz by the end of the day.

• If you miss a significant number of sessions, you'll automatically get an F.

Communication

Registration

• Make sure you can log in the lab submission website.

  • Reset your password here: https://gg.kaist.ac.kr/accounts/password_reset/ The email address is your @kaist.ac.kr address.

  • The id is your student id (e.g., 20071163).

  • Log in with your student id and the new password. If you cannot, please contact the head TA in the chat.

Rules

• Course-related announcements and information will be posted on the website as well as on the GitHub issue tracker. You are expected to read all announcements within 24 hours of their being posted. It is highly recommended to watch the repository so that new announcements will automatically be delivered to your email address.

• Ask questions on course materials and assignments in this repository's issue tracker.

  • Don't send emails to the instructor or TAs for course materials and assignments.

  • Before asking a question, search for it in Google and Stack Overflow.

  • Describe your question in as much detail as possible. It should include the following things:

    • Environment (OS, gcc, g++ version, and any other related program information).
    • Command(s) that you used and the result. Any logs should be formatted in code. Refer to this.
    • Any directory or file changes you've made. If it is the solution file, just describe which part of the code is modified.
    • Googling result. Search before asking, and share the keyword used for searching and what you've learned from it.

  • Give a proper title to your issue.

  • Read this for more instructions.

  • I'm requiring you to ask questions online first for two reasons. First, clearly writing a question is the first step to reaching an answer. Second, you can benefit from the questions and answers of other students.

• Ask your questions via email only if they are either confidential or personal. Any questions failing to do so (e.g. email questions on course materials) will not be answered.

• We are NOT going to discuss new questions during office hours. Before coming to the office hour, please check if there is a similar question on the issue tracker. If there isn't, file a new issue and start a discussion there. The agenda of the office hour will be the issues that are not resolved yet.

• Emails to the instructor or the head TA should begin with "CS431:" in the subject line, followed by a brief description of the purpose of your email. The content should at least contain your name and student number. Any emails failing to do so (e.g. emails without student number) will not be answered.

• If you join the session remotely from Zoom (https://kaist.zoom.us/my/jeehoon.kang), your Zoom name should be <your student number> <your name> (e.g., 20071163 강지훈). Change your name by referring to this.

• This course is conducted in English. But you may ask questions in Korean. Then I will translate it into English.

Ignore

1830eaed90e5986c75320daaf131bd3730b8575e866c4e92935a690e7c2a0717