I have a short snippet of code that simply computes a weighted average for surrounding elements in a square matrix. The actual implementation that I'm working on is not an average (more complex equation), but I am using this one to figure out how to handle various performance hinderances.
A few notes about my system:
- Windows 7, x64
- Visual Studio 2010, with the Intel C++ Compiler
- Profiling it using Intel VTune Amplifier
- Running in Release, with optimizations on (Intel compiler doesn't specify which level, but with comparison I did I think it's O2 or O3).
- The timing values I am mentioning I got from running it here with -O2
DIM=512
andITERATIONS=1000
Complete code is provided at the end, but for the next few explanations I will just focus on this loop of interest (it's the only loop, so...). I started off with a pretty straightforward, basic implementation:
for (int iter = 0; iter < ITERATIONS; iter++)
{
for (int x = 1; x < DIM-1; x++) // avoid boundary cases for this example
{
for (int y = 1; y < DIM-1; y++)
{
f0 = d_matrix[x][y];
f1 = d_matrix[x-1][y];
f2 = d_matrix[x+1][y];
f3 = d_matrix[x][y-1];
f4 = d_matrix[x][y+1];
d_res_matrix[x][y] = f0*0.6 + f1*0.1 + f2*0.1 + f3*0.1 + f4*0.1;
}
}
for (int x = 0; x < DIM; x++)
{
for (int y = 0; y < (DIM); y++)
{
d_matrix[x][y] = d_res_matrix[x][y];
}
}
}
This attempt took ~1.9s to execute. VTune suggested that I had problems with 4K Aliasing (read-before-write memory situations) specifically on lines for the y-loop and the memory writes that preceed them (in both loops). It also identified back-end bound, core-bound problems. I figured that the 4K aliasing problems might be causing the core-bound issues as well. To address this, I decided to get rid of the constant need to fetch x
and y
and rewrote the code using pointers:
for (int iter = 0; iter < ITERATIONS; iter++)
{
for (int x = 1; x < DIM-1; x++) // avoid boundary cases for this example
{
pf3 = &d_matrix[x][0];
pf0 = &d_matrix[x][1];
pf1 = &d_matrix[x-1][1];
pf2 = &d_matrix[x+1][1];
pf4 = &d_matrix[x][2];
save_write_loc = &d_res_matrix[x][0];
for (int y = 1; y < DIM-1; y++)
{
f0 = *pf0; pf0++;
f1 = *pf1; pf1++;
f2 = *pf2; pf2++;
f3 = *pf3; pf3++;
f4 = *pf4; pf4++;
*save_write_loc++ = f0*0.6+f1*0.1+f2*0.1+f3*0.1+f4*0.1;
}
}
for (int x = 0; x < DIM; x++)
{
s_m = &d_matrix[x][0];
s_r_m = &d_res_matrix[x][0];
for (int y = 0; y < (DIM; y++)
{
*s_m = *s_r_m;
s_m++; s_r_m++;
}
}
}
With this the execution time became ~1.3s. I ran VTune again. It once again complained about 4K Aliasing, but now it was about all the pointer dereferencing lines (such as f1 = *pf1
). I figured it was probably caused by the the incrementing of the pointer I'm doing right after. It also suggested avoiding storing intermediate values, so I collapsed the loop into two lines as below. I also unrolled the 2nd loop 8 times to become:
for (int iter = 0; iter < ITERATIONS; iter++)
{
for (int x = 1; x < DIM-1; x++) // avoid boundary cases for this example
{
pf3 = &d_matrix[x][0];
pf0 = &d_matrix[x][1];
pf1 = &d_matrix[x-1][1];
pf2 = &d_matrix[x+1][1];
pf4 = &d_matrix[x][2];
save_write_loc = &d_res_matrix[x][0];
for (int y = 1; y < DIM-1; y++)
{
*save_write_loc++ = (*pf0)*0.6 + (*pf1)*0.1 + (*pf2)*0.1 + (*pf3)*0.1 + (*pf4)*0.1;
pf0++; pf1++; pf2++; pf3++; pf4++;
}
}
for (int x = 0; x < DIM; x++)
{
s_m = &d_matrix[x][0];
s_r_m = &d_res_matrix[x][0];
for (int y = 0; y < (DIM/8); y=y+8)
{
*s_m = *s_r_m;
s_m++; s_r_m++;
*s_m = *s_r_m;
s_m++; s_r_m++;
*s_m = *s_r_m;
s_m++; s_r_m++;
*s_m = *s_r_m;
s_m++; s_r_m++;
*s_m = *s_r_m;
s_m++; s_r_m++;
*s_m = *s_r_m;
s_m++; s_r_m++;
*s_m = *s_r_m;
s_m++; s_r_m++;
*s_m = *s_r_m;
s_m++; s_r_m++;
}
}
}
This cut the execution time further to ~0.7s. (I also tried unrolling it 4 and 16 times, but those were slower, so I settled on 8).
I am now stuck. I don't really know what else I can do to make it go any faster (if anything, but I'm sure there is something).
VTune is still complaining about 4K Aliasing in the *save_write_loc++ =...
line. Maybe that is caused by the pointer increments happening right after since it is such a tight loop? That same line is still triggering back-end bound, core-bound port utilization problems. Since there is so much going on (multiplications, additions, fetches, stores), I don't really know which part is causing the problem exactly.
The complete code that can be compiled is here.
I'm thinking of having a 1D array instead of a 2D matrix. In that case, the locations will be next to each other, and perhaps they can be cached more efficiently. I am going to try this and report back. But I would appreciate any sort of suggestions on how to make this code faster.