COSC 065 Hardware Systems

Fall 2008

Homework Assignment #8

Memories Of The Bits We Used To Be

Due: Thursday, Nov 06, 11:59PM CST

Submit: Turn in your source files using the turnin command on Morbius. Please name your files "main-q1.S", "main-q2.S", "main-q3.S",and "main-q4.S". Failure to follow this simple convention may significantly delay grading of your assignment. Include your answers to analysis sections as comments in your code.

Work may be completed in teams of two. The names of both partners must appear in a comment block at the top of your file for credit to be given.

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 "mips-console". 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 -Morse Code

Write a MIPS assembly program that reads in characters until EOF, and outputs alphabet letters in Morse Code using one of the router's front panel LEDs.

The MIPS Playground provides a basic timer function called "sleep()" which takes a single argument number of milliseconds to sleep before returning.

Short elements should be 100ms, long elements 300ms, with 100ms pauses between elements, and 300ms pauses between letters.

The white "Cisco" LED on the router is controlled by bit 3 of at memory location 0xB8000068. This code snippet at the beginning of your main program will enable this output.

This other code snippet declares a data array that encodes the standard Morse Code values for letters A to Z. Since the Morse Code alphabet consists entirely of no more than four dashes or dots per letter, we use four bit pairs to encode the possiilities "short dash" (binary 01), "long dash" (binary 11) or "not part of letter" (binary 00) for letters that are fewer than four parts. Thus, letter 'E', one short dash, is 0x01. Letter 'Q', long-long-short-long, is 0xF7.

Q2 - Eight Queens

Write a MIPS Assembly program that produces a graphical representation of all of the solutions for the Eight Queens Problem. There are many algorithms available for solving instances of the problem, but the easiest way to produce all of the solutions for a given board size is to recursively search the possible combinations and print out the ones that work. The chessboard in the problem is best represented by a single array of 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.

The professor has provided an example program for your reference, runnable on Morbius as ~brylow/cosc065/bin/hw8-queens.

Q3 - Heap of Trouble

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?
  • Q4 - 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?

  • Back
    [Revised 2008 Oct 19 20:58 DWB]