Lab 5 – Mastering the Memory Map

Mastering the Memory Map


  • Develop an understanding of how memory is used by a program.
  • Practice writing programs in MIPS assembly.
  • Practice using git for revision control.

One of the key learning goals in this class is the stored program concept, which we can state in two complementary parts:

  • Data and instructions are represented as numbers in the computer’s memory.
  • Programs are stored in memory to be read or written, just like numbers.

The most immediate consequence of this concept is that it determines that the data and the code of a program coexist in memory. In order to keep things understandable (and somewhat predictable), systems work with a convention for the structure of the memory that is allocated for a program. Assembly programmers see this convention as a memory map, something that helps them visualize how memory is being used.  This map allows one to find items in memory, just like a physical map allows one to find landmarks in a given locale.

As we have discussed in class, every program’s memory map is made of four basic segments of memory: text, data, heap, and stack.

Stack: a dynamically sized segment beginning at the top of memory growing down to smaller addresses. It is used to store the activation record (stack frame) for procedures, a.k.a. functions, and automatic variables (that is, variables local to a function).

Heap: a dynamically sized segment beginning at the end of the data segment growing up towards the stack. Used for general purpose dynamically allocated memory (by malloc, calloc, and realloc).

Data: Storage for static variables. Static variables exist through the entire execution of the program and can be accessed by any procedure/function, i.e., they are global variables.

Text: Storage for the machine language (binary) representation of the program.

Exercise 1: Creating a memory map

Provided below is a simple C program, named squares.c. Study this program to understand what it does.

For this problem, you will create the memory map for this program as if it were running on a MIPS machine. In the notes.txt file, write the 4 memory segments, as in the figure above (text, data, heap, and stack). For each memory segment, specify the beginning address, ending address, and size (in bytes) – write all addresses of each segment in hexadecimal (the beginning and ending addresses should be inclusive). For the data segment, write the address of each global variable. For the stack segment, determine the maximum stack size used by this program, assuming that the stack space used by this program is as follows: the main function uses 0x16 bytes and the printf function uses 0x64 bytes). A sample memory map is shown below.

Here are a couple of additional facts you need to consider to flesh out this memory map:

  • The text segment begins at address 0x0040 0000.
  • The last addressable byte in memory is at address 0x7fff ffff.
  • The data segment begins immediately after the text segment ends.
  • The heap is unused in this program.
  • All integers require 32-bits of storage (4 bytes).
  • The size of the generated machine code is exactly 0x100 bytes (that is, 256 bytes in base 10).

Exercise 2: Syscalls

When working with file I/O, we learned that the Unix system provides functions that we referred to as system calls (syscalls) for various basic operations, such as open, read, write, and close. The model of MIPS system used in our textbook provides mechanisms for I/O that match the concept of syscall very closely and you can read about them in zyBook 14.7 (SPIM). Take the time to read this section – don’t be puzzled by the fact that the book refers to the MIPS simulator by the name SPIM. In this class, we have opted to work with MARS instead, which offers everything you would find in SPIM and more. Once you are done with this short reading, take a look at the following web page to get acquainted with MARS syscalls:

Once you have studied this material, write MIPS code fragments in your notes.txt file to implement each of the actions below using syscalls (the original ones from SPIM or the dialog-based ones from MARS):

  1. read an integer from the keyboard into $t0
  2. print an integer in $t0 to the terminal
  3. read from the keyboard a string and store it at the address corresponding to the label my_str
  4. print to the terminal a string declared at the address corresponding to the label prompt
  5. exit a program returning with the value -1

Save the notes.txt and add it to your git repo.

Exercise 3: searcharray.s

Copy the file searcharray.s from the ~cs206/Labs/Lab05  folder to your Lab05 working directory. Startup MARS and load the file searcharray.s. Study the source code, and run it as it is, before making any changes. You should get the output:

loop terminated, i= 4

This program searches the array save in memory for the occurrence of the value stored in $t0, which is assigned in the instruction just before the test label is defined. When the value is found in the array, the program stops the search and prints the index of the matching element.

This program illustrates how one can write MIPS assembly code to access the element of an array indexed by a variable, as in save[i], for instance. The difficulty is that instructions for memory access, such as lw and sw, require one to use a constant offset from the base address stored in a register. For instance, in the instruction below:

lw $t0, 4($s1)

the offset 4 is a constant that is encoded in the machine language instruction. The program given to you illustrates how one can use the instructions sw and lw to access elements of an array indicated by an arbitrary index.

This program also illustrates how a MIPS assembly program can use system calls, which correspond roughly to the library and operating system functions you used in C programming. These syscalls are invoked as follows: you load into register $v0 the numeric code that identifies a function, then you load any other parameters into their respective registers, and finally invoke the instruction syscall. In this program you see examples of calls to print a null-terminated string, to print an integer, and to terminate the program. The full list of MARS syscalls is available through the Help->Help menu (similar to a Linux man page). Take a minute to explore the help menu (all of the tabs)–there is a lot of other useful information in there.

Looking back at searcharray.s, you might realize that it would be better to ask the user to enter the value for which they want to search the array. This will require you to use the print string (4) syscall to display a prompt to the user and then the read integer (5) syscall. [Note: do NOT use InputDialogInt (51)].

