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: 
Explorer
Explorer
7,109 Views
Registered: ‎10-09-2014

Question about BRAM binary search with II=1

Hi,

 

I am working on a HLS function that will call several sub-functions. II is very important for me since I have to make sure the core can consume one data per cycle whenever it is possible. One of the sub functions is a binary search to a sorted array (block RAM). I have been trying different solutions to achieve 1 as II for this function as otherwise the top function won't be able to achieve II=1. I know it is safe because I have FIFO before the binary search (BS) and the input to the BS only happen once per 100 data input. The two approaches I am trying are:

1) state machine style. See the attached code for detail, we use state machine to read data out and check data. However, though the latency of bram read is 1, HLS still infers 2 cycles for reading from bram, so this solution ends up with II=2. 

2) for loop. I also tried something like:

distance = 256;

index = 512;

for ( int i=0; i<10; i++)

{

       temp = table[index];

       if (temp > search_vlue)

               index += distance;

       else if (temp < search_value)

               index -= distance;

      distance >>= 1;

}

 

With loop pipeline, this approach can achieve II=1 for the loop, however the II for the whole function is about 30. 

 

I understand that it is impossible to really do binary search in one cycle, but I am hoping that there is a way to issue the data read only when it is done, eg state machine or a done signal, and keep II down to 1 for the function. Can anyone help out here please? Thank you.

 

Best Regards,

Jimmy

0 Kudos