|
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 GoalThe goal of this programming project is to give you
experience writing assembly language for the MIPS processor. To
successfully complete this project, you will need to understand the
following items:
- The MIPS instruction set (lectures 2, 3)
- The function calling convention for the MIPS processor.
We recommend that you use xemacs to edit your
files. If you are logged in remotely, use xemacs -nw to edit
files. Other editors installed include vi , pico ,
and emacs .
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. |
| | |
| |