Matrix Multiplication

Memory hierarchy

Shared Memory Parallelism

Roofline and Performance Modeling

Sources of Parallelism and Locality

Communication-avoiding matrix multiplication

Data Parallel Algorithms

CUDA (Compute Unified Device Architecture)

Graphics Processor (GPU)

Distributed Memory Machines and Programming

Advanced MPI

Collective Communication Algorithms

UPC++: Partitioned Global Address Space Languages

Domain Specific Languages (Halide)

Distributed Data Structures (BCL)

Parallel Matrix Multiply

Dense Linear Algebra

Sparse-Matrix-Vector-Multiplication

Iterative Solvers

Structured Grids

Machine learning

Supervised learning

Deep learning

Unsupervised learning

Graph Partitioning

Fast Fourier transform

Graph Algorithms

Cloud Computing

Big Data Processing

High Performance Computing (HPC)

Dynamic Load Balancing

Hierarchical Methods for the N-Body Problem

Sorting algorithm

Search algorithm

Computational Biology

Quantum Computing

CS 267: Applications of Parallel Computers UC Berkeley Spring 2020 The course addresses programming parallel computers to solve complex scientific and engineering problems. It covers an array of parallelization strategies for numerical simulation, data analysis, and machine learning, and provides experience with popular parallel programming tools. CS267 was originally designed to teach students how to program parallel computers to efficiently solve challenging problems in science and engineering, where very fast computers are required either to perform complex simulations or to analyze enormous datasets. CS267 is intended to be useful for students from many departments and with different backgrounds, although we will assume reasonable programming skills in a conventional (non-parallel) language, as well as enough mathematical skills to understand the problems and algorithmic solutions presented. CS267 satisfies part of the course requirements for the Designated Emphasis ("graduate minor") in [Computational Science and Engineering](http://www.google.com/url?q=http%3A%2F%2Fcitris-uc.org%2Finitiatives%2Fdecse%2F&sa=D&sntz=1&usg=AOvVaw1fRFGvIaIYhkwE3kp4J1nf).

While this general outline remains, a large change in the computing world started in the mid 2000's: not only are the [fastest computers](http://www.google.com/url?q=http%3A%2F%2Fwww.top500.org%2F&sa=D&sntz=1&usg=AOvVaw1SiByfUjOpTR6ctURAV2Ef) parallel, but nearly all computers are becoming parallel, because the physics of semiconductor manufacturing will no longer let conventional sequential processors get faster year after year, as they have for so long (roughly doubling in speed every 18 months for many years). So all programs that need to run faster will have to become parallel programs. (It is considered very unlikely that compilers will be able to automatically find enough parallelism in most sequential programs to solve this problem.) For background on this trend toward parallelism, click [here](http://www.google.com/url?q=http%3A%2F%2Fwww.eecs.berkeley.edu%2FPubs%2FTechRpts%2F2006%2FEECS-2006-183.html&sa=D&sntz=1&usg=AOvVaw2XoPTheTzKVlyjp1G_YcM5).

Students in CS267 will get an overview of the parallel architecture space, gain experience using some of the most popular parallel programming tools, and be exposed to a number of open research questions. The lectures will also cover a broad set of parallelization strategies for applications covering numerical simulation and data analysis to machine learning.   

CS 267: Applications of Parallel Computers

Parallelism and Distributed 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

Data Parallelism

Prefix Sum

Apache Spark

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

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

Big-O notation

Integer multiplication

Master theorem

Median finding

Coefficient/value representation

Roots of unity

Topological sorting

Paths in graphs

Greedy Algorithm

Kruskal's Algorithm

Linear Programming

Simplex Algorithm

Bipartite Matching

Zero Sum Games

Search problem

Reductions

Sampling

Streaming

Arithmetic

Recurrence relation

Polynomial multiplication

Complex numbers

Fourier Transform

Depth-first search (DFS)

Strongly connected components

Single Source Shortest Paths

Dynamic programming

Algorithms to Linear Programming

Duality

Multiplicative Updates

NP-completeness

Sketching

Minimum Spanning Tree (MST)

Network flow problem

CS 170: Efficient Algorithms and Intractable Problems UC Berkeley Spring 2020 This is an introductory course to computer science theory, exploring the design and analysis of various algorithms, number theory, and complexity. The prerequisites include familiarity with mathematical induction, big-O notation, basic data structures, and programming in a standard language. CS 170 is Berkeley’s introduction to the theory of computer science. In CS 170, we will study the design and analysis of graph algorithms, greedy algorithms, dynamic programming, linear programming, fast matrix multiplication, Fourier transforms, number theory, complexity, and NP-completeness.  The prerequisites for CS 170 are CS 61B and CS70. You will need to be comfortable with mathematical induction, big-O notation, basic data structures, and programming in a standard imperative language (e.g., Java/C/Python). Another “prerequisite” for doing well in the course is [mathematical maturity](https://en.wikipedia.org/wiki/Mathematical_maturity), or the ability to think about and work with proof-based math (which CS70 can help build). The required textbook is [Algorithms](http://cseweb.ucsd.edu/~dasgupta/book/index.html) by Dasgupta, Papadimitriou, and Vazirani, also known as DPV. Most readings will be from the textbook, and the relevant textbook chapters will be linked for each lecture. Any readings not from the textbook will be freely available as notes.

CS 170: Efficient Algorithms and Intractable Problems

Data Structures and Algorithms

Theoretical Computer Science