# How does a non-FPGA (ie a PC with a CPU, RAM, hard drive) mimic logic gates?

I know that an FPGA uses look-up tables (LUTs) to synthesize logic gates. A LUT is a block of RAM that is indexed by a number of inputs. The output is the value stored at that memory address. The magic is that the LUT can be programmed to display whatever you want for a particular input. So, a LUT can be programmed with the truth table of any logic gate in order to mimic it! That's how an FPGA synthesizes the logic gates that you specify in your HDL code.

I was thinking the other day, how does a normal computer mimic logic gates? As far as I know (which is not far), if I write a program in C++, first it must be compiled to machine code so that the CPU can read it. Then when I press "run", the machine code goes to memory to await processing by the CPU. I'm not real clear on what happens next, but at some stage the CPU must have execute the logical operations that my program contains, right? Unlike an FGPA, the CPU can't just synthesize whatever resources it needs. So how does it execute the program?

My Guesses:

1. The CPU has a number of pre-built logic gates. When it encounters an AND statement in the C++ code it's executing, it uses one of its AND gates. If it sees an OR statement, it uses one of its OR gates; if it sees an IF statement, it uses one of its IF gates; etc.

2. Or, logic is implemented in memory in some way similar to a LUT. This makes more sense to me since it doesn't rely on a limited number of gate resources. If my program requires tons of OR logic for instance, the CPU won't get bottlenecked by a lack of OR gates.

So, how far off am I?

