4
\$\begingroup\$

Suppose I have two time series, such as stock valuations or radioactive diagnosis, for which I need things such as covariances (QP -problem) among other things. Covariance calculations should be easy easy speed up -- the future stages are not depended on latter. Can I do this kind of problems in constant time in FPGA? -If I have understood right, yes. What other statistical analysis -toolbox things you can considerably speed up with FPGA? Everything not on depended on the last stage? Look if my thinking is right, there must be a massive potential here -- could someone help me to find out projects specializing in time-series analysis with FPGAs?

\$\endgroup\$
  • 2
    \$\begingroup\$ FPGA seems like overkill - what makes you think that you can't do this adequately fast with a normal CPU ? \$\endgroup\$ – Paul R Oct 10 '11 at 15:11
  • 1
    \$\begingroup\$ @PaulR: I used 2 time-series as an example but the basic idea was to change the \$O(n^{2})\$ problem to \$O(1)\$ problem with FPGA. Can you solve this problem other way as efficiently? Suppose I want to calculate covariances of all stocks or all radiation sources, a very massive number, in constant time how would you do it? Cannot see this as an overkill at all, would be a fascinating project... \$\endgroup\$ – hhh Oct 10 '11 at 15:25
  • 1
    \$\begingroup\$ At the very least you might want to benchmark this on a general purpose CPU first and see whether there is an actual performance problem to solve. Of course if you have time to burn and just want to do this for the hell of it and/or to get some FPGA experience then go ahead ! \$\endgroup\$ – Paul R Oct 10 '11 at 16:07
8
\$\begingroup\$

In theory, you could do it in constant time, but only until you run out of resources. Let's just consider hardware multiplies for now, since they will likely constrain the design. For example, the largest Xilinx Spartan-6 (the value line) contains 180 multipliers; the largest Virtex-6 contains 2128 multipliers (and will probably cost tens of thousands). These are 18-bit multipliers, but for the sake of argument treat them as abstractions. The number of multipliers then gives you the number of multiplications you can do at one time. If I understand the problem right, the square root of that number gives you the dataset that can run in one clock cycle.

In practice there are add/subtractions to worry about, the required precision will lower the amount of multiplies you can do, and the connections you'll need to make across the FPGA fabric will be very dense. All of these factors lower the maximum speed you can clock the FPGA at. Plus you have to get the data in and out of the FPGA. Thus my gut feeling is that this is not a 'killer app' for FPGAs. Conventional processors and GPUs are probably a better bet. (See R+GPU.)

\$\endgroup\$
6
\$\begingroup\$

Yes, these can be done in constant time on an FPGA, but only for a value of \$n\$ limited by the number of gates in your FPGA. You're misunderstanding or misrepresenting the definition of \$O(n^2)\$ - Anything which can be done in parallel can be made \$O(1)\$ for a small, finite value of \$n\$ by implementation on a multi-core CPU, graphics card, FPGA, or networked supercomputer array.

Let's work through your example of calculating covariances of stocks. There are approximately 3500 stocks on the NYSE right now, so let's build the system to support 4096 items.

On a single-core CPU, that would require \$\left(2^{12}\right)^2 = 2^{24} \approx 16,000,000\mbox{ }\$ calculations (Which is not a lot of time, consider that a 4GHz CPU can do that 250 times per second), because the algorithm is \$O(n^2)\$, as stated before.

If you had a 4096-core CPU, ignoring inefficiencies, you could do this in 4096 instructions. You've simply divided the number of operations by the number of parallel cores on which to do the operations.

If you had an FPGA algorithm that could calculate the covariance of 4096 items simultaneously, and room on the FPGA to assemble 4096 of these blocks, you could theoretically calculate the covariance of 4096 or fewer items in a single operation.

That doesn't mean that the algorithm is now \$O(1)\$, it means you've divided \$n\$ by \$2^{24}\$. The algorithm is still \$O(n^2)\$. FPGAs are great for some tasks, but they're not magic.

\$\endgroup\$
2
\$\begingroup\$

Yes, if there are no data-dependencies, then it should be an easy speedup. But it'll be an easy speedup to any other kind of parallelism (such as using the GPU or SSE) and you'll probably find that they can beat an FPGA in most applications for that.

For sufficiently large problems you might be able to build a lower-power or higher-throughput implementation in FPGA, but don't forget to factor in the power and time required to get data sets from a processor to the FPGA and get the results back again.

One place FPGAs can get spectacular speedups over other implementations is when there's lots of parallelism and you know lots about how memory accesses are patterned and a processor cache controller can't "see" those patterns. You can take advantage of this to schedule memory accesses to ensure that the memory bus is never idle (or flushing things it's going to need in the near future)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.