UPGRADE YOUR BROWSER

We have detected your current browser version is not the latest one. Xilinx.com uses the latest web technologies to bring you the best online experience possible. Please upgrade to a Xilinx.com supported browser:Chrome, Firefox, Internet Explorer 11, Safari. Thank you!

cancel
Showing results for 
Search instead for 
Did you mean: 
Observer linuxhippy
Observer
16,377 Views
Registered: ‎03-27-2014

Unable to enforce a carried dependency constraint?

Jump to solution

Hi,

 

When compiling the code attached, Vivado reports the following issue and generates a schedule with ii=2:

@W [SCHED-68] Unable to enforce a carried dependency constraint (II = 1, distance = 1)
   between 'store' operation (cpp_FIR.cpp:14) of variable 'lines_3_load' on array 'lines_2' and 'load' operation ('result', cpp_FIR.cpp:14) on array 'lines_2'.

 

Which kind of problem could arise with the code when scheduled within ii=1 (as it is generated with the #pragma HLS dependence variable=lines inter false)?

 

Actually what I am trying to achive is a 2d line buffer which is able to operate within ii=1.

 

Thank you in advance, Clemens

 

          //directive PIPELINE set

uint8_t process_image(uint8_t pxVal)
{
    static unsigned int x = 0;
         static uint8_t lines[16][WIDTH];

         

         //directive UNROLL set
    for(int i=0; i < 15; i++) {
        lines[i][x] = lines[i + 1][x];
    }
    lines[15][x] = pxVal;


    uint8_t result = lines[1][x];


    x = (x + 1) == WIDTH ? 0 : (x + 1);
    return result;
}

0 Kudos
1 Solution

Accepted Solutions
Xilinx Employee
Xilinx Employee
17,945 Views
Registered: ‎11-28-2007

Re: Unable to enforce a carried dependency constraint?

Jump to solution

The dependency check on array access is based on loop index only. To be on the safe side, the tool will report carried dependency for array access with all other variable indexes even though the index distance can be determined in the code. If you are sure this is a false dependency (and it is in your test code), you can add false dependency directive to your code so the tool will scheudle the design to achive II=1/

 

 

 


@linuxhippy wrote:

> The problem is that the array is stored in a single large memory.  

> The code is attempting to do two writes and a read on a two port memory.

 

Are you sure?

I ask because the compiler tends to give me different messages when the number of memory access exceeds the number of available ports, however in my case it only complains about dependencies.

Also if I set the inter-dependency-pragma to false it can be scheduled with ii=1, however the pragma doesn't change the number of memory ports.

I guess in this case the compiler is able to optimize the redundant memory accesses away.

 

So I'll keep re-asking my question again:

 

> This just mean that in between 2 calls,

> VHLS doean't know how x behaves.

> You have to insert an "inter" dependency (2 calls of the functions) to false to get an II=1.

 

This is what I did - however I am new to HLS and don't know how this code is implemented in logic.

So the sum my question: Does the optimizer just fail to predict how x will behave and therefore will my code behave correct with " #pragma HLS dependence variable=lines inter false" set, or will it cause any issues?

 

Thanks, Clemens




Cheers,
Jim

View solution in original post

14 Replies
Observer linuxhippy
Observer
16,348 Views
Registered: ‎03-27-2014

Re: Unable to enforce a carried dependency constraint?

Jump to solution

or to make the question more precise:

 

Is it safe to disable inter-dependency checks (#pragma HLS dependence variable=_____ inter false) when I know the values written to the array in the current invokation won't be read again for quite a few (100s) clocks?

 

Thanks, Clemens

0 Kudos
Xilinx Employee
Xilinx Employee
16,344 Views
Registered: ‎11-28-2007

Re: Unable to enforce a carried dependency constraint?

Jump to solution

The dependency reported is between different iterations of the loop within the same invokation of this function, so how the arrays are accessed between invokations don't change this dependency. In other words, you can't the inter dependency to false.

 


@linuxhippy wrote:

or to make the question more precise:

 

Is it safe to disable inter-dependency checks (#pragma HLS dependence variable=_____ inter false) when I know the values written to the array in the current invokation won't be read again for quite a few (100s) clocks?

 

Thanks, Clemens




Cheers,
Jim
0 Kudos
Observer linuxhippy
Observer
16,337 Views
Registered: ‎03-27-2014

Re: Unable to enforce a carried dependency constraint?

Jump to solution

Hi Jim,

 

I still fail to see where this dependency should come from (assuming it is real and not a false positive of the optimizer).

Therefore I tried to simplify my example further:

 

unsigned char testdep(unsigned char newVal)
{
#pragma HLS pipeline

    static unsigned int x = 0;
    static unsigned char lines[2][1024], tmp;

    lines[0][x] = tmp;
    lines[1][x] = newVal;

    tmp = lines[1][x + 100];

    x++;
    return tmp;
}

HLS also fails to schedule this piece of code within ii=1, complaining that a dependency exists between the load at line lines[1][x + 100] and the store one line above it. However as far as I can see, there is no dependency (as there is none in my original example), the load only accesses addresses which are never ever written to.

Or do I misunderstand the whole issue?

 

It would be great if you could help me to understand why HLS complains, so I can write code / design my datastructures in a way to avoid such issues.

 

Thank you in advance, Clemens

 

0 Kudos
Observer linuxhippy
Observer
16,292 Views
Registered: ‎03-27-2014

Re: Unable to enforce a carried dependency constraint?

Jump to solution

I would really appreciate a qualified answer to this question.

 

We require our algorithm to run with ii=1, and beside this single issue with dependencies everything seems to work out fine (the final algorithm works as expected when compiled with gcc, and with the pragma we can achieve ii=1).

Once this issue is resolved we can start ordering development tools and boards, however I would like to make sure we can meet expectations before ordering development sfuff.

 

- Regards

 

 

0 Kudos
Teacher muzaffer
Teacher
16,287 Views
Registered: ‎03-31-2012

Re: Unable to enforce a carried dependency constraint?

Jump to solution
is it possible that the dependency is happening based on how lines is mapped to memory ? with a single port memory it seems you can only do one access at a time. Try partitioning lines and see if that helps.
- Please mark the Answer as "Accept as solution" if information provided is helpful.
Give Kudos to a post which you think is helpful and reply oriented.
0 Kudos
Observer linuxhippy
Observer
16,273 Views
Registered: ‎03-27-2014

Re: Unable to enforce a carried dependency constraint?

Jump to solution

0 Kudos
Xilinx Employee
Xilinx Employee
16,256 Views
Registered: ‎01-09-2008

Re: Unable to enforce a carried dependency constraint?

Jump to solution

Actually with your code it's difficult to see if it is an inter or an intra dependency.

If you rewrite it as:

 Loop:for(int i=0; i < 15; i++) {
#pragma HLS UNROLL
        unsigned char tmp;
        tmp = lines[i + 1][x];
        lines[i][x] = tmp;
    }
    lines[15][x] = pxVal;

 

Then the warning message becomes:

@W [SCHED-68] Unable to enforce a carried dependency constraint (II = 1, distance = 1)
   between 'store' operation (DecalMem.cpp:42) of variable 'lines_3_load' on array 'lines_2' and 'load' operation ('result', DecalMem.cpp:41) on array 'lines_2'.
@I [SCHED-61] Pipelining result: Target II: 1, Final II: 2, Depth: 2.

 

The dependency problem starts from the store of line 42 and finishes on line 41 of the NEXT CALL OF THE FUNCTION.

As you unrolled the loopTHERE IS NO LOOP ANYMORE.

 

This just mean that in between 2 calls, VHLS doean't know how x behaves.

You have to insert an "inter" dependency (2 calls of the functions) to false to get an II=1.

 

Olivier

 

==================================
Olivier Trémois
XILINX EMEA DSP Specialist
0 Kudos
Observer linuxhippy
Observer
16,251 Views
Registered: ‎03-27-2014

Re: Unable to enforce a carried dependency constraint?

Jump to solution

Hi Olivert,

 

Thanks a lot for taking the time to look at this issue.

 

> The dependency problem starts from the store of line 42 and finishes

> on line 41 of the NEXT CALL OF THE FUNCTION.

> As you unrolled the loopTHERE IS NO LOOP ANYMORE.

 

Yes, I am aware the dependency warning is caused by the different "invocations" of the function and not caused by the loop which is completely unrolled (to meet ii=1). This was also stated in the original question.

 

> This just mean that in between 2 calls,

> VHLS doean't know how x behaves.

> You have to insert an "inter" dependency (2 calls of the functions) to false to get an II=1.

 

 

This is what I did - however I am new to HLS and don't know how this code is implemented in logic.

So the sum my question: Does the optimizer just fail to predict how x will behave and therefore will my code behave correct with " #pragma HLS dependence variable=lines inter false" set, or will it cause any issues?

 

Thanks and best regards, Clemens

0 Kudos
Visitor andrewsj
Visitor
16,248 Views
Registered: ‎10-24-2013

Re: Unable to enforce a carried dependency constraint?

Jump to solution

The problem is that the array is stored in a single large memory.  The code is attempting to do two writes and a read on a two port memory.

 

The fix is pretty easy.  You need to partition the array into multiple sub-arrays with pragmas like this:

 

#pragma HLS ARRAY_PARTITION variable=lines complete dim=1

#pragma HLS ARRAY_PARTITION variable=lines block factor=10 dim=2

 

This will make the 2x1024 single array into 20 1x102 arrays (some are 1x103).  That way, each block of memory is on a separate BRAM so access can happen simultaneously.

0 Kudos
Visitor andrewsj
Visitor
10,328 Views
Registered: ‎10-24-2013

Re: Unable to enforce a carried dependency constraint?

Jump to solution

If you only need to access the next cell, you can change the pragmas to this:

 

#pragma HLS ARRAY_PARTITION variable=lines complete dim=1

#pragma HLS ARRAY_PARTITION variable=lines cyclic factor=2 dim=2

 

This puts the 2x1024 array into 4 1x512 arrays.  The cyclic keyword with factor of 2 means the even index values go into one BRAM, and the odd index values go into a separate BRAM.

0 Kudos
Observer linuxhippy
Observer
10,321 Views
Registered: ‎03-27-2014

Re: Unable to enforce a carried dependency constraint?

Jump to solution

> The problem is that the array is stored in a single large memory.  

> The code is attempting to do two writes and a read on a two port memory.

 

Are you sure?

I ask because the compiler tends to give me different messages when the number of memory access exceeds the number of available ports, however in my case it only complains about dependencies.

Also if I set the inter-dependency-pragma to false it can be scheduled with ii=1, however the pragma doesn't change the number of memory ports.

I guess in this case the compiler is able to optimize the redundant memory accesses away.

 

So I'll keep re-asking my question again:

 

> This just mean that in between 2 calls,

> VHLS doean't know how x behaves.

> You have to insert an "inter" dependency (2 calls of the functions) to false to get an II=1.

 

This is what I did - however I am new to HLS and don't know how this code is implemented in logic.

So the sum my question: Does the optimizer just fail to predict how x will behave and therefore will my code behave correct with " #pragma HLS dependence variable=lines inter false" set, or will it cause any issues?

 

Thanks, Clemens

0 Kudos
Xilinx Employee
Xilinx Employee
17,946 Views
Registered: ‎11-28-2007

Re: Unable to enforce a carried dependency constraint?

Jump to solution

The dependency check on array access is based on loop index only. To be on the safe side, the tool will report carried dependency for array access with all other variable indexes even though the index distance can be determined in the code. If you are sure this is a false dependency (and it is in your test code), you can add false dependency directive to your code so the tool will scheudle the design to achive II=1/

 

 

 


@linuxhippy wrote:

> The problem is that the array is stored in a single large memory.  

> The code is attempting to do two writes and a read on a two port memory.

 

Are you sure?

I ask because the compiler tends to give me different messages when the number of memory access exceeds the number of available ports, however in my case it only complains about dependencies.

Also if I set the inter-dependency-pragma to false it can be scheduled with ii=1, however the pragma doesn't change the number of memory ports.

I guess in this case the compiler is able to optimize the redundant memory accesses away.

 

So I'll keep re-asking my question again:

 

> This just mean that in between 2 calls,

> VHLS doean't know how x behaves.

> You have to insert an "inter" dependency (2 calls of the functions) to false to get an II=1.

 

This is what I did - however I am new to HLS and don't know how this code is implemented in logic.

So the sum my question: Does the optimizer just fail to predict how x will behave and therefore will my code behave correct with " #pragma HLS dependence variable=lines inter false" set, or will it cause any issues?

 

Thanks, Clemens




Cheers,
Jim

View solution in original post

Observer linuxhippy
Observer
10,313 Views
Registered: ‎03-27-2014

Re: Unable to enforce a carried dependency constraint?

Jump to solution
 
0 Kudos
Observer linuxhippy
Observer
10,311 Views
Registered: ‎03-27-2014

Re: Unable to enforce a carried dependency constraint?

Jump to solution

Hi Jim,

 

> The dependency check on array access is based on loop index only.

> To be on the safe side, the tool will report carried dependency for array access

> with all other variable indexes even though the index distance can be determined in the code.

> If you are sure this is a false dependency (and it is in your test code),

> you can add false dependency directive to your code so the tool will scheudle the design to achive II=1/

 

This is really good news! It means we actually can meet our performance target using Vivado HLS :)

Thanks a lot for taking the time looking at the question in-depth.

 

Regards, Clemens

0 Kudos