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

Question

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.

Answer 1

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).

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.