Great Ideas in Computer Architecture (Machine Structures)

CS 61C at UC Berkeley with Dan Garcia and Miki Lustig - Fall 2019

Project 2 released, part A due 10/16, part B due 10/23

Lab06: We are pushing the due date back a week (you will receive full credit if you submit by 10/25, and half credit if you submit by 11/1)

Lab07: We are removing the Project 3-1 requirement for checkoff for this lab.

Midterm: We will be removing pipelining as a required topic for the midterm. So the midterm will hold content up to and including Single-Cycle CPU Control. The last lecture that is in scope is Lecture 20: Single-Cycle CPU Control.

Lecture: M 3:00 pm - 3:59 pm Soda 306, WF 12:00 pm - 12:59 pm Li Ka Shing 245

Textbooks:

• Computer Organization and Design RISC-V Edition, 1st ed. by David Patterson, and John Hennessy
• The C Programming Language, 2nd ed. by Brian Kernighan and Dennis Ritchie
• The Datacenter as a Computer by Luiz André Barroso and Urs Hölzle, freely available here
• By Week
• Lectures
• Discussions
• Labs
• Homeworks
• Projects
• Exams

Week 1

Lec 1

8/28

Great Ideas in Computer Architecture, Intro
Webcast

Readings: Course Policies

Lec 2

8/30

Number Representation
Webcast

Readings: P&H:2.4 , Binary slides

Assignments

• Lab 0: Intro and Set Up
• Homework 0 Due 8/30
• Homework 1 Due 9/6

Week 2

No Lecture

9/2

No Lecture (Labor Day)

Lec 3

9/4

C Intro - Basics
Webcast

Readings: K&R Ch. 1-5, C Reference Slides , Brian Harvey's Intro to C

Lec 4

9/6

C Intro - Pointers, Arrays, Strings

Readings: K&R:5-6

Assignments

• Discussion 1: Number Rep (Solutions)
• Lab 1: Number Rep, C and CGDB
• Homework 2 Due 9/13
• Homework 2.5 Due 9/13

Week 3

Lec 5

9/9

C Memory Management
Webcast

Readings: K&R 7.8.5, 8.7

Lec 6

9/11

Floating Point
Webcast

Readings: P&H:3.5, 3.9 , IEEE 754 Simulator

Lec 7

9/13

RISC-V Intro
Webcast

Readings: P&H:2.1-2.3

Assignments

• Discussion 2: C Basics (Solutions)
• Lab 2: C checkoff + Time for Homework/Project
• Homework 3 Due 10/4
• Project 1 Due 9/30 (Part A due 9/23)

Week 4

Lec 8

9/16

RISC-V lw, sw, Decisions I
Webcast

Readings: P&H:2.9, 2.10 , QUEST 9-10PM (only covers up to C (no floating point, no RISCV))

Lec 9

9/18

RISC-V Decisions II
Webcast

Readings: P&H:2.6, 2.7, 3.2

Lec 10

9/20

RISC-V Procedure
Webcast

Readings: P&H:2.8

Assignments

• Discussion 3: Floating Point, RISC-V Intro (Solutions)
• Lab 3: Advanced C
• Homework 4 Due 10/4

Week 5

Lec 11

9/23

RISC-V Instruction Formats I
Webcast

Readings: P&H:2.5, 2.10

Lec 12

9/25

RISC-V Instruction Formats II
Webcast

Readings: P&H:2.5, 2.10

Lec 13

9/27

Compilation, Assembly, Linking, Loading
Webcast

Readings: P&H:2.12

Assignments

• Discussion 4: RISC-V Control Flow, ISA (Solutions)
• Lab 4: RISC-V Assembly
• Project 2 Due 10/23 (Part A due 10/16) Project Party 10/3 & 10/17 8-10PM Cory 5th Floor

Week 6

Lec 14

9/30

Intro to Synchronous Digital Systems
Webcast

Readings: SDS Handout

Lec 15

10/2

States, State Machines (Guerilla Section 8-10PM Soda 310 &320)
Webcast

Readings: (Guerilla Section 8-10PM Soda 310 &320) P&H:A.3-A.6 , State Handout

Lec 16

10/4

Combinational Logic
Webcast

Readings: P&H:A.2-A.3 , Logic Handout

Assignments

