Project 1: Assembly Language Programming

SETUP

The first thing you need to do is add the path to the course tools to your .cshrc file, if you haven't already.  The .cshrc is a script that runs whenever you log into the cluster or when you type the 'source .cshrc' command from your home directory (where it exists).  One of the important things that this script does is set your PATH environment variable, which you can see by typing 'printenv PATH'.  The PATH environment variable is the path in which the command interface will search for a command that you type, so instead of having to type absolute paths to each program/script/command, you can just type the name of the program/script/command.   

To edit you .cshrc file, go to your home directory and type either 'xemacs .cshrc &' or 'pico .cshrc', depending on which editor you'd rather use.  Now find the line in the .cshrc file which contains set path = ( ... ), where '...' are the elements of the current path.  Add the following paths to the path (if they don't already exist) /usr/local/cad/bin and /usr/class/ececs314/bin.  You can specify each additional path on the same line or on different lines, as long as each line ends in '\ ' (except the last line of the path).  This should seem obvious once you examine your own .cshrc.  So when you're finished it should look something like this:

set path = (... \

                    /usr/local/cad/bin \

                    /usr/class/ececs314/bin \

                    ...) 

In order for this changes to take effect, you need to relog or type 'source .cshrc' for each console window you have open.  If you need more details on the text editors or the process of editting your .cshrc file, a simple web search will yield lots of info.  Note, you only have to do this once.

The next thing you need to do is create a group on the bsdcluster (this has nothing to do with CMS, that's another story).  Creating a group using the addgroup.pl script on the cluster will do two things: create a group and create a directory for your work in the /work directory.  To create a group, use the following command:

addgroup.pl mygroup netid2 ... netidn

Here, I'm calling the group mygroup and assuming netid1 is your netid.  You don't need to explicitly enter your netid, just each additional netid for your group.  If you need to change the group at anytime, only the owner(you) can rerun the above command with a different set of netids.  To check the groups that you belong to, just type the command 'groups'.  As noted earlier, a directory for your group work (with the correct permissions) is created in /work/mygroup (or whatever your group name was).  Remember, to move to this directory use the 'cd /work/mygroup' command.  If you keep the same group all semester this is a one time deal, if not you have to change your groups accordingly.

IMPORTANT: Group creation gets queued and runs at 12am , 4am, 8am, 12pm, 4pm, and 8pm. This means that if I run the addgroup.pl script at 2pm, I won't see the results until after 4pm.

Now on to more project specific info, please read everything here carefully:

• The template files for this project are in /usr/class/ececs314/proj1.tar.gz. You can extract them into your current directory by executing

  tar xzfv /usr/class/ececs314/proj1.tar.gz

  This creates a directory named ececs314/proj1 that contains the template files for this project.  You'll most likely want these directories to be in your home directory, so use the 'cd' command to ensure that you are there.  The tar command merges multiple files into a single archive and can extract files from such an archive.  The .gz extension indicates that tar was performed with the z flag and is compressed.
• You will turn in this project electronically. See the end of this document for specific details.  
• The consultants and TAs can help you when you encounter problems. If you still have problems after talking to the consultants, you can either schedule an appointment or try the newsgroups.

Project Goal

• The MIPS instruction set (lectures 2, 3)
• The function calling convention for the MIPS processor.

Consult the first set of section notes for more details about signing into the bsd-cluster 

A program you might find useful for this project is hexcalc. hexcalc is a simple multi-radix calculator that can convert numbers from one base to another. You can also use the calculator from Windows by chosing the scientific view.

IMPORTANT! Get started as soon as possible. It will take you a bit of time to get accustomed to the CSL teaching lab environment if you have never used Unix before.

Part 1: Finding the smallest element in an array
	The first assembly program you will write finds the smallest element in an array of signed integers. (Recall that an integer is stored in one word---4 bytes---of memory; in 2's complement form.) The template for this program is file part1.s in the eecs314/proj1 directory. Given that register $4 contains the address of the array in question, and register $5 contains the length of the array, write an assembly language program that calculates the smallest element in the array and stores it in register $2. Insert your program in the space indicated by the comments in part1.s . Compile your program into a memory image file by saying gmake part1 in the proj1 directory. This generates a file called part1.image (and a few others) that specifies the contents of the memory. To run this program through the simulator, use the command gmipc Select part1.image as the image file to run it.

Part 2. Write a function that finds the smallest element in an array.
	In this part your task is to convert the assembly code you wrote for part 1 into the code for a function that calculates the smallest element in an array. The function has the following prototype: int arraymin (int *array, int len); (int *array declares variable array to be of a type that contains an address in memory where an integer is stored.) Modify file arraymin.s so that it contains the function. Pay attention to the MIPS calling convention. You are supplied with a test file test_array.s that calls the function with three different arrays. You should only modify arraymin.s . Compile your program into a memory image file by saying gmake part2 This generates a file called part2.image . To run this program through the simulator, use the command gmipc (Select part2.image as the image file.)

Part 3: Recursive Merge-Sort
	In this exercise, you will implement merge-sort (non-descending order) in assembly language. To merge-sort an array, we conceptually split the array in half, recursively sort the two halves, and then merge the two halves, preserving the order. Asymptotically, merge-sort is as efficient as any other sorting algorithms (e.g., heap-sort) and has a worst-case running time of O(n log n) where n is the size of the array. The only tricky part of the algorithm is merging the two halves that are sorted. To do so, we need to use a scratch array. The basic idea behind merging is as follows: keep an index into both halves (say lo_index and hi_index) and an index into the scratch array. If A[lo_index] <= A[hi_index], then copy A[lo_index] into the scratch array at the current scratch index, and increment both lo_index and the scratch array index. Otherwise, copy A[hi_index] into the scratch array and increment both hi_index and the scratch array index. If you run out of elements to copy from one half, then you just copy the rest of the elements in the other half into the scratch array. Once all of the elements have been merged into the scratch array, you can copy them back into the original array. It's a very good idea to write and test your merge-sort algorithm in a high-level language before trying to translate it to assembly code. In fact, we expect to see your high-level code in the comments that explain your assembly code. You also need to pay special attention to the calling conventions and stack frame management, as this function is recursive. We provide you with the necessary framework to get started and to test your code. msort.s contains the skeleton for the merge-sort function that you have to write. The merge-sort function has the following prototype: void msort (int *array, int *scratch, int len); The file test_msort.s contains the code that tests your assembly routine. You need not modify this file, although you can if you want to run additional tests. You can compile your assembly file and generate part3.image by saying: gmake part3

Submitting Your Project
	There are no written reports you have to hand in for this project. All submission is done electronically once you have finished the project. In your ececs314/proj1 directory, create a file named README. The first four lines MUST BE: NAME: username1 username2 Name of person1 Name of person2 PROJECT 1 username1 and username2 should be the login ids of you and your partner. If you have any special instructions or anything you'd like us to know about your project, please let us know by typing it into the README file.  For this project, the only files that you will edit are "part1.s", "arraymin.s", "test_array.s", "msort.s", and "test_msort.s" (although the test files are really there for your convenience).  There is a script available that will tar these up for you, and check that all the files are present, so that you can submit them to CMS.  Once you have finished the project, simply type: proj1tar.314 in your ececs314/proj1 directory.  The script will create proj1_valid_sub.tar.gz, which you can submit to CMS via the web.  The script will complain if you are missing files.