What is the lowest level of CPU programming above transistors?

Question

In my CS program, my professor has claimed that NAND gates are the most basic gate to engineer, and so every other gate and higher-level circuits found in CPUs are made from NAND gates (no source found). I'm skeptical of this claim, as it seems prohibitively slow, and I would expect that many optimizations can be made by avoiding such restrictions. My question, then, is: what is the lowest level of programming a standard general-purpose CPU, above physical wires and transistors?

My uninformed research has led me to a few possible resolutions. In section 1.3.2 of Fundamentals of Layout Design for Electronic Circuits (pp. 24), the following passage occurs:

Considering the physical design of digital circuits, standard elements with an immutable internal structure are stored as cells in a library. These cells, such as logic gates and memories, provide standard functions and their layouts have already been produced.

This communicates to me that not just NAND gates, but all logic gates and further functions such as latches, adders, flip-flops, and others, are implemented directly at the transistor level and the next step up is combining these optimized cells. I was satisfied with this answer until I was notified that VLSI chips are sometimes programmed at the gate level, which tells me the next layer is the standard logic gates, though still not just NAND. I've also found mentions of CMOS logic and its capabilities, but lack the expertise to parse an answer to my question from it.

Ideally, I'm looking for some definitive list of what functions are directly implemented at the transistor level, and what the next level of abstraction for designing a general-purpose CPU is. I suspect the list is complicated and differs by company and model, but any clarification for a curious layman would help.

Answer 1

In my CS program, my professor has claimed that NAND gates are the most basic gate to engineer, and so every other gate and higher-level circuits found in CPUs are made from NAND gates

“Yeah? Well, you know, that's just like, uh, your opinion, man.” - The Dude

Your professor is … not correct, on several levels.

Let's unpack this.

NAND gates are the most basic gate to engineer

No, they're not. That would be the NOT gate. NAND and NOR are comparably complex, each needing at least two transistors using a pull-up (in CMOS, each type takes four.)

so every other gate and higher-level circuits found in CPUs are made from NAND gates

The identical claim can be made for NOR, as it is equally complex as NAND and can implement the same palette of functions through application of DeMorgan's Theorem.

So the prof's claims are neither true in theory, nor in practice as we'll see below.

The prof may be quite surprised to learn that a very important early CPU built using a single gate type (and quite possibly, the only one of such construction, ever) exists in the Apollo Guidance Computer (AGC). This machine's logic was built entirely from just one IC: a dual 3-input (positive-logic) NOR. Not a NAND in sight, nor (pun intended) in flight.

More here: http://www.righto.com/2019/09/a-computer-built-from-nor-gates-inside.html

And their rationale for choosing that IC: https://www.ibiblio.org/apollo/hrst/archive/1716.pdf.

In the most general sense, if you have just two things: inversion, and any kind of Turing-complete base 2-input function, you have the ability to make any kind of logic of any complexity. DeMorgan’s Theorem tells us so. NOR and NAND by themselves satisfy this, as well AND+NOT and OR+NOT. Choose one, or a combination, they all work.

Do people still make things out of a single type of gate, be it NAND or NOR? Not so much. Gate arrays or sea-of-gates are extreme examples of this idea, and yes these can be based exclusively on a single inverting logic type like NAND or NOR. Gate arrays have limits, inefficiencies and costs; and as a consequence aren’t so popular anymore. They've been largely supplanted by microcontrollers, CPLDs, FPGAs and of course ASICs.

For the hierarchy of chip structures (that is, levels of abstraction), we have as you stated transistors and interconnect wires as the the lowest level. What's the abstraction level above that, then? We’ll get to that, I promise.

In the salad days of chip design (think of Jack Kilby, Robert Noyce), the answer was… not much. Transistors and interconnect were laid out polygon-by-polygon and layer-by-layer, by hand (first in rubylith, then later by physical CAD software), to capture the design and create a mask set. This practice originated in bipolar and persisted well into the development of MOS technology.