• Discussion 5: CALL, RISC-V Procedures (Solutions)
• Lab 5: RISC-V Functions, Pointers
• Homework 5 Due 10/23

Week 7

Lec 17

10/7

Combinational Logic Blocks
Webcast

Readings: Blocks Handout

Lec 18

10/9

Single-Cycle CPU Datapath I
Webcast

Readings: P&H:4.1. 4.3

Lec 19

10/11

Single-Cycle CPU Datapath II
Webcast

Readings: P&H:4.4

Assignments

• Discussion 6: SDS, Logic (Solutions)
• Lab 6: Logisim
• Homework 6 Due 10/23

Week 8

Lec 20

10/14

Single-Cycle CPU Control
Webcast

Readings: P&H:4.4, 4.5

Lec 21

10/16

Pipelining
Webcast

Readings: P&H:4.6

Lec 22

10/18

Pipelining II

Readings: P&H:4.7, 4.8

Assignments

• Discussion 7: Single-Cycle Datapath (Solutions)
• Lab 7: Pipelining and CPU

Week 9

Lec 23

10/21

Pipelining III

Readings: P&H:4.10

Lec 24

10/23

Caches I

Readings: P&H:5.1, 5.2, 5.3, 5.4, 5.8, 5.9, 5.13 , Cache Flowchart

Lec 25

10/25

Caches II

Readings: P&H:5.1, 5.2, 5.3, 5.4, 5.8, 5.9, 5.13 , Cache Flowchart

Assignments

• Discussion 8: Pipelining (Solutions)
• Lab 8: Midterm Review
• Homework 7 Due 11/8
• Project 3 Due 11/15 Project Party 11/5&11/14 8-10PM Cory 5th Floor

Week 10

Lec 26

10/28

Caches III, MIDTERM 8-10PM

Readings: P&H:5.1, 5.2, 5.3, 5.4, 5.8, 5.9, 5.13 , Cache Flowchart

Lec 27

10/30

Caches IV

Readings: P&H:5.1, 5.2, 5.3, 5.4, 5.8, 5.9, 5.13 , Cache Flowchart

Lec 28

11/1

Virtual Memory I

Readings: P&H:5.7-5.8

Assignments

• Discussion 9: Caches (Solutions)
• Lab 9: Caches
• Homework 8 Due 11/22

Week 11

Lec 29

11/4

Virtual Memory II

Readings: P&H:5.7-5.8

Lec 30

11/6

Virtual Memory III

Readings: P&H:5.7-5.8

Lec 31

11/8

Flynn Taxonomy, SIMD Instructions

Readings: P&H:1.7, 1.8, 4.10, 4.11, 6.1, 6.2, 6.3, 6.7

Assignments

• Discussion 10: Virtual Memory (Solutions)
• Lab 10: Virtual Memory

Week 12

No Lecture

11/11

No Lecture (Veterans Day)

Lec 32

11/13

Thread-Level Parallelism I

Readings: P&H:2.11, 4.10, 5.10, 6.5 , OpenMP Summary Card

Lec 33

11/15

Thread-Level Parallelism II

Readings: P&H:2.11, 4.10, 5.10, 6.5 , OpenMP Summary Card

Assignments

• Discussion 11: Data-Level Parallelism (Solutions)
• Lab 11: SIMD Insturctions
• Homework 9 Due 12/4

Week 13

Lec 34

11/18

Thread-Level Parallelism III

Readings: P&H:2.11, 4.10, 5.10, 6.5 , OpenMP Summary Card

Lec 35

11/20

MapReduce, Spark

Readings: The Datacenter as a Computer:Ch 1, Ch 2.4, Ch 3, 5.1-5.3 , P&H:6.7

Lec 36

11/22

Data Centers, Cloud Computing

Readings: The Datacenter as a Computer:Ch 1, Ch 2.4, Ch 3, 5.1-5.3 , P&H:6.7

Assignments

• Discussion 12: Parallelism (Solutions)
• Lab 12: Thread-Level Parallelism

Week 14

Lec 37

11/25

I/O - Basics, Dependability, Parity, ECC

Readings: P&H 5.2, 5.5, 5.11, A-64 to B-66 , Berkeley RAID Paper

No Lecture 38

11/27

No Lecture (Thanksgiving Break)

No Lecture 39

11/29

No Lecture (Thanksgiving Break)

Assignments

