Apache Spark

Disks

Buffers

Computer file

Pages

Records

B+ Trees

Indices & B+ TreeRefinements

Buffer Management

Relational Algebra

Sorting & Hashing

Iterators & Joins

Query Optimization

Transactions

Concurrency

DB Design: Entity-Relationship Models

DB Design: FDs and Normalization

Recovery

Parallel Query Processing

Distributed Transactions

NoSQL

MapReduce

CS 186 Introduction to Database Systems UC Berkeley Spring 2023 This project-heavy course covers access methods, data models, query languages, database services, and interfaces. It introduces transaction processing and requires CS 61A, CS 61B, and CS 61C as prerequisites/corequisites. It suggests proficiency in Java for project work. Access methods and file systems to facilitate data access. Hierarchical, network, relational, and object-oriented data models. Query languages for models. Embedding query languages in programming languages. Database services including protection, integrity control, and alternative views of data. High-level interfaces including application generators, browsers, and report writers. Introduction to transaction processing. Database system implementation to be done as term project.  We will expect students to have taken CS 61A, CS 61B, and CS 61C. CS61A/B will be enforced as a prerequisite, and CS61C will be enforced as a corequisite. This class is project-heavy, and there will almost always be a project assigned to you throughout the semester. Students have noted an increase in difficulty compared to offerings of this course predating Fall 2018. We expect proficiency with Java (around the level taught in CS 61B) in order to work on the projects, with the exception of Project 1. Projects vary in difficulty. You can find more information about them in the Projects section below. There is no required textbook for this class, and we will not be assigning required readings. However, if you would like to use a textbook while in this class, we recommend the following:

- [Database Management Systems](http://pages.cs.wisc.edu/~dbbook/), 3rd Edition, by Ramakrishnan and Gehrke (Former official textbook of this class)

- [Database Systems Concepts](https://www.db-book.com/), 6th Edition, by Silberschatz, Korth and Sudarshan

- [Database Systems: The Complete Book](http://infolab.stanford.edu/~ullman/dscb.html), 2nd Edition, by Garcia-Molina, Ullman, and Widom (Previously used by Prof. Cheung)

Note that exams and all other aspects of the course will center on material as covered in the lectures, so defer to course material if there are any discrepancies with the textbook(s) you are using.

If you want to try to target your reading to the topics of this class, reading assignments from previous offerings of CS 186 for the Database Management Systems textbook can be found [here](https://docs.google.com/spreadsheets/d/1JfrHl8hn8-iMqL2se4SYS0lxQyiwz54YIATFXuzaPlA/edit?usp=sharing). Reading assignments from a database class taught at a different university by Prof. Cheung for Database Systems: The Complete Book can be found [here](https://courses.cs.washington.edu/courses/cse414/18sp/calendar/lecturelist.html), although the topics taught in that class differ from those taught in this class.

CS 186 Introduction to Database Systems

Database Systems

Lock (computer science)

Parallel computing

Parallel efficiency

Multi-core processor

SIMD (Single Instruction, Multiple Data)

Multithreading

Latency

Bandwidth (computing)

ISPC (Intel SPMD Program Compiler)

Work Stealing

Message Passing

Asynchronous Communication

Pipelining

Arithmetic Intensity

Contention

GPU Architecture

CUDA (Compute Unified Device Architecture)

Data Parallelism

Prefix Sum

Resilient Distributed Dataset (RDD)

Cache coherence

MSI Protocol

MESI Protocol

False Sharing

Memory Consistency

Non-blocking algorithm

Transactional memory

Software Transactional Memory (STM)

Hardware Transactional Memory (HTM)

Energy-Efficient Computing

Heterogeneous Computing

Fixed-function

Field-Programmable Gate Array (FPGA)

System on a Chip (SoC)

Domain-Specific Language (DSL)

Halide (programming language)

Graph Processing

DRAM (Dynamic Random-Access Memory)

Reconfigurable Computing

Deep Neural Network

Matrix Multiplication

Layer Fusion

TensorCore

Tensor Processing Unit (TPU)

CS 149 PARALLEL COMPUTING Stanford University  Fall 2022 Focused on principles and trade-offs in designing modern parallel computing systems, this course also teaches parallel programming techniques. It is intended for students looking to understand both parallel hardware and software design. Prerequisite knowledge in computer systems is required. From smart phones, to multi-core CPUs and GPUs, to the world's largest supercomputers and web sites, parallel processing is ubiquitous in modern computing. The goal of this course is to provide a deep understanding of the fundamental principles and engineering trade-offs involved in designing modern parallel computing systems as well as to teach parallel programming techniques necessary to effectively utilize these machines. Because writing good parallel programs requires an understanding of key machine performance characteristics, this course will cover both parallel hardware and software design.  [CS110: Principles of Computer Systems](http://web.stanford.edu/class/cs110/) is strong prerequisite for CS149. If you have not taken CS110 and feel like you have the background to take CS149, please contact your friendly instructors and let's talk it over. There is no required textbook for CS149. However, you may find the following textbooks helpful. However, in general these days there's plenty of great parallel programming resources available for free on the web.

John L. Hennessy and David A. Patterson

Computer Architecture, Sixth Edition: A Quantitative Approach. Morgan Kaufmann, 2017

[[ On Amazon ]](https://www.amazon.com/Computer-Architecture-Quantitative-Approach-Kaufmann/dp/0128119055)


Jason Sanders

CUDA by Example: An Introduction to General-Purpose GPU Programming. 1st Edition. Addison-Wesley. 2010

[[ On Amazon ]](https://www.amazon.com/CUDA-Example-Introduction-General-Purpose-Programming/dp/0131387685)


David Kirk and Wen-mei Hwu

Programming Massively Parallel Processors, Second Edition: A Hands-on Approach. 2nd Edition. Morgan Kauffmann. 2012

[[ On Amazon ]](https://www.amazon.com/Programming-Massively-Parallel-Processors-Second/dp/0124159923)

CS 149 PARALLEL COMPUTING

Parallelism and Distributed Systems

System R

File system

Flash File Systems

Isolation Levels

Transactional Recovery

Practical Byzantine Fault Tolerance

Exokernel

Resource Allocation and Scheduling

Edge Computing

Distributed Storage

Column Stores

Microkernels

Spectre Attack

Unix

Bigtable

Databases

End-To-End Arguments in System Design

File System Reliability

Transaction Locking

The Byzantine Generals Problem

Google File System (GFS)

Dynamo

seL4

Virtual Machine (VM)

Peer To Peer Networks

Distributed Consensus

Security

CryptDB

CS 262a Advanced Topics in Computer Systems UC Berkeley Fall 2021 A graduate survey of systems managing computation and information. Topics include volatile and persistent memory management, system support for networking, security infrastructure, extensible systems, APIs, and large software system performance analysis. Students are expected to engage in quality systems research, culminating in a publishable group project. Graduate survey of systems for managing computation and information, covering a breadth of topics: early systems; volatile memory management, including virtual memory and buffer management; persistent memory systems, including both file systems and transactional storage managers; storage metadata, physical vs. logical naming, schemas, process scheduling, threading and concurrency control; system support for networking, including remote procedure calls, transactional RPC, TCP, and active messages; security infrastructure; extensible systems and APIs; performance analysis and engineering of large software systems. Homework assignments, exam, and term paper or project required.

The main work of this class is to read frequently and deeply, while working toward a group research project of publishable quality.  Each student will be individually responsible for writing up a short summary of every paper. There will be one midterm exam (albeit near the end), and no final exam. Research projects are a critical aspect of the course.  Your goal is to do some quality systems research; that is, to add to our understanding of how to build systems.  Research projects must be written up in a term paper, and will be presented in a poster in a departmental mini-conference.  Suggested project ideas will be provided by the instructors, but you are strongly encouraged to come up with your own project ideas.  Potential projects include implementation or analysis of some piece of an OS, a DBMS, or an Internet service; extending one of these systems with new functionality; or measurement and analysis of existing systems with the goal of better understanding issues in system design.   [CS 162](https://cs162.org/), or equivalent. There is no required textbook, but some of the papers are in [*Readings in Database Systems*](http://redbook.cs.berkeley.edu/). We will read and discuss 2-4 papers per week. Likely all of the papers will be available online.

General information: ISBN-10: 0-262-69314-3, ISBN-13: 978-0-262-69314-1

Link to MIT press site: [Readings in Database Systems, 4th Edition](http://mitpress.mit.edu/catalog/item/default.asp?tid=10480&ttype=2)

CS 262a Advanced Topics in Computer Systems

Computer Systems

Frequent Itemsets Mining

Locality-Sensitive Hashing

Clustering

Dimensionality Reduction

Recommender Systems

PageRank

Community Detection in Graphs

Graph Representation Learning

Graph neural network (GNN)

Learning Embeddings

Decision Trees

Mining Data Streams

Matrix Sketching

Computational Advertising

Learning through Experimentation

Optimizing Submodular Functions

CS246: Mining Massive Data Sets Stanford University Spring 2023 This course focuses on data mining and machine learning algorithms for large scale data analysis. The emphasis is on parallel algorithms with tools like MapReduce and Spark. Topics include frequent itemsets, locality sensitive hashing, clustering, link analysis, and large-scale supervised machine learning. Familiarity with Java, Python, basic probability theory, linear algebra, and algorithmic analysis is required. ### What is this course about? [[Info Handout](https://web.stanford.edu/class/cs246/handouts/CS246_Info_Handout.pdf)]

The course will discuss data mining and machine learning algorithms for analyzing very large amounts of data. The emphasis will be on MapReduce and [Spark](http://spark.apache.org/) as tools for creating parallel algorithms that can process very large amounts of data.

**Topics include**: Frequent itemsets and Association rules, Near Neighbor Search in High Dimensional Data, Locality Sensitive Hashing (LSH), Dimensionality reduction, Recommendation Systems, Clustering, Link Analysis, Large-scale Supervised Machine Learning, Data streams, Mining the Web for Structured Data, Web Advertising.  Students are expected to have the following background:

- Knowledge of basic computer science principles and skills, at a level sufficient to write a reasonably non-trivial computer program (e.g., CS107 or CS145 or equivalent are recommended).
- Good knowledge of Java and Python will be extremely helpful since most assignments will require the use of Spark.
- Familiarity with basic probability theory (CS109 or Stat116 or equivalent is sufficient but not necessary).
- Familiarity with writing rigorous proofs (at a minimum, at the level of CS 103).
- Familiarity with basic linear algebra (e.g., any of Math 51, Math 103, Math 113, CS 205, or EE 263 would be much more than necessary).
- Familiarity with algorithmic analysis (e.g., CS 161 would be much more than necessary). ### Reference Text

The following text is useful, but not required. It can be downloaded for free, or purchased from Cambridge University Press.

[Leskovec-Rajaraman-Ullman: Mining of Massive Dataset](http://www.mmds.org/)

CS246: Mining Massive Data Sets

Machine Learning

The Internet

Classical synchronization

Time Synchronization

Distributed Mutual Exclusion

Remote Procedure Call (RPC)

Distributed File Systems

Concurrency Control

Logging and Crash Recovery

Fault Tolerance

RAID (Redundant Array of Inexpensive Disks)

Distributed Replication

Distributed Databases

Spanner

Apache Hadoop Distributed File System (HDFS)

Data-Intensive Computing

Hadoop

In-memory cluster compute

Distributed ML

Internet Content Delivery

DNS (Domain Name System)

Content Delivery Network (CDN)

Publish-Subscribe

Kafka

Virtualization

3-tier Web Service Architecture

Security Protocols

Byzantine Fault Tolerance

P2P Network

Distributed Ledgers

Blockchain

 15-440 Distributed Systems Carnegie Mellon University Fall 2020 A course offering both theoretical understanding and practical experience in distributed systems. Key themes include concurrency, scheduling, network communication, and security. Real-world protocols and paradigms like distributed filesystems, RPC, MapReduce are studied. Course utilizes C and Go programming languages. Most software is now distributed in some sense. This course is meant to serve as an introduction to distributed systems, emphasizing techniques for creating functional, usable, and high-performance distributed systems.

This course aims to: (1) provide students with an understanding of the principles and techniques behind the design of distributed systems, such as locking, concurrency, scheduling, and communication across the network. (2) provide students with practical experience designing, implementing, and debugging real distributed systems.

Major themes covered in this course include scarcity, scheduling, concurrency and concurrent programming, naming, abstraction and modularity, imperfect communication and other types of failure, protection from accidental and malicious harm, optimism, and the use of instrumentation and monitoring and debugging tools in problem solving. As the creation and management of software systems is a fundamental goal of any undergraduate systems course, students will design, implement, and debug large programming projects. After this course, students will have learned to…

- Implement and structure distributed systems programs.
- Write programs that can interoperate using well-defined protocols.
- Debug highly concurrent code that spans multiple programs running on multiple cores and machines.
- Reason about distributed algorithms for locking, synchronization and concurrency, scheduling, and replication.
- Use standard network communication primitives such as UDP and TCP.
- Understand the general properties of networked communication necessary for distributed systems programming in clusters and on the Internet.
- Employ and create common paradigms for easing the task of distributed systems programming, such as distributed filesystems, RPC, and MapReduce. Be able to clearly elucidate their benefits, drawbacks, and limitations.
- Identify the security challenges faced by distributed systems programs.
- Be able to select appropriate security solutions to meet the needs of commonly encountered distributed programming scenarios. Because this course has a big project component, you must be proficient in C and programming on UNIX systems. We will use the [Go programming language](https://golang.org/) throughout the term. It is required that you have taken 15-213 and gotten a “C-“ or higher since many of the programming skills you will need are taught in that course. **However, if you received a C in 15-213, you must meet with your academic advisor to discuss your background before taking 15-440/640, perhaps taking an additional course to sharpen your systems skills. Your advisor must email us approval and an explanation of why you have sufficient background to take 15-440/640.** 

 15-440 Distributed Systems

Floating Point

RISC-V Procedures

Loader

RISC-V Single-Cycle Datapath

Caches - Multilevel

Parallelism

Translation Lookaside Buffer (TLB)

Amdahl's law

Virtual memory

RISC-V Instruction Formats

Combinational Logic

RISC-V Single-Cycle Control

Caches - Set-associative

Thread-level Parallelism

Page faults

Virtual memory performance

Data-level parallelism

Data center

Assembly language

Number Representation

RISC-V

Compiler

Synchronous Digital Systems (SDS) State

RISC-V 5-Stage Pipeline

Performance with Caches

OpenMP

Multilevel

Dependability

Warehouse-scale Computing

Input/output

C (programming language)

RISC-V Data Transfer

Assembler

Finite State Machine (FSM)

Hazards

Flynn taxonomy

Interrupts

Parity

C Memory (Mis)Management

RISC-V Decision Making Logical Ops

Linker

Combinational Logic Blocks

Caches - Direct Mapped

Single instruction, multiple data (SIMD)

Performance

Exception handling

Error-correcting Codes (ECC)

CS 61C Great Ideas in Computer Architecture (Machine Structures) UC Berkeley Fall 2022 This course deepens students' understanding of computer architecture and the translation of high-level programs into machine language. Emphasis is on C and assembly language programming, computer organization, parallelism, CPU design, and warehouse-scale computing. Prerequisites include CS61A and CS61B or equivalent C-based programming experience. [Official Academic Guide course description](https://classes.berkeley.edu/content/2022-fall-compsci-61c-001-lec-001)

The subjects covered in this course include C and assembly language programming, translation of high-level programs into machine language, computer organization, caches, performance measurement, parallelism, CPU design, warehouse-scale computing, and related topics.  CS61A and CS61B (or equivalents) or experience with a C-based programming language (e.g. Java, C++). There is no official textbook for this class. However, there are three optional textbooks as additional references:

- **P&H**: Second edition of Patterson and Hennessy's *Computer Organization and Design RISC-V Edition* book ("P&H"), ISBN 0128122757.
- **K&R**: *The C Programming Language, Second Edition* by Kernighan and Ritchie. Other C programming books are also suitable if you are already comfortable with them, but our lectures will be based on K&R.
- **WSC**: *The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines*, which is freely available [on our website](https://inst.eecs.berkeley.edu/~cs61c/resources/WSCBarrosoHolzle.pdf).

Please contact staff on Ed if you have trouble finding or paying for these textbooks.

CS 61C Great Ideas in Computer Architecture (Machine Structures)