20
\$\begingroup\$

I don't understand how FPGA can be used to accelerate an algorithm. Currently I'm running a time consuming real time algorithm on a quadcore laptop so that four computations can be done in parallel.

I have been recently alerted that FPGA may yield even better performance. I don't understand how that works. Can someone explain how FPGA accelerates an algorithm and if I should switch to a Xilinx or Altera FPGA solution or keep performing the computations on my quadcore laptop.

Additional Details: The algorithm runs 20 artificial neural networks using inputs fed in through the wavelet packet transform

Thank you all for the great answers.

\$\endgroup\$
  • 1
    \$\begingroup\$ Have you considered running the algorithm on a desktop (or server) CPU? Those are typically faster than laptop CPUs. (By a constant factor, but still faster.) \$\endgroup\$ – ntoskrnl Nov 28 '14 at 13:13
  • 1
    \$\begingroup\$ Think about using GPU for neural network processing. GPUs have many units that can multiply floating point numbers in parallel. \$\endgroup\$ – Kamil Nov 28 '14 at 16:42
  • \$\begingroup\$ @ntoskrnl I assume he has i5 or better cpu (4 cores) so performance on desktop or server will be just proprotional to clock speed. Maybe on Xeon he can gain little (20%?) performance thanks to huge cache and better memory bandwidth, but thats not much. \$\endgroup\$ – Kamil Nov 28 '14 at 17:31
  • \$\begingroup\$ What CPU you have? \$\endgroup\$ – Kamil Nov 28 '14 at 17:40
  • \$\begingroup\$ Interesting timing of questions, we got a similar question on networkengineering.SE \$\endgroup\$ – Mike Pennington Nov 29 '14 at 14:01
23
\$\begingroup\$

A colleague of mine benchmarked this and came to the conclusion that FPGAs would outperform a PC once you had more than about 100 independent, integer tasks that would fit in the FPGA. For floating point tasks GPGPU beat FPGA throughout. For narrow multithreading or SIMD operation then CPUs are extremely optimised and run at a higher clock speed than FPGAs typically achieve.

The other caveats: tasks must be independent. If there are data dependencies between tasks then that limits the critical path of computation. FPGAs are good for boolean evaluation and integer maths, as well as hardware low-latency interfaces, but not for memory-dependent workloads or floating point.

If you have to keep the workload in DRAM then that will be the bottleneck rather than the processor.

\$\endgroup\$
  • 3
    \$\begingroup\$ To decide if DRAM is the limit, you also have to know that FPGAs have many small distributed RAMs (e.g. 500 independent 9kbit RAM blocks) that can all read/write during the same clock cycle. \$\endgroup\$ – maxy Nov 28 '14 at 20:15
19
\$\begingroup\$

An FPGA works completely differently from a processor.

For a processor you write software that tells the hardware what to do. On an FPGA you describe "what the hardware should look like" internally. It is as if you are making a chip specially made for your algorithm.

This speeds up a lot of things and can bring down the power consumption. But it has its drawbacks: The development takes much longer and is much more complicated. You need to think in a completely different way and cannot use algorithms that work in software in a straight forward manner.

For Artificial Neural Networks the FPGA is a great choice. There is a lot of ongoing research in this area.

\$\endgroup\$
  • \$\begingroup\$ Actually, FPGA development is often done using languages like Verilog or VHDL which describe behavior rather than implementation--a fact which is sometimes useful but can sometimes greatly complicate the design of asynchronous sequential logic. If one were specifying implementations, propagation delays would be somewhat consistent, but in behavioral languages they aren't even guaranteed to be positive. The key thing with FPGA design is that the languages make it very easy to have many (potentially hundreds or thousands) of different parts of the chip perform simple behaviors simultaneously. \$\endgroup\$ – supercat Nov 29 '14 at 5:06
13
\$\begingroup\$

It depends a lot on the algorithm, but the principle can be explained quite simply.

Suppose that your algorithm has to sum a lot of 8-bit numbers. Your CPU will still need to fetch each instruction, get the operands from the RAM or the cache memory, execute the sum, store the result in cache, and go on with the next operation. The pipeline helps, but you can execute only as many simultaneous operations as the cores you have.

If you use an FPGA, you can implement a large number of simple adders that work in parallel, crunching perhaps thousands of sums in parallel. Although a single operation may take more time, you have a huge degree of parallelism.

You can also use a GPGPU to do similar tasks, as they are also made of many simpler cores.

\$\endgroup\$
  • \$\begingroup\$ GPGPU is a great input for neural networks using! \$\endgroup\$ – Botnic Nov 28 '14 at 10:16
  • \$\begingroup\$ There are also neural network ASICs. Intel used to make one which implemented 16 neurons in the 80s. \$\endgroup\$ – Lior Bilia Nov 28 '14 at 16:55
  • \$\begingroup\$ @LiorBilia well I don't know anything about them :). I've never worked with neural networks, and very little with FPGA \$\endgroup\$ – clabacchio Nov 28 '14 at 17:07
  • \$\begingroup\$ @clabacchio Software neural network is a program that mostly does multiply and compare operations on floating point numbers. By mostly I mean... 95% or more. \$\endgroup\$ – Kamil Nov 28 '14 at 22:06
  • \$\begingroup\$ A conventional CPU can do a pretty good job of summing together lots of 8-bit numbers; on a fast machine the execution time would be dominated by the cost of fetching data from memory (99% of code fetches would come from catch). A more interesting example would be working with data encoded using a scheme that requires rather "unusual" arrangements or permutations of bits. For example, if a piece of video sampling data returns interleaves bits for red, green, and blue, an FPGA could easily rearrange the bits; a conventional CPU would have much more trouble. \$\endgroup\$ – supercat Nov 29 '14 at 0:07
