|
|
|
Lab Assignment 5: Tuning PerformanceIntroduction
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
For this lab, we will consider an image to be represented as a
two-dimensional matrix The rotate operation turns an image 90°
counter-clockwise, by moving each element
The smooth operation is implemented by replacing every pixel
value with the average of all the pixels around it (in a maximum of
The values of pixels
| ||
|
| ||||
|
|
LogisticsYou may work in a group of up to two people in solving the problems for this assignment. The only “hand-in” will be electronic. Any clarifications and revisions to the assignment will be posted to the WebCT discussion forum. Hand Out Instructions
Start by copying
Looking at the file Team name in the struct is of the form “ID”, where “ID” is your CS account login name, if you are working alone, or “ID1+ID2”, where “ID1” is the CS login name of the first team member and “ID2” is the CS login name of the second team member. Implementation OverviewData StructuresThe core data structure deals with image representation. A pixel is a struct as shown below:
typedef struct {
unsigned short red; /* R value */
unsigned short green; /* G value */
unsigned short blue; /* B value */
} pixel;
As can be seen, RGB values have 16-bit representations. An image
I is represented as a one dimensional array of pixels,
where the (i,j)th pixel is
I[RIDX(i,j,N)]. Here N is the width
(height) of the image matrix, and RIDX is a macro defined
as follows:
#define RIDX(i,j,N) ((i)*(N)+(j))See the file defs.h for this code.
RotateThe following C function computes the result of rotating the source image src by90° and stores the result in destination
image dst. N is the width (height) of
the image.
void naive_rotate(int N, pixel *src, pixel *dst) {
int i, j;
for(i=0; i < N; i++)
for(j=0; j < N; j++)
dst[RIDX(N-1-j,i,N)] = src[RIDX(i,j,N)];
return;
}
The above code scans the rows of the source image matrix, copying to the
columns of the destination image matrix. Your task is to rewrite
this code to make it run as fast as possible using techniques like code
motion, loop unrolling and blocking.
See the file Smooth
The smoothing function takes as input a source image src and returns the
smoothed result in the destination image
void naive_smooth(int N, pixel *src, pixel *dst) {
int i, j;
for(i=0; i < N; i++)
for(j=0; j < N; j++)
dst[RIDX(i,j,N)] = avg(N, i, j, src); /* Smooth the (i,j)th pixel */
return;
}
The function avg returns the average of all the pixels
around the (i,j)th pixel. Your task is to optimize
smooth (and avg) to run as fast as
possible. (Note: The function avg is a local
function and you can get rid of it altogether to implement
smooth in some other way.)
This code (and an implementation of Performance measures
Our main performance measure is CPE or Cycles per
Element. If a function takes
The ratios (speedups) of the optimized implementation over the naive one
will constitute a score of your implementation. To
summarize the overall effect over different values of
Assumptions
To make life easier, you may assume that Infrastructure
We have provided support code to help you test the correctness of your
implementations and measure their performance. This section
describes how to use this infrastructure. The exact details of
each part of the assignment are described in the following
section.
VersioningYou will be writing many versions of the rotate and smooth routines. To help you compare the performance of all the different versions you’ve written, we provide a way of “registering” functions. For example, the file
void register_rotate_functions() {
add_rotate_function(&rotate, rotate_descr);
}
This function contains one or more calls to
A similar function for your smooth kernels is provided in the file
DriverThe 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 driverYou 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> ./driverThe driver can be run in four different modes:
If run without any arguments,
Team Information
Important: Before you start, you should fill in the struct in
Assignment DetailsOptimizing Rotate (50 points)
In this part, you will optimize unix> ./driver Teamname: ta Member 1: ta Email 1: ta's email address Rotate: Version = naive_rotate: Naive baseline implementation: Dim 64 128 256 512 1024 Mean Your CPEs 20.6 20.7 21.5 37.2 407.0 Baseline CPEs 20.7 20.7 21.4 37.4 400.0 Speedup 1.0 1.0 1.0 1.0 1.0 1.0 Optimizing Smooth (50 points)In this part, you will optimize smooth to achieve as low a CPE as possible. For example, running unix> ./driver Teamname: ta Member 1: ta Email 1: ta's email address Smooth: Version = naive_smooth: Naive baseline implementation: Dim 128 256 512 1024 2048 Mean Your CPEs 307.2 309.1 306.0 306.3 363.9 Baseline CPEs 300.2 313.1 300.4 315.1 361.0 Speedup 1.0 1.0 1.0 1.0 1.0 1.0
Some advice: Look at the assembly code generated
for
Coding RulesYou may write any code you want, as long as it satisfies the following requirements:
kernels.c. You are
allowed to define macros, additional global variables, and other
procedures in this file.
Evaluation
Your solutions for
“Trivia” AssignmentBefore noon, Thursday, March 17, send email to the TAs containing answers to the following questions (a single email per team is acceptable).
Turn In Instructions
When you have completed the lab, you will hand in one file,
DUE DATES:For the “trivia” assignment: noon, Thursday, March 22. For the main assignment: 11:59pm, Monday, April 2. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
