FALL 2018
15-848: Practical information and coding theory for computer systems
Instructor: Rashmi Vinayak
Time: M-W 1:30PM - 2:50PM;
starting Sept. 5, 2018 (Friday slot reserved for use only in case needed)
Location: NSH 1305 (Friday lectures, if any, will be at NSH 3002)
Units: 12
Office hours: Wednesdays 11:30 - noon and 3 - 3:30pm at GHC 9011
We will be using CMU Canvas for all communication. If you are enrolled in the course, please join the course site on Canvas here.
Description:
Emerging computing systems often operate in regimes where they are prone to failures, high variance in performance, and tight constraints on resources. This brings up the critical challenge of introducing resource-efficient redundancy at various levels of the system stack. The domain of information and coding theory (error-correcting-codes) provides many valuable tools to address this challenge, and these are increasingly finding their way into modern computer systems. In this course, we will cover practical tools from information and coding theory relevant to computer systems. Along the way, we will learn how these tools have impacted real-world systems through case studies. Coding-theoretic approach to computing often leads to insightful tradeoffs and surprising results. As such, this course should be of interest to both students interested in computer systems/networking and students interested in applied theory.
The course will be structured around lectures by the instructor and paper reading/presentations by the students with open discussions.
Grading: (tentative)
Final project with intermediate milestones (~60%), Class presentations (~15%), Homeworks (~15%), Class participation (~10%)
Pre-requisites: Basic understanding of probability (e.g., conditional probability) and basic understanding of linear algebra (e.g., matrix inverse, transpose) will be assumed. Basic understanding of computer systems will help in understanding the application context better.
Course goals:
- If you are interested in systems/networking:
This course will introduce to you to powerful practical tools from coding and information theory that are increasingly finding their ways into modern computer systems. You will be able to start using them in your research.
- If you are interested in applied theory:
This course will introduce you to modern applications of coding and information theory in emerging computing systems.
- For both systems/networking and theory students:
Coding for modern computing systems is a hot area of research. Several ideas for research projects and open problems will be discussed throughout the course.
Topics: (tentative; order of presentation may be differnt)
- Introduction to erasure and error-correcting codes and fast implementations
- Erasure codes for disk-based storage systems: classical and modern storage codes and system level tradeoffs in erasure-coded storage systems
- Codes for communication/networking including codes for multimedia communication and low-latency communication
- Basic understanding of working of LDPC codes employed in memories (e.g., DRAM)
- Codes for newer storage media such as flash devices and system-level tradeoffs in coding for distributed SSD storage systems
- Codes for reducing tail latency in distributed caching and machine learning systems
- Coded shuffle for distributed computation (e.g., for Map-Reduce/Spark)
- Basic concepts from information theory such as entropy and information
- Information theoretic tools for security and privacy in cloud storage systems
- Using machine learning to designing erasure and error-correcting-codes
- More topics will be added based on the interest of the class