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
[ Video ]

Readings: Course Policies

Lec 2

8/30

Number Representation
[ Video ]

Readings: P&H:2.4 , Binary slides

Materials

• Lab 0: Intro and Set Up

Assignments

• Homework 0: Mini-bio
  Due 8/30
• Homework 1: Number Reps
  Due 9/6

Week 2

No Lecture

9/2

No Lecture (Labor Day)

Lec 3

9/4

C Intro - Basics
[ Video ]

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

Lec 4

9/6

C Intro - Pointers, Arrays, Strings
[ Video ]

Readings: K&R:5-6

Materials

• Discussion 1: Number Rep (Solutions)
• Lab 1: Number Rep, C and CGDB

Assignments

• Homework 2: C Concepts (on Gradescope)
  Due 9/13
• Homework 2.5: Cellular Automata (Coding Assignment)
  Due 9/13

Week 3

Lec 5

9/9

C Memory Management
[ Video ]

Readings: K&R 7.8.5, 8.7

Lec 6

9/11

Floating Point
[ Video ]

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

Lec 7

9/13

RISC-V Intro
[ Video ]

Readings: P&H:2.1-2.3

Materials

• Discussion 2: C Basics (Solutions)
• Lab 2: C checkoff + Time for Homework/Project

Assignments

• Homework 3: Floating Point
  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
[ Video ]

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
[ Video ]

Readings: P&H:2.6, 2.7, 3.2

Lec 10

9/20

RISC-V Procedure
[ Video ]

Readings: P&H:2.8

Materials

• Discussion 3: Floating Point, RISC-V Intro (Solutions)
• Lab 3: Advanced C

Assignments

• Homework 4: RISC-V
  Due 10/4

Week 5

Lec 11

9/23

RISC-V Instruction Formats I
[ Video ]

Readings: P&H:2.5, 2.10

Lec 12

9/25

RISC-V Instruction Formats II
[ Video ]

Readings: P&H:2.5, 2.10

Lec 13

9/27

Compilation, Assembly, Linking, Loading
[ Video ]

Readings: P&H:2.12

Materials

• Discussion 4: RISC-V Control Flow, ISA (Solutions)
• Lab 4: RISC-V Assembly

Assignments

• 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
[ Video ]

Readings: SDS Handout

Lec 15

10/2

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

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

Lec 16

10/4

Combinational Logic
[ Video ]

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

Materials

• Discussion 5: CALL, RISC-V Procedures (Solutions)
• Lab 5: RISC-V Functions, Pointers

Assignments

• Homework 5: Logic, Timing
  Due 10/24

Week 7

Lec 17

10/7

Combinational Logic Blocks
[ Video ]

Readings: Blocks Handout

Lec 18

10/9

Single-Cycle CPU Datapath I
[ Video ]

Readings: P&H:4.1. 4.3

Lec 19

10/11

Single-Cycle CPU Datapath II
[ Video ]

Readings: P&H:4.4

Materials

• Discussion 6: SDS, Logic (Solutions)
• Lab 6: Logisim

Assignments

• Homework 6: RISC-V Datapath
  Due 10/24

Week 8

Lec 20

10/14

Single-Cycle CPU Control
[ Video ]

Readings: P&H:4.4, 4.5

Lec 21

10/16

Pipelining
[ Video ]

Readings: P&H:4.6

Lec 22

10/18

Pipelining II
[ Video ]

Readings: P&H:4.7, 4.8

Materials

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

Week 9

Lec 23

10/21

Pipelining III
[ Video ]

Readings: P&H:4.10

Lec 24

10/23

Caches I
[ Video ]

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
[ Video ]

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

Materials

• Discussion 8: Review + Pipelining (Solutions)
• Lab 8: Midterm Review

Assignments

• Homework 7: Caches
  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
[ Video ]

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
[ Video ]

Readings: P&H:5.7-5.8

Materials

• Discussion 9: Caches (Solutions)
• Lab 9: Caches

Assignments

• Homework 8: Virtual Memory
  Due 11/22

Week 11

Lec 28

11/4

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

[ Video ]

Readings: P&H:5.7-5.8

Lec 29

11/6

Virtual Memory III
[ Video ]

Readings: P&H:5.7-5.8

Lec 30

11/8

Flynn Taxonomy, SIMD Instructions
[ Video ]

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

Materials

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

Assignments

• 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
[ Video ]

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

Lec 32

11/15

Thread-Level Parallelism II
[ Video ]

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

Materials

• Discussion 11: Data-Level Parallelism (Solutions)
• Lab 11: SIMD Instructions

Assignments

• Homework 9: Performance Programming
  Due 12/4
• Homework 9.5 Due 12/4

Week 13

Lec 33

11/18

Thread-Level Parallelism III
[ Video ]

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

Lec 34

11/20

MapReduce, Spark
[ Video ]

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
[ Video ]

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

Materials

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

Week 14

Lec 36

11/25

I/O - Basics
[ Video ]

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)

Materials

• Discussion : None
• Lab 13: Enjoy Thanksgiving!

Assignments

• Homework 10: I/O, Parity, and ECC (practice, no deadline)

Week 15

Lec 37

12/2

David Patterson “A New Golden Age for Computer Architecture”
[ Video ]

Readings: P&H 5.2, 5.5, 5.11

Lec 38

12/4

James Percy (Apple) "GPUs"
[ Video ]

