Memory hierarchy

Matrix Multiplication

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

Bits, Bytes, & Integers

Machine-Level Programming

Machine-Level Programming: Procedures

Design and Debugging

Linking

Virtual memory

Exceptions & Processes

System Level I/O

Concurrent Programming

Thread-Level Parallelism

Floating Point

Machine-Level Programming: Control

Machine-Level Programming: Data

Cache Memories

Code Optimization

Dynamic Memory Allocation

Exceptional Control Flow (ECF)

ECF: Signals & Nonlocal Jumps

Network Programming

Synchronization (computer science)

Future of Computing

15-213/18-213/14-513/15-513/18-613 Introduction to Computer Systems Carnegie Mellon University Fall 2019 This course provides a deep dive into the inner workings of computer systems, enhancing students' effectiveness as programmers. Topics span machine-level code, performance evaluation, computer arithmetic, memory management, and networking protocols. It serves as a foundation for advanced courses like compilers and operating systems. The ICS course provides a programmer's view of how computer systems execute programs, store information, and communicate. It enables students to become more effective programmers, especially in dealing with issues of performance, portability and robustness. It also serves as a foundation for courses on compilers, networks, operating systems, and computer architecture, where a deeper understanding of systems-level issues is required. Topics covered include: machine-level code and its generation by optimizing compilers, performance evaluation and optimization, computer arithmetic, memory organization and management, networking technology and protocols, and supporting concurrent computation.