With the publication of their 1978 paper (and later their book based on it), Carver Mead and Lynn Conway changed all that with their structured methodology based on MOS. Among other ideas, they introduced the concept of standard cells, a set of pre-defined functional primitives that can be re-used from chip to chip, and just as importantly, from process to process. Soon, this set of functions came to be offered as a standard cell libraries by the process vendors, characterized on their target process for guaranteed performance.

Because the fab vendor guarantees the cells' performance, using the standard cell library flow provides a ‘clean handoff’ from the designer to the foundry that was all but impossible to achieve using the polygons-in-rubylith methods of the 1960s and 70s. (Tip o’ the hat to those early pioneers that did it; the effort needed to make even the simpler chips of the time was huge.)

This philosophy of design and re-use, enabled by Mead and Conway's structured design and the standard cell libraries to support it, is what kicked chip design into high gear in the 1980s.

Mead and Conway’s book Introduction to VLSI Systems is still available, and although it focuses on NMOS it is still relevant today.

Back to the present, and your question. With contemporary CMOS design, besides the base and complex gates, you see more use of transmission gates to construct logic. It could be said for CMOS that gate primitives, transmission gates and sequential storage are the basic logic-level pieces above individual transistors and wires. Gate primitives will include NAND, NOR and NOT, as well as efficient transistor-level implementations of more-complex elements like XOR/XNOR, AOI (AND-OR-INVERT), multiplexers and arithmetic. Transmission gates, buffers, latches and flops round out the rest of the low-level library.

The AOI / OAI gates deserve special mention. These structures are very efficient in CMOS, requiring at minimum only 6 transistors. They are very handy for rendering sum-of-product or product-of-sum logic.

