search

taijusti / sleep_apnea

0 stars 0 forks source link

Implement 16-bit LFSR as pseudorandom number generator, using in 2nd point heuristic #20

Closed p-wu closed 9 years ago

p-wu commented 9 years ago

rand() is not supported by HLS. need to implement LFSR as PRNG in HDL

taijusti commented 9 years ago

are you looking into this patrick or are you just raising this issue?

p-wu commented 9 years ago

I will looking into that, we somehow need that PRNG in heuristic

taijusti commented 9 years ago

did you look into this? i noticed that the random values are taken in as parameters, this wont work because they need to change every iteration in order to prevent it from getting stuck at that start point

p-wu commented 9 years ago

Yes, I was looking some of the implementation idea on the weekend. We can implement at a C program, however, as you said, the number sequence generated will always be the same. I was thinking if we can initialize the "random generator" block, just like the local pipelines, and make it always running as long as the SMO is running. Then the block will keep generate a number. Can we use the hls::stream or something similar to that?

2015-05-12 12:25 GMT-04:00 Justin notifications@github.com:

did you look into this? i noticed that the random values are taken in as parameters, this wont work because they need to change every iteration in order to prevent it from getting stuck at that start point

— Reply to this email directly or view it on GitHub https://github.com/taijusti/sleep_apnea/issues/20#issuecomment-101339011 .

taijusti commented 9 years ago

that sounds reasonable. you wont be able to use hls::stream though--its a fifo. its not a shift register that continually shifts. it only shifts when its read from, conceptually.

taijusti commented 9 years ago

maybe just lookup a sw implementation of a prng and push it through hls?

taijusti commented 9 years ago

btw, found this online... rand() being unsythesizable is a pretty common problem as you can imagine. Xilinx employee recommended just using a C implementation of rand() and pushing it through HLS.

C implementation of rand(): http://www.christianpinder.com/articles/pseudo-random-number-generation/

Xilinx Forum Thread: http://forums.xilinx.com/t5/High-Level-Synthesis-HLS/rand-function-not-synthesizable/td-p/589063

taijusti commented 9 years ago

ok, i think we actually need this or else the hardware implementation will take forever. though maybe an LFSR isn't the easiest way to do it. currently the hardware implementation keeps increasing the start offset. it takes ~10k iterations of the inner loop like this.

taijusti commented 9 years ago

wow ok... preliminary experiments show that it can cut iteration count by 5x at 256 points.

fixed offset: 11089 iterations rand offset: ~2200

ghost commented 9 years ago

wow indeed thats a lot, I did not expect that.

On Wed, Jun 10, 2015 at 3:25 PM, Justin notifications@github.com wrote:

wow ok... preliminary experiments show that it can cut iteration count by 5x at 256 points.

fixed offset: 11089 iterations rand offset: ~2200

— Reply to this email directly or view it on GitHub https://github.com/taijusti/sleep_apnea/issues/20#issuecomment-110885158 .

taijusti commented 9 years ago

added in a different random # generator since i didn't know how to integrate an lfsr.