Does Kernighan talk about time-sharing? It would be good if students
read a little bit about processes, threads, time-sharing, and context
switching before the student presentations. (Useful background before
learning about multi-processors and virtual memory.)
Would probably be good to provide a link to a recent source on how chips are made. Some 230 students haven't a clue.
IMPORTANT NOTE:
The following schedule represents a current
best guess concerning actual due dates (and everything else), to
give you a general idea of the pace and timing of the class.
This schedule is likely to change as the quarter progresses.
Last modified on .
Reading assignments are from Patterson and Hennesey (P&H) unless specified otherwise. K&R refers to The C Programming Language by Kernighan and Ritchie. (Alternatives to K&R include Essential C and The GNU C Programming Tutorial.) K refers to Understanding the Digital World (2nd Edition) by Brian Kernighan.
Skip directly to Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10
Before Term Begins: | |||
---|---|---|---|
Read the Preparation for COMP 230 email
(you can find a copy in the Announcements channel of the CS
230 Comp. Org. team). Install any necessary software to
have an appropriate environment for this course:
Unix, Linux, or bash command line; git; gcc; and a
Markdown editor and previewer (e.g., VS Code and Chrome
with appropriate extensions).
If you have never used Git and Kit together before,
you will first need to set up SSH keys and share the
public key with Kit. I've created a
video on configuring Git and setting
up SSH keys (7.5 min). Avoid the 2 most common mistakes
people make! (1) When creating your keys, don't provide a
filename or pass phrase — just hit return to leave
them blank, or you'll complicate things. And (2), pay
particular attention to what makes up your public key
(around 5.5 minutes in to the video).
The Kit Help File I refer to in the video is
Setting Up SSH Keys.
|
|||
Week 1: Before Tuesday (or Before Term Begins) |
TUESDAY - In-Class |
Before Thursday | THURSDAY - In-Class |
Before Week 1:
Read the Preparation for COMP 230 email
and install necessary software: Unix/Linux, git, gcc, and a
Markdown editor and previewer. (See "Before Week 1" above.)
Welcome!
Welcome to "Comp. Org."!
(But, what is Comp. Org. and what will we do in this class?) - 5 min (slide)
Read the Syllabus
Review of CS 101, 105, 107, or
108:
Read additional
slide on Von Neumann architecture,
Fetch/Execute Cycle, Stored Program Concept
(terminology I didn't use in the COMP 101 class)
Read: Section 1.1 through section 1.1.2 (pp. 11-16)
in Chap. 1 of Kernighan's
Understanding the Digital World.
(Will be available on Kit.) The first minute of How a CPU Works in 100 Seconds is good, but next 1.5 min on Fetch/Execute cycle is based on an Accumulator model. That is followed by 10.5 min on M1 vs Intel that might be interesting later in the quarter. |
Welcome to the course!
A word about the syllabus and the books.
If you haven't already, make a directory for this class
in your Unix/Linux environment. This is where you will
clone repositories.
Example:
mkdir cs230 Make directory cd cs230 Change to that directory
Assignment 1:
Cloning
and Submitting Git Repository Projects in Kit
Due before Thursday.
Announce that assignments will be due at 23:59 -- if it says "Before Thursday" then it is due as 23:59 on Wednesday. Related video: Using Git to Get/Submit Code to/from Kit (or Watch Alyce do Assignment 1) - 13.5 min (Note: The issues with the Turn In button are fixed, so you can ignore my comments about that in the last minute of the video.) (Note 2: Your version of the project should include your name, the date, and a brief description.) (Note 3: You do not have to use vi, just because Alyce does! You may want to use VS code instead.) |
Unix/Linux:
Optional:
Skim (or read) the Wikipedia pages for
Shell
(computing) (Intro & Overview) and
Kernel
(operating system) (first 3 paragraphs).
Optional:
Skim (or read) the initial paragraphs and the first
three History sections (Precursors, Creation, Naming)
of
the Wikipedia page on Linux.
If you're interested:
Skim (or read)
the History section of
the Wikipedia page on GNU.
and
the Overview section of
the Wikipedia page on POSIX.
Reference:
Introduction To Unix by Mark Thomas (E-book)
C:
K&R: 1.7 - end
K&R: 5.1 - 5.5 (Arrays and Strings)
P&H: Appendix B.3, B.4 (Linkers, Loaders)
Submit to Kit:
Cloning
and Submitting Git Repository Projects in Kit
|
Beginner C
Programming Practice: Encoding/Decoding Names
Due before Tuesday.
Minutes 11 - 14 and 20:05 - 23:57 of Watch Alyce get started with the Disassembler project might be useful for students working on encode/decode.
Submit to Kit:
Week 1 Reflection is due Sunday evening
First Read Patterson
& Hennessy:
Ch. 1.1: subsection on Classes of Computing
Applications and Their Characteristics (pp. 5-7)
Ch. 1.2: Below Your Program (pp. 10-13)
(Optional) Ch. 1.3 Under the Covers (pp. 13-26)
|
Week 2: Before Tuesday | TUESDAY - In-Class | Before Thursday | THURSDAY - In-Class |
Submit to Kit:
More C Videos:
(Optional) You might find
C in 100 Seconds by Fireship interesting.
Reading:
K&R: Ch. 1 - 1.6 (Overview of C)
K&R: 6.1 - 6.2, 6.7
DisUtil Project
Clone the repository for the
Disassembler Utilities Project
from Kit
Videos — You can watch these in
class if you bring earphones
Intro to DisUtil Project and
how to run it - 7:40 min
stdin, stdout, stderr - 5 min
Intro to disUtilDriver
(
main ) - 7:44 min
Explanation of file pointers (FILE *): 1:00 - 2:58
Explanation of process_arguments function: 3:00 -
5:00
Intro to
verifyMIPInstruction - 2 min
Intro to
binToDec and
testBinToDec - 5:19 min
|
Show students how they can see their Repository Log in Kit.
Go over
Pointer
Exercise questions #1-4
(pdf version)
DisUtil Project
Watch/re-watch DisUtil videos as needed
Tip:
VS Code has 2 formatting shortcuts:
⇧⌥F/Shift-Alt-F/Ctrl-Shift-I
(Mac, Windows, Linux) - Format active document
Command-K Command-F (Mac) or Ctrl-K
Ctrl-F (Windows, Linux) - Format selection
You probably need to install the C/C++ Extension first.
You might also need this
.jsbeautifyrc
file to
update your settings to use the Braces Line Up style
pattern.
|
Even More C Videos:
How Variables are Laid Out in Memory
- 8 min
(slide)
Common Pass-by-Reference Error
- 2 min
(slide)
Videos on Number Representation:
Decimal, Octal, Binary
Representations - 8 min
(slides)
Converting Binary to Octal or
Hexadecimal - 2.5 min
(slide)
Representing Positive and Negative
Integers - 17 min
(first 1.5 minutes — review of binary numbers; next
1.5 minutes cover unsigned integers — positive-only;
rest of video
covers signed integers — positive and negative)
(slides)
Sign Extension for Integers
- 2 min
(slide)
⇒
Read about recognizing overflow
(required!) and proving
that the algorithm for computing two's complement works
(optional) in
this slide. (There is no video
for these topics).
For more depth,
read Patterson & Hennessy:
Ch. 2.4: Signed and Unsigned Integers
Ch. 3.1: Introduction to Chapter on
Arithmetic
Ch. 3.2: Addition and Subtraction
Ch. 3.3: Multiplication
|
In Class:
HW:
Interpreting Binary Data, Part A
(will be handed in with Part B)
Preview:
Quick introduction to the
K
Sub-MIPS Simulator,
which we will use next week.
Very Important Handout:
Continuously adding 1
to signed integers (credit: xkcd.com)
Very Important Number
Representation Question:
Why do computer scientists confuse Halloween and
Christmas? :-)
(show answer)
Continue working on the
Disassembler Utilities Project
Submit to Kit:
Week 2 Reflection is due Sunday evening
|
Week 3: Before Tuesday | TUESDAY - In-Class | Before Thursday | THURSDAY - In-Class |
Submit to Kit:
Disassembler Utilities Project
Videos on Number and Text Representation:
Representing Floating Point
Numbers - 15 min
(slides)
Review from COMP 101/105/107/108:
ASCII/UTF-8 - 5 min
(slides)
Intro to MIPS Assembly Language:
What is MIPS? - 2 min
(slides)
High-Level Languages to Simplest
Assembly Instructions - 3.5 min
(Slides go into more detail, with
more examples.)
(Optional:
Older, longer version of video that
matches slides - 8.5 min)
Load/Store (the Basics) - 6+ min
(slides)
Comments - 1.5 min
For more depth,
read Patterson & Hennessy:
Ch. 3.5: Representation, pp. 242 - 250
Ch. 3.5: Floating-Point Addition to
end of 3.5
Ch. 3.9, 3.10: Conclusion, Historical
Perspective
Figure 2.15 in section 2.9
|
HW:
Interpreting Binary Data, Part B
(will be handed in with Part A) |
More C Videos:
More MIPS Videos:
Getting Values Into Registers - 12.75 min (slides) Do we need this first one? Part of it is in new video for Tuesday, and the rest seems to be in the video below for Loops and Arrays.
MIPS: Conditions - 15 min
(slides)
⇒
Do Program 1 (or at least make a reasonable effort)
from Thursday's Simulator Activity.
MIPS: Loops, Arrays, and Nested
Loops - 13.75 min
(slides)
Optional:
MIPS: More Efficient Loops - 4.5 min
(slides)
Reference:
Instruction Summary After Loops (.html)
For more depth,
read Patterson & Hennessy:
Ch. 2.1 - 2.3: Computing Hardware
Operations
Ch. 2.6 - 2.7: Logical Operations,
Instructions for Making Decisions
Submit to Kit:
HW:
Interpreting Binary Data, Parts A & B
|
Brief Introduction to Process Segments in Memory
(Memory Diagram (.gif),
Segments of a Process (pdf))
MIPS Conditions and Loops
If you are having difficulties with simulating blocks, you might want to "back up" to the decisions.txt worksheet (solution) Watch Alyce program and step through the code that has become the Loop Example in K Sub-MIPS (from 2021, 28 min) Nice, but it has .data and .text, and dropouts of audio around 10:25 and 11:20?
Submit to Kit:
Week 3 Reflection is due Sunday evening
|
Week 4: Before Tuesday | TUESDAY - In-Class | Before Thursday | THURSDAY - In-Class |
Submit to Kit:
MIPS Conditions and Loops
Understanding Array Indexing vs. Pointers through
MIPS:
More MIPS Videos:
Implementing Procedures in MIPS
- Watch first 12:50 min; skip last 4 min
(slides)
NOTE around 3:40:
p. 112 in the 5th Edition of P&H is
p. 97 in the 4th Edition
4:40: Remember that
in the Fetch-Execute cycle,
the Program Counter is always incremented after
the Fetch but before the Execute.
(First 9 min are from a pre-pandemic class;
rest is from 10/22.)
Optional:
Watch Alyce Program
Simple DisUtil-ish Procedures in MIPS (No Stack)
- 22.5 min
(C code used in video,
MIPS translation (ignore main
and testB2D from Thursday's video))
11:25 - 13:30 Describes need for Stack (concept
for Thursday)
(Note that this video pre-dates our MIPS CPU
Simulator.)
Is this still relevant?
Reference:
For more depth,
read Patterson & Hennessy:
Ch. 2.14: Arrays vs Pointers
Ch. 2.8, 2.13: Supporting Procedures, Extended Example
Ch. 2.12: Translating and Starting a Program
Very Important Handout:
Can you
give me a few pointers? (credit: xkcd.com)
|
Submit to Kit:
Arrays vs. Pointers Exercise
Should this have been due Tuesday?
More MIPS Videos:
Implementing Procedures in MIPS
- Watch last 4 min of video from before Tuesday
(slides)
Activation Records: How Procedures
Use the Stack - 6:18 min
(slides)
First minute is review of memory
segments
1:18 First mention of the Stack
Pointer register
2:07 Extended example of Activation
Records on the Stack, with dynamic diagram
Optional:
Watch Alyce Program
DisUtil-ish Procedures in MIPS Using the Stack
- 19.5 min
(C code used in video,
MIPS translation)
Note: In testB2D, I forgot to copy
$a0 to $s0, which was the whole point of saving $s0
to the stack! I could have done that right after
storing $ra and $s0 to the stack.
Note2: I also forgot the jr $ra at
the end of testB2D! The code provided here
includes both corrections.
Is this still relevant?
Optional:
Two More MIPS Procedure Examples
(1 leaf procedure, 1 simple stack example)
Should make short video about conventions about which
registers to use?
|
In Class:
MIPS Procedure Calls Using the Stack
Submit to Kit:
Week 4 Reflection is due Sunday evening
|
|
Week 5: Before Tuesday | TUESDAY - In-Class | Before Thursday | THURSDAY - In-Class |
Submit to Kit:
MIPS Procedure Calls Using the Stack
MIPS Videos —
Assembly → Machine Code:
MIPS/RISC Design Principles (13 min)
(RISC = Reduced Instruction Set Computer)
(slides)
Machine Code Layout for All 3
Formats - 10 min
(slides)
Disassembler Prep: Clone Repository:
Clone the disassembler repository from Kit, then follow
the instructions in
DISASSEMBLER_TIPS.md to copy
over the appropriate files files from your DisUtil
repository. Then do a git add and
git commit -m "Include DisUtil code" .)
Optional: Watch Alyce set up
the Disassembler project - 5.5 min
This video was created before I created the encode/decode project. NEED A NEW VIDEO HERE!
Read over the Goals, the first paragraph
of the Behavioral Requirements, and the
first paragraph of the Design and Coding
Tips in the
Disassembler PP
For more depth,
read Patterson & Hennessy:
Ch. 2.5, 2.10: Mapping Assembly → Machine Code
(end of 2.10 is particularly relevant for Disassembler
project)
Ch. 2.18, 2.19: MIPS Design Considerations
|
What is an Assembler? A Disassembler? What purposes do
they serve?
Optional: Watch Alyce get started with
the Disassembler project - 28.5 min
This video was created before I created the encode/decode project. When you get to the 11 minute mark, skip to the 14 minute mark, because you have already implemented getRegName. (If you want, watch 13:30 - 14:00, which talks about the precondition.) Similarly, you can skip from 21:05 to 23:57, which covers getIJInstName and getRInstName, which you have already implemented.
Reference:
Final Instruction Summary (.html)
|
Videos — The Assembler Process:
Programming the PDP 11
(From DePauw Univ., May 2000)
(In four parts, about 16 minutes total — Watch
for the two-pass assembler!)
Optional:
What (and Why) is a Label
Table? — If you still have questions
about the purpose or contents of a label table after
doing the CPU Simulator exercises, watch the first 5:12
minutes on What and Why (Skip the final 7 minutes on
How)
(slides)
This video was created before we had the CPU Simulator exercises. |
Topic: Developing A Thorough Test Suite
Continue working on the
Disassembler PP
No Week 5 Reflection (Break!)
(but beware of 30 minutes worth of videos to watch before Tuesday) |
Week 6: Before Tuesday | TUESDAY - In-Class | Before Thursday | THURSDAY - In-Class |
Review of AND, OR, NOT and
Truth Tables from COMP 105 (Optional):
Boolean Operations and Truth
Tables - 8 min
(slides)
Videos — Logic Gates → Arithmetic:
Introduction to Logic Gates (11.5 min)
(slides)
Going from Truth Tables to Gates - 4 min
(slide)
How Do Computers Do Binary Addition? - 10 min
(slides)
Chips:
Need some reading or video that introduces the idea of chips.
(Optional) Read this July 2023
New York Times article on new chips for
AI
Very Important Handouts:
|
HW: Interpreting Binary Data, Part C
Optional Mind-Stretching Exercise:
HW: MIPS (C)
Finish the
Disassembler PP
OR
Start the LabelTable project.
Watch 2nd Half of Label Table Intro
— What are the Data Structures? —
7 min starting at the 5:12 min mark
(slides)
Clone the Label Table repository and complete the
functions in
LabelTableArrayList.c .
Optional Videos — Label Table:
Watch Alyce program and test
the printLabels and findLabel functions
— 19 min (findLabel is now findLabelAddr in
LabelTableArrayList.c — you are finding the
address for a label)
Watch Alyce program and test
the initTable and addLabel functions
— 20.5 min
(labelDuplicate is now duplLabelName in
LabelTableArrayList.c)
|
Submit to Kit:
HW: Interpreting Binary Data, Part C
Submit to Kit:
Disassembler PP
Videos — More Gates, ALU:
Optional:
Programmable Logic Arrays (PLA) - 7 min
(slides)
|
Submit to Kit:
Week 6 Reflection is due Sunday evening
|
Week 7: Before Tuesday | TUESDAY - In-Class | Before Thursday | THURSDAY - In-Class |
Submit to Kit:
Videos — Single-Cycle Datapath:
Single-Cycle Intro and the Register
File in depth - 6:44 min
(slides)
Single-Cycle Datapath (before adding control
lines) - 17:27 min
(slides)
Single-Cycle Datapath, including control
lines - 6:13 min
(slides)
⇒
Full Datapath diagrams for add, sw,
lw, beq, j (not in video, but should be!)
For more depth,
read Patterson & Hennessy:
4.1-4.3: Single-cycle Datapath
4.4: Implementing Control
Choose a
presentation topic;
fill in the Sign-Up Sheet in the Files tab of the
General channel in the CS 230 Team.
(Presentations will be due Sunday before 10th Week.)
|
Last half-hour of class:
Single-Cycle Datapath Stages, including
timings - 8:46 min
(slides)
Fill in the Single-cycle Datapath column in question 1
of
HW: Single-Cycle, Multi-Cycle,
Pipelined Datapaths
|
Videos —
Multi-Cycle and Pipeline Datapaths:
Recommended, but not Required:
Addressing Pipeline Hazards - 8.5 min
(same sources as for Pipeline Basics)
Transcript for this video has not been cleaned up yet!
Required:
Pipeline Summary - 1 min
(slide (pdf - pg 19 of 32))
For more depth,
read Patterson & Hennessy:
Ch. 4.5-4.8, 4.14,4.15: Pipelining & Conclusions
|
Complete
HW: Single-Cycle Datapath
if not completed already
Submit to Kit:
Week 7 Reflection is due Sunday evening
|
Week 8: Before Tuesday | TUESDAY - In-Class | Before Thursday | THURSDAY - In-Class |
Videos — Memory Caches:
Review Slide:
Quick Intro to Various Types of Memory
Important Background:
Memory Addressing - 11 min
(slide - click about 7 times to
see entire page)
Direct-Mapped Caches - 16.5 min
(continuation of same
slides)
Note: I forgot to say the most important thing up
front:
many words in Memory map to the same line in the
Cache, but only one of them is actually there at
any one time!
For more depth,
read Patterson & Hennessy:
Ch. 5.1 and 5.2: Cache Basics, Direct-Mapped Caches
Very Important Handout:
60 Years of Hardware Evolution
|
Direct-Mapped Caches:
Questions 1 - 6 (skip 7 and 8 for now) in
HW: Caches
|
Submit to Kit:
Label Table Project
Videos — Memory Caches:
Set Associative Caches - 10 min
(continuation of same
slides)
For more depth,
read Patterson & Hennessy:
Ch. 5.3 and 5.6: Set Associative Cache
Optional: Ch. 5.4: Virtual Memory
Preparing for Assembler:
Clone the Assembler repository from
Kit.
Copy *.c, *.h, and sm*.mips from
your LabelTable directory to your Assembler directory,
and do a git add and commit -m "Include LabelTable code".
|
Set Associative Caches:
Questions 7 and 8 in
HW: Caches
Submit to Kit:
Week 8 Reflection is due Sunday evening
|
Week 9: Before Tuesday | TUESDAY - In-Class | Before Thursday | THURSDAY - In-Class |
Submit to Kit:
HW: Caches
Videos — Assembler:
Description of existing Pass 1
code — 9 min (plus optional 4.5 minutes
on how getLabel works)
(From 1:00 - 3:55 is review from end of 2nd Label
Table video)
Transcript has not been cleaned up yet!
Description of Pass 2 (not
including functions in printAsBinary.c) —
17 min
Transcript has not been cleaned up yet!
Introduction to functions in
printAsBinary.c — 9 min
Transcript has not been cleaned up yet!
Presentation:
Work on your presentation —
due Sunday before 10th Week
|
Work on
Assembler Programming Project
|
Presentation:
Work on your presentation —
due Sunday before 10th Week
Assembler:
Continue working on
Assembler Programming Project
Suggestions:
Download new
smallSampleTestfile.mips.decimal
Copy
testPass1.c to assembler.c
and uncomment the 2 lines of code for pass2, if you haven't
already. Compile and run with sample test file.
Change
printf in processR to
printInt(0, 6); printReg(arguments[1], lineNum); printInt(functCode, 6); printf("\n");
Add
printInt(opCode, 6); to existing
processIorJ function.
Start coding
getOpCode ,
getFunctCode and printReg
in any order. Test early and often.
Improve processR ,
processIorJ , printJumpTarget ,
and printBranchOffset as needed.
|
Continue working on
Assembler Programming Project
No Week 9 Reflection
Upload your presentation to the Student Presentations folder
in the Files tab of the General channel
no later than Sunday evening.
Don't assign this on Kit until
ready to enter Presentation grades! Much cleaner,
more reliable to have students upload to the Student
Presentations folder on the Teams site.
|
Week 10: Before Tuesday | TUESDAY - In-Class | Before Thursday | THURSDAY - In-Class |
By Sunday evening:
Upload your presentation to the Student Presentations
folder in the Files tab of the General channel.
Don't assign this on Kit until
ready to enter Presentation grades! Much cleaner,
more reliable to have students upload to the Student
Presentations folder on the Teams site.
Assembler:
Continue working on
Assembler Programming Project
|
Course-specific evaluation questions for this course?
|
Watch Student Presentations and Submit Reflective Responses
to Kit.
Submit the 3 required reflections in one assignment, and up to 5 additional reflections in the second assignment. Use this Markdown template.
Provide some guidance on whether the extra 5 are optional, who
should do it, what the impact will be!
|
Work on
Assembler Programming Project
Assignments Due End of 10th Week:
Submit to Kit:
Assembler Programming Project
— Due Friday of 10th Week
Submit to Kit:
Final Reflection is due Tuesday evening
|