Posted: June 10, 2003

Revised Late Penalty

There is a 20% deduction if you turn it in by July 13th on Sunday before 11:59, but after 11:59 PM.

Emailed projects will not be accepted. You can't email because "submit doesn't work". Emailed projects receive a 0.

Late Penalty

There is a 5% deduction per day. All projects are due by July 12, 2003.

Purpose

The goals of the project are:

• Write MIPS code
• Understand how to implement functions and arrays in MIPS
• Be familiar with the SPIM simulator
• Be able to find and read the SPIM documentation online.

Academic Integrity Statement

Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only, unless otherwise specified IN PRINT by official webpages.

Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Hardcoding is considered a violation of academic integrity

Collaboration on P3

You may work with one other person on this project. There should be a single submission for the project, with both your names.

Topological Sort

You should implement topological sort, using an adjacency matrix. The adjacency matrix should be implemented using a two-dimensional array. In MIPS (and C), a two dimensional array, is really a one dimensional array, where you use a formula with row and column to access elements. Recall that two dimensional array is stored in row major order.

You may wish to use the stack to store the arrays.

Your topological sorrt should be implemented using recursion. This means you should have function calls in your implementation.

Like C, you should not have to copy arrays. You should pass around the address of element 0 to the array.

We will provide you C-code for topological sort. If you can't remember how it works, you may wish to consult 351 notes, or ask a TA.

Input Format

The project can be run using input redirection. However, you need to read the spim documentation (in particular, the command line switches) to determine how you might be able to use input redirection.

The format is:

• Number of vertices
• Number of directed edges
• A list of directed edges

Vertices are numbered from 0 to N-1, where N is the number of vertices.

Thus, the following is a sample input:

5
4
0 2
1 3
2 3
2 1

Thus, line 1 tells you there are 5 vertices. Line 2 tells you that there are 4 edges. Line 3 tells you that (0, 2) is an edge

Lines 3-6 tell you the edges. There are four edges, since line 2 told you there were 4 edges.

At this point, your program does topological sort on all vertices that have indegree of 0, starting from the smallest vertex to the largest. It should produce the same output as the C program provided to you.

A sample C program will be posted in the posting account, and you can copy and compile that to see it in action. You can use that program to help you write the MIPS version.

There will be an explanation of topological sort in the posting account too.

You can assume each edge has unit weight, not that it really matters because edge weights aren't used in topological sort.

Note: the input format listed above is incorrect. We will test your code with an input file that has one value per line. This has to do with the way spim reads in input (which is, not very well, i.e., it can only read one value per line).

Extra Credit

Topological sort only works if the graph contains no cycles, i.e., that it is a directed acyclic graph (DAG). For an additional 15 points of extra credit, determine whether you have a DAG or not. If you have a DAG, then perform topological sort as before. If not, then output the following error message:

Error in topological sort: graph contains a cycle

For an additional 15 points, print out any ONE of the cycles that exist in the graph. For example:

Error in topological sort: graph contains a cycle
Cycle is:  0 - 3 - 5 - 0 

If there is a cycle, do not print any other additional information.

Submitting

You should tar your file and a README. We will post a name for the name of your spim program. It should be named exactly topSort.asm.

You can submit this as project 3. We will post directions to submit in the posting account.

SPIM documentation

To find the documentation, do a Google search on the name, and find the first PDF file that discusses this.

System Calls

The documation for spim is rather lengthy. Most of it is moderately useless. The important parts are the command line arguments, and the system calls.

I/O (i.e., reading input and writing output) in SPIM is rather primitive. I/O is usually taken care of by "system calls", which are like function calls, but handled by the operating system.

If you've ever given much thought to I/O (reading and printing), you realize it must be a difficult think to read in input and print output for so many different kinds of monitors, keyboards, etc. This is usually made easier by having a system call to the operating system called read and write, and letting the OS take care of it.

Read the simple examples on system calls in the documentation. Try a few of them out, make simple modifications, etc.

Basic SPIM

spim basically is an environment. You type spim, type commands that load files, and run programs. This is the usual enviroment. Many interpreted languages behave this way too (like Lisp, Python, etc).

An environment allows you to type commands, make changes to code, and rerun, without recompiling.

However, even though this is the usual way to run spim, it won't do input redirection properly, which is why you need to read the command line arguments and find an appropriate one that will let you do this.

See the class syllabus for policies concerning email Last Modified: Thu Feb 13 09:13:38 EST 2003

Web Accessibility