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)?
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.
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).
All of the other popular answers presented here talk about literal differences between FPGAs and CPUs. They point out the parallel nature of the FPGA vs the sequential nature of a CPU, or give examples of why certain algorithms might work well on an FPGA. All of those are good and true, but I would suggest however that there is a more fundamental difference between CPUs and FPGAs.
What’s the common denominator between an FPGA and a CPU? It is that they are both built on top of silicon. And in some cases literally the same silicon processes.
The fundamental difference is the abstractions that we pile on top of that silicon. It’s not possible for one human to understand the full detail of a single modern CPU design from silicon to packaged IC. So as part of the engineering process we divide that complex problem into smaller manageable problems that humans can wrap their heads around.
Consider what it takes to turn that silicon into a functioning CPU. Here’s a somewhat simplified view of the layers of abstraction necessary for that goal:
First we have engineers who know how to create transistors from silicon. They know how to design tiny transistors that sip power and switch at the rate of 10’s or even 100’s of gigahertz, and they know how to design beefy transistors that can drive signals with enough power to send them out of an IC package and across a PCB to another chip.
Then we have digital logic designers who know how to put those transistors together to libraries with hundreds of different logic cells. Logic gates, flip flops, muxes, and adders, to name a few. All in a variety of configurations.
Next we have various groups of engineers who know how to put those digital (and sometimes analog) blocks together to form higher level functional blocks as as high speed transceivers, memory controllers, branch predictors, ALUs, etc.
Then we have CPU designers to architect high end CPU designs by pulling together those functional units into a complete system.
And it doesn’t stop there. At this point we have a working CPU which runs assembly code but that’s not a language most programmers write to these days.
And the abstraction layers can go on from there. The important point here is that those abstraction layers combine to yield a CPU based system that scales massively and costs a tiny fraction of a custom silicon design.
HOWEVER, the important point to be made here is that each abstraction also carries a cost itself. The transistor designer doesn’t build the perfect transistor for every use case. He builds a reasonable library, and so sometimes a transistor is used that consumes a little more power or a little more silicon than is really needed for the job at hand. And similarly the logic designers don’t build every possible logic cell. They might build a 4 input NAND gate and a 8 input NAND gate but what happens when another engineer needs a 6 input NAND? He uses an 8 input NAND gate and ties off 2 unused inputs which results in lost silicon resources and waisted power. And so it goes up the chain of abstractions. Each layer giving us a way to handle the complexity, but at the same time charging us an additional incremental cost in terms of silicon and power.
Now compare those abstractions to what is needed for an FPGA. Essentially, the FPGA abstractions stop at #2 in the list above. The FPGA allows developers to work at the digital logic layer. It’s somewhat more sophisticated than that because CPUs are ‘hard coded’ at this layer and FPGAs must be configured at run time (which, BTW, is why CPUs typically run a much higher frequencies), but the essential important truth is that that are far few abstractions for FPGAs than for CPUs.
So, Why can an FPGA be faster than an CPU? In essence it’s because the FPGA uses far fewer abstractions than a CPU, which means the designer works closer to the silicon. He doesn’t pay the costs of all the many abstraction layers which are required for CPUs. He codes at a lower level and has to work harder to achieve a given bit of functionality but the reward he gets higher performance.
But of course there is a down side for fewer abstractions as well. All those CPU abstractions are there for good reason. They give us a much simpler coding paradigm which means more people can easily develop for them. That in turn means that there are many more CPU designs in existence and thus we have massive price/scale/time-to-market benefits from CPUs.
So there you have it. FPGAs have fewer abstractions and so they can be faster and more power efficient but difficult to program for. CPUs have many abstractions design to make them easy to develop for, scalable, and cheap. But they give up speed and power in trade for those benefits.
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.
The answers above, while correct, miss the point about why FPGAs (and custom ASICs) are especially good for bitcoin calculations.
The real advantage is that a large proportion of the SHA-256 calculations are logical operations (for example, bit shifts) which can be done in wiring. When done this way, they require 0 clock cycles.
Another important advantage is that FPGAs are much more power-efficient (i.e. MIPS per Watt) than CPUs, so the amount of energy required for the calculations is much less. This is important because the cost of mining a bitcoin depends on how much electricity you use to make it.
ASIC chips are more energy efficient than FPGAs, so they can execute the same code much more cheaply. You can also cram more execution units on board to make them faster. The disadvantage is that the cost of making a custom ASIC is very high so you would need to sell quite a few chips to cover the manufacturing cost.
GPUs,are also used for making bitcoins, but since they are much less energy-efficient they have been losing ground to FPGAs and custom ASICs.
