CS 2340 Computer Architecture - Video Notes (Vocabulary Flashcards)

Big-Endian or Little-Endian

• Topic header visible in the lecture: BIG-ENDIAN OR LITTLE-ENDIAN, under the broader unit "6 Data Arrays, Conditional Decisions" by Dr. Alice Wang.
• (Content largely decorative in Page 1; core takeaway is that endian-ness is a topic of computer architecture discussions.)

Subu: Unsigned Subtraction

• Subroutine: Research subu - Unsigned subtraction instruction, assumes operands are unsigned.
• Question raised: What happens when you get a negative number after using subu?
• Answer from the slide: Result is stored as a two’s complement signed number.
• Practical note: In MIPS, subu is an unsigned subtraction that wraps around on overflow, yielding a result modulo 2^32; the result is interpreted as a signed 32-bit value if you view it as signed.
• Key concept: Overflow behavior differs between signed and unsigned arithmetic; be aware of interpretation when reading results.

Term Project: Binary Game (Overview)

• Topic release: The term project topic is the Binary game.
• Reference for feel/specs: https://learningnetwork.cisco.com/s/binary-game
• Game modes per round:
  • Binary-to-decimal mode: The display shows eight boxes containing '0' or '1' plus a blank box for the decimal input.
  • Decimal-to-binary mode: The display shows eight blank boxes for binary input and a final box showing the decimal value.
• Platform considerations: MARS lacks graphics; ASCII-based board is acceptable.
• Minimum requirements:
  • Single-player vs computer.
  • Randomized problems each playthrough.
  • ASCII board display (baseline). Creativity for better visuals earns extra credits.
  • Binary/decimal input validation with error indication for invalid answers.
  • 10 levels total; each level adds one line to the board (Level 1 has 1 line, Level 2 has 2 lines, etc.).
• Extra credit opportunities:
  • Graphic display (5 pts)
  • Sound (5 pts)
  • Timeout feature (5 pts)
• Important note: This is an individual project (not team-based).

Term Project: What It Looks Like (Interface example)

• A sample ASCII board layout is shown with common binary weight columns and a score/level display.
• Binary weights displayed at the top: 128, 64, 32, 16, 8, 4, 2, 1 (and corresponding input areas).
• Score display example: SCORE 1700, LEVEL 1, LINES LEFT 3.
• Binary/decimal boxes and a representation of the current problem state (e.g., 1000000-0, 00000010-128, etc.).
• Controls: PAUSE, SOUND OFF, END GAME.
• This section emphasizes how the ASCII board is used to visualize the game state given the lack of graphics in MARS.

Term Project Submission (Requirements & Evaluation)

• Each student must submit their own work:
  1) Written report
  2) Assembly code – each student’s code must be uniquely authored
  3) User Manual
  4) Oral interview with the grader
• Evaluation breakdown: 60% implementation (verified through oral interview), 20% documentation, 20% demonstration
• Due date: 10/24
• Practical note: Start early to avoid last-minute rush.

Review of Last Lecture (Key Topics)

• Arithmetic Operations:
  • add, sub, addi
  • addu, subu, addiu
• Memory Operations:
  • lw (load word), sw (store word)
  • lb (load byte), sb (store byte)
• Memory architecture:
  • MIPS uses byte-addressable memories
  • Word-address = 4 × element index (i.e., addressing is offset by 4 for 32-bit words)

Arrays of Words (Concepts & Addressing)

• Purpose: Access large amounts of similar data via indexing and sizing.
• Example: 5-element array of words
  • Base address: 0x12348000 (array[0])
  • Steps to access: load base address into a register (la), then use lw/sw with offset for each element
  • Address progression (assuming 32-bit words):
  • array[0] at 0x12348000
  • array[1] at 0x12348004
  • array[2] at 0x12348008
  • array[3] at 0x1234800C
  • array[4] at 0x12348010
• Core idea: The address for element i is base + 4*i.
• Important concept: Access pattern uses base address plus an offset scaled by the element size.

Array vs Pointers (Indexing vs Direct Addresses)

• Array indexing:
  • Requires multiplying the index by the element size and adding to the base address.
• Pointers:
  • Can point directly to a memory address; can simplify or optimize by avoiding explicit indexing math.
• Practical implication: Modern compilers optimize array-iteration loops to similar pointer-based patterns for efficiency.

Array vs Pointer: Code Illustrations

• C example (arrays):
  • clear1(int array[], int size) {
    int i;
    for (i = 0; i < size; i += 1)
    array[i] = 0;
    }
• C example (pointers):
  • clear2(int *array, int size) {
    int *p;
    for (p = &array[0]; p < &array[size]; p = p + 1)
    *p = 0;
    }
