About the exam

Monday 29 October 2018 in the normal lecture room (Ford 204) at the normal lecture time (1:50 pm)

study resources: lecture notes, on-line materials (check the homepage), and especially lab assignments

the exam will be one hour long, closed book, closed notes, and closed computer!

typical format: some True/False, some short answer, a few longer "conceptual" questions

Look at the course homepage for topics, diagrams, etc.

See especially items in the News section and the handout archive (which has some sample problems!)

Numeral systems: binary, decimal, hexadecimal, etc.

basic concepts: bases, places, valuation

numerals can be viewed as the coefficients of a polynomial—the base is the “unknown”

what is the highest digit used in base n? how many digits are used in base n?

how many things can we count/represent with n digits in base b? what is the highest number we can represent?

ordering of the numerals: odometer style

fast conversion between bases (Horner's left-to-right accumulating technique; the role of div and mod)

(for each digit, starting with a total of zero: multiply current total by base and add next digit)

addition algorithms on strings of bits (or other digits): carries, etc.

Data Representation

natural numbers: based on the numeral systems above

integers (including negative): standard signed/magnitude representation (with sign bit)

two's complement: conversion to and from, use in addition, checking for overflow

high-order bit always tells sign (no negative zero)

asymmetric coverage: highest magnitude negative number is one greater

for negative numbers, read zeros as ones and vice versa (but also then off by one)

overflow only if sign of result differs from common sign of arguments

letters, symbols, etc.: ASCII code (7 bits, plus maybe one parity bit) versus Unicode (complex, multi-byte, “encoded codes”)

some properties of ASCII codes for letters: each set in order, upper and lower case separated by 32

you should understand the UTF-8 encoding technique (see the Wikipedia description)

sound, graphics, etc.: you should understand basic principles of how various data are represented digitally

see the old lecture on Data Represntation from the course homepage

Boolean Logic

we consider functions (and expressions) over a two-valued (boolean) domain of truth values, 0/1 or T/F

how many combinations are there of a certain number of arguments?

how many functions (with a given number of arguments) are there?

standard operators: AND, OR, NAND, NOR, XOR, XNOR, NOT

use of truth tables to determine the valuation of expressions

use binary numeral “odometer” ordering to cover the possible values of variables

to write a formula for a truth table, use disjunction of conjunctions technique

Gates and Circuits

represent 0/false as either no voltage or lower voltage, and 1/true as higher voltage

transistor allows electrical control of “switching” a signal: either ON to enable flow or ON to prevent flow

can build basic gates (AND, OR, etc.) from a few transistors (e.g., in serial or parallel)

we build circuits by connecting gates with wires, according to the hierarchical structure of the expression

real physical implementation requires some attention to timing, amplification, etc.

combinatorial versus sequential circuits (the latter may include feedback “loops”)

some simple combinatorial circuits (as in lab):

add, shift, count, increment, selection, etc.

sequential circuits can represent memory storage over time

there may be multiple consistent states, which depend on previous inputs

Computer Organization

combinations of circuits are used to build memory, control, ALU

components are connected by busses: groups of wires (under some communication protocol) with control lines to ”direct traffic”

memory: a hierarchy from registers to cache to RAM to disk (network can be seen as especially slow-but-large external storage)

(from closer/fewer/faster/more expensive to farther/more/slower/cheaper)

the control unit decodes instructions, selects an operation, and dispatches arguments/results

ALU (arithmetic-logic unit) performs actual data transformation (e.g., ADD, SHIFT)

realistic modern architectures include many more features:

pipelining: execute several instructions in parallel in stages (fetch, execute, write)

hardware-based stacks (for expression evaluation, method calls)

Instruction Set Architecture and Assembly Programming

program versus data storage: both in RAM, but conceptually separate

issues of word size (trade-off with richness of instruction set)

typically choose some fixed-width binary “word size” (e.g., 8, 12, 16 or 32 bits)

addressing modes: how are operands specified?

implicit: the location of the data is part of the specification of the opcode (e.g. DATA)

immediate: data is encoded in the instruction itself (e.g. SET)

direct: number of register or address of RAM is encoded in the instruction (e.g. ADD, JUMP)

indirect: a register or RAM location holds the address of the actual data (e.g. LOAD, JPIF)

indexed: some architectures allow an “array address” and an index to be combined (not in PC-231)

assembler directives: not actual instructions on the machine, just to the assembler program (e.g., CONST on the PC-231)

macro assemblers: allow abbreviation of instruction sequences as a single “pseudo-instruction”

issue: how do you avoid over-use of registers? (those used in the macro and those in the calling context)

issue: multi-line macros may change line numbering (labels thus become crucial)

issue: how are “arguments”/parameters to macros specified?

issue: can one macro “call” another? (i.e. recursive macros)

Machine code and Assembly Language Programming Techniques

basic problems have to do with limited availability of space (e.g. registers) and movement of data

sometimes need to simulate operations which are not directly available

examples: maximum of two numbers, comparison of numbers, multiplication

approaches to subroutines (“functions” or “methods”)

use macros and simply expand the code in-line (faster)

use a jump to a secondary set of instructions in memory

how do we get back to the calling address?

how do we communicate parameters? (in registers)

do we “save” the values in other registers for the caller, or only use a special subset of registers?

simulating arrays

use consecutive RAM locations to store array values

get continuing access to array elements by holding a RAM address in a register and incrementing (up or down)

array access may depend on the size of array elements (might be more or less than one word of RAM)