# How can an FPGA outperform a CPU

I hear of people using FPGAs to improve performance of systems that do things like bit-coin mining, electronic trading, and protein folding.

How can an FPGA compete with a CPU on performance when the CPU is typically running at least an order of magnitude faster (in terms of clock speed)?

-
The FPGA does everything at once. –  Ignacio Vazquez-Abrams Mar 2 at 2:50

CPU's are sequential processing devices. They break an algorithm up into a sequence of operations and execute them one at a time.

FPGA's are (or, can be configured as) parallel processing devices. An entire algorithm might be executed in a single tick of the clock, or, worst case, far fewer clock ticks than it takes a sequential processor. One of the costs to the increased logic complexity is typically a lower limit at which the device can be clocked.

Bearing the above in mind, FPGA's can outperform CPU's doing certain tasks because they can do the same task in less clock ticks, albeit at a lower overall clock rate. The gains that can be achieved are highly dependent on the algorithm, but at least an order of magnitude is not atypical for something like an FFT.

Further, because you can build multiple parallel execution units into an FPGA, if you have a large volume of data that you want to pass through the same algorithm, you can distribute the data across the parallel execution units and obtain further orders of magnitude higher throughput than can be achieved with even a multi-core CPU.

The price you pay for the advantages is power consumption and $$'s. - +1; FPGAs however are not as dynamic as CPUs, which is why CPUs are usually better suited for PCs – Nick Williams Mar 2 at 3:24 "The price you pay for the advantages is power consumption and$$$'s." -- This is often true, but you can squarely beat a high-end multi-$1000 Intel Xeon machine with a low-end \$50 Xilinx Spartan-6 for many algorithms. But that typically takes a lot of engineering time and you may end up with a very custom design that only works for one application and is hard to change. So the tradeoff is not just power and money, but algorithm development time, reusability and flexibility. (Although you can argue time == money.) –  wjl Mar 2 at 13:05
markt, about your last sentence, aren't FPGAs much lower power than CPUs? There are a broad range of devices for both CPUs and FPGAs, but if we look at the ones that are used for things like bit-coin mining, aren't the CPUs used for those tasks much more power hungry than the FPGAs that would be used? –  David Gardner Mar 2 at 15:13
@David: When talking about Bitcoin mining, the relevant metric is number of hashes per watt. Markt is talking about overall power consumption. That is, a given FPGA may consume 3x the power of a typical CPU, but be much more than 3x faster at Bitcoin mining; so for Bitcoin that's a win. –  Billy ONeal Mar 2 at 18:05
@Billy: the number of hashes per watt · second, not per watt. –  Paŭlo Ebermann Mar 3 at 9:28

Markt has this mostly right, but I'm going to throw in my 2 cents here:

Imagine that I told you that I wanted to write a program which reversed the order of bits inside of a 32-bit integer. Something like this:

int reverseBits(int input) {
output = 0;
for(int i = 0;i < 32;i++) {
// Check if the lowest bit is set
if(input & 1 != 0) {
output = output | 1; // set the lowest bit to match in the output!
}

input = input >> 1;
output = output << 1;
}
return output;
}


Now my implementation is not elegant, but I'm sure you agree that there would be some number of operations involved in doing this, and probably some sort of loop. This means that in the CPU, you have spent many more than 1 cycle to implement this operation.

In an FPGA, you can simply wire this up as a pair of latches. You get your data into some register, then you wire it into the different register in reverse bit order. This means that the operation will complete in a single clock cycle in the FPGA. Thus, in a single cycle, the FPGS has completed an operation that took your general purpose CPU many thousands of cycles to complete! In addition, you can wire up probably a few hundred of these registers in parallel. So if you can move in a few hundred numbers onto the FPGA, in a single cycle it will finish those thousands of operations hundreds of times over, all in 1 FPGA clock cycle.

There are many things which a general purpose CPU can do, but as a limitation, we set up generalized and simple instructions which necessarily have to expand into lists of simple instructions to complete some tasks. So I could make the general purpose CPU have an instruction like "reverse bit order for 32 bit register" and give the CPU the same capability as the FPGA we just built, but there are an infinite number of such possible useful instructions, and so we only put in the ones which warrant the cost in the popular CPUs.

FPGAs, CPLDs, and ASICs all give you access to the raw hardware, which allows you to define crazy operations like "decrypt AES256 encrypted bytes with key" or "decode frame of h.264 video". These have latencies of more than one clock cycle in an FPGA, but they can be implemented in much more efficient manners than writing out the operation in millions of lines of general purpose assembly code. This also has the benefit of making the fixed-purpose FPGA/ASIC for many of these operations more power-efficient because they don't have to do as much extraneous work!

Parallelism is the other part which markt pointed out, and while that is important as well, the main thing is when an FPGA parallelizes something which was already expensive in the CPU in terms of cycles needed to perform the operation. Once you start saying "I can perform in 10 FPGA cycles a task which takes my CPU 100,000 cycles, and I can do this task in parallel 4 items at a time," you can easily see why an FPGA could be a heck of a lot faster than a CPU!