Readings: P&H 5.2, 5.5, 5.11

Lec 39

12/6

Summary and Goodbye

Materials

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

Lec 1

8/28

Great Ideas in Computer Architecture, Intro
[ Video ]

Readings: Course Policies

Week 1

Lec 2

8/30

Number Representation
[ Video ]

Readings: P&H:2.4 , Binary slides

Week 1

Lec 3

9/4

C Intro - Basics
[ Video ]

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
[ Video ]

Readings: K&R:5-6

Week 2

Lec 5

9/9

C Memory Management
[ Video ]

Readings: K&R 7.8.5, 8.7

Week 3

Lec 6

9/11

Floating Point
[ Video ]

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

Week 3

Lec 7

9/13

RISC-V Intro
[ Video ]

Readings: P&H:2.1-2.3

Week 3

Lec 8

9/16

RISC-V lw, sw, Decisions I
[ Video ]

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
[ Video ]

Readings: P&H:2.6, 2.7, 3.2

Week 4

Lec 10

9/20

RISC-V Procedure
[ Video ]

Readings: P&H:2.8

Week 4

Lec 11

9/23

RISC-V Instruction Formats I
[ Video ]

Readings: P&H:2.5, 2.10

Week 5

Lec 12

9/25

RISC-V Instruction Formats II
[ Video ]

Readings: P&H:2.5, 2.10

Week 5

Lec 13

9/27

Compilation, Assembly, Linking, Loading
[ Video ]

Readings: P&H:2.12

Week 5

Lec 14

9/30

Intro to Synchronous Digital Systems
[ Video ]

Readings: SDS Handout

Week 6

Lec 15

10/2

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

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

Week 6

Lec 16

10/4

Combinational Logic
[ Video ]

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

Week 6

Lec 17

10/7

Combinational Logic Blocks
[ Video ]

Readings: Blocks Handout

Week 7

Lec 18

10/9

Single-Cycle CPU Datapath I
[ Video ]

Readings: P&H:4.1. 4.3

Week 7

Lec 19

10/11

Single-Cycle CPU Datapath II
[ Video ]

Readings: P&H:4.4

Week 7

Lec 20

10/14

Single-Cycle CPU Control
[ Video ]

Readings: P&H:4.4, 4.5

Week 8

Lec 21

10/16

Pipelining
[ Video ]

Readings: P&H:4.6

Week 8

Lec 22

10/18

Pipelining II
[ Video ]

Readings: P&H:4.7, 4.8

Week 8

Lec 23

10/21

Pipelining III
[ Video ]

Readings: P&H:4.10

Week 9

Lec 24

10/23

Caches I
[ Video ]

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
[ Video ]

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
[ Video ]

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
[ Video ]

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

[ Video ]

Readings: P&H:5.7-5.8

Week 11

Lec 29

11/6

Virtual Memory III
[ Video ]

Readings: P&H:5.7-5.8

Week 11

Lec 30

11/8

Flynn Taxonomy, SIMD Instructions
[ Video ]

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
[ Video ]

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

Week 12

Lec 32

11/15

Thread-Level Parallelism II
[ Video ]

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

Week 12

Lec 33

11/18

Thread-Level Parallelism III
[ Video ]

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

Week 13

Lec 34

11/20

MapReduce, Spark
[ Video ]

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
[ Video ]

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
[ Video ]

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”
[ Video ]

Readings: P&H 5.2, 5.5, 5.11

Week 15

Lec 38

12/4

James Percy (Apple) "GPUs"
[ Video ]

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

Week 2

Disc 2

C Basics

Worksheet Solutions

Week 3

Disc 3

Floating Point, RISC-V Intro

Worksheet Solutions

Week 4

Disc 4

RISC-V Control Flow, ISA

Worksheet Solutions

Week 5

Disc 5

CALL, RISC-V Procedures

Worksheet Solutions

Week 6

Disc 6

SDS, Logic

Worksheet Solutions

Week 7

Disc 7

Single-Cycle Datapath

Worksheet Solutions

Week 8

Disc 8

Review + Pipelining

Worksheet Solutions

Week 9

Disc 9

Caches

Worksheet Solutions

Week 10

Disc 10

Virtual Memory

Worksheet Solutions

Week 11

Disc 11

Data-Level Parallelism

Worksheet Solutions

Week 12

Disc 12

Parallelism

Worksheet Solutions

Week 13

Disc 13

WSC, MapReduce, Spark

Worksheet Solutions

Week 15

Lab 0

Intro and Set Up

Link

Week 1

Lab 1

Number Rep, C and CGDB

Link

Week 2

Lab 2

C checkoff + Time for Homework/Project

Link

Week 3

Lab 3

Advanced C

Link

Week 4

Lab 4

RISC-V Assembly

Link

Week 5

Lab 5

RISC-V Functions, Pointers

Link

Week 6

Lab 6

Logisim

Link

Week 7

Lab 7

Pipelining and CPU

Link

Week 8

Lab 8

Midterm Review

Link

Week 9

Lab 9

Caches

Link

Week 10

Lab 10

Virtual Memory

Link

Week 11

Lab 11

SIMD Instructions

Link

Week 12

Lab 12

Thread-Level Parallelism

Link

Week 13

Lab 13

Enjoy Thanksgiving!

Link

Week 14

Lab 14

MapReduce and Spark

Link

Week 15

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