View on GitHub

CS274

Computer Architecture

CS274: Computer Architecture - Data Structures

Activity Goals

The goals of this activity are:

To model and manipulate strings using MIPS
To explain the use of the null terminator when using strings
To model and manipulate arrays using MIPS
To model and manipulate linked lists using MIPS

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: MIPS Strings

Questions

What is the difference between the lb instruction and the lw instruction?
Modify this program to convert each character of a String to uppercase, and then to lowercase.

Model 2: MIPS Arrays

Questions

Now that you know what an array is, what is a string?
What is the difference between a string and an array, in terms of its size and how it is terminated?
Why was it necessary to multiply i by 4 before adding it to the base address of the array?

Model 3: Linked Lists in MIPS

Questions

In your own words, what is a linked list?
Modify this program by adding and calling a function to find and return the address of the node with the value 2.

Model 4: Key Formulas and Concepts Recap

A one-page summary of data structures in MIPS.

Key address formulas:

Structure	Address formula	Micro-example
Word array	address of arr[i] = base + 4 × i	arr at `0x10010000`: arr[3] lives at `0x1001000C`; compute 4i with `sll $t4, $t2, 2`
String (bytes)	address of s[i] = base + 1 × i	s at `0x10010000`: s[3] lives at `0x10010003`; step with `addi $t0, $t0, 1` and read with `lb`
Linked list node (value, next)	value at node + 0; next pointer at node + 4	`lw $s2, 0($s1)` reads the value; `lw $s1, 4($s1)` follows the arrow

Key rules:

Rule	Micro-example
Arrays end when a separately stored size counter runs out; strings end at a 0 byte (the null terminator).	Loop on `beq $t2, $t1, done` (i == size) vs. `beq $t1, $zero, done` (char == 0)
`lb`/`sb` move 1 byte; `lw`/`sw` move 4 bytes and need word-aligned addresses.	Characters use `lb`; integers and pointers use `lw`
A pointer is just an address in a register; NULL is 0, and `$zero` makes the test easy.	`beq $s1, $zero, finished` stops a list traversal
Array elements are contiguous (jump by index arithmetic); list nodes can live anywhere (follow next pointers one at a time).	arr[7] is one multiply-and-add away; node 7 takes seven `lw ... 4(...)` hops
ASCII arithmetic works on characters like numbers: 'a' - 'A' = 32.	Uppercase a letter with `addi $t1, $t1, -32`

The linked list from this activity, drawn in memory (each node is value at offset 0, next at offset 4; the list reads 1 → 2 → 3):

heap base = &heap (say 0x10010000)

address        contents        meaning
-----------    ------------    -------------------------------
heap + 0       3               node C value
heap + 4       0               node C next = NULL (end of list)
heap + 8       2               node B value
heap + 12      heap + 0        node B next --> node C
heap + 16      1               node A value  (head of the list)
heap + 20      heap + 8        node A next --> node B

head = heap + 16:   [1 | *]-->[2 | *]-->[3 | NULL]

Glossary:

Term	One-line definition
Array	A block of equal-size elements stored back to back, indexed by base + size × i.
String	An array of 1-byte characters ending with a 0 byte instead of a stored length.
Null terminator	The 0 byte that marks the end of a string (`.asciiz` adds it for you).
Pointer	A register or memory word holding an address; dereference it with `lw`/`lb`.
Linked list	Nodes scattered in memory, each holding a value and the address of the next node.
Node	One element of a list: here two words, value at offset 0 and next at offset 4.
Traversal	Visiting each element in order: increment an index (array) or follow next pointers (list) until NULL.
Heap	The memory region for dynamically created data, like our hand-built list nodes.
Byte vs. word addressing	Addresses count bytes, so consecutive words are 4 apart -- the reason for the `sll ... 2`.

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.