Reducing initiation interval, relaxing loop-carried dependency

#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.

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.

Since your kernel only has three global buffers, you can saturate the bandwidth of a maximum of 3 memory banks (reference: https://arxiv.org/abs/1910.06726) even with interleaving enabled. If you disable interleaving and do manual [DDR] memory banking (S10 MX with HBM doesn't even support interleaving as far as I know), you should hit the "memory wall" if each of those 3 buffers are being read/written with 16 floats per loop iteration, an II=1, and an operating frequency of 300 MHz on S10 GX/SX (I think you need 400 MHz for MX with HBM memory, or a larger vector size). Of course all this is with the assumption that your memory ports are all coalesced; performance should stop going up with smaller vector sizes when you have non-coalesced memory accesses since such accesses are less efficient.

If you fix the memory coalescing problem and reduce the number of memory ports to three, the LSU bloat will largely disappear and you can continue increasing the vector size (unroll factor). A big portion of the LSU bloat is also typically because of the private cache the compiler might create for each port, the area overhead of which will increase proportional to the number of ports. You should consider tiling your loops and manually creating a scratchpad memory to absorb the data reuse in your kernel, and completely disabling the private cache by [falsely] marking your global buffers as volatile to avoid its area overhead. On Stratix 10 GX/SX, you will very likely hit the memory wall far much faster than you utilize the FPGA resources. For S10 MX with HBM, however, you might be able to scale the performance until you properly saturate the DSPs, but you will have to split your global buffers into 32 chunks (since the HBM memory has 32 banks...) on the host yourself and do manual DDR banking and use large switch/cases in the kernel code to read from and write to all the 32 chunks of each buffer simultaneously... You are going to have a lot of LSUs in this case anyway, which will have a large area overhead even if you disable the private cache; I am hoping Intel has thought of something in the compiler to address this problem already...

P.S. You can further reduce area overhead of burst coalesced LSUs by inferring aligned LSUs instead of non-aligned. This can reliably be achieved if you use OpenCL vectors or wide structs for reading/writing from/to global buffers. But of course this will only work if all your memory accesses are aligned by the vector size.

I changed the access patern so that in is now accessed sequentially. With a UF of 64 (fmax=220MHz) this becomes coalesced to a 2048-bit read. This results in a 5x increase in runtime compared to the non-sequential access pattern above. Minding your comment about memory saturation I decreased that UF to 16 (fmax=309MHz) and resynthesized. Area is drastically saved in both cases but performance does not improve much. I would have imagined that sequential reads would have greatly improved performance here, but it does not. I've included some profiled test cases below (from OCL events).

N, M, O: runtime

UF 64, II=1

64, 112, 32, : 14.711209 ms

128,56, 64, : 14.717709 ms

128,56, 128, : 29.326209 ms

256,28, 128, : 10.700833 ms

256,28, 256, : 29.360500 ms

512,14, 256, : 2.439333 ms

512,14, 512, : 21.220958 ms

1024, 7, 512, : 2.243875 ms

1024, 7, 1024, : 3.990750 ms

UF 16, II=1

64, 112, 32, : 10.554042 ms

128,56, 64, : 10.457500 ms

128,56, 128, : 20.892041 ms

256,28, 128, : 10.520417 ms

256,28, 256, : 20.920375 ms

512,14, 256, : 10.513583 ms

512,14, 512, : 21.001666 ms

1024, 7, 512, : 8.579375 ms

1024, 7, 1024, : 21.323458 ms

In comparison, the non-sequential read (as per the kernel code in a previous post) with 64x UF gets this:

64, 112, 112, 32: 7.376835 ms

128, 56, 56, 64 : 3.769259 ms

128, 56, 56, 128: 5.600221 ms

256, 28, 28, 128: 2.882847 ms

256, 28, 28, 256: 4.712566 ms

512, 14, 14, 256: 2.420952 ms

512, 14, 14, 512: 4.206385 ms

1024, 7, 7, 512 : 2.233914 ms

1024, 7, 7, 1024: 4.076918 ms

Regarding the HBMs, I don't think much has changed, only one HBM channel can be assigned to a global memory arg. Creating 32 different kernels as per the bandwidth test example seems to be another way of doing it... but also cannot think of other ways, or if it would be worthwhile...

That doesn't make much sense to me, sequential access must improve performance compared to non-sequential. The only other thing I can think of is if the compiler creates the private cache for the non-sequential case, but does not create it for the sequential one, and your kernel has a lot of data reuse which gets absorbed by the cache and improves performance substantially in the non-sequential case.

The compiler is creating a private cache for both cases, but I have just noticed that in the sequential case the compiler is building a non-aligned burst-coalesced cached LSU (whereas for the non-sequential case, it is aligned). Perhaps this might account for the performance drop.

That is expected; in the non-coalesced case, all accesses are 32-bit and all are 32-bit-aligned, so you will always get aligned LSUs without coalescing. With coalescing, however, unless the compiler can guarantee all the accesses are aligned by the size of the coalesced port (i.e. vector size), you will get non-aligned LSUs, and this is what actually happens in 99% of the cases. However, if all your access are actually aligned by the vector size, then whether the LSU is aligned or not will not affect performance, it is just that the non-aligned LSU has slightly higher area overhead. As I mentioned earlier, you can infer aligned coalesced LSUs by using OpenCL vector types or a wide struct that has one multi-index array as its only member, but you would be able to describe your computation like this only if all the accesses are aligned by the vector size already, in which case you should not expect performance improvement over what you already have. If, however, you have some or a lot of non-alinged accesses, then you will lose out on a lot of memory performance (again refer to https://arxiv.org/abs/1910.06726 for numbers) and you should try to fix the alignment problems which can potentially result in a substantial improvement in memory performance.

I see, that makes sense. In this case all the accesses are always aligned by the vector size, so this shouldn't be an issue. I did have a few experiments in the past with non-aligned accesses and have seen the same results, almost 5-10x reduction in performance.

At this point I guess I can try maintaining my own private caches manually. Perhaps I can revisit loop reordering & tiling optimizations again...