Answer the following C language prompt about image rotation given the following grading criteria and info:

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 following C function computes the result of rotating the source image src by 90 and stores the result in destination image dst. dim is the dimension of the image.

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

int i, j;

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

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

dst[RIDX(dim-1-j,i,dim)] = src[RIDX(i,j,dim)]; 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 code optimization techniques"

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: Rotate is combination of the two matrix operations: Transpose: For each (i, j) pair, Mi,j and Mj,i are interchanged. Exchange rows: Row i is exchanged with row N 1 i.

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