[Course Syllabus](https://www.cs.cmu.edu/afs/cs/academic/class/15213-f19/www/syllabus/syllabus.pdf) Our aim in the course is to help you become a better programmer by teaching you the basic concepts underlying all computer systems. We want you to learn what really happens when your programs run, so that when things go wrong (as they always do) you will have the intellectual tools to solve the problem.

Why do you need to understand computer systems if you do all of your programming in high level languages? In most of computer science, we’re pushed to make abstractions and stay within their frameworks. But, any abstraction ignores effects that can become critical. As an analogy, Newtonian mechanics ignores relativistic effects. The Newtonian abstraction is completely appropriate for bodies moving at less than 0.1c, but higher speeds require working at a greater level of detail.

The following “realities” are some of the major areas where the abstractions you’ve learned in previous classes break down:

1. Int’s are not integers, Float’s are not reals. Our finite representations of numbers have significant
limitations, and because of these limitations we sometimes have to think in terms of bit-level representations.
1. You’ve got to know assembly language. Even if you never write programs in assembly, The behavior of a program cannot be understood sometimes purely based on the abstraction of a high-level language. Further, understanding the effects of bugs requires familiarity with the machine-level model.
1. Memory matters. Computer memory is not unbounded. It must be allocated and managed. Memory referencing errors are especially pernicious. An erroneous updating of one object can cause a change in some logically unrelated object. Also, the combination of caching and virtual memory provides the functionality of a uniform unbounded address space, but not the performance.
1. There is more to performance than asymptotic complexity. Constant factors also matter. There are systematic ways to evaluate and improve program performance.
1. Computers do more than execute instructions. They also need to get data in and out and they interact with other systems over networks.

By the end of the course, you will understand these “realities” in some detail. As a result, you will be prepared to take any of the upper-level systems classes at Carnegie Mellon (both CS and ECE). Even more important, you will have learned skills and knowledge that will help you throughout your career.

In detail, we set forth the following learning objectives, as activities you should be able to do after completing the course:

1. Explain common bit-level representations of numeric values (unsigned, two’s complement, floating point) and the consequent mathematical properties of arithmetic and bitlevel operations on them.
1. Recognize the relation between programs expressed in C and in assembly code, including the implementation of expressions, control, procedures, and data structures.
1. Demonstrate ability to understand basic intention of a program through its binary representation and apply these skills to debugging programs.
1. Investigate the programmer’s interaction with the underlying system through the different APIs and abstractions, including system support for process and thread control, virtual memory, and networking.
1. Analyze the consequences of imperfect system usage, such as poor memory and CPU performance, crashes, and security vulnerabilities.
1. Apply tools, both standard and self-developed, that will aid program development, including compilers, code analyzers, debuggers, consistency checkers, and profilers.
1. Apply these analytic and tool-use abilities to create reliable and efficient programs exercising the
different components of a modern computing system.
1. Understand the sources of conflict that can arise when multiple threads of execution share resources, and demonstrate the ability to use synchronization constructs to mediate those conflicts.  [Textbook](http://csapp.cs.cmu.edu/)

15-213/18-213/14-513/15-513/18-613 Introduction to Computer Systems

Computer Systems

Combinational Logic

C Pointers

Memory allocation

Digital Logic

Arithmetic Logic

C Arrays

Process (computing)

Transistors to Gates

Sequential logic

Data as Bits

Processor Datapath

Call stack

Process modeling

Software Tools

Floating Point Number Representation

Representing Data Structures

Shell (computing)

Integer Representation

Programming with Memory

Buffer overflow

Thread (computing)

CS 240 Foundations of Computer Systems Wellesley College Spring 2023 This course explores the inner workings of computers, focusing on how they execute programs. Students gain an in-depth understanding of software and hardware abstractions, ranging from programming languages to transistors. Key areas covered include computational building blocks, hardware-software interfaces, data representation, and practical system abstractions. The course also emphasizes structured reasoning about program execution and promotes skills for independent learning, critical thinking, and problem-solving in computer science. CS 240 examines how computers run programs, introducing key abstractions and implementations in software and hardware between programming languages and transistors. ## Goals

Course goals include:

- To understand how computers execute programs.
- To understand the roles of key software and hardware abstractions, their implementations, and their relation through translation and representation, including: digital logic, microarchitecture, instruction set architecture, the memory hierarchy, basics of programming language implementations, and operating system abstractions.
- To understand when and how computer system implementation impacts correctness or performance of arbitrary high-level programs.
- To become proficient in structured reasoning about the execution of programs on well-defined models, including the use of assertions and debugging tools to inspect program invariants and execution state.
- To develop foundations for further study of programming language implementation, security, computer architecture, operating systems, networks, concurrent and distributed systems, or other systems/implementation topics in computer science.
- [**To develop skills for independent learning, critical thinking, and problem-solving as a self-reliant computer scientist.**](#compact)

## Topics

The [course home page](https://cs.wellesley.edu/~cs240/s23/) hosts the working schedule. +Optional extensions are prefixed in the schedule with a plus sign. We may visit these if there is time. They are always available for your own exploration in further depth.

**Computational Building Blocks:**

- Hardware computation building blocks: 
    - Transistors, digital logic gates
    - Combinational and arithmetic logic
    - Sequential (stateful) logic
    - Overview of computer processor architecture
- Data representation fundamentals: 
    - Data representation with bits, bit-level computation
    - Number representation, arithmetic
    - The memory model, pointers, and arrays in the C language
    - Assertions, debugging

**Hardware-Software Interface:**

- The instruction set architecture model, machine code, assembly language, x86
- Basic program translation
- Control flow
- Procedures, call stack
- Data layout, security implications

**Abstractions for Practical Systems:**

- The memory hierarchy, caches
- Memory allocation
- Operating system basics: 
    - Exception control flow
    - The process model
    - Virtual memory
- Compilers, run-time systems, programming tools
- Beyond 240 ### When Should You Take CS 240?

**Prerequisite:** CS 230 or permission of the instructor is **required** to enroll in CS 240.

**Recommendations:**

- Consider your courseload carefully. CS 240 is a 1.25-credit lab course that requires a larger time commitment and workload than most 1-credit courses.
- Take CS 240 early after finishing the CS 111 / CS 230 introductory sequence. CS 240 should boost your independence, give valuable context for *how things work* as you approach further computing studies, and open doors to a wide range of courses and areas in CS.

Please talk to the [instructors](#staff) if you have any questions or concerns. We are happy to work with you to make your time in CS 240 most effective and rewarding for you. ### Texts

Electronic options are available for all required sources. At least one physical copy of each text is also available in the physical SCI L037 CS Systems Lab **for use within the CS department area.**Please use them in the data lab area and return them to the shelf when you are done.

**We use one primary textbook extensively:**

- **CSAPP 3e** ([*Wellesley online access*](https://drive.google.com/drive/folders/1eFNJ7GqAHH8_W4dNv0UC4qkZX-kEMQH_?usp=sharing)):   
    [*Computer Systems: A Programmer’s Perspective, 3/E*](http://csapp.cs.cmu.edu). (**3rd edition**, significant changes since 2nd)   
    Bryant and O’Hallaron, Pearson, 2016. ISBN-13: 9780134092669. 
    - We **need the 3rd edition**. See [the errata](http://csapp.cs.cmu.edu/3e/errata.html).
    - Unfortunately, the library is not able to acquire an electronic version, but there are several options to access the book, including, but not limited to: 
        - If you prefer physical books, paperback copies are available for much less than the hardcover version. “Global” 3rd editions mostly work, but have some additional errors (not listed on the errata page).
        - [6 months of access to an electronic version is available for $35.](https://www.vitalsource.com/products/computer-systems-a-programmer-39-s-perspective-randal-e-bryant-david-r-v9780134092997)
        - During difficult pandemic circumstances, [we have scans of the relevant excerpts available for CS 240 students (Wellesley ONLY)](https://drive.google.com/drive/folders/1eFNJ7GqAHH8_W4dNv0UC4qkZX-kEMQH_?usp=sharing). Being scans, these excerpts are not quite as good quality as some other electronic or paper options.
    - Please contact the instructors if none of the available options work for you.

**Other textbooks are used during the first part of the course:**

- **DDCA** ([*Wellesley online access*](https://ebookcentral.proquest.com/lib/well/detail.action?docID=404196)):   
    [*Digital Design and Computer Architecture*](https://ebookcentral.proquest.com/lib/well/detail.action?docID=404196).   
    Harris and Harris, Morgan Kaufmann, 2007. 
    - [The library has an electronic version of this text](https://ebookcentral.proquest.com/lib/well/detail.action?docID=404196)

**We recommend a good reference on the C programming language.**Here are a couple solid options:

- **[Essential C](http://cslibrary.stanford.edu/101/)** (PDF)  
    Nick Parlante, 2003. Stanford University.
- **K&amp;R:**  
    [*The C Programming Language, 2nd edition*](http://luna.wellesley.edu/record=b1630956~s1).   
    Kernighan and Ritchie, Prentice Hall, 1988. ISBN-13: 978-0131103627, ISBN-10: 0131103628.

**Additional materials** will be posted directly on the [course website](/~cs240/s23/).

CS 240 Foundations of Computer Systems

Memory hierarchy

3 courses cover this concept

CS 267: Applications of Parallel Computers

15-213/18-213/14-513/15-513/18-613 Introduction to Computer Systems

CS 240 Foundations of Computer Systems