Forum Discussion
New ContributorReducing initiation interval, relaxing loop-carried dependency
I did some testing on your kernel, the problem is from your overly large unroll factor and all the memory ports it creates. If you set II_CYCLES to 5 (but not below that) and reduce UF to 16, you will get an II of 1. Moreover, at least with v19.4 (probably 19.0+ but I didn't test), you will get an II of 1 even with II_CYCLES set to 1 on Arria 10 because the compiler optimizes out the shift register and implements single-cycle accumulation instead. This bring me to a better solution to your problem if you are targeting Arria 10:
#define UF 16 kernel void shift_reg(global float* restrict compute, global float* restrict in, global float* restrict w, int N, int M, int O) { for (int i = 0; i < N; ++i) { for (int yy = 0; yy < M; ++yy) { for (int xx = 0; xx < M; ++xx) { int yy_curr = yy * M; int i_curr = i * O; float final_sum = 0.0f; int exit = O / UF; for (int j = 0; j < exit; j++) { float acc_i = 0.0; #pragma unroll for (int k = 0; k < UF; k++) { int rc = j * UF + k; acc_i += in[((((rc * M) + yy) * M) + xx)] * w[((i_curr) + rc)]; } final_sum += acc_i; } compute[((yy_curr) + xx)] = final_sum; } } } }This will give an II of 1 regardless of UF; though I think single-cycle accumulation is not available on Stratix 10 since the default target frequency on Stratix 10 is 480 MHz which is too high for single-cycle accumulation. Either way, you can still use the shift register method on Stratix 10, just don't use an unroll factor larger than 16. My guess is that if you compile your kernel with varying values of UF from 1 to 32, performance will probably go up until 4 or 8, but it will start going down after that.
P.S. You should also consider the operating frequency when doing performance comparison between different kernels.
New ContributorHi HRZ, thanks for the response. I've been able to get the II down to 1 with the optimization in Figure 3-5 and setting the shift register size to 32. The first problem I was having was that setting the shift register size to the actual MAC latency was still getting an II~6 for an "Undetermined reason". Despite this, the shift register optimization leads to worse results in practice, about 2 to 4x worse runtime on my board. Is this something that you encountered?
I will consider reordering the buffer for consecutive access.
HRZFrequent Contributor
Can you post your new kernel? You should not need to set the shift register size to a value higher than the MAC latency using the method I mentioned.
Regarding run time, it is worse than which case? Due to the non-coalescable accesses in your code to the "in" buffer, you are going to experience a huge amount of contention caused by all those memory ports competing for the memory bus, and your unroll factor is also quite large which makes things even worse; it is not very surprising to get worse performance in such cases compared to the non-unrolled case or smaller unroll factors since the kernel would be memory-bound anyway while lower unroll factor will result in less memory contention and better performance. Moreover, in the method I mentioned, you will be doing some extra unused computation in the last iteration; hence, if your iteration count is not divisible by the unroll factor and at the same time, it is not very large compared to the unroll factor, the unused computation in the last iteration can potentially have a substantial effect on run time.
- SChun19
#define II_CYCLES 24 #define UF 32 kernel void shift_reg(global float* restrict compute, global float* restrict in, global float* restrict w, int N, int M, int O) { for (int i = 0; i < N; ++i) { for (int yy = 0; yy < M; ++yy) { for (int xx = 0; xx < M; ++xx) { int yy_curr = yy * M; int i_curr = i * O; float shift_reg[II_CYCLES] = {0.0f}, final_sum = 0.0f; int exit = O / UF; for (int j = 0; j < exit; j++) { float acc_i = 0.0; #pragma unroll for (int k = 0; k < UF; k++) { int rc = j * UF + k; acc_i += in[((((rc * M) + yy) * M) + xx)] * w[((i_curr) + rc)]; } shift_reg[II_CYCLES - 1] = shift_reg[0] + acc_i; #pragma unroll for (unsigned k = 0; k < II_CYCLES - 1; ++k) shift_reg[k] = shift_reg[k+1]; } #pragma unroll for (int jj = 0; jj < II_CYCLES; ++jj) { final_sum += shift_reg[jj];; } compute[((yy_curr) + xx)] = final_sum; } } } }This is the new kernel. It is worse than all of the above. It still does get much better performance than the non-unrolled case as the generation of 32 separate cache lines greatly reduces memory contention due to a much higher hit rate compared to a single LSU. In my case, the iteration count is always divisible by the unroll factor as they are known prior to runtime.
The MAC latency is 4 cycles. If I set it to 4, then I get this from Loops Analysis:
So I tried setting it to 7+4=11. Still scheduled with II~2. Only with larger shift registers does the compiler successfully schedule it to 1.
- HRZ
I did some testing on your kernel, the problem is from your overly large unroll factor and all the memory ports it creates. If you set II_CYCLES to 5 (but not below that) and reduce UF to 16, you will get an II of 1. Moreover, at least with v19.4 (probably 19.0+ but I didn't test), you will get an II of 1 even with II_CYCLES set to 1 on Arria 10 because the compiler optimizes out the shift register and implements single-cycle accumulation instead. This bring me to a better solution to your problem if you are targeting Arria 10:
#define UF 16 kernel void shift_reg(global float* restrict compute, global float* restrict in, global float* restrict w, int N, int M, int O) { for (int i = 0; i < N; ++i) { for (int yy = 0; yy < M; ++yy) { for (int xx = 0; xx < M; ++xx) { int yy_curr = yy * M; int i_curr = i * O; float final_sum = 0.0f; int exit = O / UF; for (int j = 0; j < exit; j++) { float acc_i = 0.0; #pragma unroll for (int k = 0; k < UF; k++) { int rc = j * UF + k; acc_i += in[((((rc * M) + yy) * M) + xx)] * w[((i_curr) + rc)]; } final_sum += acc_i; } compute[((yy_curr) + xx)] = final_sum; } } } }This will give an II of 1 regardless of UF; though I think single-cycle accumulation is not available on Stratix 10 since the default target frequency on Stratix 10 is 480 MHz which is too high for single-cycle accumulation. Either way, you can still use the shift register method on Stratix 10, just don't use an unroll factor larger than 16. My guess is that if you compile your kernel with varying values of UF from 1 to 32, performance will probably go up until 4 or 8, but it will start going down after that.
P.S. You should also consider the operating frequency when doing performance comparison between different kernels.
- SChun19
I see. From what I read I thought that as well but in practice I was seeing a linear increase in performance from 4 to 64, so this is why I went with this. One thing that I should mention is that I am using an experimental Stratix 10 MX board with HBM2 on Quartus 19.1, though I have seen the same thing occur with the Stratix 10 SX (PAC with DDR4) on vLab. I will give that a try.
Aside from this (and making the in reads coalesceable), what are more common methods to increase parallelism? I can think of vectorization or invoking more compute units -- but I find it hard to imagine how I would be able to maximize parallel use of DSPs before hitting a BRAM/logic wall due to LSU bloat.
I will also keep the fmax in mind for future comparisons. Thank you so much for your help so far.