• Lab 13: Enjoy Thanksgiving!
• Homework 10 Due 12/13

Week 15

Lec 40

12/2

David Patterson “A New Golden Age for Computer Architecture”

Readings: P&H 5.2, 5.5, 5.11

Lec 41

12/4

James Percy (Apple) "GPUs"

Readings: P&H 5.2, 5.5, 5.11

Lec 42

12/6

Summary and Goodbye

Assignments

• Discussion 13: WSC, MapReduce, Spark (Solutions)
• Lab 14: MapReduce and Spark

Lec 1

8/28

Great Ideas in Computer Architecture, Intro
Webcast

Readings: Course Policies

Week 1

Lec 2

8/30

Number Representation
Webcast

Readings: P&H:2.4 , Binary slides

Week 1

Lec 3

9/4

C Intro - Basics
Webcast

Readings: K&R Ch. 1-5, C Reference Slides , Brian Harvey's Intro to C

Week 2

Lec 4

9/6

C Intro - Pointers, Arrays, Strings

Readings: K&R:5-6

Week 2

Lec 5

9/9

C Memory Management
Webcast

Readings: K&R 7.8.5, 8.7

Week 3

Lec 6

9/11

Floating Point
Webcast

Readings: P&H:3.5, 3.9 , IEEE 754 Simulator

Week 3

Lec 7

9/13

RISC-V Intro
Webcast

Readings: P&H:2.1-2.3

Week 3

Lec 8

9/16

RISC-V lw, sw, Decisions I
Webcast

Readings: P&H:2.9, 2.10 , QUEST 9-10PM (only covers up to C (no floating point, no RISCV))

Week 4

Lec 9

9/18

RISC-V Decisions II
Webcast

Readings: P&H:2.6, 2.7, 3.2

Week 4

Lec 10

9/20

RISC-V Procedure
Webcast

Readings: P&H:2.8

Week 4

Lec 11

9/23

RISC-V Instruction Formats I
Webcast

Readings: P&H:2.5, 2.10

Week 5

Lec 12

9/25

RISC-V Instruction Formats II
Webcast

Readings: P&H:2.5, 2.10

Week 5

Lec 13

9/27

Compilation, Assembly, Linking, Loading
Webcast

Readings: P&H:2.12

Week 5

Lec 14

9/30

Intro to Synchronous Digital Systems
Webcast

Readings: SDS Handout

Week 6

Lec 15

10/2

States, State Machines (Guerilla Section 8-10PM Soda 310 &320)
Webcast

Readings: (Guerilla Section 8-10PM Soda 310 &320) P&H:A.3-A.6 , State Handout

Week 6

Lec 16

10/4

Combinational Logic
Webcast

Readings: P&H:A.2-A.3 , Logic Handout

Week 6

Lec 17

10/7

Combinational Logic Blocks
Webcast

Readings: Blocks Handout

Week 7

Lec 18

10/9

Single-Cycle CPU Datapath I
Webcast

Readings: P&H:4.1. 4.3

Week 7

Lec 19

10/11

Single-Cycle CPU Datapath II
Webcast

Readings: P&H:4.4

Week 7

Lec 20

10/14

Single-Cycle CPU Control
Webcast

Readings: P&H:4.4, 4.5

Week 8

Lec 21

10/16

Pipelining
Webcast

Readings: P&H:4.6

Week 8

Lec 22

10/18

Pipelining II

Readings: P&H:4.7, 4.8

Week 8

Lec 23

10/21

Pipelining III

Readings: P&H:4.10

Week 9

Lec 24

10/23

Caches I

Readings: P&H:5.1, 5.2, 5.3, 5.4, 5.8, 5.9, 5.13 , Cache Flowchart

Week 9

Lec 25

10/25

Caches II

Readings: P&H:5.1, 5.2, 5.3, 5.4, 5.8, 5.9, 5.13 , Cache Flowchart

Week 9

Lec 26

10/28

Caches III, MIDTERM 8-10PM

Readings: P&H:5.1, 5.2, 5.3, 5.4, 5.8, 5.9, 5.13 , Cache Flowchart

Week 10

Lec 27

10/30

Caches IV

Readings: P&H:5.1, 5.2, 5.3, 5.4, 5.8, 5.9, 5.13 , Cache Flowchart

Week 10

Lec 28

11/1

Virtual Memory I

Readings: P&H:5.7-5.8

