COSC 065 Hardware Systems

Fall 2007

Homework Assignment #7

Recursion is Recursion.

Due: Friday, Nov 02, 2:00PM CDT
Submit: E-mail zipped tarball of main program source files to professor, with a subject header "COSC 065 HW#7".
Work may be completed in pairs. Each team should submit only once. Be certain to put both team member names on work submitted. It would be courteous to carbon-copy your partner when e-mailing the final submission.

Background

Take time to familiarize yourself with the UNIX environment, using the tutorial here.

Always start your MIPS programming assignments using the MIPS Playground tarball. Download the tarball, and open it in your working directory using the UNIX command "tar xvzf xinu-cosc065.tgz". The file main.S is ready for you to begin programming in MIPS assembly language.

Your work must be compiled on a machine with the proper tools, such as the dual-head Linux boxen in the Systems Lab (CU 310). Consult the professor for advice on connecting remotely if the lab is full or you must work from elsewhere.

In order to assemble your program, use the command "make". In order to run your program, use the command "./mipcon". At any time, you can shutdown the MIPS remote console system by hitting Ctrl-Space, followed by the letter 'q', for 'quit'.

Few rules govern the format of assembly language programs. Make an effort to keep your programs readable and well-documented; sometimes the professor gives partial credit if he can tell what you were trying to do, even if it doesn't quite make it.

Q1 - The N Queens Problem

Write a MIPS Assembly program that reads an integer number "n" and produces a graphical representation of all of the solutions for the N Queens Problem associated with that value. There are many algorithms available for solving instances of the problem, but the easiest way to produce all of the solutions for a given value of n is to recursively search the possible combinations and print out the ones that work. The NxN chessboard in the problem is best represented by a single array of N integers, representing the rows, each containing the coordinate of the queen, representing the columns. A solution is an assignment of queens in which no queens share a row, column, or diagonal. (Hint: there is an easy formula for checking whether two queens are on the same diagonal.) Print out the solutions you find using your function from the previous assignment.

Q2 - Heap Limits

Write a MIPS assembly language program that requests dynamic allocation of memory from the operating system (malloc function) until the operating system will not allocate any more.

Analysis Questions:

How much memory will the MIPS Playground give you?

How does this amount compare to the physical memory on the router?

Experiment with different request sizes. What do you see?

What is the lowest address returned by malloc? What is the highest?

Q3 - Text Dump

Write a MIPS assembly program that prints out the memory address and the contents of every location between "main:" and the last line of your main program. Recall that the "%X" format specifier to kprintf() prints hexadecimal values.

Analysis Questions:

Where is your program in memory?

Does your program change locations if you run it again?

What is the meaning of what you are displaying?

Where is the Operating System for the MIPS Playground?

Q4 - Nuke Stack

Having worked so hard to understand the discipline of activation records, now let's break them. Write MIPS assembly function "nukeStack" that when called -- from anywhere in a program that obeys standard calling conventions-- destroys all of the activation records above it on the stack until it finds the stack frame for the main program, and then returns directly to the main program. Suffice it to say, nukeStack does not follow the standard calling convention. Test your nukeStack by calling it from within various programs from previous assignments.