More MIPS Assembly: 2D Arrays and Nested Loops

Due 11:55pm on Wednesday, October 23, 2019.

Exercise 1: Matrix Multiplication

Let us revisit the matrix multiplication exercise from Lab 5. In that exercise, you wrote a C program to implement matrix multiplication using the following definition: If the two input matrices are A[m][m] and B[m][m], and the result of multiplication is C[m][m], the elements of C are given by:

Here, all the matrices are of size mxm, where m will be at most 10. And a_ij, b_ij and c_ij are elements of the matrices A, B and C, respectively.

NOTE: The above is a mathematical definition in which rows and columns are numbered 1 to m. When converted to an algorithm for implementation in a program, we use row and column ranges of 0 to m-1 instead of 1 to m.

But in this exercise, we will represent all matrices as linear (i.e., one-dimensional) arrays, instead of 2-D arrays, inside the program. Let us call the linearized arrays AA, BB and CC. Thus, these linearized arrays will be declared as AA[100], BB[100] and CC[100], instead of A[10][10], etc.

The reason for linearizing the 2-D matrices is that it is significantly harder to represent and manipulate 2-D matrices directly in assembly. In fact, in almost all situations, statically declared 2-D matrices in C are converted to linear arrays by the C compiler. (An exception is dynamically allocated 2-D arrays which are constructed using the pointer-to-pointer method, as explained in the lecture on pointers using the example of array of strings.)

Row-Major Ordering: When a 2-D matrix is linearized, its elements are stored in the linear array in row-major order, i.e., all the elements of row 0 are stored first, followed by the elements of row 1, etc. Here is a diagram that illustrates row-major (and also column-major) orderings. For example, when a 3x3 matrix D[3][3] is linearized into a 1-D array DD, the latter will have 9 elements stored linearly. Here's a mapping between the elements of D[][] and those of DD[] for the case of m = 3:

    D[0][0] ==> DD[0]
    D[0][1] ==> DD[1]
    D[0][2] ==> DD[2]
    D[1][0] ==> DD[3]
    D[1][1] ==> DD[4]
    D[1][2] ==> DD[5]
    D[2][0] ==> DD[6]
    D[2][1] ==> DD[7]
    D[2][2] ==> DD[8]

Please use ex1.c as a starter file for this exercise. Observe how the declarations for the 2-D matrices at the top of your program from Lab 5 have now been replaced with 1-D arrays. Convert your matrix multiplication code from Lab 5 to adapt it to the linearized representation of the matrices. (If your code for Lab 5 was not correct, please fix it first before proceeding!)

Just as in Lab 5, the first line of the input will be the value of m, which will definitely be within the range 1 to 10. This is followed by m*m integers, one per line, for the values of the matrix A. Then another m*m integers for the values of matrix B. These values are in row-major order. All numbers are in base ten.

We will make a slight change to the output format. We will relax the requirement to use a 6-character width for each element. Instead, each value will simply be printed without any width specification, followed by one space, i.e., printed using printf("%d ",...). This is done because we will convert the C code to assembly (see below), and MARS has no equivalent for specifying widths when printing integers. Once you have printed all the values for a row of matrix C, print a newline, and then proceed to the next row.

TIP: Your code from Lab 5 will change very little. You will simply replace each instance of A[i][j] with AA[...], where the index in the latter will be some function of i and j. Similarly for B and C. Other than these simple changes made in place, the rest of your code can remain the same, line by line.

Compile and run your program on inputs of your choice, and also make sure it runs correctly on the sample inputs provided. The self-checking script for this exercise will be somewhat "whitespace lenient": it will ignore any extra space characters at the beginning or end of each line, or between the values within a line.

Assembly version

Once your C version is working correctly, you will implement the same code in MIPS assembly using MARS.

Please use ex1.asm as a starter file for this exercise. The assembly program should behave exactly as your C program.

TIPS:

The best strategy for this exercise is to convert the C code one line at a time into its assembly equivalent.
Before starting this exercise, carefully review Slides 14-17 of Lecture 8, which show how to convert C language's if/if-else statements and while/for loops into fragments of MIPS assembly.
Since you will need to nest loops, write each loop in a modular fashion. First write the outermost loop. Then, while writing its body, embed another loop inside it, and so on. Each loop will have distinct names for its labels.
Also review the assembly coding examples and your own work for Lab 6.

Test Inputs, Due Date and Submission Procedure

Sample inputs and corresponding outputs are provided on the comp411-2fa19.cs.unc.edu server under /home/students/montek/comp411/samples/lab7.

Your assignment (i.e., the files ex1.c and ex1.asm) must be submitted electronically by 11:55pm on Wednesday, October 23, 2019.

Once you are satisfied that your assembly program is running fine within MARS on your laptop, copy the file ex1.asm to the server under the appropriate folder in your home directory (e.g., comp411lab/lab7). If you have developed your C code on the server, the file ex1.c should already be in that directory, else copy it to that folder. Then, run the self-checking script:

% cd ~/comp411lab/lab7
% cp /home/students/montek/comp411/samples/lab7/* .
% selfchecklab7

How to submit: If the final version of either of your programs were edited on the server, first transfer your work back to your laptop. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.

In case of any problems, please contact the instructor or the TAs.

16 October 2019, Montek Singh, montek@cs.unc.edu