Histogram-Capp

ILP_Rate

ILP_Rate = ILP_16K /ILP_32.

ILP_32 = 32/ D.D

ILP_16K = (16K*I_new)/ (16K + I_new*D.D),

where I_new = I/4 if loop can be unrolled (4 levels), and I_new = I if loop cannot be unrolled.

Where I = Number of instructions per iteration of the loop (that contains the piece of code that contributed to the dependency depth).

Dependency Depth Calculation:

Consider hist[pixel_value] = hist[pixel_value] + 1

1,2: Do address translation and load hist[pixel_value]

3: Calculate hist[pixel_value] + 1

4: Store hist[pixel_value]

Dependency Depth = 4.

ILP_32

ILP_32 = 32/ D.D = 32/4 = 8.

ILP_16K

Number of iterations of loop i (N) = 262144

Number of instructions per iteration of the loop i (I) = 9

Take level-4 loop unrolling.

N_new = N/4 = 65536

I_new = I*4 = 36

ILP_16K = (16 * 1024 * 36)/((16 * 1024)+(36*4)) = 35.68

ILP_Rate = 35.68 / 8 = 4.46