Computer Architecture SNE 2015

Assignment 1

Date: September 10th, 2015
Deadline:September 23rd 2015, 23:59

1   Instructions

2   Prerequisites

You will need the following:

3   Getting acquainted with the environment

  1. Open the program hello.c in a text editor. Analyze what it does. Picture in your mind its expected output.

  2. Compile the program down to assembly:

    ./alpha-cc -S hello.c -o hello.s
    
  3. Assemble the code:

    ./alpha-cc -c hello.s -o hello.o
    
  4. Assemble the minicrt:

    ./alpha-cc -c minicrt-alpha.s -o minicrt-alpha.o
    
  5. Link both objects to form an executable file

    ./alpha-cc hello.o minicrt-alpha.o -o hello.bin
    

    Note

    You can simplify steps 2-5 as follows:

    ./alpha-cc hello.c minicrt-alpha.s -o hello.bin
    
  6. Run this program:

    mgsim -c minisim.ini hello.bin
    

    Check that the program indeed prints the expected output. Once the program terminates, the simulator prints a prompt where you can enter commands to inspect the architecture. Use the command "help" for an overview of the possible inspection commands. Use "quit" to exit the simulator.

    Note

    Depending on your system, the command to run may be called mtalpha-mgsim instead. Try this if mgsim fails.

  7. Repeat steps #1-#6 using theother programs helloworld.c, fibo.c, comp.c and sumdemo.c. Note that some files must be linked with others (e.g. sumdemo with sum and roman).

4   Mandatory assignment

(Successful completion of this part gets you to grade 6,5.)

  1. Generate the unoptimized Alpha assembly code for comp.c:

    ./alpha-cc -O0 -S comp.c
    
  2. Rename the assembly file to comp-0-alpha.s. Add code comments to this file that explain how the code works.

    Explain how the different registers are used and describe the structure of the assembly program.

    Relate this structure to the original C code.

    Your comments should explain the workings of the program and not the (trivial) meaning of the instructions themselves. (eg we know that lda $1,104($31) loads the value 104 into register $1, so don't tell us)

    Place the annotated file in your submission archive.

  3. Calculate by hand, for this program:

    1. the number of static instructions (number of instructions encoded in the program image).
    2. the number of dynamic instructions (actual number of instructions executed at run-time).
    3. the number of memory accesses (dynamic count of memory load and store instructions).

    Report these numbers in your report.

  4. MGSim can report the number of instructions executed and the number of load and store instructions performed at the end of the execution of a program. Use MGSim to verify your estimations for #3b, #3c. Summarize MGSim's output in your report.

    Note

    You may notice that MGSim's measurement is different than yours in the previous question. This will not necessarily reduce your grade. However, if you measure a difference you must explain in your report what you didn't take into account in the manual count.

    Tip

    The instructions in print_roman will "pollute" the results reported by MGSim. Determine a way to exclude this overhead from the verification.

  5. Generate the unoptimized RISC-V assembly code for comp.c:

    ./riscv-cc -O0 -S comp.c
    
  6. Again, rename the assembly file to comp-0-riscv.s. Add code comments to this file that explain how the code works. Explain how the different registers are used and describe the structure of the assembly program. Relate this structure to the original C code.

  7. Create an approximate correspondance table between the RISC-V and Alpha instruction sets, for the instructions used in this program (ie. not for the complete RISC-V & Alpha ISA).

    For each instruction, give a 1-line short summary of what the instruction does.

5   Understanding optimizations

(Successful completion of this part can get you to grade 8, but only after you get a minimum of 5 on the first part.)

  1. Compile the same source file again using -O1 to comp-1-alpha.s.

    Compare comp-1-alpha.s to comp-0-alpha.s. Add code comments to this file that relate the code back to the C source. Explain in your own words (separately) what the compiler did to optimize.

  2. Compile again using -O2 to comp-2-alpha.s. Compare comp-2-alpha.s to comp-1-alpha.s. Again, related the assembly to the original program, then explain in your own words the optimizations.

    Place these generated files and their annotations in the submitted archive.

  3. Calculate by hand, for the optimized assembly sources:

    1. the number of static instructions.

    2. the number of dynamic instructions.

    3. the number of memory accesses.

    4. assume that the execution time is proportional to the dynamic instruction count. Estimate the speedup at each optimization stage.

      (Speedup = ref count / new count)

    Note: exclude the execution of print_roman in your analysis.

    Place this prediction in your report.

  4. Use MGSim to verify your estimations for the previous question.

    Report the measurement results and explain the differences found, if any.

6   Manual optimization of assembly

(Successful completion of this part can get you to grade 10, but only after you get a minimum of 7 on the previous part.)

  1. Copy comp-0-riscv.s to comp-opt-riscv.s. Optimize the code in comp-opt-riscv.s by hand and explain your optimizations. Do not use the RISC-V compiler's optimization flags! However, you can inspire yourself from the Alpha techniques you learned from the compiler optimizations in the previous section. Ensure that your optimized assembly code is recognized by the assembler, by compiling it to binary code.

    Of course the output of the program should be identical; as well as the contents of arrays A and B at the end of the execution.

    Any idea that may contribute to a performance increase may be used (everything about the structure of the program may be changed), provided that you explain in detail what you did. In other words: give thorough comments on what you did!

  2. Calculate by hand the static and dynamic instruction counts, and the number of memory accesses, for both the unoptimized version and after your optimizations.

Note

Place the optimized code comp-opt-riscv.s in your submission archive. Place your separate explanations in your report.rst.

Tip

You cannot yet test (run) your optimized RISC-V code in MGSim. However, preserve your optimized assembly source! In the next assignments, you will extend MGSim with the RISC-V ISA; you will then use this week's code to test your future simulator.

7   Preparing for the next assignments

(This part does not count for your grade in assignment 1, however it is a prerequisite for the next assignment.)

  1. Compile to RISC-V binary code for all the test programs provided.

  2. Using the command riscv64-unknown-elf-objdump -d, inventarize all the different RISC-V instruction names that are effectively used by the test programs.

    Note that you may get different results depending on whether you compile with optimizations enabled (-O2) or not. Try both and see if there are any differences.

Note

Place the files hello-riscv.bin, helloworld-riscv.bin, fibo-riscv.bin, comp-riscv.bin and sumdemo-riscv.bin in your submission archive. Place your inventary for #2 in your report.rst.

Tip

Consider using a smart combination of awk, grep and sort -u to avoid counting all instructions by hand.

Tip

This list of instructions defines the minimum set of ISA instructions your future assignments will need to emulate. In other words, as soon as your own RISC-V simulator supports these instructions, you will be able to run these programs.

8   Duo acknowledgement - mandatory!

If you have worked in a group of 2, you must provide at the start of your report a section with the following information:

If you do not provide this information, or if it appears in the evaluation period afterwards that the information on how you shared the work was not accurate, your grade on assignment 1 will be penalized with -2 points (for both students).

(This section does not apply to students who complete assignment 1 individually.)

9   Summary of submission contents

Your final submission archive should contain the following files:

report.rst
comp-0-alpha.s
comp-0-riscv.s
hello-riscv.bin
helloworld-riscv.bin
fibo-riscv.bin
comp-riscv.bin
sumdemo-riscv.bin

# Optionally:
comp-1-alpha.s
comp-2-alpha.s
comp-opt-riscv.s