Real-Time FPGA Code Optimization - Monte Carlo Simulations

[John80]

Hi,

I am relatively new to programming Real-Time and FPGA targets using LabVIEW.  First of all, I want to say that I am very impressed with the ability of LabVIEW to convert itself into VHDL code...  I am reading a book on VHDL for fun (yes, for fun), and there is an entire chapter devoted to implementing an integer accumulator in VHDL.

So, I am implementing a Monte Carlo Simulation for Financial Applications and the very nature of the work is to have exact copies of the same code (sub VI) run in parallel on the same chip.  Monte Carlo Simulations are very easy to split up - due to the independent nature of each part - and I have been able to achieve astounding performance gains by using a 3M Gate cRIO 9103 vs my own dual core 3.0GH Intel Core Duo.  But I have some questions regarding how to speed things up:

1 - Would it be better to have many single-cycle timed loops? Or just one large single-cycle timed loop with many copies of the same sub VI inside running in parallel?

2 - Advanced Math - Are there any advanced Math Libraries other than the Fixed Point Math Library? i.e. I want to calculate the exponential of a number that is larger than 1.

3 - Any pipelined Gaussian Random # Generators?

Thanks!

John Stratoudakis

john@aleconsultants.com

[srm@viewpointusa.com]

1. good question, I think it takes less fabric to use a single loop.

2.  other than the IP on the website, I don't know of any other places to look for advanced functions.

3.  Not yet.

I think that both 2 and 3 will depend on using a LUT.  the LUT requires a full clock cycle in single cycle loops so there will have to be some pipelining involved to do other work as well in the SCTL.

What range of x for exp(x) do you need?  What output value precision?  What range of gauss distribution output do you need. fxp 16.1?

[Robbob]

Stu answered these pretty well, but I'll throw in my 2 cents...

1) 'Better' is a misnomer in FPGA - It is usually a compromise between execution speed and FPGA space.  With 3M gates, you have plenty of space to work with.  Individual loops will take more space, but may run *slightly* faster, as in microsecond range faster.  The single loop may take a little longer to compile as well, but in this case you could go either way and probably not even notice a difference.

2) Stu mentioned IPnet, you can find it here, there is an exponential function there.

3)There is a pseudo-random number generator on IPnet, but I have personally not used it and cannot vouch for how well it works.  Maybe you can create random numbers on the host side and pass them to FPGA through DMA or a read/write control?

[Robbob]

In addition...there IS a white noise generator on FPGA under FPGA Math and Analysis->Generation.  You can set this up to generate white or gaussian noise, and either in or out of a timed loop.  What exactly did you mean by pipelined?

[John80]

Thanks for your responses.  I did leave out a few details... so let me fill in some holes.

First off, I have been using a Single-Cycle Timed Loop to perform up to 5 simultaneous Monte Carlo Simulations, where each Monte Carlo Simulation is enclosed in one sub-VI.

As for the random number generator, I am using the "White Noise Generator", from the "FPGA Math & Analysis->Generation"palette. Now this VI has two operating modes, one is "Uniform", while the other is "Gaussian".  Uniform is very simple to implement, and is able to produce a new value with each clock tick.  Gaussian on the other hand requires a more comple algorithm to run, and is able to produce a new Normally Distributed number every 12 clock cycles.  For more information on why this is so, see the following pages on the Box-Muller Transform (http://en.wikipedia.org/wiki/Box-Muller_transform), which shows how to take a Uniformly distributed random number source and output Gaussian distributed random numbers.

My original question with this was to see if there was another VI that was able to produce a new Gaussian/Normal Distributed random number on every clock cycle instead of on every 12th cycle.  I imagined that for such an implementation to work that a significant amount of pipelining would have been used.  I ended up implementing this myself, by placing a series of White Noise Generators with a feedback node in between the seeds (to delay enabling each one by one clock tick) and then a large select case statement to select the value that was valid.  The problem is that I am sure that my implementation is not nearly as efficient as one would be of a more experienced FPGA Developer (I am relatively new to this...)

Now... with regards to the Exponential function from the Fixed Point Math Library 8.6, I saw from the documentation that the input value x for exp(x),  must be within the range [-1, 1), and that if I need input outside of that range I have to perform some preprocessing of x to get it to fall within that range.  The only problem is that the logic for preprocessing x can take 1-n iterations, and I was having a hard time dealing with how to have a loop - that preprocesses x, run inside of a larger loop, that was my main program loop.  This would give me a timing violation, because both loops were Single-Cycle Timed Loops.  I understand that I am supposed to use feedback nodes or shift registers for this, but the complexity became just too much for me to grasp, so I decided to instead scale down my value of x by dividing it by 6, and then after my calculation was complete, I would take the 6th power of the result.  I hope to code something up soon that does this the right way.

Thanks, I will read through the rest of the responses again and write anything else that I discover/find soon.

-John

[srm@viewpointusa.com]

how "pure" do you need the result.  I am assuming you are doing a simulation that includes exp(x) where x is uniform or gauss with some range.  What range of x?  By "how pure", I mean what error term of exp() would be acceptable?  1e-6? 1e-8?

[John80]

My precision requirements for the output of exp(x) are not that strict, but I like to keep it at 1e-4.  My input values however, will be in the range [-6, 6).   (A normally distributed random number with mean 0 and variance 1, it wouldn't be the end of the world if I decreased it to say [-4,4), but for now I am just sticking to 6.