Great Ideas in Computer Architecture (Machine Structures)

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

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
Webcast

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/24

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/24

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
Webcast

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
Webcast

Readings: P&H:4.10

Lec 24

10/23

Caches I
Webcast

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
Webcast

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

Assignments

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

Week 10

Lec

10/28

Cancelled

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

Lec 26

10/30

Caches III
Webcast

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

Lec 27

11/1

Virtual Memory I
MIDTERM 7-9PM
Midterm advice and resources
Webcast

Readings: P&H:5.7-5.8

Assignments

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

Week 11

Lec 28

11/4

Virtual Memory II
Project Party Tuesday (11/5) 8-10pm 5th floor Cory

Webcast

Readings: P&H:5.7-5.8

Lec 29

11/6

Virtual Memory III
Webcast

Readings: P&H:5.7-5.8

Lec 30

11/8

Flynn Taxonomy, SIMD Instructions
Webcast

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
• Project 3.2 Due 11/15 Project Party 11/5&11/14 8-10PM Cory 5th Floor

Week 12

No Lecture

11/11

No Lecture (Veterans Day)

Lec 31

11/13

Thread-Level Parallelism I
Webcast

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

Lec 32

11/15

Thread-Level Parallelism II
Webcast

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

Assignments

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

Week 13

Lec 33

11/18

Thread-Level Parallelism III
Webcast

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

Lec 34

11/20

MapReduce, Spark
Webcast

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

Lec 35

11/22

Data Centers, Cloud Computing
Webcast

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 36

11/25

I/O - Basics
Webcast

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

No Lecture

11/27

No Lecture (Thanksgiving Break)

No Lecture

11/29

No Lecture (Thanksgiving Break)

Assignments

• Lab 13: Enjoy Thanksgiving!
• Homework 10 (practice, no deadline)

Week 15

Lec 37

12/2

David Patterson “A New Golden Age for Computer Architecture”
Webcast

Readings: P&H 5.2, 5.5, 5.11

Lec 38

12/4

James Percy (Apple) "GPUs"
Webcast

Readings: P&H 5.2, 5.5, 5.11

Lec 39

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
Webcast

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
Webcast

Readings: P&H:4.7, 4.8

Week 8

Lec 23

10/21

Pipelining III
Webcast

Readings: P&H:4.10

Week 9

Lec 24

10/23

Caches I
Webcast

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
Webcast

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

Week 9

Lec

10/28

Cancelled

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

Week 10

Lec 26

10/30

Caches III
Webcast

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

Week 10

Lec 27

11/1

Virtual Memory I
MIDTERM 7-9PM
Midterm advice and resources
Webcast

Readings: P&H:5.7-5.8

Week 10

Lec 28

11/4

Virtual Memory II
Project Party Tuesday (11/5) 8-10pm 5th floor Cory

Webcast

Readings: P&H:5.7-5.8

Week 11

Lec 29

11/6

Virtual Memory III
Webcast

Readings: P&H:5.7-5.8

Week 11

Lec 30

11/8

Flynn Taxonomy, SIMD Instructions
Webcast

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

Week 11

Lec 31

11/13

Thread-Level Parallelism I
Webcast

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

Week 12

Lec 32

11/15

Thread-Level Parallelism II
Webcast

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

Week 12

Lec 33

11/18

Thread-Level Parallelism III
Webcast

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

Week 13

Lec 34

11/20

MapReduce, Spark
Webcast

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

Week 13

Lec 35

11/22

Data Centers, Cloud Computing
Webcast

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/25

I/O - Basics
Webcast

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

Week 14

Lec 37

12/2

David Patterson “A New Golden Age for Computer Architecture”
Webcast

Readings: P&H 5.2, 5.5, 5.11

Week 15

Lec 38

12/4

James Percy (Apple) "GPUs"
Webcast

Readings: P&H 5.2, 5.5, 5.11

Week 15

Lec 39

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

Review + 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 Instructions

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/24

Link

Homework 6

Deadline: 10/24

Link

Homework 7

Deadline: 11/8

Link

Homework 8

Deadline: 11/22

Link

Homework 9

Deadline: 12/4

Link

Homework 9.5

Deadline: 12/4

Link

Homework 10

Deadline: N/A (practice)

Link

Project 1

Deadline:

Mandelbrot

Link

Project 2

Deadline:

CS61Classify

Link

Project 3.1

Deadline:

CPU Part A

Link

Project 3.2

Deadline:

CPU Part B

Link

Quest

9/16

9:00PM - 10:00PM

Midterm

10/28

8:00PM - 10:00PM

Final Exam

12/20

11:30AM - 2:30PM