6
\$\begingroup\$

There are roughly 3 levels of specialization of computing equipment:

CPU (like in your laptop) is the most generic of them all. It can do everything, but this versatility comes at a price of slow speed and high power consumption. CPU is programmed on the go, the instructions come from RAM. Programs for CPU are quick, cheap and easy to write and very easy to change.

FPGA (which means Field Programmable Gate Array) is the middle tier. As it's name implies it can be programmed "in the field", that is outside of a factory. FPGA usually gets programmed once, this process can be described as setting up it's internal structure. After this process it behaves like a tiny computer specialized for the one task you've chosen for it. This is why it can fare better than generic CPU. Programming FPGA is very difficult and expensive and debugging them is very hard.

ASIC (which means Application Specific Integrated Circuit) is the ultimate specialist. It's a chip designed and produced for one and only one task - a task it does extremely fast and efficiently. There is no possibility to reprogram ASIC, it leaves the factory fully defined and is useless when it's job is no longer needed. Designing ASIC is something only large corporations can afford and debugging them is well, pretty much impossible.

If you think in "cores", then look at it this way: CPUs have 4, 6, maybe 8 big cores that can do everything. ASICS often have thousands of cores, but very tiny ones, capable of one thing only.

You can look at bitcoin mining community. They do SHA256 hashes.

  • CPU core i7: 0.8-1.5 M hash/s
  • FPGA: 5-300M hash/s
  • ASIC: 12000M hash/s per one tiny chip, 2000000M (yep, that 2T)hash/s for one 160-chip device

Of course, those ASIC babies cost almost $2000 when mass produced, but it gives you an idea about how a jack-of-all-trades can fare against a specialist.

The only question is: can FPGA bring you more savings than designing it would cost? Of course, instead of running it on ONE laptop, you can try running it on 20 PCS.

\$\endgroup\$
  • \$\begingroup\$ Hashing is a very special case though; note that scrypt-based coins are (deliberately) not very accelerateable by specialised hardware. \$\endgroup\$ – pjc50 Nov 28 '14 at 16:47
  • 1
    \$\begingroup\$ & ASIC debugging is typically handled in simulation before shipping to manufacture. So it's usually 6 months or more from spec to manufacture. Diagnosing bugs after manufacture is .. expensive but not impossible. \$\endgroup\$ – pjc50 Nov 28 '14 at 16:49
  • \$\begingroup\$ And while it is hard, in fact can be very very hard, there are things such as boundary scan, JTAG test and direct techniques using FIB etc. So it's far from impossible to debug them, you just need to know what you're doing. Now a days ASIC refers more to a design flow (HDL, Synthesis, P&R) that it actually refers to an actual device since most devices are ASIC's including such things as ARM processors. \$\endgroup\$ – placeholder Nov 28 '14 at 17:10
  • \$\begingroup\$ @pjc50 Yeah, that was my point - in special cases, speed difference is tremendous. But scrypt asics still pwn CPUs and GPUs. Not by a factor of million (as with sha), but still well over 100. \$\endgroup\$ – Agent_L Nov 28 '14 at 19:50
  • \$\begingroup\$ @placeholder yeah, but even if you find the bug, it's not much use for all those chips already manufactured. I meant "debugging" as in "removing the bug" not just "here it is". \$\endgroup\$ – Agent_L Nov 28 '14 at 19:53
5
\$\begingroup\$

Yes, FPGA can outperform modern CPU (like Intel i7) in some specyfic task, but there are easier and cheaper methods to improve neural network performance.

By cheaper - I mean total effort, not FPGA IC cost, but also very fast memory for FPGA (you would need it for neural network) and whole development process.

  1. Use SSE - I've seen pretty simple neural network implementations with 2-3x better performance. This might be good idea if you have no dedicated GPU in your laptop.

    Improving the speed of neural networks on CPUs by Vincent Vanhoucke and Andrew Senior

  2. Use GPGPU (General-purpose computing on graphics processing units) - I think you can archieve 100-200x performance boost on medium class laptop GPU like GeForce 730M.

    Here is neural network implementation (and free code). It uses Nvidia CUDA.

    GPGPU approach is very scalable, if at some point you realize that you need more computing power - you can just use desktop computer with more powerful GPU or even Nvidia Tesla K80 with 4992 cores (thats expensive).

\$\endgroup\$
  • 1
    \$\begingroup\$ The problem here is to define performance. If we mean faster then yes, fpga can be faster than normal cpus. However, fpga are not so flexible as the CPU, They are designrd to execute eficiently just a predefined task. Executing another task would mean change its internal wiring actually implementing another fpga \$\endgroup\$ – Gianluca Ghettini Nov 28 '14 at 21:08

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.