Computer Organization - Exam 1 Topic List

TEXT CHAPTERS

• Chapter 1: Computer Abstractions and Technology
• Chapter 2: Instructions: Language of the Computer
• Appendix A: Assemblers, Linkers, and the SPIM Simulator

LECTURE NOTES

• Topic 1: Overview
• Topic 2: Arithmetic and Data Movement
• Topic 3: Control Flow
• Topic 4: Program Translation

TOPICS

History

• why we care about computer organization
  • philosophical view: should cover all principles underlying CS
  • practical view: HW defines what SW does, so CompOrg helps us understand how SW works
  
  
• language levels
  • high-level language (HLL)
  • assembly language (ASM)
  • machine language (ML)
  
  
• HLL as abstraction of machine-level operations
  • relative power of each statement
  • translation: HLL to ASM, ASM to ML
  
  
• internal representation of information
  • analog vs. digital
  • reason for using binary
  • why int isn't integer, float isn't real
  
  
• classic elements of computer organization
  • memory, CPU (control unit, processor unit), input/output devices
  • components: registers, buses, arithmetic unit, etc.
  • datapath vs. control
  
  
• concept of generations of computers

Instructions

• concept: instruction set architecture (ISA)
  
  
• assembly language vs. machine language
  • mnemonic form vs. binary
  
  
• competing design philosophies
  • CISC: Complex Instruction Set Computing (e.g., VAX, x86)
  • RISC: Reduced Instruction Set Computing (e.g., MIPS, SPARC)
  
  
• RISC design principles
  • simplicity favors regularity
  • smaller is faster
  • make the common case fast
  • good design demands good compromise
  
  
• concept: ``word'' of storage (32 bits)
  
  
• basic memory organization
  • bytes, halfwords, words, doublewords
  • addresses
  • endianness: big- vs. little-endian
  • alignment concept
  
  
• register vs. variables
  • numbers: $0 through $31
  • names
  • restrictions on use: $zero, $at, $k0, $k1, $gp, $sp, $fp, $ra
  
  
• statement syntax: label, operation, operands, comment
  
  
• types of MIPS statements
  • arithmetic: add, addi, sub, etc.
  • data movement: lw, sw
  • pseudo: move, la, li
  • unconditional transfer: j, jr, jal, jalr
  • conditional transfer: bne, beq
  • condition testing: slt, slti
  • assembler directives: .word, .byte, .ascii, etc.
  
  
• operands
  • registers: $r
  • immediates: n
  • memory: n($r), effective address (EA); displacement addressing
  • destination address for transfers
  
  
• implementing control structures
  • basic concept: condition tests and conditional branches
  • if-then-else, switch
  • for, while loops; loop variations (pretest, posttest, etc.)
  • procedure/function calls
  
  
• subprogram linkage
  • return address
  • stack frame
  • parameter passing: registers, stack
  • register usage: s vs. t registers, v registers

Program Structure and Representation

• general concept: converting code from one form to another
  
  
• forms
  • interpreter vs. translator
  • differences between the two (level of abstraction, execution efficiency)
  • when you would use one instead of the other
  
  
• language levels
  • high-level language (HLL)
  • assembly language (ASM)
  • machine language (ML)
  
  
• basic steps and mechanisms
  • HLL -> ASM: compiler
  • ASM -> object module: assembler
  • object module -> load module: linker
  • load module -> running program: loader (part of OS)
  
  
• assemblers
  • read ASM programs as input, produce object modules as output
  • the assembly process
    • analysis phases
      • lexical analysis (scanner) - converts input into sequence of tokens
      • syntax analysis (parser) - verifies validity of token sequences
      • semantic analysis - determines meaning of token sequences
    • tokens
      • concept: uniform symbols representing language elements
      • self-evident: COMMA, COMMENT, etc.
      • generic (require additional information): OP, REG, SYM, etc.
    • data structures used by the assembler
      • location counter (LC)
        • vs. program counter (PC)
      • operation table (OPTAB)
      • directive table (DIRTAB)
    • data structures built/modified by the assembler
      • symbol table (SYMTAB)
      • definition table (DEFTAB)
      • reference table (REFTAB)
      • relocation table (RELTAB)
    • passes
      • typical assembler is a ``two-pass'' assembler
      • pass 1 tasks
        • build SYMTAB
        • syntax verification
        • (optional) partial translation
        • (optional) intermediate file
        • typical actions for different types of tokens
      • pass 2 tasks
        • final semantic checking
        • final ASM -> ML translation
        • (optional) assembly listing
        • typical actions for different types of tokens
  
  
• fundamental concept: everything is binary
  • no difference between instructions and data
  • bit patterns have meaning depending on how you use them
  • instruction representation
    • formats: i-type, r-type, j-type
    • fields, field contents
    • operand representation (esp. branch/jump destinations and optimization)
      • optimized representations - low-order two bits are always zero, so don't represent them
      • branch destination: 16-bit displacement from instruction after branch (effectively, 18-bit displacement)
      • jump destination: 26-bit target address (effectively, 28-bit address)
    • how to choose most appropriate representation
  • data structures
    • arrays: sequences of words
    • subscript vs. offset into the array