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 2ⁿ 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 rⁿ-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 rⁿ - 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
    • 6 in all representations
  • 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