Bigger ‘regular’ functional units like RAMs and ROMs are also offered, being designed from the transistor level and characterized as blocks. These are usually handled as parameterized macros that are auto-generated based on user inputs (depth, width, # of ports, etc.)

More about standard cell libraries here: https://www.eng.biu.ac.il/temanad/files/2017/02/Lecture-4-Standard-Cell-Libraries.pdf

Do people still 'push polygons'? Sure. Critical-path blocks benefit from transistor-level hand-tweaked design to achieve higher performance, greater density or lower power. Mixed-signal blocks may also be done at least partially by hand. You can think of these as 'custom' cells that a designer may re-use from project to project, but nevertheless will also be characterized for a specific process as add-ons to the standard library.

Aside from those hand-made edge cases, chips are built using synthesis based on the standard cell library, with the designer’s main work being architecture, logic design and synthesis, as well as partitioning and placement - all to achieve the target performance using the least possible die area and at acceptable power.

In short, and at long last, in modern chip design the standard cell library is the next level of abstraction above transistors and wires that most designers interact with to create chips.

What's the next layer above the standard cell library to 'program' the CPU? Depends on the CPU. There might be PLAs (Programmable Logic Arrays), microcode ROMs or some other mapping structures that would be mask-programmed by rearranging only one or two contact layers. Such blocks allow making changes / fixing bugs without doing an entire base-layer tapeout. They can shorten schedule and reduce prototyping cost, at the expense of increased area compared to synthesized logic.

Answer 2

On most processors today, the lowest level of programming is machine code.

There were some processors in the past which actually ran their own programs which interpreted your programs, but that was rare and the company eventually went out of business.

You may have heard of microcode. Some low-end CPUs did run actual interpreters written in microcode. On modern CPUs, the microcode is not exactly "programming" - it is more of a lookup table that helps the instruction decoder with certain instructions that are difficult to execute. All the "fast" instructions are decoded and executed directly without microcode help. So the lowest level of actual programming on these CPUs is still machine code.

Even on systems with microcode interpreters, microcode is always designed together with the hardware. That means they design the hardware to do exactly what the built-in microcode needs - no more and no less. It's not a general-purpose programming language. You couldn't write a Python interpreter in microcode. Otherwise they'd call it machine code.

---

You mentioned "VLSIs being programmed at the gate level" in the context of Hardware Description Languages (specifically Verilog). However, HDLs are not programs for CPUs. They are more like programs for the systems that design CPUs. A designer can write some HDL, and feed it through their "Verilog compiler", and out comes a plan for building a CPU. Then they can send that plan to their manufacturing plant, and in several months, they can get a CPU (or more likely, a hundred thousand CPUs). And then they can write machine code programs for the CPU.

The linked document mentions different "levels" of Verilog programming. The levels talk about how much work the Verilog compiler has to do. You can tell it "place a transistor here" or you can tell it "place a NAND gate here" or you can tell it "place an adder which adds the numbers coming from here and here and sends the result here" or you can tell it "please make it a machine that computes a fixed-point Fourier transform".

But that's all to do with the compiler. The actual chip, that you get after running the compiler and then sending the plans to the manufacturing plant, is still programmed in machine code.

---

By the way, you don't have to use Verilog to design a CPU. You can use it to design any chip you want. But those chips aren't called CPUs.

---

In the past there have been attempts to design chips that efficiently execute certain high-level languages, like Lisp machines. They didn't run Lisp directly, though - they ran machine code which was designed in a way that made Lisp programs fast. You still had to write a Lisp interpreter or Lisp compiler using machine code.

Answer 3

"In my CS program, my professor has claimed that NAND gates are the most basic gate to engineer, and so every other gate and higher-level circuits found in CPUs are made from NAND gates"

A two input CMOS NAND gate uses four transistors. A CMOS NOT gate uses only two transistors. Therefore a NAND gate is definitely not the smallest CMOS gate in terms of transistors.

Both the two-input CMOS NAND gate and two input CMOS NOR gate can be constructed using four transistors, and they can both be used as the basis for constructing any Boolean function. I would argue that a NAND gate is not any more "basic" than a NOR gate.

I'm skeptical of this claim, as it seems prohibitively slow, and I would expect that many optimizations can be made by avoiding such restrictions.

While its possible to construct any Boolean logic function form only NAND gates, its not necessarily optimal. Constructing a 2-input CMOS NOR gate uses 4 transistors. Constructing a 2-input COMOS NOR gate by gluing together four CMOS NAND gates uses 16-tansistors. And its going to run slower too.

So while we may construct a CPU from just NAND gates, in practice we don't do it unless we have to.

The exception would be if you are making an ASIC using standard cells. In that case you are limited to constructing the logic using the technology available in the manufacturer's process. And they may very-well limit you to just using NAND gates.

Ideally, I'm looking for some definitive list of what functions are directly implemented at the transistor level, and what the next level of abstraction for designing a general-purpose CPU is. I suspect the list is complicated and differs by company and model, but any clarification for a curious layman would help.

Which elements are going to be available in your process depends on which manufacturer you are going to use.

1. For example you could write the logic description for your CPU in VHDL or Verilog, and then prototype it on a Xilinx FPGA. You can then go to Xilinx and use their Easy-Path process to convert the FPGA design directly into an ASIC without any modifications needed on your part. In that case the elements available for you to design with are basically any of the cells in the FPGA.

2. Alternatively you could use a prototype CMOS fabrication service like MOSIS. In that case you can make CMOS transistors directly, and you can basically do anything you want. The university I attended used this service to fabricate the designs from their graduate level CPU design course. https://www.mosis.com/

Answer 4

You asked for "the lowest level above transistors". And the lowest level you will use either a NAND gate or a NOR gate, depending on how you interpret voltages as truth values, and depending on your exact technology.

However, that lowest level is not a "two input, one output NAND gate"; you'd throw away too much if you go straight to this level. Instead you'll have a NAND gate with n inputs, 1 ≤ n ≤ some value. And your inputs / outputs will not be true or false but still voltages, and the output voltages will not be quite the perfect voltages that you would want. So you have gates that require a certain quality of the input signal and produce a certain quality in their output signal. A four input NAND will not produce quite the same output signal as a two input NAND. So when you build on this level, you need to make sure your signals are strong enough so that your gates actually work.

At the next higher level, your standard logic gates will be built from these. Someone will design say an adder from NAND gates and will use two input, three input, whatever is better, and make sure all weak output signals are used as inputs that can handle these weak inputs.

At that point we are still miles away from "CPU programming".