Computer Organization: Program 2

Sieve of Eratosthenes in MIPS

Due: Tuesday, November 26 at 3pm


Instructions

  1. read this document in its entirety
  2. experiment with the supplied C version of the sieve
  3. implement and test a MIPS version of the sieve
  4. optimize and retest your MIPS code
  5. submit, via email attachment, your completed, documented MIPS program.

Submit one MIPS assembly language file (as an attachment replying to the official email announcing this assignment). Name your file as sieve_yourname.s where yourname is either your username or the name you generally go by. (I do not care which - as long as I can easily distinguish your programs. For example, mine could be sieve_msiff.s or sieve_mike.s.)


Details

Before proceeding further you should familiarize yourself with the basics of the Sieve of Eratosthenes, for example here.

Download this C version of the sieve. You can compile it using gcc and run it like this:

$ gcc -o sieve sieve.c
$ ./sieve
Enter number up to which to perform sieve: 20
2
3
5
7
11
13
17
19
8 primes found.

For your assembly code, rather than work from scratch, you should start with this MIPS program. It assembles in MARS, though it is not yet close to working correctly.

You will notice that I have included two auxiliary functions which should be used to shield the rest of the code from syscall operations of MARS which will be used: for printing integers and printing newline characters. (The main code, which has been supplied for you, makes direct use of syscalls, but you should not have to modify any of that.)

For example:

# print_int: displays supplied integer (in $a0) on console
print_int:
    li $v0, 1
    syscall
    ...
    jr $ra

The point of these wrapper functions is that you should write the rest of your code to act as if these functions are in a library where you cannot see the code and, therefore, must assume the conventions of saving and restoring appropriate registers whenever you call them. The existence of these wrapper functions means you should not use the syscall operation in the rest of your code.

You should use MARS early and often to test your code.

Unless otherwise indicated you should confine your programs to the following MIPS commands:

    beq bne slt slti
    add addi sub
    sll srl sra
    and andi or ori nor
    j jal jr
    lw lb lbu sw sb

plus the pseudoinstructions (la, li and move). As mentioned, I have used syscall in the library routines, you should not need it elsewhere. (Note: you most likely will not come close to needing all the MIPS instructions listed above.)

Your assembly-language program should be well documented - that could mean a short comment after almost every line and, certainly, larger comments as a prologue to each function.

Your task is to complete the implementation of the three functions: fill_buffer, sieve, and print_primes.


Extra credit

Optimize, optimize, optimize!