CSE 378 Assignment 2

Winter 2001

Due: Wednesday 1/17/01

Purpose

Introduction

 1  # compute the factorial of 8, using the following algorithm:
 2  #
 3  #   N = 8;
 4  #   result = 1;
 5  #   for (counter = 1; counter <= N; counter++)
 6  #     result = result * counter 
 7  #
 8
 9          .data                           # begin data section
10  msg:    .ascii  "The factorial is: "    # message string
11          .text                           # begin program text
12          .globl  main                    # main must be a global symbol
13  main:
14          subu    $sp, 28                 # adjust stack pointer
15          sw      $ra, 20($sp)            # save return address
16          li      $t0, 1                  # $t0 will hold result, init 1
17          li      $t1, 8                  # $t1 will hold N, init 8
18          li      $t2, 1                  # $t2 will hold counter, init 1
19  top:
20          bgt     $t2, $t1, bottom        # if counter > N, exit loop
21          mul     $t0, $t0, $t2           # result = result * counter
22          addu    $t2, $t2, 1             # increment counter
23          j       top                     # goto top
24  bottom:
25          sw      $t0, 24($sp)            # we'd better save result
26          li      $v0, 4                  # finished w/ loop, now print out
27          la      $a0, msg                # message, by invoking syscall 4
28          syscall                         # (print_string)
29
30          li      $v0, 1                  # now print out result, by 
31          lw      $a0, 24($sp)            # invoking syscall 1 (print_int)
32          syscall
33
34          lw      $ra, 20($sp)            # restore return address
35          addu    $sp, 28                 # pop stack frame
36          jr      $31                     # return to caller
37          .end    main

/cse/courses/cse378/CurrentQtr/homework/hw2.spim

Using the Simulator: Instructions and Questions

1. You'll first want to read over the document, Getting Started with Spim.

2. Start the simulator, load the program, and run it by single-stepping through it. What is printed on the spim console?

3. List the differences between the provided program and the instructions being executed:

4. Complete the following table by examining various registers and memory location contents after the appropriate instructions are executed. Using the breakpoint command may help in certain situations.

   Location	Line 17	Line 22 2nd iteration	Line 22 4th iteration	Line 22 7th iteration	Line 34
   $t0
   $t1
   $t2
   20($sp)
   24($sp)

5. In total, how many instructions (in the simulator) are executed to calculate the factorial of 8? The right way to answer this question is not to step the program through 8 loops and count instructions, but rather determine how many instructions are exectuted before the loop, during one iteration of the loop, and after the loop. Then you can give us an answer in terms of N, where N is the value we're calculating the factorial of (as well as the number of times the loop iterates).

Assembly Programming: Modifications

Compilers

#include <stdio.h>

/* Compute the factorial of 8 */

void main ()
{
  int counter;
  int N;
  int result;
  N = 8;
  result = 1;
  for (counter=1; counter <= N; counter++)
    result = result * counter;
  printf("The factorial is: %d\n", result);
}

The cross-compiler lives in /cse/courses/cse378/CurrentQtr/bin/mips-gcc. To use it, just type:

  mips-gcc hw2.c

1. First, compile the program without optimizations: mips-gcc -O0 hw2.c. The -O flag (that's the letter "O", not zero) is the optimization flag for the compiler. -O0 ("oh-zero") turns off all optimizations. This will produce a file called hw2.s. Take a look at this file to see the relationship and differences between operations in high-level language and assembly language. You'll want to save a copy of this file before moving on to the next step. (Something like cp hw2.s hw2-unopt.s should do the trick.)

2. Next, compile the program with (more or less) full optimization: mips-gcc -O2 hw2.c. This will produce a file called hw2.s. Save a copy of this program in hw2-opt.s. The compiler generated assembly programs may contain some syntax which you do not understand (particularly the assembler directives). Don't worry about this.

3. Compare hw2.spim (the hand-coded assembly program we have provided) and hw2-unopt.s (the compiler-generated, unoptomized assembly program). What is the main difference between the main loop of hw2-unopt.s and hw2.spim? Which program do you think will execute faster? Why?

4. Compare hw2.spim and hw2-opt.s (the compiler-generated, fully optimized assembly program). Which program do you think will execute faster? Why?

5. Compare hw2-unopt.s and hw2-opt.s. Describe, briefly, what kind of instruction(s) the compiler has eliminated in order to optimize the program. (One sentence should suffice.)

Ask a Question (or Two)

Deliverables