Lab 1: Profiling and Compiler Optimization

Assigned: Sept 17th, Due: Sept 27th, 11:59PM

The TA for this lab is: Kai Shen

Introduction

Upon graduating from Skule as a high-performance program-optimizing expert, you launch a code optimization consulting firm. Following the success of your first project, you secure a second client: a virtual reality (VR) headset startup. Co-founded by hardware engineers specializing in circuit design and sensor integration, the startup has nearly completed its prototype hardware. However, it lacks a high-performance software image rendering engine. Although the engineering team has written functionally correct code in C, they need your expertise to supercharge its performance and efficiency.

The rendering engine processes a time-series input dataset of object manipulation actions. Each action is applied to a 2D object in a bitmap image, creating the illusion of motion for the viewer. To ensure smooth, realistic animations, sensor data points are oversampled at 1500Hz - 25 times the standard 60 frames per second screen refresh rate.

The diagram below shows all the possible object manipulation actions. The goal of the rendering engine is to process all the basic object manipulation actions and output rendered images for the display at 60 frames/s.

Setup

Tip: You will be profiling Lab 2's source code in Lab 1. You will not be modifying this source code in Lab 1 and so you are not required to understand what the code is doing exactly. However, it will be a good idea to use this opportunity to understand the code and think about how you can optimize this code in Lab 2 while you work on Lab 1.

Start by copying the hw2.tar.gz file from the shared directory /cad2/ece454f/hw2/ on the UG machines into a protected directory in your UG home directory. Then run the command:

tar xzvf hw2.tar.gz

This will cause several files to be unpacked into the directory.

Compilation

The lab assignment utilizes the open-source, cross-platform CMake packaging system to manage the source code. Unlike the simple projects you have seen before, CMake generates the Makefile based on your computer configuration. The instructions to compile the project are shown below:

> cd ECE454-Lab2         // Navigate to the lab assignment directory
> mkdir bin && cd bin    // Make a new bin directory, then navigate in it
> cmake ../              // Use cmake to generate Makefile automatically

After these simple configuration steps, the Makefile is automatically generated. Simply run make and an executable named ECE454_Lab2 should appear in the bin directory. When you run this executable using the commands shown below, you should see output similar to the output shown below.

$ cd ECE454-Lab2
$ ./bin/ECE454_Lab2 -g -f lab1.csv -i lab1.bmp
Loading input sensor input from file: lab1.csv
Loading initial 2D object bmp image from file: lab1.bmp
********************************************************************************
Team Information:
team_name: default-name
student_first_name: john
student_last_name: doe
student_student_number: 0000000000
********************************************************************************
Performance Results:
   Number of cpu cycles consumed by the reference implementation: 14054946468
   Number of cpu cycles consumed by your implementation: 14051076100
   Optimization Speedup Ratio (nearest integer): 1
********************************************************************************
SUCCESS: frame #0 is the same compared to the reference implementation
SUCCESS: frame #1 is the same compared to the reference implementation
SUCCESS: frame #2 is the same compared to the reference implementation
SUCCESS: frame #3 is the same compared to the reference implementation

Performance Measurement

For this lab, please answer all the questions below using a few bullet points or short sentences. Performance measurements must be performed on the UG machines.

Q1 (1 mark): List the function you think will be important to optimize in Lab 2's source code?

Measuring Compilation Time

In this assignment, you will use the /usr/bin/time command to measure compilation time and program runtime. In the output, note that the number that ends in "user" is the runtime in seconds for user-mode execution. This is the time you should use in this report. Note that since you are measuring performance in a real system, measurements may vary due to system load. Try to measure on an unloaded machine. For every timing measurement always do 5 runs and average them (please only report the final average).

To build the gprof version, use the flags: -g -pg

To build the gcov version, use the flags: -g -fprofile-arcs -ftest-coverage