Week 10

Lec 29

11/4

Virtual Memory II

Readings: P&H:5.7-5.8

Week 11

Lec 30

11/6

Virtual Memory III

Readings: P&H:5.7-5.8

Week 11

Lec 31

11/8

Flynn Taxonomy, SIMD Instructions

Readings: P&H:1.7, 1.8, 4.10, 4.11, 6.1, 6.2, 6.3, 6.7

Week 11

Lec 32

11/13

Thread-Level Parallelism I

Readings: P&H:2.11, 4.10, 5.10, 6.5 , OpenMP Summary Card

Week 12

Lec 33

11/15

Thread-Level Parallelism II

Readings: P&H:2.11, 4.10, 5.10, 6.5 , OpenMP Summary Card

Week 12

Lec 34

11/18

Thread-Level Parallelism III

Readings: P&H:2.11, 4.10, 5.10, 6.5 , OpenMP Summary Card

Week 13

Lec 35

11/20

MapReduce, Spark

Readings: The Datacenter as a Computer:Ch 1, Ch 2.4, Ch 3, 5.1-5.3 , P&H:6.7

Week 13

Lec 36

11/22

Data Centers, Cloud Computing

Readings: The Datacenter as a Computer:Ch 1, Ch 2.4, Ch 3, 5.1-5.3 , P&H:6.7

Week 13

Lec 37

11/25

I/O - Basics, Dependability, Parity, ECC

Readings: P&H 5.2, 5.5, 5.11, A-64 to B-66 , Berkeley RAID Paper

Week 14

Lec 40

12/2

David Patterson “A New Golden Age for Computer Architecture”

Readings: P&H 5.2, 5.5, 5.11

Week 15

Lec 41

12/4

James Percy (Apple) "GPUs"

Readings: P&H 5.2, 5.5, 5.11

Week 15

Lec 42

12/6

Summary and Goodbye

Week 15

Disc 1

Number Rep

Worksheet Solutions

Disc 2

C Basics

Worksheet Solutions

Disc 3

Floating Point, RISC-V Intro

Worksheet Solutions

Disc 4

RISC-V Control Flow, ISA

Worksheet Solutions

Disc 5

CALL, RISC-V Procedures

Worksheet Solutions

Disc 6

SDS, Logic

Worksheet Solutions

Disc 7

Single-Cycle Datapath

Worksheet Solutions

Disc 8

Pipelining

Worksheet Solutions

Disc 9

Caches

Worksheet Solutions

Disc 10

Virtual Memory

Worksheet Solutions

Disc 11

Data-Level Parallelism

Worksheet Solutions

Disc 12

Parallelism

Worksheet Solutions

Disc 13

WSC, MapReduce, Spark

Worksheet Solutions

Lab 0

Intro and Set Up

Link

Lab 1

Number Rep, C and CGDB

Link

Lab 2

C checkoff + Time for Homework/Project

Link

Lab 3

Advanced C

Link

Lab 4

RISC-V Assembly

Link

Lab 5

RISC-V Functions, Pointers

Link

Lab 6

Logisim

Link

Lab 7

Pipelining and CPU

Link

Lab 8

Midterm Review

Link

Lab 9

Caches

Link

Lab 10

Virtual Memory

Link

Lab 11

SIMD Insturctions

Link

Lab 12

Thread-Level Parallelism

Link

Lab 13

Enjoy Thanksgiving!

Link

Lab 14

MapReduce and Spark

Link

Homework 0

Deadline: 8/30

Link

Homework 1

Deadline: 9/6

Link

Homework 2

Deadline: 9/13

Link

Homework 2.5

Deadline: 9/13

Link

Homework 3

Deadline: 10/4

Link

Homework 4

Deadline: 10/4

Link

Homework 5

Deadline: 10/23

Link

Homework 6

Deadline: 10/23

Link

Homework 7

Deadline: 11/8

Link

Homework 8

Deadline: 11/22

Link

Homework 9

Deadline: 12/4

Link

Homework 10

Deadline: 12/13

Link

Project 1

Deadline:

Mandelbrot

Link

Project 2

Deadline:

CS61Classify

Link

Project 3

Deadline:

CPU

Link

Quest

9/16

9:00PM - 10:00PM

Midterm

10/28

8:00PM - 10:00PM

Final Exam

12/20

11:30AM - 2:30PM