CS 3330: Performance labs and homeworks

This page is for a prior offering of CS 3330. It is not up-to-date.

The perf labs are working labs; there is not separate lab and homework assignments.

The associated homeworks are both the same file and are submitted as the same submission entry. However, they have distinct due dates. I’ll take a snapshot of the submissions at rotate’s due date and use it to compute rotate’s score.

You may work with a single partner for both smooth and rotate, or may work alone.

Q: Can I switch partners between rotate and smooth?
A: It can be done, but you’ll need to talk to Prof Reiss so he can fix the grading script to handle your swap.

Q: Can I have a partner for rotate and then work solo for smooth?
A: Yes

Q: Can I work solo for rotate and then have a partner for smooth?
A: It can be done, but you’ll need to talk to Prof Reiss so he can fix the grading script to handle your joining up.

Q: Can we work in a group of three?
A: No

Q: Can my partner and I be from different lab sections?
A: Yes, if you can both attend the same lab section for this assignment.

The following kinds of conversations are permitted with people other than your partner or course staff:

1 Set Up

  1. Download perflab-handout.tar on linux (last modified 2017-04-06).

  2. run tar xvf perflab-handout.tar to extract the tarball, creating the directory perflab_handout.

  3. Edit kernels.c; on lines 12 through 20 you’ll see a team_t structure, which you should initialize with your name and email (and your partner’s, if you have one), as well as what you’d like your team to be called in the scoreboard.

  4. kernels.c is the only file you’ll get to submit, though you are welcome to look at the others or even modify them for debugging purposes.

2 Overview

This assignment deals with optimizing memory-intensive code. Image processing offers many examples of functions that can benefit from optimization. In this lab, we will consider two image processing operations: rotate, which rotates an image counter-clockwise by 90◦, and smooth, which smooths or blurs an image.

For this lab, we will consider an image to be represented as a two-dimensional matrix M, where Mi,j denotes the value of (i, j)th pixel of M. Pixel values are triples of red, green, and blue (RGB) values. We will only consider square images. Let N denote the number of rows (or columns) of an image. Rows and columns are numbered, in C-style, from 0 to N − 1.

2.1 Rotate

Given this representation, the rotate operation can be implemented quite simply as the combination of the following two matrix operations:

This combination is illustrated in the following figure:

Fig 1: Image rotation
Fig 1: Image rotation

2.2 Smooth

Smooth is designed to benefit from different optimizations than rotate

The smooth operation is implemented by replacing every pixel value with the average of all the pixels around it (in a maximum of 3 × 3 window centered at that pixel).

Consider the following image:

Fig 2: Image smoothing
Fig 2: Image smoothing

In that image, the values of pixels M2[1][1] is

2 2
i = 0 j = 0

In that image, the value of M2[N-1][N-1] is

N − 1 N − 1
i = N − 2 j = N − 2

2.3 Code

2.3.1 Structures we give you

A pixel is defined in defs.h as

typedef struct {
    unsigned short red;
    unsigned short green;
    unsigned short blue;
} pixel;

Images are provided in flattened arrays and can be accessed by RIDX, defined as

#define RIDX(i,j,n) ((i)*(n)+(j))

by the code nameOfImage[RIDX(index1, index2, dimensionOfImage)].

All images will be square and have a size that is a multiple of 32.

2.3.2 What you should change

In kernel.c you will see several rotate and several smooth functions.

3 Driver

The source code you will write will be linked with object code that we supply into a driver binary. To create this binary, you will need to execute the command

unix> make driver

You will need to re-make driver each time you change the code in kernels.c. To test your implementations, you can then run the command:

unix> ./driver

The driver can be run in four different modes:

If run without any arguments, driver will run all of your versions (default mode). Other modes and options can be specified by command-line arguments to driver, as listed below:

4 About our Testing Server

We will be testing the performance of this program on our machine. We will be build your programs with the same compiler as on the lab machines. For this compiler gcc --version outputs gcc-4.9 (Ubuntu 4.9.4-2ubuntu1~14.04.1) 4.9.4. We will compile your submitted files using the options -g -Wall -O2 -std=gnu11.

Our testing server has an Intel Skylake processor with the following caches:

The size of a cache block in each of these caches is 64 byte.

Things about our processor that some students might want to know but probably aren’t that important:

5 Grading

5.1 Rules

Violations of the following rules will be seen as cheating, subject to penalties that extend beyond the scope of this assignment:

Additionally, the following rules will result in grade penalties within this assignment if violated:

5.2 Grading

Speedups vary wildly by the host hardware. I have scaled the grade based on my timing server’s hardware so that particular strategies will get 75% and 100% scores.

Smooth and Rotate will each be weighted as a full homework assignment in gradebook.

Note (added 12 April): In retrospect, I probably set the 1.6x threshold for rotate a little too low to ensure that you did the kind of solution we wanted, but we’re not going to change this this late. We would recommend, however, aiming for something >1.65x to ensure that you learned from this assignment what we want you to know for the final. (Our suite of example solutions was built for different problem sizes and this turned out to make it not representative.)

Rotate will get 0 points for 1.0× speedups on my computer, 75% for 1.30×, and 100% for 1.6× speedups, as expressed in the following pseudocode:

if (speedup < 1.0) return MAX_SCORE * 0;
if (speedup < 1.3) return MAX_SCORE * 0.75 * (speedup - 1.0) / (1.3 - 1.0);
if (speedup < 1.6) return MAX_SCORE * (0.75 + 0.25 * (speedup - 1.3) / (1.6 - 1.3));
return MAX_SCORE;

Smooth will get 0 points for 1.0× speedups on my computer, 75% for 1.30×, and 100% for 1.97× speedups, as expressed in the following pseudocode:

if (speedup < 1.0) return MAX_SCORE * 0;
if (speedup < 1.3) return MAX_SCORE * 0.75 * (speedup - 1.0) / (1.3 - 1.0);
if (speedup < 1.97) return MAX_SCORE * (0.75 + 0.25 * (speedup - 1.3) / (1.97 - 1.3));
return MAX_SCORE;

Exact speedups may vary by computer; see this viewing page to view your latest results on my machine. Experience has shown that timing does not change by more than .04× upon resubmission. We will also post a scoreboard of everyone’s latest submission times.

5.3 Submission

You will submit only kernels.c, and need submit it only once per homework though you probably want to submit it often to see what my server’s timing results are.

Submit at the usual place. One of my machines will attempt to time your code and post the speedups I find here. Since running all of the timing for everyone’s code can take a while, expect 30-60 minute delays before your results are posted. I time all of your code and report only the fastest run of each method, so it is in your interest to have several optimizations in your submission; note, however, that if your code runs for more than a couple minutes I will stop running it and post no results.

If you are in a team, it does not matter to me if one or both partners submit so long as at least one does.

Copyright © 2016–2017 by Samira Khan, Luther Tychonievich, and Charles Reiss.
Last updated 2017-04-12 18:13:56