I'm working on the following C language prompt given the following grading criteria about :

Overview:

"The 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 (16-bit color). An image I is represented as a onedimensional array of pixels, where the (i, j)th pixel is I[RIDX(i,j,n)]. Here n is the dimension of the image matrix, and RIDX is a macro defined as follows: #define RIDX(i,j,n) ((i)*(n)+(j))"

Task:

The smoothing function takes as input a source image src and returns the smoothed result in the destination image dst. Here is part of an implementation:

void naive_smooth(int dim, pixel *src, pixel *dst) {

int i, j;

for(i=0; i < dim; i++)

for(j=0; j < dim; j++)

dst[RIDX(i,j,dim)] = avg(dim, 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.)

Grading:

Our main performance measure is CPE or Cycles per Element. If a function takes C cycles to run for an image of size N N, the CPE value is C/N2 . Table 1 summarizes the performance of the naive implementations shown above and compares it against an optimized implementation. Performance is shown for 5 different values of N. All measurements were made on Pentium III Xeon machines. 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 N, we will compute the geometric mean of the results 4

Test case 1 2 3 4 5:

Method N: 64 128 256 512 1024 Geom. Mean

Naive rotate (CPE): 14.7 40.1 46.4 65.9 94.5

Optimized rotate (CPE): 8.0 8.6 14.8 22.1 25.3

Speedup (naive/opt): 1.8 4.7 3.1 3.0 3.7 3.1

Method N: 32 64 128 256 512 Geom. Mean

Naive smooth (CPE) 695 698 702 717 722

Optimized smooth (CPE) 41.5 41.6 41.2 53.5 56.4

Speedup (naive/opt) 16.8 16.8 17.0 13.4 12.8 15.2

*assume N is a multiple of 32*

the measured speedups for N = {32, 64, 128, 256, 512} are R32, R64, R128, R256, and R512 then we compute the overall performance as R = (R32 R64 R128 R256 R512)^(1/5)

"CPE: You will get full credit for your implementations of rotate and smooth if they are correct and achieve mean CPEs above thresholds 2.0 and 2.8"

helpful note: 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 Figure 2. The values of pixels M2[1][1] and M2[N-1][N-1] are given below: M2[1][1] = (P2 i=0 P2 j=0 M1[i][j])/9 M2[N 1][N 1] = (PN1 i=N2 PN1 j=N2 M1[i][j])/4

What is a faster version of this C code using code optomization techniques???