Edit: Thanks for the answers everyone, I learned quite a bit about CPUs and ALUs. Also, the "IF gate" in my first guess is a typo, that should be "OR gate" (although it's just an example, any logic gate would do). Sorry about that confusion.

-
Look up something like "diy 8-bit cpu" or something similar on Google. It'll give you a bottom up look at it, rather than a top down. –  Josh Beam Jul 17 '14 at 16:11
I'm not terribly experienced in this field, but I'm pretty sure that's what instruction words are for in Machine Language –  Supuhstar Jul 18 '14 at 5:51

Actually your first guess is not as afar off as some are claiming.

A CPU is built around something called an "Arithmetic Logic Unit" (ALU) and a simplistic implementation of that is to have the logic gates implementing all basic operations wired up to the inputs in parallel. All of the possible elementary computations are thus performed in parallel, with the output of the actually desired one selected by a multiplexor.

In an extremely simple (chalk-board-model) CPU, a few bits of the currently executing instruction opcode are wired to that multiplexor to tell it which logic function result to use. (The other, undesired results are simply wasted)

The actual technology used to implement the computations in the ALU varies - it could be "real" logic gates, or it could be LUT's if the CPU is implemented inside an LUT-based FPGA (one very good way to understand the essentials of stored-program computing is to design a simple processor and build it in a logic simulator and perhaps then an FPGA).

-
Yes, this is what I was getting at in my first guess. So when the CPU needs to do logic it uses the gates (or LUTs or whatever other technology) in its ALU to perform the operation. Is it possible for the CPU to be bottlenecked by its ALU due to limited computational resources? For example, each clock cycle the ALU can only perform a number of computations limited by the number of relevant gates it has. As long as the FPGA has room, it can just build more gates to go faster. I realize that the logic gets executed in parallel on the FPGA vs. sequentially for the CPU, but there –  user3716057 Jul 17 '14 at 16:40
must be some advantage to raw number of gates right? –  user3716057 Jul 17 '14 at 16:40
A classic CPU executes only one useful computation per clock (at most, often less) since of all the possible computations run in parallel, only one is actually desired. Modern techniques however often do incorporate multiple parallel execution units, either doing the same thing to multiple sets of data (especially the GPUs on a graphics card), or pursuing two possibilities with the wrong one discarded (will the conditional branch be taken or not?), or as actual distinct cores running different program threads. But it's not trivial to make something faster just by throwing more gates at it. –  Chris Stratton Jul 17 '14 at 16:44
I see. So if a CPU needed to execute many many XORs for example, an ALU with a huge number of XOR gates would not necessarily make this happen faster than an ALU with a lesser number. So what dictates the optimal number of a particular type of gate on an ALU? –  user3716057 Jul 17 '14 at 16:51
@user3716057: It depends on your processor architecture. x86 has SIMD instructions that allow multiple operations in parallel, and various Vector processors have been around to process large amounts of data in parallel. GPUs are one such incarnation of a similar idea, of a chip designed for highly parallel computations. –  whatsisname Jul 17 '14 at 18:17

Pretty far off.

A CPU is made up of real gates (not programmable LUTs). The key operations on data are done in a block of logic often known as an ALU (arithmetic-logic unit). Inside this block is a set of gates that can, for example, AND two operands together, bit-by-bit. There's another set of gates that can add them together, and so on.

When you execute instructions on the CPU, the instructions are decoded one at a time, and the logic associated with that instruction is activated inside the ALU.

The difference is a time-vs-area tradeoff. If you have a lot of ANDs to do, you can do them in an FPGA using many LUTs in parallel and get them done in a short amount of time. If you do them in a CPU, they will be done one at a time (sequentially) in the tiny block of logic that is designed for that task.

-
Isn't that pretty much my first guess? –  user3716057 Jul 17 '14 at 16:20
@user3716057, no, not quite. For example, there is no "if" gate. Your code is broken down into a bunch of individual instructions (limited to the width of the CPU buses, etc.). This can be hundreds of instructions for very little higher-level code. As Dave said, the ALU performs logical operations, like AND, OR, and arithmetic operations, like ADD, SUB. An "if" statement in your C++ code could be many machine instructions. –  Josh Beam Jul 17 '14 at 17:57
The AND gate part was fine, but you went off the rails with the IF gate, which doesn't exist. An IF statement is turned into a series of instructions that compare values, while the simulation presents the result as if it had been done in parallel. –  skrrgwasme Jul 17 '14 at 17:58
Oops typo, that was supposed to be OR. Or really any gate. Other than that though, I'm not sure how my answer is "pretty far off" from Dave's answer. –  user3716057 Jul 17 '14 at 18:10
@user3716057: It's pretty far off in the sense that it doesn't use "one of" its AND gates but rather trigger the AND operation of the ALU which always operate on word length (8/16/32/68 bits) at once to AND two registers together. If you want to operate on a single bit then you have to creatively use the AND, OR, XOR, Left/Right Shift operations to get what you want. –  slebetman Jul 17 '14 at 19:31

The CPU doesn't just have 'a number' of pre-build logic gates. A modern processor has between around 50 million to several billion transistors, corresponding to many millions of gates.

The CPU already has all the resources needed to execute your C++ program. The resources provided fulfill the instruction set defined by that hardware platform, be it x86, ARM, MIPS, etc. Those instructions all include Arithmetic instructions, Moving memory around, conditionals, etc. Look at the instruction sets of your platform to get an understanding of how the CPU itself actually operates.

When the CPU performs an "AND" operation, while it somewhere it uses an AND gate, there are millions of AND gates in the CPU for all kinds of operations.

Those instructions are all implemented in the layout of transistors in the chip. To see how some of those work, look up stuff like flip-flops, Adders, or other digital logic.

-
But it is a limited number of gates. What I'm really getting at with my question is the following idea: if an FPGA needs to do lots of XORs for example, it can do this faster by synthesizing more XOR gates and doing all the logic in parallel. As long as there is still space on the FPGA, more gates can be built. The CPU has to come prepared for any possible logic, it can't create just the logic it needs. So if my program uses tons of XOR logic but nothing else, the CPU won't be able to leverage all of its resources. –  user3716057 Jul 17 '14 at 16:27
@user3716057: It's all about trade-offs. There are special purpose CPUs that are able to do lots of XORs in parallel if that is what a particular application needs. Popular x86 have SIMD instructions for that sort of thing. FPGAs are good for many applications, and general purpose CPUs are good for many others. –  whatsisname Jul 17 '14 at 18:12
Your first sentence is totally wrong. Of course the CPU has a number of gates. You seem to object to this on the basis that it's a large number, which is.. odd. –  Ollie Ford Jul 17 '14 at 22:38
@OllieFord: I said that for two reasons, one, is that saying a CPU just has "a number of gates" conveys the wrong idea, like saying software is just "ones and zeros". Sure, both are true, but they confuse the idea. Second, CPUs today aren't really designed gate by gate, they are designed by functional blocks consisting between a few and several thousand gates and transistors, laid out by specialized software. Focusing on the gates is focusing on the wrong level. –  whatsisname Jul 18 '14 at 3:47
I disagree - I think for a good understanding it's an excellent idea to know what a logic gate actually is, how they form some of those functional blocks, and so on up to how your compiler works. –  Ollie Ford Jul 18 '14 at 7:19

Other answers have addressed the specific questions at a nuts and bolts detail level, but I think there is an opportunity here to look at it from a different angle. Processors today have many millions (billions in current generation desktop CPUs) of transistors implementing a comparably large number of gates. While only a few of those gates are actually used to implement the XOR calculation, it is difficult to see them in the huge forest of supporting functions.

The old-timers here (I think I can admit to having earned that label too) watched that forest grow up, but it is easy to see how a newcomer to the field with just a little digital design experience might find it hard to see the parallels between a pure-hardware computation and a modern multi-core CPU with many layers of cache, branch prediction, and pipelined execution.

I would recommend that you find data sheets and programmer's reference material for several (but one at a time) of the old 8-bit microprocessors from the 70s and 80s. In many cases, you can even find open source implementations of them in the form of pure software emulators as well as Verilog or VHDL for use in an FPGA.

I recommend starting here because the 8080 (used in the 1975 Altair 8800 that launched the hobiest computer market), MC6800 (appeared in a lot of small computers in the late 70s), 6809 (RadioShack Coco and others), 6502 (Apple 1, Apple ][, and many more) and many more like them were largely designed and implemented by single engineers or very small teams and hence had to be fully understood by a very small team. They also demonstrate the minimum number of features needed for a commercially successful CPU without adding in extra memory, cache, or peripherals.

Much of the 8080 heritage is preserved at the Z80 Family Page. The Z80 was Zilog's extension of the intel 8080 platform, and cores implementing it can still be found today. A Verilog 8080 is at OpenCores.org, along with several more 8080 and Z80 implementations. A wealth of documentation, operating systems, assemblers, and compilers exist for the MCS80 architecture and its extensive family.

OpenCores has a large number of open source cores. There are nearly 100 pure CPUs, along with another 50 or so SOCs that could be the basis for further exploration.

-
Out of curiosity, do you have any idea to what extent the architectural features of early microcomputers resembled any earlier (non-"micro") computers? I think most non-microcomputers usually operated on larger word sizes, but it I can certainly imagine that for some applications an 8-bit computer or even a 4-bit one could have been useful. –  supercat Dec 13 '14 at 19:01
For example, I would think even a 4-bit computer could probably operate a time-shared automated score system for 16 bowling lanes if it could assemble three four-bit registers to form 12-bit addresses; building a 4-bit computer from discrete parts would seem like it might be cheaper than trying to design an automated scoring system some other way. –  supercat Dec 13 '14 at 20:09
@supercat Some pocket calculators were based on a 4-bit CPU, which suited BCD arithmetic quite well by operating one decimal digit at a time. 12 decimal digit results were common. There were early machines that used a 1-bit ALU serially to perform useful calculations on larger numbers. Many early machines had distinct sizes for the ALU, Address, and Instruction word. The 8080 had a 16-bit address bus with an 8-bit ALU and accumulator, for instance. –  RBerteig Dec 15 '14 at 22:43
Did any "pocket calculators" predate the invention of the microprocessor? Did any of those that did use any form of "documented" CPU which fetched code out of an addressable code store (ROM), as opposed to simply using sequential logic to trigger various actions? –  supercat Dec 15 '14 at 22:53

As you have observed, the contents of the lookup table determine whether a certain LUT is an OR gate (0, 1, 1, 1), and AND gate (0, 0, 0, 1), an XOR (0, 1, 1, 0) etc.

The lookup table itself is implemented using hardcoded gates, i.e. the result is

(lut[0] AND NOT a AND NOT b) OR
(lut[1] AND     a AND NOT b) OR
(lut[2] AND NOT a AND     b) OR
(lut[3] AND     a AND     b)


If you look at this line by line, you can see that only one of these lines can ever have a logic one, so this selects one of the LUT entries. In the same way, you can also select between multiple data sources:

If op1 is the two-bit register number, the lhs operand can be selected as

(reg0 AND NOT op1[0] AND NOT op1[1]) OR
(reg1 AND     op1[0] AND NOT op1[1]) OR
(reg2 AND NOT op1[0] AND     op1[1]) OR
(reg3 AND     op1[0] AND     op1[1])


Then, opcode can select the operation to be performed:

((lhs AND rhs) AND NOT opcode[0] AND NOT opcode[1]) OR
((lhs OR rhs)  AND     opcode[0] AND NOT opcode[1]) OR
((lhs + rhs)   AND NOT opcode[0] AND     opcode[1]) OR
((lhs - rhs)   AND     opcode[0] AND     opcode[1])


Where res = (lhs + rhs) is defined as

res[0] = lhs[0] XOR rhs[0];
res[1] = lhs[1] XOR rhs[1] XOR (lhs[0] AND rhs[0]);
...


So in the end, I can boil everything down to fixed gates, leaving only the inputs variable. An FPGA is one such variant, where the gates are arranged that they perform a table lookup.

In a real world system I'd additionally optimize, e.g. combine equivalent signals and attempt to minimize gates switching when that signal is later on eliminated by an AND gate and will not have any effect on the result:

is_and_op = NOT opcode[0] AND NOT opcode[1];


Multiple circuit elements want to know whether we are currently executing an "and" operation.

lhs_and = lhs AND is_and_op;
rhs_and = rhs AND is_and_op;


If not, we pass zeros into the gates performing the operation.

res_and = lhs_and AND rhs_and;


This is the actual operation, as before.

res = res_and AND is_and_op OR ...;


Selection can also use our shorthand.

-
My question was more about how a CPU does logical operations. I know how FPGAs use LUTs to build logic. As another poster pointed out, CPUs don't use LUTs in this way. –  user3716057 Jul 17 '14 at 16:22
My point is that a LUT is just a bunch of fixed gates that implements a selection logic which can then be used to implement a "gate" by providing certain inputs to the selection process. That is, all you ever get to do is provide inputs, while the hardware is fixed. –  Simon Richter Jul 17 '14 at 16:31

The difference between a CPU and FPGA is parallelism. FPGA's are very good at performing a number of (logically) simpler tasks at once with minimal delay. More complex logic and sequences of operations are better catered for by the CPU's ALU (Arithmetic and Logic Unit).

If you are interested in a common software emulation of gate design, which is typically (if naively) employed to simplify boolean logic functions then take a look at Quine–McCluskey algorithm. I used this to design my own synthesis software at Uni when I couldn't forward the expensive studio's, and for fun.

-