Computer Organization - Exam 2 Topic List
TEXT CHAPTERS
- Chapter 3: Arithmetic for Computers
- Appendix A: Assemblers, Linkers, and the SPIM Simulator
- Appendix B: The Basics of Logic Design
LECTURE NOTES
- Topic 4: Program Translation
- Topic 5: Information Representation
- Topic 6: Introduction to Digital Design
- Topic 7: Larger Digital Circuits
TOPICS
Linking and Loading
- object module
- relocatable vs. absolute modules
- contents: header, code, reltab, symtab, deftab, reftab
- example format: ELF (general details)
- linkers
- also called link editors or linkage editors
- load module vs. object module
- linking process
- concept of relocation, load point(s)
- relocating vs. absolute linkers
- basic tasks; relocating linker algorithm
- loaders
- part of the OS
- basic tasks
- libraries
- concept - archive of precompiled code
- static vs. dynamic linking
- shared libraries
Information Representation
- internal form: binary
- must encode information to hold it in memory
- instructions
- data - integer, floating point, non-numeric
- size of thing in memory determines range of possible values
(n bits yields 2n representations):
| Bytes |
Bits |
# of representations |
| 1 |
8 |
256 |
| 2 |
16 |
65,536 |
| 4 |
32 |
4,294,967,296 |
- non-numeric data
- typically, characters
- mapping of bit patterns to characters defines a character set
- common character sets: ASCII (7-bit), BCD (6-bit), EBCDIC (8-bit),
Unicode (16-bit)
- order of mappings defines the collating sequence for the set
- MIPS instructions for working with characters:
lb rt,n(rs) load byte, sign-extends to 24 bits
lbu rt,n(rs) load byte unsigned, zero-extends to 24 bits
sb rt,n(rs) store byte, stores low-order 8 bits
- can also do sign or zero extension with shift instructions;
- left logical shift:
sll rd,rs,shamt and sllv rd,rs,rt
- right logical shift:
srl rd,rs,shamt and srlv rd,rs,rt
- right arithmetic shift:
sra rd,rs,shamt and srav rd,rs,rt
- numeric data
- representation of an abstract concept
- we represent ``numbers'' as a sequence of numerals
- numerals encode values using positional representation
- positional representation
- digits have values, as do positions
- ``meaning'' of a digit is its value multiplied by the value of its
position
- important concept: any number can be represented in any radix
(base) as a sequence of numerals
- common radix values:
- decimal: powers of 10, digits 0-9
- binary: powers of 2, digits 0-1
- octal: powers of 8, digits 0-7
- hexadecimal: powers of 16, digits 0-9 and A-F
- positional values are powers of the radix (base) of the representation
- positions to left of ``radix point'' are positive powers of the radix
- positions to right of ``radix point'' are negative powers of the radix
- converting numbers from one representation to another
- other base to decimal: use multiplication-based algorithm
- decimal to other base: use division-based algorithm
- between power-of-two bases (2, 8, 16, etc.): use bit groupings
- representing numeric data
- bits are numbered from 0 (rightmost, least significant) to N-1
(leftmost, most significant)
- rightmost byte is least significant (LSB)
- leftmost byte is most significant (MSB)
- MIPS stores these in big-endian form
- halfwords must be aligned on even boundaries
- words must be aligned on multiple-of-four boundaries
- all use fixed-size representations (1, 2, 4, or 8 bytes)
- all have the potential for overflow (result from operation won't fit
in the representation)
- unsigned integers
- easy - interpret N-bit value as an unsigned binary value
- arithmetic is simple
- signed integers
- must encode sign along with value
- encoding schemes:
- sign-magnitude
- most significant bit is sign, other bits are (unsigned) magnitude
- arithmetic is complicated (esp. for differently-signed operands)
- two representations for 0 (positive 0, negative 0)
- diminished radix complement
- in binary, this is called one's complement
- representation is rn-1 - magnitude for n bits
- arithmetic is easier than with sign-magnitude, but still tricky
(must use end-around-carry if generate a carry of 1 off the left end of
the result)
- still two representations for 0
- radix complement
- in binary, this is called two's complement
- representation is rn - magnitude for n bits
- arithmetic is trivial - can ignore any carry off the left end
- only one representation for 0
- fundamental concept behind encoding: ``value'' of bit pattern
depends on the encoding being used
- ex:
0110 in a four-bit representation
- ex:
1011 in a four-bit representation
- 11 if unsigned
- -3 in sign-magnitude
- -4 in one's complement
- -5 in two's complement
- non-integer numeric values
- fixed point vs. floating point
- use scientific notation to represent value
- critical concept: ``meaning'' of a sequence of bits depends on how
you use it
- ex: 32-bit value
00110100010100100100100101010100
- as 32-bit FP value:
1.642863 * 2-23 = 1.958 * 10-7
- as 32-bit integer:
877,807,956
- as 32-bit instruction:
ori $18,$2,18772
- as four ASCII characters:
4RIT
Introduction to Digital Design
- use Boolean algebra to describe circuits
- Boolean operations: AND, OR, NAND, NOR, XOR, NOT
- use of truth tables to describe functionality
- deriving Boolean expressions from truth tables
- variations: Sum of Products, Product of Sums
- minterms: AND together values of input variables to get result of 1
- maxterms: OR together values of input variables to get result of 0
- SP ORs together minterms for which function is 1
- PS ANDs together maxterms for which function is 0
- can prove SP and PS forms are equivalent with truth tables
- manipulating Boolean expressions
- can use Boolean identities to combine/reduce terms to simplify
expressions
- laws: identity, zero/one, inverse, commutative, associative,
distributive, simplification, DeMorgan
- can reduce terms using Karnaugh Maps (K-maps)
- concept: convert logical adjacencies in truth table to physical
adjacencies
- can circle groups of adjacent '1' values and derive reduced SP terms
from grouping
- or, can circle groups of adjacent '0' values and derive reduced PS terms
from grouping
- groups are power-of-two in size (2, 4, 8, etc.)
- size of k-map depends on number of input variables
- circuit design
- Boolean operations are implemented using gates
- implement Boolean expressions as combinations of gates
- basic gates: AND, OR, Buffer, NOT, NAND, NOR, XOR
- can do gate substitution by using DeMorgan's Law
- apply two complements to entire expression
- carry one of them partway ``in'' by using DeMorgan's Law
- SP expression (OR of AND subexpressions) can be implemented using
only NAND gates
- PS expression (AND of OR subexpressions) can be implemented using
only NOR gates