Transcript COMS W1004 Introduction to Computer Science

Midterm Exam Logistics
• Thursday, Oct. 25
• Exam starts at 4:35pm and lasts 75 minutes
• Location: DRL A6
• Open-book! Open-notes!
• No electronic devices!
• Review session: Weds Oct. 24, 6:15pm, Towne 315
What does “open-book” mean?
• You may use:
– your textbook
– your lecture notes
– lecture notes from course website
– sample questions and solutions
– graded homeworks and solutions
What does “open-book” mean?
• You may not use:
– electronic devices (no exceptions!)
– the book/papers of the person sitting next to you
(even if that person is really good looking!)
– secret notes that you are sharing with your
friends in the men's room trash bin
Midterm Exam Material
• Assigned reading from P&P chapters 2-10
–
not chapter 6
• Anything covered in lecture
• No UNIX stuff from lab!
• No computer science history!
Format of the exam
• Multiple-choice definitions/concepts
• Short answer and problem solving
– Like questions from book and homework
• Understanding LC-3 code
– no writing LC-3 from scratch!
Preparing for the exam
• Review the lecture notes
• Go through the sample questions from the
study guide and last year's exam
• Make sure you understand the examples
we did in class
• Find students who are smarter than you
and convince them to form a study group
• Use Piazza to ask questions
• Don't panic!
Preparing for an open-book exam
• Make sure you actually study!
• Have a sheet of definitions and terms
• Create an index mapping concepts to
chapters in the textbook
• Organize all your documents so you can
find things quickly
Secret of the Chris Murphy exam
• The number of points a question is worth is
(roughly) equal to the number of minutes you
should be spending on it
–
–
You have 75 minutes to complete the exam
There are 60 total points on the exam
• I like questions that are easy to grade
–
Quantitative instead of qualitative
• Some questions have lots of words: do those
later
Any questions about the
FORMAT of the exam?
Topics Covered
•
•
•
•
•
•
•
•
Computer Numbers (Chp.2)
Digital Logic and Circuits (Chp.3)
von Neumann Architecture (Chp.4)
LC-3 Instruction Set Architecture (Chp.5)
Assembly Language (Chp.7)
Input/Output (Chp.8)
Subroutines (Chp.9)
Interrupts (Chp.10)
Computer Numbers
• Unsigned binary integers
– Decimal-to-binary conversion
– Hexadecimal numbers
– Unsigned binary arithmetic
• Signed binary integers
– Sign/magnitude
– Two’s complement
– Overflow
Computer Numbers (cont.)
• Floating point representation
• Logical operations and bit vectors
• Character representation
– ASCII
– Unicode
Digital Logic
• p-type and n-type transistors
• NOT, AND, and OR gates
• Sum-of-products algorithm
Combinational Logic Circuits
• Adder (1-bit, 4-bit, n-bit)
• Decoder: n inputs, 2n outputs
• Demultiplexer: 1 input, n select lines, 2n output
• Multiplexer: 2n inputs, n select lines, 1 output
Exercises 3.13 and 3.14
• How many output lines will a five-input
decoder have?
• How many output lines will a 16-input
multiplexer have?
• How many select lines will this multiplexer
have?
Memory
• R-S Latch: depends on “state”
• Gated D Latch: single bit of memory
• Register: some number of Gated D
Latches that form a single unit of memory
von Neumann Architecture
• Memory
–
–
address space vs. addressability
MAR and MDR
• Control Unit
–
–
–
fetch, decode, execute
IR and PC
ALU, registers
MAR/MDR questions
• 32-bit address space
• 8-bit addressability
• How many bits in MAR?
• How many bits in MDR?
• How are MAR/MDR used?
• ST R2, DATA
• LD R3, DATA
Homework #3, Part 1
•
•
•
•
•
Instructions are 24 bits long
43 distinct operations in ISA
16 one-byte registers
each memory address holds one byte
total addressable memory space is 64kB
• In “fetch” phase of instruction cycle, what
value is added to program counter?
LC-3 Instruction Set Architecture
• Instruction format
– Opcode
– Operands
• Encoding from assembly language to
machine language (and decoding)
• Types of instructions & what they do
– ALU operations
– Data movement operations
– Control operations
LC-3 Addressing Modes
• Immediate
– LEA R1, DATA
• Direct
– LD R1, DATA
• Indirect
– LDI R1, DATA
• Base-offset
– LEA R0, DATA
– LDR R1, R0, #0
Label
DATA
Address
x1234
x1235
x1236
Value
x1236
xABAB
x5588
Assembly Language
•
•
•
•
Assembler and symbol table
Finding and fixing bugs
What does this program do?
How can this program be improved?
• BLKW, FILL, and STRINGZ
Homework 4 Question #3
.ORIG x3000
ADD R2, R2, #-1
LEA R0, PHRASE
BRp LOOP
LEA R1, DATA
LD
END HALT
R2, VALUE
LOOP LDR R3, R0, #0
STR R3, R1, #0
PHRASE .STRINGZ
“This is not a test!”
ADD R0, R0, #1
DATA
.BLKW x10
ADD R1, R1, #1
VALUE
.FILL x10
Input/Output
• Polling: keep checking to see if input
device has data available (or if output
device is ready to receive data)
• memory-mapped I/O: special addresses in
memory are dedicated to I/O related
actions:
–
KBDR, KBSR, DDR, DSR
Traps, Interrupts, Subroutines
• How are subroutines called? How does the
program know where to go back to?
• How do traps work? How does the
program know where to go back to?
• How do interrupts work? How is the state
saved? What happens when the handler
finishes?
• Traps: GETC, IN, OUT, PUTS, HALT
Exercise 9.2
• How many trap service routines can be
implemented in the LC-3?
• Why must a RET instruction be used to
return from a trap routine? Why not BR?
• How many accesses to memory are made
during the processing of a TRAP
instruction? Assume instruction is already
in the IR
Additional review questions
Exercise 3.5
Complete the truth table for
a transistor-level circuit
Exercise 3.27
Truth table for circuit
with feedback loop
Exercise 5.22
PC: x3010
Address
x3050
x70A2
x70A3
x70A4
Value
x70A4
x70A3
xFFFF
x123B
What do these three lines of code do?
x3010 1110 0110 0011 1111
x3011 0110 1000 1100 0000
x3012 0110 1101 0000 0000
Exercise 5.30
Address
x3100
x3101
x3102
x3103
Data
1001
0001
1001
0000
001
010
010
010
001 111111
000 000 001
010 111111
111111100
What is known about R1 and R0 if the
conditional branch redirects to x3100?
Exercise 8.15
Interrupt-driven I/O