COSC 065 Hardware Systems

Fall 2006

Homework Assignment #7

Recursion and Memory
Due: Tuesday, Nov 21, 12:00PM CST
Work may be completed in groups of up to two students. I strongly recommend that you take the time to meet with your partner in person and work together on these projects, rather than work separately and try to integrate at the last minute.
Background:

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

Always start your assignments using the template here.

Your work must be assembled and run on Morbius (morbius.mscs.mu.edu).

Assemble your programs on Morbius using the command:

gcc <myfile.S>

Run your programs on Morbius using the command:

./a.out
unless you have used the "-o" option to gcc to change the name of your assembled executable.

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 PowerPC 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 PowerPC assembly language program that requests dynamic allocation of memory from the operating system (malloc function) until the operating system will not allocate any more.

  • How much memory will Linux on Morbius give you?
  • How does this amount compare to the physical memory on Morbius?
  • Experiment with different request sizes. What do you see?
  • Is your answer affected by others using Morbius at the same time? What about running two copies of your program at the same time?
  • What is the lowest address returned by malloc? What is the highest?
    Q3 - Text Dump

    Write a PowerPC 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 printf() prints hexadecimal values.

  • Where is your program in memory?
  • Does your program change locations if you run it again?
  • How does your program behave if you run two copies at the same time?
  • Do the contents of the last five memory locations look familiar?
    Q4 - Nuke Stack

    Having worked so hard to understand the discipline of activation records, now let's break them.

    Write PowerPC 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.
    What to turn in:

  • E-mail your assembly source files for Q1 and Q4 to the professor with a subject header "COSC 065 HW#7".
  • Turn in the written component (Q2 and Q3) as hardcopy in the professor's mailbox on the due date, before you leave for break.
  • Be certain to put all team member names on work submitted. It would be courteous to carbon-copy your group when e-mailing the final submission.
    Back