Add code to searcharray.s to show the user the following prompt:

Enter the value to search for:

In order to implement this, you should use the assembler directive .asciiz, which stands for zero-terminated ASCII string, to store the prompt string in the data segment. In the program’s code, you invoke the appropriate syscall to display it;  after displaying the prompt, use a syscall to read an integer and store the entered value in $t0. 

Assemble your program and get ready to execute it a few times in order to test it. Use the following inputs:

  • 7 –> This should produce output i=4
  • 0 –> This should produce output i=0
  • 5 –> What output do you see? What is happening with your program?

To figure out what is happening with this last test case, you will use the debugging features of MARS, that is, you will “watch” the program as it executes. To control how fast the program executes, you can adjust the “Run speed” slider on the top right of the main window (in the Execute view shown below). If this slider doesn’t appear, resize your window to be wider and it will magically appear.

If you drag the slider down to something less than the maximum value, you can watch your program run in real time. It seems to spin forever in the main loop. By now, you should be realizing that there is no code to stop the search when the program hits the end of the array. Knowing that the array has 10 elements, the natural thing to do is to modify the program to stop when it gets to the end of the array. You can assume this program will always just have an array of 10 elements, in the next exercise we will work with a variable length array. In your modified program, if there is no match found in the array, the message “value not found” should be printed out.

When you are ready to move on, don’t forget to add your modified searcharray.s to git.

Exercise 4: Variable length arrays

Working with arrays of fixed length is fine, but sometimes we work with arrays not knowing its length ahead of time. C Strings are a great example of this: they use a null terminator or zero byte (‘\0’) to mark the end of the array. This value which marks the end of a variable length array is called the sentinel value. Typical sentinel values are 0, MAX_INT, -1, or any arbitrary magic number like 0xF00D. Any value will work as long we are certain the sentinel won’t show up in the array!

If you haven’t already, copy the file ~cs206/Labs/Lab05/sumarray.s  to your Lab05 folder and open the file sumarray.s in MARS. There isn’t much implemented in this program because the task is up to you! The main idea in the assembly program you will write is to traverse the variable length array A, count the number of elements encountered, and summing them up. Although the array A is defined as having 6 elements, you should not assume this will always be true. The assumption you can count on is that the array will always be terminated by a sentinel value 0 (zero). Notice that the sentinel does not count as an element.

The array has been declared for you and you can refer to the address of the base of array using the label A. Since A is an array, you will have to refer to it as a memory location, using offset ($regbase) addressing. At execution time, the value in the base register and the offset are added together to yield the memory address. There are at least two ways to accomplish this, one of which you’ve already seen in Exercise 3. The alternative is to let the assembler do some of the work and use a form of base+offset addressing that looks more like a subscript. The gist of the idea is illustrated in the unfinished code snippet below:

move $t0,$zero
lw $t1, A($t0) # assembler uses address of A as offset, $t0 as
# base – adding them together yields address of
# the first element in array
addi $t0,$t0,4 # adjusting the base to “see” next element

Your solution to this problem must use this alternative method. When you assemble your code, you will notice that every  lw instruction in the format above gets translated to the following 3 instructions: lui/addu/lw which compute the proper memory address in the $at register.

The output of your program with the given input should be:

Number of elements = 6
Summation = 19

Test your program with other inputs to make sure that you program works if you add elements to A. Verify that your program also works correctly if the first element in A is 0 (an empty list with 0 elements and sum of 0).

When you are ready to move on, change the array A to have at least 5 non-zero items (so we can easily grade your program) and don’t forget to add sumarray.s to git!

Exercise 5: Adding Squares

In this activity you will write a MIPS assembly translation of the C program given in Exercise 1. Name your new assembly program sumsquares.s. Use the appropriate syscalls for I/O. Make sure the output and general behavior matches exactly what the C version does. For example, C variables should be created in memory in the same memory segment as the C program. Your assembly program should store the results from registers into these variables in memory. Use the previous exercises to model the structure of your program.

To allocate space for your array, you might want to look at the .space compiler directive.

When you are satisfied with your solution, don’t forget to add sumsquares.s to git, then commit and push all to gitlab!


When you are done with this assignment, add all relevant source and text files go git and push to gitlab.

  • notes.txt
  • searcharray.s
  • sumarray.s
  • sumsquares.s

Grading Rubric

100 points total: (no prelab due to exam)

  1. [2 points each, 20 total] Exercise 1: In notes.txt, begin address, ending address, and size for each of the 4 memory segments (text, data, heap, stack).
  2. [2 point each, 10 total] Exercise 2: In notes.txt, the 5 syscalls are provided with the correct details to run using functionality from SPIM or MARS (GUI).
  3. [20 points] Exercise 3: searcharray.s was modified to prompt the user for the value to search for and stop if the value is not found and print “value not found“.
  4. [20 points] Exercise 4: sumarray.s completed, correctly detects the length of the array and computes the sum (including if it is zero-length) using the appropriate array access method.
  5. [30 points] Exercise 5: sumsquares.s completed and runs; output matches the C version (minor formatting variations are acceptable).
Print Friendly
Posted in Lab

Leave a Reply

Your email address will not be published. Required fields are marked *


This blog is kept spam free by WP-SpamFree.