• MIPS translations (high level):
  • Loop1 (array indexing):
  • la $a0, array # base address of array
  • li $a1, size # size
  • move $t0, $zero # i = 0
  • loop1: mul $t1, $t0, 4
  • add $t2, $a0, $t1
  • sw $zero, 0($t2) # array[i] = 0
  • addi $t0, $t0, 1
  • slt $t3, $t0, $a1
  • bne $t3, $zero, loop1
  • Loop2 (pointers):
  • la $a0, array
  • li $a1, size
  • move $t0, $a0 # p = &array[0]
  • mul $t1, $a1, 4 # t1 = size * 4
  • add $t2, $a0, $t1 # t2 = &array[size]
  • loop2: sw $zero, 0($t0)
  • addi $t0, $t0, 4
  • slt $t3, $t0, $t2
  • bne $t3, $zero, loop2
• Takeaway: Pointer version often yields fewer instructions in the loop, which compilers may optimize automatically.

Strings (Arrays of Bytes) and Manipulation

• Strings defined as arrays of characters; example: A = "Hello World!"
• Element access examples:
  • A[0] = 'H'
  • A[5] = ' '
  • A[8] = 'r'
• Strings are treated as arrays at the byte level; operations performed with byte-level memory operations.

String Manipulation (Overview)

• Techniques include:
  • Concatenation: join two or more strings
  • Substring extraction: pull a sequence of characters
  • Case transformation: upper/lower case conversions
  • Replacement: substituting a substring with another or deleting it
  • Splitting: dividing a string into pieces at a delimiter
  • Slicing: extracting a substring by start/end indices

String Manipulation in MIPS (Byte-wise Ops)

• Core MIPS instructions for strings:
  • lb rt, offset(rs) # load byte
  • sb rt, offset(rs) # store byte
• Emphasizes byte-wise memory operations for string processing.

String Manipulation: Examples

• Example 1: MyString = "Hello! My name is Tim\n"; replace substring 'T' with 'J' at index 18 (byte-indexing).
• Example 2: MyString = "Hello! My name is Jim\n"; replace substring 'Jim' with 'Meg' at indices 18-20. (Note: A loop would handle this more elegantly.)

Decision Making: Decision Trees and Conditional Operations

• Decision nodes and branches illustrate simple decision trees (e.g., should I accept a new job offer? with branches for accepting/declining). The lecture uses a visual example with a root node and leaf nodes.
• Key idea: Decision trees model conditional paths and outcomes.

Conditional Operations: Branching & Jumping

• Branch to a labeled instruction if a condition is true; otherwise continue sequentially.
• Examples:
  • beq rs, rt, L1 # if (rs == rt) branch to L1
  • bne rs, rt, L1 # if (rs != rt) branch to L1
  • j L1 # unconditional jump to L1
• Uses for control structures like if, while, and for loops.

Conditional Operations: If-Then-Else (Python vs. MIPS Examples)

• Example #1 (Python-like Pseudocode):
  • if (a != b) then else
• MIPS Example #1:
  • bne $s3, $s4, LabelNotEq # code if not equal
  • j ExitLabel
  • LabelNotEq: # code if not eq
  • ExitLabel:
• Example #2 (Python-like Pseudocode):
  • if (a == b) then else
• MIPS Example #2:
  • beq $s3, $s4, LabelEq # code if equal
  • j ExitLabel
  • LabelEq: # code if eq
  • ExitLabel:

If-Then-Else: Practical Binary-branch Example

• Example from Page 19:
  • bne $s0, $s1, Then
  • addi $t2, $t2, 2
  • j Exit
  • Then: addi $t2, $t2, -2
  • Exit:
• Exercise prompt asks to fill in: if (condition) $t2 = else $t2 = ; end result for $t2.

Conditional Operations: Set Less Than & Immediate

• Set result to 1 if a condition is true; otherwise 0.
• Instructions:
  • slt rd, rs, rt # rd = 1 if (rs < rt) else 0
  • slti rt, rs, constant # rt = 1 if (rs < constant) else 0
