Robert Mullins

Computer Fundamentals and MIPS assembly language programming

The Computer Fundamentals Course material

Supervision Questions

  1. Write out the hexadecimal number "ABCD" in binary.
  2. (a) What is the two's complement 8-bit signed binary representation of the decimal numbers -28 and 16. (b) Show how the numbers can be added together in binary. Convert the answer to decimal.
  3. How is the number 1.75 held as a single precision IEEE floating point number?
  4. Imagine a processor with a 16-bit address bus. What is the largest main memory such a processor can support?
  5. (a) Imagine a processor with 64 registers and 128 instructions. How many bits will be required to encode an instruction that adds the contents of two registers and stores the result in a third register?
  6. What happens when a processors receives an interrupt?

Assembly Language Exercises

The MIPS processor is described in your "Digital Design and Computer Architecture" book by Harris/Harris. Read about the MIPS processor and then attempt the questions below and the practical exercises using SPIM.

  1. Describe the journey a typical ALU instruction might take when executing on a simple implementation of a MIPS processor. How is the instruction initially fetched from memory? how are its operands obtained and from where? where is its result finally stored?
  2. Imagine an array of integers stored in memory that we wish to read one by one. To read the first element we first set a register to hold the address in memory of the start of the array. We then execute a "load word" instruction to transfer the data from memory into one of the processor's registers. In order to load the next element in the array we must add 4 to the current address. Why do we add 4 and not simply increment the address by 1?
  3. Why does a processor typically have a small set of registers in addition to a large main memory?
  4. Why isn't the synthetic instruction "la" (Load Address) an actual instruction in the MIPS instruction set?
  5. What does the program listed below do? Try and guess by looking at the code. If you get stuck you can always run it using the SPIM simulator (see below).
    # mystery.s
    
            .text
            .globl main
    
    main:   la $t0, str1
            li $t1, 6
    
    loop:   lb $t2, 0($t0)
            add $t2, $t2, 1
            sb $t2, 0($t0)
            add $t0, $t0, 1
            
            sub $t1, $t1, 1
            bnez $t1, loop
            
            la $a0, str1
            li $v0, 4
            syscall
    
            li $v0, 10  # exit program system call
            syscall
    
    
            .data
    str1:   .asciiz "cdbncdd!"
    

Installing SPIM

Download the SPIM MIPS simulator by following the instructions here.

If you are using Microsoft Windows, download the ZIP file, open it and run the setup.exe program.

If you are using Ubuntu Linux, type the following to install SPIM:

sudo apt-get install spim

To run SPIM type: xspim

A command line version is also available by simply typing: spim

Exercise 0

Try loading and running the "tick0.s" program (you should be able to download and save the file by right-cliking on the "tick0.s" link, alternative just click on the link and cut-and-paste the code into a text editor.)

Exercise 1

Write an assembly language program that takes an array of 10 values and reverses its contents (so A[0]:= A[9], A[1]:= A[8], ... A[9]:= A[0]).

I've made a start for you here: "tick1.s"

(I'm stuck! Here is one possible solution to help: tick1-complete.s)

Exercise 2

Let's try and sort the elements of the array now. The completed program should print the sorted array (with the lowest number first and highest last). A very simple sorting algorithm that you could use is called 'bubblesort'.

Again, I've made a start for you here: "tick2.s"

Optional Extras!

(i) Try and write a program that calculates the 1000th prime number.

(ii) Try and find the 1000th prime number without using the "div" instruction.

(iii) Write a subroutine to calculate integer square roots.

(iv) Write a program that multiplies two 32-bit numbers without using the multiply instruction. You only need to calculate the lower 32-bits of the 64-bit result.

References and more examples

A gentle introduction to MIPS and the SPIM simulator
SPIM MIPS instruction set summary

Please also refer to the recommended course text books.

History

"Preliminary Discussion of the Logical Design of an Electronic Computing Instrument", Arthur W. Burks, Herman H. Goldstine and John von Neumann, Institute for Advanced Study, 1946.

It is interesting to read Section 4.1 (The Memory Organ), where the authors identify the need for "constructing a hierarchy of memories, each of which has greater capacity than the preceding but which is less quickly accessible".