Occasional Contributor
Frequent ContributorSolution mentioned by @MGRAV is the right way to run loop iterations in "parallel". However, the difference you are experiencing here is likely caused by the resource used to implement i[], rather than the loop-carried dependency. If i[] is implemented using registers (which can be quite inefficient in case ITEM_LENGTH is too large), then you should achieve an II of 1 in all of the cases you mentioned above. You can force implementation using registers using the respective pragma mentioned in Intel's documentation and see what happens. If, however, i[] is implemented using Block RAMs, then you will end up with a load/store dependency since it is not possible to perform single-cycle read/write from/to Block RAMs and that is where the II=6 comes from (latency of one Block RAM read + write). There is nothing you can do to improve the II in this case, since your the load/store dependency is real and any attempt to force the compiler to ignore it using ivdep will result in incorrect output.
P.S. You should probably move "if ( i == 0 ) a[i] = j; " outside of the "i" loop and start "i" from 1. This will allow you to completely eliminate the branch from the code and save some area.
Occasional ContributorMany thanks for replying HRZ.
Your insights are very helpful. However, this is a very abstracted example of the problem. In the actual design the main inner loop is complex with a critical dependency of over 80 clocks which cannot easily be reduced. The data itself is too large to be implemented as registers.
The long dependency is resolved (as in the example) by operating on many data vectors concurrently and inverting the consequent pair of nested loops. The ivdep is needed because although there is a data dependency on the array as a whole the loop inversion ensures that LD/ST of any one element of the array is separated by at least the natural II (GROUP_SIZE=10 is greater than II of 6 in the example).
I am now trying to run several of these inverted loops in parallel on distinct data sets. In the example this is represented by the third array dimension indexed by block. The first iteration of the loop only accesses array elements with first index equal to 0 (a[0][j][i]), the second iteration only accesses array elements with first index 1 (a[1][j]i]).
Following MGRAV's suggestion on the unroll pragma, it unfortunately does not result in parallel execution because the compiler is insisting there is a memory dependency preventing it. I will be confirming that this is actually the case with an actual run as soon as the FPGA runtime nodes are available again. I will post the results here.
Any further insights would be most welcome.
Occasional ContributorHi again MGRAV and HRZ
I have further developed the example to avoid the false memory dependency and manually unrolled the loop. This allows the compiler to automatically fuse the 2 two loops thus achieving the desired concurrency. BUT even though both loops carry the ivdep the resulting fused loop nevertheless has an II of 6 (as if the ivdeps had been ignored). Here is the code:
const int ITEM_LENGTH = 10000;
const int GROUP_SIZE = 10;
uint16_t a[GROUP_SIZE][ITEM_LENGTH];
uint16_t b[GROUP_SIZE][ITEM_LENGTH];
[[intel::ivdep]]
for (int k = 0; k < GROUP_SIZE * ITEM_LENGTH; k++)
{
int i = k / GROUP_SIZE;
int j = k - i * GROUP_SIZE;
if ( i == 0 )
a[j][i] = j;
else
a[j][i] = a[j][i-1] + i;
}
[[intel::ivdep]]
for (int k = 0; k < GROUP_SIZE * ITEM_LENGTH; k++)
{
int i = k / GROUP_SIZE;
int j = k - i * GROUP_SIZE;
if ( i == 0 )
b[j][i] = j;
else
b[j][i] = b[j][i-1] + i;
}
I'm at a loss. Why can't the fused loop respect the ivdep?
New ContributorHi @Mickleman,
I am not sure but I assume that is the way you get you i and j out of the division and the modulo.
I imagine you rewrite as follow (that do basically the same, without branching)
uint16_t* c=(uint16_t*)a
bool test=(k<GROUP_SIZE) ;
int i=k / GROUP_SIZE;
c[k]= (c[k-1]+i)*(!test)+(test)* (k-i*GROUP_SIZE);
you can get that the compiler don't see the opportunity over the GROUP_SIZE parallelization.
I think to get it automatically you should permute you array, a[j][i] ==> a[i][j] so the dependency inside look like c[k-GROUP_SIZE].
I don't know if I am clear in what I mean
Frequent ContributorCan you post the snippet of the report that mentions why the II has been increased to 6? I am not convinced your issue is because of the loop-carried dependency. I believe your issue is because of load/store dependency caused by latency of accessing Block RAM-based buffers which cannot be ignored with ivdep.
You will probably also be better off recovering "i" and "j" in the fused loop as follows, rather than by using "div":
i++;
if (i == ITEM_LENGTH)
{
i = 0;
j++;
}
Note that there is no need to reset "j" here since the loop will exist after ITEM_LENGTH * GROUP_SIZE iterations anyway.
Occasional ContributorHi @HRZ
Thank you for your time helping me to find a solution to this problem - it is very much appreciated.
The reason for the II of 6 is not a mystery - it is as you say a (false) LD/ST memory dependency. If I compile the last example with just one of the loops the II is scheduled at 1 and the code gives the correct answer. So the compiler is able to respect the ivdep in the face of the LD/ST dependency. So why can't it do the same on the fused loop?
On the subject of the i,j recovery you are right this could be done differently (as it is in the full design) but it is not relevant to the issue being explored here.