Measure compilation times using the 1) gprof, 2) gcov, 3) -g, 4) -O2, 5) -O3, and 6) -Os compilation flags. Be sure to regenerate the Makefile and run make clean in between each build to ensure that all files are rebuilt properly.

Note: We have intentionally left out the details on how to add compiler flags to CMake to encourage you to read CMake documentation.

Q2 (1 mark): Report the compilation times of the 6 compilation methods as speedups relative to the slowest compilation method. Eg., If gcov is the slowest, and -g is twice as fast as gcov, then the speedup for -g relative to gcov is 2.0.

Q3 (1 mark): Which compilation time is the slowest and why?

Q4 (1 mark): Which compilation time is the fastest and why?

Q5 (1 mark): Which of gprof and gcov compilation method is faster and why?

Measuring Program Size

Use ls -l to measure the size of each version of the binary generated in the previous section.

Q6 (1 mark): Report the 6 size measurements as speedups relative to the smallest size. Eg., if -g generates the smallest binary, and gprof is twice the size of -g, then the relative size increase for gprof relative to -g is 2.0.

Q7 (1 mark): Which size is the smallest and why?

Q8 (1 mark): Which size is the largest and why?

Q9 (1 mark): Which of gprof and gcov size is smaller and why?

Measuring Performance

Measure the runtime of all six versions generated in the previous section.

Q10 (1 mark): Report the six measurements. Also, report the speedups relative to the slowest measurement.

Q11 (1 mark): Which version is the slowest and why?

Q12 (1 mark): Which version is the fastest and why?

Q13 (1 mark): Which of gprof and gcov is faster and why?

Profiling With gprof

Compile gprof support for the -g, -O2, and -O3 versions, by using flags -g -pg, -O2 -pg and -O3 -pg respectively. Run each of these versions to collect the gprof results. You don't have to time any of these experiments.

Q14 (1 mark): For each version, list the top 3 functions (provide the function name and percentage execution time).

Q15 (1 mark): For the top function for -O3 (the one with the greatest percentage execution time), how does its percentage execution time compare with the percentage execution time for the same function in the -g version? How is this possible? What transformation did the compiler do and to which functions?

Inspect Assembly

Use the objdump program to list the assembly instructions for the -g and -O3 versions (e.g., run objdump -d OBJ/main.o to examine the assembly instructions for the main.c file).

Q16 (1 mark): Report the number of instructions in the top function identified in Q15 as well as the reduction in the number of instructions (reported as a ratio) for the -O3 version versus the -g version (ie., if the -O3 version has half as many instructions as the -g version, the reduction is 2.0x).

Profiling With gcov

Use gcov to get the per-line execution counts of the top function from the -O3 version identified in Q15 (but use -g to build the gcov version). After running the gcov version, execute the gcov program to generate a profile of the appropriate file. For example, run gcov -o OBJ -b main.c to profile the file main.c. This will create the main.c.gcov file.

Note: if you run the gcov program multiple times it will add to the counts in main.c.gcov; you have to remove the .gcda and .gcno files in the OBJ directory to start counting from zero.

Q17 (1 mark): Based only on the gcov results, list the functions in the order that you would focus on optimizing for the provided Lab 1 inputs and why. Identify each location by its line numbers in the original source file.

GCC Man Pages

Use the man gcc shell command or view the gcc manual page.

Q18 (1 bonus mark): Name the shortest GCC compiler flag (i.e, -xxxxxxxxxxx) that enables a compiler optimization that requires memory alignment. How many bytes does the data need to be aligned?

FAQ

For more details about the lab, read the Lab 1 FAQ.

Submission

Please answer the questions above in a lab1.txt file. The format to use is in /cad2/ece454f/hw1/lab1.txt. Make sure to fill out your personal details before submitting the file using the following command. Submit your assignment on one of the UG machines as follows:

submitece454f 1 lab1.txt

Changing the format or failure to submit using the template file will result in a zero mark. If you wish to change your report, you may overwrite your submitted file by executing the above command again. To view your submission, enter:

submitece454f -l 1