So why don't we use FPGAs, CPLDs, and ASICs for everything? Because in general it is a whole chip which does nothing but one operation. This means that although you can get a process to run many orders of magnitude faster in your FPGA/ASIC, you can't change it later when that operation is no longer useful. The reason you can't (generally) change an FPGA once it's in a circuit is that the wiring for the interface is fixed, and normally the circuit doesn't include components which would allow you to repgrogram the FPGA into a more useful configuration. There are some researchers trying to build hybrid FPGA-CPU modules, where there is a section of the CPU which is capable of being rewired/reprogrammed like an FPGA, allowing you to "load" an effective section of the CPU, but none of these have ever made it to market (as far as I'm aware).

-
For the example of reversing bits (and all other bit swap/selection tasks) it doesn't really take 1 clock cycle, it takes 0. In your example, it takes 1 clock cycle to store data in a latch, which is not the same operation. It takes 1 clock cycle whether you reverse the bits or not. The operation of reversing the bits is 0 clock cycles; no overhead, just different routing. The difference is not just semantics, especially when you starting adding things up. For example, how long does it take to shift a 32-bit word down 3 bits, then swap every other nibble, then reverse it? –  wjl Mar 2 at 13:16
"hybrid FPGA-CPU module" -- these have been on the market for a long time (see xilinx.com/products/silicon-devices/soc/zynq-7000/index.htm for a modern successful one), but even without special support, combining software & HDL is commonly done by implementing a soft CPU inside the FPGA on the fabric. –  wjl Mar 2 at 13:18
@wjl You're right that it technically takes no cycles to perform the operation itself. I would argue that your example is only semantically different though, mostly because doing those three operations logically translates into a fixed bit pattern (i.e. I start with b1b2b3b4 and I end with b3b1b4b2). This was kind of my point in the whole answer. I was trying to point out that describing an operation as a series of steps is frequently only necessary when you have a fixed instruction set/gate arrangement. –  Kit Scuzz Mar 2 at 23:42
@wjl: The way david-gardner asked the question, he seems to be saying "CPU" is equivalent to an Intel or AMD x86/x86_64 highly clocked, pipelined, and optimized CPU. There are many soft "CPUs" but I none of the ones designed to sit in an FPGA can be clocked like an i7, nor are they nearly as optimized or capable. As for hybrids, I more meant something like this: newsroom.intel.com/docs/DOC-1512 which apparently does exist –  Kit Scuzz Mar 2 at 23:52
the Zynq really isn't too bad of a processor (ARM Cortex-A9 -- the same thing that runs tablet computers, etc), but I agree it would be way more awesome to have an integrated FPGA with a high speed x86_64. =) –  wjl Mar 3 at 1:16

Whilst the other answers are all correct, none of them yet addresses the bitcoin mining example from your question, which is indeed a decent example. Bitcoin mining involves repeatedly calculating a cryptographic hash function, SHA-256 of the result of another SHA-256 calculation, of data where only a single 32-bit integer changes, until the resulting hash has certain properties. Each SHA-256 consists of 64 repetitions of the same algorithm involving 32-bit additions, bitshifts, and some more bit-mangling operations.

If you program this loop on a 32-bit (or more) CPU, you will find its instruction set very well suited for the task---SHA-256 was designed to run efficiently on CPUs. Still you will only be using maybe 2% of a modern CPU's silicon area, with area-intensive functionality like caching, multiplication, division, floating point operation, branching and brach prediction, etc., either not used at all or unable to provide significant performance boost for this particular task.

In configurable hardware like a FPGA, you simply only implement those 2%, and optimize further by forgetting all about code execution, rather designing gates to directly compute each one of those often repeated subfunctions. Pipelined such that each of them passes a result into the next every clock cylce, and repeated 128-times (and with some special additional logic where each SHA-256 begins and ends), you end up getting a result every clock cycle (for maybe 100 million hashes per second on a FPGA advertised to support 300 MHz on simpler logic than this) whilst on a modern CPU, you could expect one result every few thousand clock cycles per core, say 10 million hashes per second on a multi-core multi-GHz CPU.

If this particular example is of interest to you, you may want to have a look at my related answer about the internals of ASIC miners on bitcoin.stackexchange, since many FPGA miners work in the same way using configurable rather than custom-made hardware. Just for completeness' sake: There are other possibilities, like limiting or avoiding the pipelining I described in favor of a more trivial parallelization by using multiple independent SHA-256 hashers. Depening on the constraints given by your FPGA's internals and its total size, that can even give better performance although it would be less efficient in terms of gate count and routing overhead if you had perfect freedom in designing the entire chip, not just a FPGA's configuration.

-
That's a very good point about utilization of silicon. –  markt Mar 2 at 20:01
But maybe (unintentionally!) misleading, considering that a FPGA consists of somewhat complex cells with many physical gates, of which a typical application again only uses a fraction, allowing their manufacturers to advertise equivalent gate counts in an attempt to tell you how much all of that might be worth in a "typical" application... –  pyramids Mar 2 at 21:13