CS 3330: Performance labs and homeworks

This page does not represent the most current semester of this course; it is present merely as an archive.

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 Tychonievich 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 Tychonievich 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.

  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 Grading

4.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:

4.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.

Rotate will get 0 points for 1.0× speedups on my computer, 75% for 1.3×, 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.2×, and 100% for 2.0× speedups, as expressed in the following pseudocode:

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

Exact speedups may vary by computer; see the submission results page for what speedup I found from your most recent submission. Experience has shown that timing does not change by more than .03× upon resubmission.

4.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 5 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 by Luther Tychonievich and Charles Reiss. All rights reserved.
Last updated 2016-11-15 14:06:27