More MIPS Assembly

Due 11:59pm on Wednesday, October 17, 2018.

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:

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.

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.

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.)

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. 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 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 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.
• 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 under /home/montek/comp411/samples/lab7.

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

Once you are satisfied that your assembly program is running fine within MARS on your laptop, copy the file ex1.asm to the server (classroom) under the appropriate folder in your home directory (e.g., comp411lab/lab7).

Then, log in to classroom, and run the self-checking and submit scripts as you normally do:

% /home/montek/comp411/bin/comp411start
% cd ~/comp411lab/lab7
% selfchecklab7
% submitlab7

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