• These are often used with beq/bne for more complex conditions (e.g.,
• Example: slt $t0, $s1, $s2 # if ($s1 < $s2) then $t0 = 1 else 0

Conditional Operations: For Loop (MIPS & Python Comparison)

• MIPS example #1 shows a for-loop pattern using:
  • Initialization: $t0 = 0
  • Loop body:
  • Increment: addi $t0, $t0, 1
  • Condition: slt $t2, $t0, $t1
  • Branch: bne $t2, $zero, Loop
• Python analogue: for i in range(j): …
• Key point: Demonstrates how loop control is implemented in MIPS using slt and conditional branches.

For Loop: My Turn (MIPS) – Step-Through

• Provided MIPS code snippet (simplified):
  • addi $s1, $zero, 2
  • addi $t0, $zero, 3
• Loop:
  • addi $s1, $s1, 3
  • addi $t0, $t0, 1
  • slti $t1, $t0, 5
  • bne $t1, $zero, Loop
• Question: What is the final state of the register table?
• Given in the slides: final values are presented in a table, showing how $s1, $t0, and $t1 change across iterations (Loop 0 through 5).
• Expected outcome (from slide): after looping, you reach Loop #5 with final values: $s1 = 8, $t0 = 5, $t1 = 0 (approximately; the slide displays a state table that shows the progression).

For Loop: Another Turn (My Turn) – Algorithmic Walkthrough

• Provided MIPS code sequence that computes a small looped update:
  • Initialization: $s1 = 2, $t0 = 3
  • In the loop: $s1 = $s1 + 3, $t0 = $t0 + 1
  • Condition: slti $t1, $t0, 5
  • Loop until condition false
• Expected algorithm result: $s1 becomes 8, $t0 becomes 5, and $t1 becomes 0 at loop exit (based on the example calculations shown).

While Loop: MIPS & Python

• While loop example (MIPS):
  • beq $t0, $t2, Exit # branch if t0 == t2
  • addi $t0, $t0, 1 # increment t0
  • j Loop
  • Exit:
• Corresponding Python example: i = 1; while i < 6: i += 1
• Key pattern: check condition, body, then loop back to test.
• Relevant instructions: beq, bne, j for control flow.

While Loop: Your Turn (MIPS) – Final State

• Given MIPS code snippet (summarized):
  • Loop: add $t1, $t1, $t4
  • beq $t0, $t2, Exit
  • addi $t0, $t0, 1
  • j Loop
  • Exit: …
• The slide lists the final register state for Loop, including values for $t0, $t1, and $t2 across iterations.
• Final state shown in the slide: $t0 = 5, $t1 = 0, $t2 = 9; Branch column indicates the loop exit condition.

Strings: Loops & Loop-Based String Manipulation

• Strings are manipulated using loops (for/while) just like arrays, but within the context of character data.
• Typical operations in string processing include concatenation, search, replace, and transform.
• The CPU uses for- and while-loops to apply these operations, using lb and sb for byte-level access.

String Copy: While-Loop Example (Practice Exercise)

• Input/Output example:
  • Input: x = "Hey you!"; y = ""
  • Output: x remains unchanged; y becomes "Hey you!"
• Pseudocode:
  • i = 0
  • while ((y[i] = x[i]) != '\0')
    i = i + 1
• Data layout (MIPS):
  • x: .asciiz "Hey you!"
  • y: .space 8 # empty string storage
• Pseudocode hints for completing in MARS:
  • Get address of x[i]
  • Read x[i] into a temporary register
  • Get address of y[i]
  • Store the value into y[i]
  • Exit loop if x[i] == 0
  • i = i + 1
• Practical note: This exercise emphasizes byte-by-byte copy and termination on the null terminator.

MIPS Pair Programming Exercise (String Copy & Concatenation Theme)

• Goal: Implement an algorithm that merges two strings into a Result buffer.
• Pseudocode:
  • i = 0; j = 0
  • for i from 0 to N-1: Result[i] = x[i]
  • for j from 0 to M-1: Result[N+j] = y[j]
• Given:
  • Base addresses: x in $a0, y in $a1
  • N in $s0, M in $s1
  • i in $t0, j in $t1
  • Base address of Result in $v0
• Interpretation: The code concatenates x and y into Result (i.e., string concatenation).

Summary (Key Takeaways)

• Arrays: Data and Strings
• Conditional Decision Operations: Branch, Set, Jump
• If-then-else, For-loops, While-loops
• Core examples provided throughout the lecture illustrate how to model control flow in MIPS and understand memory addressing and string manipulation concepts.

Next Lecture Preview

• Topics: Shifters, Logical, Machine Coding - Part 1
• Q&A session planned.

Quick Formulas & Notation (LaTeX)

• Word address calculation for array access:
  • \text{address} = \text{base} + 4 \cdot i
• Binary weights in an 8-bit display (example from the Binary Game board):
  • 128, 64, 32, 16, 8, 4, 2, 1
• Example arithmetic from a loop (s1 example):
  • s_1 = 2 + 2 \times 3 = 8
• For memory operations: word size relation to indexing
  • \text{Word address} \propto 4 \times \text{index}