Computer Architecture and the Structure of a CPU: From Transistors to RISC-V

0. Key points

• A computer is, at bottom, a network of switches. Two transistors make a NOT gate, four make a NAND gate, and NAND alone suffices to build every logic function (Corollary 2.4).
• There are only $2^{2^n}$ Boolean functions of $n$ variables, and every one of them can be written in disjunctive normal form (Theorem 2.3). What hardware can compute rests on this finiteness.
• An adder is a concrete implementation of a Boolean function. Its correctness is proved by induction on the carries (Theorem 4.2), and its speed is determined by the depth of the circuit (Proposition 4.4).
• The clock and the flip-flop are what create “time”. The upper bound on the operating frequency comes from the setup constraint $T \ge t_{cq} + t_{pd} + t_{su} + t_{skew}$ (Proposition 5.2).
• The von Neumann architecture embodies one design decision: instructions and data live in the same memory, as the same kind of bit string. Generality is bought at the price of a narrow channel to memory, which becomes the bottleneck.
• An instruction set architecture (ISA) is the contract between hardware and software. RISC-V publishes that contract in a form anyone may implement, and add x5, x6, x7 encodes to the 32-bit word 0x007302B3 (Example 8.2).

1. Motivation: from rewiring the machine to reading a program

ENIAC, unveiled in 1946, was fast beyond comparison for its day. But changing what it computed meant physically replugging thousands of cables and switches by hand, a job that took days. The computation itself finished in seconds; specifying the computation took days. That asymmetry is the starting point for the next design.

In 1945 a draft report on the EDVAC, circulated under John von Neumann’s name, gave one answer to the problem. Instructions are numbers too; so put them in the same memory as the data and let the machine read them out itself. Rewiring was replaced by rewriting memory. This is the stored-program principle, and it is the basic design of almost every computer built since.

A naive question arises here. Why does a lump of sand (silicon) compute? Stones do not think. But a switch made of stone can distinguish two states, a high and a low voltage. Two distinguishable states let you represent truth values; truth values let you represent logic functions; logic functions let you represent arithmetic. Add a mechanism that remembers the previous value and a clock that marks which step you are on, and a static circuit becomes a computational process unfolding in time.

This article follows that construction from the bottom up, one level at a time.

1. From switches (transistors) to logic gates (Theorem 2.3, Section 3)
2. From logic gates to arithmetic (adders) (Section 4)
3. From combinational circuits to memory and the clock (Section 5)
4. The five functional units and the von Neumann architecture (Section 6)
5. The internal structure of a CPU and the execution of an instruction (Section 7)
6. The ISA as a contract between hardware and software, and RISC-V (Section 8)

2. Preliminaries: the language of Boolean functions and switches

Before talking about circuits, let us fix in mathematical language what a circuit is trying to realise.

Definition 2.1（Boolean function）

A Boolean function of $n$ variables over $\{0,1\}$ is a map $f : \{0,1\}^n \to \{0,1\}$. On $\{0,1\}$ we define the operations

$$x \land y = \min(x,y), \qquad x \lor y = \max(x,y), \qquad \lnot x = 1 - x, \qquad x \oplus y = (x + y) \bmod 2$$

and call them AND, OR, NOT and XOR respectively.

Designing a circuit is nothing other than writing the desired Boolean function as a composite of these basic operations. Let us first count how many such targets there are.

Proposition 2.2（The number of Boolean functions）

For $n \ge 1$, the total number of Boolean functions $f : \{0,1\}^n \to \{0,1\}$ of $n$ variables is exactly $2^{2^n}$.

Proof（Proposition 2.2）

Specifying $f$ is the same as assigning the value $0$ or $1$ to each element of the domain $\{0,1\}^n$. The domain has $2^n$ elements, since each of the $n$ coordinates has 2 possibilities. The assignments to distinct elements are independent, and each has 2 possibilities. Hence the total number of assignments is $2$ multiplied by itself $2^n$ times, that is, $2^{2^n}$.

∎

Concretely: 4 functions for $n=1$, 16 for $n=2$, 256 for $n=3$, 65536 for $n=4$, and about 4.3 billion for $n=5$. The count grows doubly exponentially in $n$, so functions of large $n$ cannot be handled by truth tables at all. That is precisely why we need a way to construct functions as formulas. The next theorem supplies one.

Theorem 2.3（Disjunctive normal form and the completeness of AND, OR, NOT）

Let $n \ge 1$ and let $f : \{0,1\}^n \to \{0,1\}$ be an arbitrary Boolean function. Then $f$ can be expressed by a formula using only the variables $x_1, \ldots, x_n$ and the operations $\land, \lor, \lnot$. Explicitly, for $a = (a_1,\ldots,a_n) \in \{0,1\}^n$ set

$$m_a(x_1,\ldots,x_n) = \bigwedge_{i=1}^{n} x_i^{a_i}, \qquad x^1 = x,\quad x^0 = \lnot x$$

Then, provided $f$ is not identically $0$,

$$f(x_1,\ldots,x_n) = \bigvee_{a \in f^{-1}(1)} m_a(x_1,\ldots,x_n)$$

holds. If $f$ is identically $0$, then $f = x_1 \land \lnot x_1$.

Proof（Theorem 2.3）

We first verify two properties of $m_a$.

(i) $m_a(a) = 1$. The $i$-th factor is $a_i^{a_i}$. If $a_i = 1$ the factor is $a_i = 1$; if $a_i = 0$ the factor is $\lnot a_i = 1$. In both cases it equals $1$. Every factor is $1$, so the AND is $1$ as well.

(ii) If $x \ne a$ then $m_a(x) = 0$. Since $x \ne a$, there is an index $i$ with $x_i \ne a_i$. If $a_i = 1$ then $x_i = 0$ and the $i$-th factor is $x_i = 0$; if $a_i = 0$ then $x_i = 1$ and the $i$-th factor is $\lnot x_i = 0$. A single factor equal to $0$ makes the AND equal to $0$.

Now suppose $f$ is not identically $0$ and put $g(x) = \bigvee_{a \in f^{-1}(1)} m_a(x)$ for the right-hand side (this is a non-empty OR, since $f^{-1}(1) \ne \emptyset$). For every $x \in \{0,1\}^n$ the following holds.

• If $f(x) = 1$, then $x \in f^{-1}(1)$, so $a = x$ occurs among the terms of the OR, and $m_x(x) = 1$ by (i). An OR with even one term equal to $1$ is $1$, so $g(x) = 1$.
• If $f(x) = 0$, then every $a$ occurring in the OR satisfies $a \in f^{-1}(1)$, hence $a \ne x$, so by (ii) all the terms are $0$. Therefore $g(x) = 0$.

So $f$ and $g$ agree on every input, that is, $f = g$; and $g$ is written using only the variables and $\land, \lor, \lnot$.

Finally, if $f$ is identically $0$, then $x_1 \land \lnot x_1$ is $0$ both for $x_1 = 0$ and for $x_1 = 1$, so it represents $f$.

∎

This theorem guarantees that any input-output table whatsoever can be realised by a circuit. Moreover the proof is constructive: write down the truth table and the formula falls out mechanically. On actual silicon, however, it is cheaper to get by with a single kind of gate rather than to build AND, OR and NOT directly. The following corollary supplies it.

Corollary 2.4（Functional completeness of NAND）

Define $x \barwedge y = \lnot(x \land y)$ (NAND). Every Boolean function $f : \{0,1\}^n \to \{0,1\}$ can be expressed by a formula using only the variables and NAND.

Proof（Corollary 2.4）

By Theorem 2.3, $f$ can be written as a formula in $\land, \lor, \lnot$, so it suffices to build these three out of NAND alone.

• $\lnot x = \lnot(x \land x) = x \barwedge x$. Indeed $x \land x = x$, so the two sides agree.
• $x \land y = \lnot(x \barwedge y) = (x \barwedge y) \barwedge (x \barwedge y)$, applying the construction of $\lnot$ from the previous line to $x \barwedge y$.
• $x \lor y = (x \barwedge x) \barwedge (y \barwedge y)$. The right-hand side is $\lnot(\lnot x \land \lnot y)$, which by De Morgan’s law equals $x \lor y$.

Applying these three substitutions recursively to the formula for $f$ yields a formula using NAND only.

∎

Example 2.5（Turning the 3-variable majority function into a formula）

We construct the function $M$ that returns $1$ when at least two of $x_1, x_2, x_3$ are $1$. In the truth table, the inputs with $M = 1$ are the four tuples $(0,1,1), (1,0,1), (1,1,0), (1,1,1)$. Writing out the construction of Theorem 2.3 verbatim gives

$$M = (\lnot x_1 \land x_2 \land x_3) \lor (x_1 \land \lnot x_2 \land x_3) \lor (x_1 \land x_2 \land \lnot x_3) \lor (x_1 \land x_2 \land x_3)$$

which uses four 3-input ANDs, one 4-input OR and three NOTs: eight gates in all. Now we simplify. Since $a \lor a = a$, the last term $x_1 \land x_2 \land x_3$ may be used three times, so we may rewrite this as

$$\begin{aligned} M &= (\lnot x_1 \land x_2 \land x_3) \lor (x_1 \land x_2 \land x_3) \\ &\quad \lor (x_1 \land \lnot x_2 \land x_3) \lor (x_1 \land x_2 \land x_3) \\ &\quad \lor (x_1 \land x_2 \land \lnot x_3) \lor (x_1 \land x_2 \land x_3) \end{aligned}$$

Using $x \lor \lnot x = 1$ on each line, the first line becomes $(\lnot x_1 \lor x_1) \land x_2 \land x_3 = x_2 \land x_3$, the second becomes $x_1 \land x_3$, and the third becomes $x_1 \land x_2$. Hence

$$M = (x_1 \land x_2) \lor (x_2 \land x_3) \lor (x_3 \land x_1)$$

which uses three 2-input ANDs and one 3-input OR: four gates, half the previous count. The same function can cost twice as much or half as much depending on how the formula is written. Reducing that cost is the job of the design step called logic synthesis.

3. Transistors: turning physics into logic

We now realise the $\land, \lor, \lnot$ of the previous section physically. The dominant device today is the MOSFET (metal-oxide-semiconductor field-effect transistor). Structurally it is a small capacitor: a metal (or polysilicon) electrode sitting on the silicon surface with a thin insulating film in between. Applying a voltage to this electrode (the gate) draws charge to the silicon surface underneath the insulator, and the region between the two flanking terminals (source and drain) becomes conducting. Voltage controls conduction. That is a switch.

For logic design it is enough to treat the device with the following idealised model.

• nMOS: conducts when the gate voltage is high (logical $1$) and blocks when it is low (logical $0$).
• pMOS: conducts when the gate voltage is low and blocks when it is high; complementary in behaviour to nMOS.

CMOS logic combines the two kinds by placing a network of pMOS transistors (the pull-up network) on the supply side $V_{DD}$ and a network of nMOS transistors (the pull-down network) on the ground side, arranged so that for every input exactly one of the two conducts. The smallest example is the NOT gate.

A CMOS inverter (NOT gate). When the input A is 0 only the upper pMOS conducts and the output Y is pulled to the supply voltage; when A is 1 only the lower nMOS conducts and Y is pulled to ground. In the steady state there is no conducting path from supply to ground.

If the input is $A = 0$, the pMOS conducts and the nMOS blocks, so the output $Y$ is tied to the supply and equals $1$. If $A = 1$ the reverse happens and $Y$ is tied to ground, giving $0$. That is, $Y = \lnot A$: a NOT gate out of two transistors. The same idea with two nMOS in series and two pMOS in parallel gives NAND in four transistors, and swapping series for parallel gives NOR in four. Building an AND requires appending a NOT after the NAND, hence six. In CMOS the inverting version is always the cheaper one, which is why the NAND and NOR of Corollary 2.4 are the basic units of implementation.

From this structure we can derive a basic law about power consumption.

Proposition 3.1（Energy consumption of CMOS）

Consider a CMOS gate whose output drives a capacitance $C$. Assume the pull-up and pull-down networks never conduct simultaneously and that transistor leakage current is negligible. Then:

1. In the steady state, when the output is not changing, the current flowing from supply to ground is $0$ and the power consumption is $0$ as well.
2. Each time the output makes a full round trip $0 \to 1 \to 0$, the energy drawn from the supply and turned into heat is exactly $C V_{DD}^2$, and this value does not depend on the resistance of the conducting path.
3. If the clock frequency is $f$ and on average $\alpha$ transitions $0 \to 1$ occur per clock cycle, the average power consumption is $P = \alpha \, C \, V_{DD}^2 \, f$.

Proof（Proposition 3.1）

(1) In the steady state, by assumption exactly one of the pull-up and pull-down networks conducts. Hence there is no conducting path joining supply to ground and no current flows. Power is the product of voltage and current, so it is $0$.

(2) Consider first the charging $0 \to 1$. When the capacitance is charged from $0$ to $V_{DD}$, the charge delivered by the supply is $Q = C V_{DD}$. The supply voltage is constant at $V_{DD}$, so the energy it provides is

$$E_{\text{supply}} = \int V_{DD} \, i(t) \, dt = V_{DD} \int i(t)\, dt = V_{DD} Q = C V_{DD}^2$$

Meanwhile the energy stored in the capacitance is

$$E_{C} = \int_{0}^{V_{DD}} C v \, dv = \tfrac{1}{2} C V_{DD}^2$$

so the difference $\tfrac{1}{2} C V_{DD}^2$ is dissipated as heat in the on-resistance of the pMOS. Note that the resistance $R$ does not appear anywhere. Next, in the discharge $1 \to 0$, the $\tfrac{1}{2} C V_{DD}^2$ stored in the capacitance is entirely dissipated as heat in the on-resistance of the nMOS, and the supply provides no energy. The round-trip total is $\tfrac{1}{2} C V_{DD}^2 + \tfrac{1}{2} C V_{DD}^2 = C V_{DD}^2$.

(3) There are $f$ clock cycles per second and on average $\alpha$ transitions $0 \to 1$ per cycle, so there are $\alpha f$ round trips per second. By (2) each round trip costs $C V_{DD}^2$, so the energy per unit time, that is the power, is $P = \alpha C V_{DD}^2 f$.

∎

The single most important feature of this formula is that $V_{DD}$ enters squared.

Example 3.2（What happens when the supply voltage is lowered）

Consider a chip with $10^9$ signal wires. Take the capacitance of each wire to be $C = 2\ \mathrm{fF} = 2 \times 10^{-15}\ \mathrm{F}$, the operating frequency $f = 3\ \mathrm{GHz}$, the average transition rate per clock $\alpha = 0.01$, and the supply voltage $V_{DD} = 1.0\ \mathrm{V}$. By Proposition 3.1,

$$P = 0.01 \times 10^{9} \times (2\times 10^{-15}) \times (1.0)^2 \times (3 \times 10^{9}) = 60\ \mathrm{W}$$

If we now raise only the supply voltage to $1.8\ \mathrm{V}$, then $P$ grows by a factor of $(1.8/1.0)^2 = 3.24$, reaching $194\ \mathrm{W}$. Given that air cooling can shed on the order of 100 W, this difference is decisive. The reason supply voltages have been pushed down from 5 V to around 1 V as feature sizes shrank is exactly this square law.

Remark 3.3（Why binary?）

With ten distinct voltage levels, a single wire could carry one decimal digit. Two values are nonetheless used, for the sake of the margin against noise (the noise margin). At a supply voltage of $1\ \mathrm{V}$, ten levels means the spacing to be distinguished is about $0.1\ \mathrm{V}$, whereas two values give about $1\ \mathrm{V}$. Moreover, as part (1) of Proposition 3.1 shows, CMOS consumes almost no power only when the output is driven fully to the supply voltage or to ground; intermediate voltages translate directly into wasted energy. Both reliability and power point to two values.

Remark 3.4（Homemade transistors, homemade chips）

The principle that a MOSFET is “a device controlling the conductivity of a silicon surface by means of an electrode behind an insulating film” is a simple one. As a result there are several cases of individuals making working transistors with home equipment. Jeri Ellsworth built and operated field-effect transistors using a homemade furnace and vacuum apparatus, and Sam Zeloof assembled a full photolithography setup in his home garage and fabricated homemade chips integrating several transistors. Going in the opposite direction, James Newman’s Megaprocessor is a 16-bit processor built from about 40,000 discrete off-the-shelf transistors, with every register bit lit by an LED so that the operation can be watched.

These are not practical devices, but they let one walk back down the ladder of abstraction and confirm the fact that computation is a physical phenomenon. The very characters you are reading now are the result of charge gathering and dispersing on some silicon surface.

4. From combinational circuits to arithmetic: the adder

With logic gates in hand, we build arithmetic. Binary addition is realised by lining up, for each digit position, a component that produces “the sum digit” and “the carry to the next position”.

Definition 4.1（Full adder and ripple-carry adder）

A combinational circuit which, on inputs $a, b, c \in \{0,1\}$, outputs

$$s = a \oplus b \oplus c, \qquad c' = (a \land b) \lor \bigl(c \land (a \oplus b)\bigr)$$

is called a full adder. We call $s$ the sum bit and $c'$ the carry out.

The circuit obtained by chaining $n$ full adders so that the carry out $c_{i+1}$ of the $i$-th one feeds the carry in of the $(i+1)$-st, with $a_i, b_i$ the inputs at digit $i$ and $c_0$ the carry into the least significant position, is called an $n$-bit ripple-carry adder (carry-propagate adder).

Theorem 4.2（Correctness of the ripple-carry adder）

Let $n \ge 1$ and let $a_i, b_i \in \{0,1\}$ ($0 \le i \le n-1$) and $c_0 \in \{0,1\}$ be arbitrary. If $s_i, c_{i+1}$ ($0 \le i \le n-1$) are defined by the recurrence of Definition 4.1, then the integer identity

$$\sum_{i=0}^{n-1} (a_i + b_i) 2^i + c_0 \;=\; c_n 2^n + \sum_{i=0}^{n-1} s_i 2^i$$

holds. That is, the sum of $a$ and $b$ read as $n$-bit binary numbers, plus $c_0$, equals the $(n+1)$-bit number whose low $n$ bits are $s$ and whose most significant bit is $c_n$.

Proof（Theorem 4.2）

Step 1: the one-digit identity. We show that for each $i$, as integers,

$$a_i + b_i + c_i = 2 c_{i+1} + s_i$$

The left-hand side is an integer between $0$ and $3$. Since XOR is addition modulo $2$ (Definition 2.1), $s_i = a_i \oplus b_i \oplus c_i$ equals the remainder of the left-hand side on division by $2$. Next we check by cases that $c_{i+1}$ equals the quotient of the left-hand side by $2$, that is, “at least two of the three are $1$”.

• If $a_i = b_i = 1$: then $a_i \land b_i = 1$, so $c_{i+1} = 1$. The left-hand side is $2 + c_i \ge 2$, so the quotient is $1$. They agree.
• If $a_i \ne b_i$: then $a_i \land b_i = 0$ and $a_i \oplus b_i = 1$, so $c_{i+1} = c_i$. The left-hand side is $1 + c_i$, whose quotient equals $c_i$. They agree.
• If $a_i = b_i = 0$: then $a_i \land b_i = 0$ and $a_i \oplus b_i = 0$, so $c_{i+1} = 0$. The left-hand side is $c_i \le 1$, so the quotient is $0$. They agree.

Quotient and remainder agree, so the one-digit identity follows from the uniqueness of division with remainder.

Step 2: induction on the number of digits. We prove, for $0 \le k \le n$,

$$P(k):\quad \sum_{i=0}^{k-1} (a_i + b_i) 2^i + c_0 = c_k 2^k + \sum_{i=0}^{k-1} s_i 2^i$$

For $k = 0$ both sums are empty, so the left-hand side is $c_0$ and the right-hand side is $c_0 \cdot 2^0 = c_0$; thus $P(0)$ holds.

Assume $P(k)$ with $k \le n-1$. Adding $(a_k + b_k) 2^k$ to both sides, the left-hand side becomes the left-hand side of $P(k+1)$. The right-hand side becomes

$$\begin{aligned} c_k 2^k + \sum_{i=0}^{k-1} s_i 2^i + (a_k + b_k)2^k &= (a_k + b_k + c_k) 2^k + \sum_{i=0}^{k-1} s_i 2^i \\ &= (2 c_{k+1} + s_k) 2^k + \sum_{i=0}^{k-1} s_i 2^i \\ &= c_{k+1} 2^{k+1} + \sum_{i=0}^{k} s_i 2^i \end{aligned}$$

where the second line uses the one-digit identity of Step 1. This is the right-hand side of $P(k+1)$. Hence $P(k+1)$ holds, and by induction we obtain $P(n)$.

∎

Example 4.3（Following a 4-bit addition to the end）

Take $a = 1011_2$ ($= 11$), $b = 0110_2$ ($= 6$) and $c_0 = 0$, and run the recurrence of Definition 4.1 from the least significant digit upward.

$i$	$a_i$	$b_i$	$c_i$	$a_i+b_i+c_i$	$s_i$	$c_{i+1}$
0	1	0	0	1	1	0
1	1	1	0	2	0	1
2	0	1	1	2	0	1
3	1	0	1	2	0	1

The result is $c_4 s_3 s_2 s_1 s_0 = 1\,0001_2 = 17$, and indeed $11 + 6 = 17$. The identity of Theorem 4.2 holds.

Reading the same circuit as signed (two’s complement) arithmetic, $1011_2 = -5$ and $0110_2 = 6$, and the low four bits of the result, $0001_2 = 1$, give $-5 + 6 = 1$, which is also correct. The advantage of two’s complement is that the addition circuit can be reused verbatim. What does change is the test for validity: unsigned, the carry out $c_4 = 1$ signals overflow, whereas signed we compute $c_4 \oplus c_3 = 1 \oplus 1 = 0$, so there is no overflow.

In a ripple-carry adder the carry, as the name says, propagates from the low digits to the high ones in sequence. If the delay of one full adder is $d$, then $n$ bits give a delay of $n d$, that is, $\Theta(n)$. At 64 bits this would dictate the speed, so real CPUs use the following structure.

Proposition 4.4（Carry lookahead and prefix computation）

Setting $g_i = a_i \land b_i$ and $p_i = a_i \oplus b_i$, the carry of Definition 4.1 can be written as $c_{i+1} = g_i \lor (p_i \land c_i)$. Define the binary operation on $\{0,1\}^2$

$$(g', p') \circ (g, p) = \bigl(g' \lor (p' \land g),\ p' \land p\bigr)$$

Then the following hold.

1. $\circ$ is associative and makes $\{0,1\}^2$ a monoid with identity element $(0,1)$.
2. Putting $(G_i, P_i) = (g_i, p_i) \circ (g_{i-1}, p_{i-1}) \circ \cdots \circ (g_0, p_0)$, we have $c_{i+1} = G_i \lor (P_i \land c_0)$.
3. All the carries $c_{i+1}$ ($0 \le i \le n-1$) can be computed by a circuit of fan-in-2 AND, OR and XOR gates of depth $O(\log n)$ using $O(n \log n)$ gates.

Proof（Proposition 4.4）

First we verify $c_{i+1} = g_i \lor (p_i \land c_i)$. The defining formula in Definition 4.1 is $c_{i+1} = (a_i \land b_i) \lor (c_i \land (a_i \oplus b_i))$; substituting the definitions of $g_i, p_i$ gives $g_i \lor (c_i \land p_i)$, and commutativity of AND puts it in the stated form.

(1) Associativity. We compute both bracketings on three elements.

$$\begin{aligned} \bigl((g_3,p_3) \circ (g_2,p_2)\bigr) \circ (g_1,p_1) &= (g_3 \lor (p_3 \land g_2),\ p_3 \land p_2) \circ (g_1,p_1) \\ &= \bigl(g_3 \lor (p_3 \land g_2) \lor (p_3 \land p_2 \land g_1),\ p_3 \land p_2 \land p_1\bigr), \\ (g_3,p_3) \circ \bigl((g_2,p_2) \circ (g_1,p_1)\bigr) &= (g_3,p_3) \circ (g_2 \lor (p_2 \land g_1),\ p_2 \land p_1) \\ &= \bigl(g_3 \lor \bigl(p_3 \land (g_2 \lor (p_2 \land g_1))\bigr),\ p_3 \land p_2 \land p_1\bigr). \end{aligned}$$

Since AND distributes over OR, the first component of the last expression equals $g_3 \lor (p_3 \land g_2) \lor (p_3 \land p_2 \land g_1)$, which matches the expression above. As for the identity, $(g,p) \circ (0,1) = (g \lor (p \land 0), p \land 1) = (g,p)$ and $(0,1) \circ (g,p) = (0 \lor (1 \land g), 1 \land p) = (g,p)$.

(2) Induction on $i$. For $i = 0$ we have $(G_0,P_0) = (g_0,p_0)$ and $G_0 \lor (P_0 \land c_0) = g_0 \lor (p_0 \land c_0) = c_1$. Assuming the claim for $i-1$,

$$\begin{aligned} c_{i+1} &= g_i \lor (p_i \land c_i) = g_i \lor \bigl(p_i \land (G_{i-1} \lor (P_{i-1} \land c_0))\bigr) \\ &= g_i \lor (p_i \land G_{i-1}) \lor (p_i \land P_{i-1} \land c_0) = G_i \lor (P_i \land c_0) \end{aligned}$$

where the second line uses distributivity and the last step uses $(G_i,P_i) = (g_i,p_i) \circ (G_{i-1},P_{i-1})$.

(3) Depth. The pairs $(G_i, P_i)$ are the prefixes of an associative operation. In the Kogge–Stone construction one starts from $(G^{(0)}_i, P^{(0)}_i) = (g_i, p_i)$ and updates, for $k = 1, 2, \ldots$,

$$(G^{(k)}_i, P^{(k)}_i) = (G^{(k-1)}_i, P^{(k-1)}_i) \circ (G^{(k-1)}_{i - 2^{k-1}}, P^{(k-1)}_{i - 2^{k-1}})$$

(taking the identity $(0,1)$ when the index is negative). By associativity, induction on $k$ shows that $(G^{(k)}_i, P^{(k)}_i)$ equals the product over the interval $[\max(0, i-2^k+1),\, i]$. After $k = \lceil \log_2 n \rceil$ stages we have $2^k \ge n$ and the whole interval is covered, giving $(G_i,P_i)$. One application of $\circ$ is realised by two ANDs and one OR (depth 2), and each stage performs $n$ of them in parallel, so the overall depth is $O(\log n)$ and the gate count is $O(n \log n)$. Computing $s_i = p_i \oplus c_i$ at the end costs one extra level of depth.

∎

Comparing at 64 bits: the ripple carry takes 64 stages, whereas $\lceil \log_2 64 \rceil = 6$ stages suffice. The gap between $\Theta(n)$ and $\Theta(\log n)$ translates directly into a gap in clock frequency.

5. Memory and the clock: sequential circuits

The circuits so far have no time in them. Give an input and, after a delay, the output is determined; that is all. To turn computation into a procedure we need a mechanism that remembers values, and it is obtained by introducing feedback into the circuit. Feeding the outputs of two NOR gates back into each other’s inputs yields an SR latch, which holds its previous state as long as both inputs are $0$. Stacking two of these so that the input is captured only at the instant the clock signal rises gives an edge-triggered D flip-flop. A CPU register is simply as many D flip-flops as the register is wide, side by side.

Definition 5.1（Synchronous sequential circuits and timing parameters）

A circuit in which every memory element captures its value on the rising edge of one and the same clock signal $\mathrm{clk}$ is called a synchronous sequential circuit. For an edge-triggered D flip-flop we define the following quantities.

• $t_{cq}$ ($t_{ccq}$): the maximum (minimum) delay from the clock edge until the output Q settles.
• $t_{su}$ (setup time): how many seconds before the clock edge the input D must already have settled.
• $t_{h}$ (hold time): how many seconds after the clock edge the input D must be held.

We also write $t_{pd}$ for the maximum delay and $t_{cd}$ for the minimum delay of the combinational logic between flip-flops, and $t_{skew}$ for the maximum spread in the times at which the clock arrives at the various flip-flops.

Proposition 5.2（Timing constraints and the maximum operating frequency）

In the setting of Definition 5.1, let the clock period be $T$. In order for every flip-flop to capture its value correctly, the following two conditions are necessary and sufficient.

$$T \ge t_{cq} + t_{pd} + t_{su} + t_{skew} \qquad\text{(setup constraint)}$$$$t_{ccq} + t_{cd} \ge t_{h} + t_{skew} \qquad\text{(hold constraint)}$$

In particular the operating frequency is capped at $f = 1/T \le 1/(t_{cq} + t_{pd} + t_{su} + t_{skew})$. Since $T$ does not appear in the hold constraint, a hold violation cannot be removed by slowing down the clock.

Proof（Proposition 5.2）

Let time $0$ be the moment the clock edge arrives at the sending flip-flop.

Setup constraint. The output Q of the sender settles at time $t_{cq}$ at the latest. From there the signal passes through the combinational logic, so the input D of the receiver settles at $t_{cq} + t_{pd}$ at the latest. On the other hand, allowing for the worst case of skew, the next clock edge reaches the receiver as early as $T - t_{skew}$. Since D must have settled at least $t_{su}$ before that edge, we need

$$t_{cq} + t_{pd} \le T - t_{skew} - t_{su}$$

and rearranging gives the first inequality. Conversely, if the first inequality holds then the above inequality holds and the condition is met.

Hold constraint. At the very same edge at time $0$, the sender begins to emit its new value. That value begins to reach the receiver’s D input at $t_{ccq} + t_{cd}$ at the earliest. For the receiver, allowing for the worst case of skew, this edge arrives at time $t_{skew}$ at the latest. The receiver requires D not to change for $t_{h}$ after its own edge, so

$$t_{ccq} + t_{cd} \ge t_{skew} + t_{h}$$

is necessary, which is the second inequality. Note that $T$ does not appear in it. Lengthening the period does not alter the fact that a new value comes rushing in right after the edge. A hold violation can only be repaired by inserting buffers into the path so as to increase $t_{cd}$.

∎

Example 5.3（Putting a number on the frequency）

Take $t_{cq} = 40\ \mathrm{ps}$, $t_{ccq} = 25\ \mathrm{ps}$, $t_{su} = 25\ \mathrm{ps}$, $t_{h} = 30\ \mathrm{ps}$, $t_{skew} = 20\ \mathrm{ps}$, and combinational logic with $t_{pd} = 310\ \mathrm{ps}$ and $t_{cd} = 15\ \mathrm{ps}$. By Proposition 5.2,

$$T \ge 40 + 310 + 25 + 20 = 395\ \mathrm{ps}, \qquad f \le \frac{1}{395 \times 10^{-12}\ \mathrm{s}} \approx 2.53\ \mathrm{GHz}$$

The hold constraint reads $25 + 15 = 40 \ge 30 + 20 = 50$, which is false, so it is not satisfied. No matter how slowly this circuit is clocked, it will not work. Buffers must be inserted into the shortest path to bring $t_{cd}$ up to at least $25\ \mathrm{ps}$.

Furthermore, if this combinational logic is split into two stages of equal delay with a flip-flop in between, then $t_{pd} = 155\ \mathrm{ps}$ and

$$T \ge 40 + 155 + 25 + 20 = 240\ \mathrm{ps}, \qquad f \le 4.17\ \mathrm{GHz}$$

a frequency 1.65 times higher. This is the principle of pipelining, taken up again in Proposition 7.2.

6. The five functional units and the von Neumann architecture

The parts are assembled. We now move to the machine as a whole. In the classical classification, a computer consists of the following five functional units.

Unit	Role	Modern realisation
Control unit	Fetches and decodes instructions and sends control signals to the other units	Instruction decoder, control unit
Arithmetic unit	Performs arithmetic and logical operations	ALU, multiplier, floating-point unit
Memory unit	Holds instructions and data	Registers, cache, main memory (DRAM), SSD
Input unit	Brings information in from the outside world	Keyboard, sensors, network reception
Output unit	Sends information out to the outside world	Display, network transmission

The control unit and the arithmetic unit together make up the CPU (central processing unit). In terms of the parts built in Sections 3 to 5, the arithmetic unit is a combinational circuit like the adder of Section 4, and registers, the fastest layer of the memory unit, are the rows of flip-flops of Section 5.

flowchart LR
IN["Input unit"] --> MEM["Memory unit"]
MEM --> OUT["Output unit"]
MEM <-->|"data"| ALU["Arithmetic unit"]
MEM -->|"instructions"| CU["Control unit"]
CU -.->|"control signals"| ALU
CU -.->|"control signals"| MEM

The five functional units and the flow of information. Solid lines denote the flow of data and instructions; dashed lines denote the control signals emitted by the control unit.

What is decisive in this diagram is that there is only one box for memory. Instructions and data alike are placed in the same memory, as the same kind of bit string.

Definition 6.1（The stored-program principle (von Neumann architecture)）

A machine is said to follow the stored-program principle if it holds the sequence of instructions to be executed inside the same rewritable memory as the data, in the same format (a bit string), and reads them out one after another according to a register holding the address of the next instruction (the program counter), decoding and executing each in turn. A design based on this principle is called a von Neumann architecture.

From the single decision to put instructions in the same place as data, all of the following consequences follow.

• Programs can be treated as data. Compilers, linkers, loaders, virtual machines and JIT compilers are all “programs that take programs as input and produce programs as output”. This picture works only because an instruction is nothing but a bit string in memory. The same story, seen from the side of language implementations, is taken up in Programming Language Theory (translators and interpreters（Definition 3.1）［Programming Language Theory］).
• The distinction between instruction and data is only a matter of interpretation. Whether the bit string at a given address is an instruction or data is nothing but the difference between the CPU pointing at it with the program counter and reading it with a load instruction. A buffer overflow attack is the operation of getting a bit string written as data to be executed as an instruction; it is the flip side of this design. Modern operating systems and CPUs prevent it by withholding execute permission at page granularity (address translation by paging（Definition 5.1）［What an Operating System Does］). See The Role of the Operating System for details.
• The channel to memory becomes narrow. Since instructions and data travel the same route, the bandwidth of that route determines the overall speed no matter how fast the CPU becomes. John Backus called this the von Neumann bottleneck in his 1978 Turing Award lecture.

The remedy for the third point is the memory hierarchy and caching. Common measures are separating the caches for instructions and for data (making the inside of the CPU Harvard-style, as it is often put) and multi-level caches that exploit locality of reference. The average memory access time AMAT can be estimated as

$$\text{AMAT} = t_{\text{hit}} + (\text{miss rate}) \times (\text{miss penalty})$$

With a hit time of 1 cycle, a miss rate of 3 % and a miss penalty of 100 cycles, this is $1 + 0.03 \times 100 = 4$ cycles. Merely raising the miss rate from 3 % to 6 % gives 7 cycles, a factor of 1.75. CPU performance so often hinges on the memory access pattern of an algorithm because the coefficient in the second term of this formula is large. An estimate of the same shape applies to the cache that accelerates address translation (the TLB) as well (why the TLB works, in numbers（Example 5.6）［What an Operating System Does］).

Tip

The name “von Neumann architecture” comes from the author line of the EDVAC draft, but the idea of the stored program was also a collective achievement of the EDVAC project, including J. Presper Eckert and John Mauchly, and its attribution is a matter of historical debate. The term is well established, so we use it as it stands in this article.

7. Inside the CPU: datapath and control

Opening up a CPU, we find broadly the following parts.

• Register file: a few dozen fast storage cells. In RV32I there are 32 registers of 32 bits. It is the row of flip-flops of Section 5 with address decoders for reading and writing attached.
• ALU (arithmetic logic unit): a combinational circuit performing addition and subtraction, AND, OR, XOR, shifts and comparisons. At its heart is the adder of Section 4.
• Program counter (PC): the register holding the address of the next instruction to execute.
• Control unit: the circuit that decodes the bit string of an instruction and generates the signals directing register-file reads and writes, the ALU operation, whether memory is accessed, and so on. By Theorem 2.3 this too can be realised as a family of Boolean functions taking the instruction bits as input.

The routes connecting these parts are called the datapath, and the control signals are what switch the multiplexers along those routes. It is standard to think of the execution of an instruction as divided into the following five stages.

Example 7.1（One add instruction, from start to finish）

Suppose the PC points at 0x00001000, that the machine word 0x007302B3 for add x5, x6, x7 is stored there, and that register x6 holds 12 and x7 holds 30.

1. Instruction fetch (IF): the control unit presents the address 0x00001000 to instruction memory and reads out 0x007302B3. At the same time an adder computes PC + 4 = 0x00001004.
2. Decode and register read (ID): from the low 7 bits 0110011 we learn that this is an R-format arithmetic instruction, and from funct3 = 000 and funct7 = 0000000 that the operation is addition. The control unit raises the signals “ALU does addition”, “second operand is a register (not an immediate)”, “register write enabled” and “no memory access”. In parallel, rs1 = 6 and rs2 = 7 in the instruction cause the two read ports of the register file to deliver 12 and 30.
3. Execute (EX): the ALU computes $12 + 30 = 42$. What is at work here is the adder of Theorem 4.2 and Proposition 4.4.
4. Memory access (MEM): this instruction does nothing here. A load or store instruction would touch data memory at this stage.
5. Write back (WB): 42 is written to rd = 5, that is, to x5. At the same time 0x00001004 is written to the PC, and at the next clock edge the machine moves on to the next instruction.

A design in which all of this finishes in one clock cycle is called single-cycle. In that case $t_{pd}$ in Proposition 5.2 is the delay through all five stages above, so the clock becomes slow.

Proposition 7.2（Speedup from pipelining）

Let $T_{\text{logic}}$ be the total combinational delay needed to process one instruction, and suppose it is split into $k \ge 2$ stages of equal delay with registers inserted in between. Write $t_r$ for the overhead of one register stage ($t_{cq} + t_{su} + t_{skew}$ in Proposition 5.2). Assuming there are no stalls whatsoever due to data dependences or branches, the time to process $n$ instructions is

$$T_{\text{seq}}(n) = n\,(T_{\text{logic}} + t_r), \qquad T_{\text{pipe}}(n) = (n + k - 1)\left(\frac{T_{\text{logic}}}{k} + t_r\right)$$

and as $n \to \infty$ the speedup ratio converges to

$$S(k) = \frac{T_{\text{logic}} + t_r}{\dfrac{T_{\text{logic}}}{k} + t_r} = \frac{k\,(T_{\text{logic}} + t_r)}{T_{\text{logic}} + k\,t_r} \; < \; k$$

In particular, as long as $t_r > 0$, increasing the number of stages $k$ never attains a speedup of $k$.

Proof（Proposition 7.2）

Without splitting, the clock period must be at least $T_{\text{logic}} + t_r$ by Proposition 5.2, and one instruction takes one cycle, so $n$ instructions take $T_{\text{seq}}(n) = n(T_{\text{logic}} + t_r)$.

Splitting into $k$ stages, the logic delay of each stage is $T_{\text{logic}}/k$, so the period becomes $T_{\text{logic}}/k + t_r$. The first instruction leaves the last stage in cycle $k$, and thereafter, under the assumption of no stalls, one instruction completes every cycle, so $n$ instructions take $k + (n-1) = n + k - 1$ cycles. Hence $T_{\text{pipe}}(n)$ is as claimed.

The speedup ratio is

$$\frac{T_{\text{seq}}(n)}{T_{\text{pipe}}(n)} = \frac{n}{n+k-1} \cdot \frac{T_{\text{logic}} + t_r}{T_{\text{logic}}/k + t_r}$$

and as $n \to \infty$ the first factor converges to $1$. Multiplying numerator and denominator of the second factor by $k$ gives $S(k) = k(T_{\text{logic}} + t_r) / (T_{\text{logic}} + k t_r)$. Taking its ratio to $k$,

$$\frac{S(k)}{k} = \frac{T_{\text{logic}} + t_r}{T_{\text{logic}} + k t_r}$$

and for $k \ge 2$ with $t_r > 0$ the denominator is the larger, so $S(k) < k$.

∎

For instance, with $T_{\text{logic}} = 800\ \mathrm{ps}$, $t_r = 50\ \mathrm{ps}$ and $k = 5$, the period drops from $850\ \mathrm{ps}$ to $160 + 50 = 210\ \mathrm{ps}$, giving $S(5) = 850/210 \approx 4.05$. The ideal factor of 5 is out of reach. And in practice stalls do occur, because an instruction may use the result of the one just before it, or because the branch target is not known until it is resolved. The deeper the pipeline the larger these losses, which is why pipelines deeper than about 20 stages were reconsidered in the 2000s.

8. The instruction set architecture and RISC-V

In Section 7 we simply asserted that the machine word 0x007302B3 is an add instruction. That correspondence table is precisely the contract placed at the boundary between hardware and software.

Definition 8.1（Instruction set architecture (ISA)）

The instruction set architecture (ISA) is the whole of the machine’s specification as observable from a program, namely (a) the set of instructions and their encoding into bit strings, (b) the number, width and roles of the registers, (c) the address space and the appearance of memory (alignment, byte order, ordering as seen from several agents of execution), (d) the treatment of exceptions and interrupts, and (e) the privilege levels. The same ISA can be implemented by several different circuits differing in pipeline depth and cache organisation. The manner of implementation is called the microarchitecture.

To say that an ISA is a contract means the following. A compiler emits code looking only at this contract, and a CPU designer may adopt any internal structure whatsoever so long as the contract is honoured. It is because of this separation that a binary written 20 years ago still runs on today’s CPUs.

RISC-V is an ISA that publishes this contract in a form anyone may freely implement and extend. The skeleton of the base integer instruction set RV32I is as follows.

• 32 registers of 32 bits (x0 through x31). x0 is hardwired to $0$, so writing to it changes nothing.
• Instructions are a fixed 32 bits long. There are only six instruction formats: R, I, S, B, U and J.
• Only load and store instructions touch memory; arithmetic is performed between registers (or between a register and an immediate). This is the load-store style.
• There are only about forty base integer instructions. Multiplication and division are separated out into the M extension, atomic operations into the A extension, single- and double-precision floating point into the F and D extensions, and 16-bit compressed instructions into the C extension.

The single fact that x0 is always $0$ does a great deal of work in reducing the number of instructions. addi x5, x0, 7 becomes “put 7 into x5”, add x0, x0, x0 becomes an instruction that does nothing (a NOP), and beq x6, x0, L becomes “branch if x6 is 0”. No dedicated instructions are needed for any of these.

Example 8.2（Encoding add x5, x6, x7 into 32 bits）

An R-format instruction consists, from the high bits down, of funct7 (7 bits), rs2 (5 bits), rs1 (5 bits), funct3 (3 bits), rd (5 bits) and opcode (7 bits). For add the specification fixes opcode = 0110011, funct3 = 000 and funct7 = 0000000. The register numbers are rd = 5, rs1 = 6, rs2 = 7, that is, 00101, 00110 and 00111. Laying them out:

funct7	rs2	rs1	funct3	rd	opcode
0000000	00111	00110	000	00101	0110011

Written out in a row this is 00000000011100110000001010110011. Grouping into nibbles gives 0000 0000 0111 0011 0000 0010 1011 0011, which in hexadecimal is 0x007302B3. This is the bit string the CPU read in Example 7.1. The same procedure carried out for the I-format instruction addi can be found in encoding the addi instruction（Example 2.1）［Programming Language Theory］.

The reading can also be run backwards. The rule “if the low 7 bits are 0110011 it is an R-format integer operation, and the pair funct3, funct7 determines which operation” is, seen from the hardware side, precisely the truth table of the control unit.

RISC-V came into wide use for reasons that are not only technical simplicity. Since using the specification requires neither licence fees nor permission, students can design an entire CPU in a university course, researchers can try out their own extensions, and companies can spin up application-specific processors. The property of an ISA being a “contract” works best when the contract is published.

The layer above the instructions, that is, how this contract is used to build processes (Definition 3.1［What an Operating System Does］), virtual memory and privilege modes (Definition 2.1［What an Operating System Does］), is treated in The Role of the Operating System, and the machinery that translates a high-level language down to the contract is treated in Programming Language Theory.

9. Exercises

Exercise 9.1Easy

Define $x \downarrow y = \lnot(x \lor y)$ (NOR). Express $\lnot x$, $x \lor y$ and $x \land y$ using NOR alone, and thereby show that NOR is functionally complete.

Solution

$\lnot x = x \downarrow x$. Indeed $x \lor x = x$, so $x \downarrow x = \lnot x$.

$x \lor y = \lnot(x \downarrow y) = (x \downarrow y) \downarrow (x \downarrow y)$. The first equality follows from $\lnot\lnot(x \lor y) = x \lor y$, and the second applies the construction of $\lnot$ from the previous paragraph to $x \downarrow y$.

$x \land y = (x \downarrow x) \downarrow (y \downarrow y)$. The right-hand side is $\lnot x \downarrow \lnot y = \lnot(\lnot x \lor \lnot y)$, which by De Morgan’s law equals $x \land y$.

Since $\land, \lor, \lnot$ can all be written with NOR, combining this with Theorem 2.3 shows that every Boolean function can be expressed using NOR alone. The line of argument is the same as in Corollary 2.4, only dualised.

Exercise 9.2Standard

Answer the following about 8-bit two’s complement representation. (1) Find the bit string for $-45$. (2) Compute $67 + (-45)$ with an 8-bit adder and determine $c_8$ and $c_7$ in the notation of Theorem 4.2. (3) Confirm, using this example and the example $100 + 100$, that overflow of signed addition can be detected by $c_n \oplus c_{n-1} = 1$.

Solution

(1) $45 = 00101101_2$. Inverting every bit gives $11010010_2$, and adding $1$ gives $11010011_2$ (0xD3 in hexadecimal) as the representation of $-45$. As a check, read as unsigned this is $211 = 256 - 45$, which is correct.

(2) $67 = 01000011_2$. We follow the carries from the least significant end.

$i$	$a_i$ (67)	$b_i$ ($-45$)	$c_i$	sum	$s_i$	$c_{i+1}$
0	1	1	0	2	0	1
1	1	1	1	3	1	1
2	0	0	1	1	1	0
3	0	0	0	0	0	0
4	0	1	0	1	1	0
5	0	0	0	0	0	0
6	1	1	0	2	0	1
7	0	1	1	2	0	1

The result is $s = 00010110_2 = 22$, matching $67 - 45 = 22$. We have $c_8 = 1$ and $c_7 = 1$.

(3) In this example $c_8 \oplus c_7 = 1 \oplus 1 = 0$, so no overflow is signalled, and indeed the answer is the correct value. Read as unsigned, $c_8 = 1$ is a carry out of range, but in the signed reading the carry into the most significant bit and the carry out of it cancel, so there is no problem.

Next take $100 + 100$. Since $100 = 01100100_2$, following from the bottom: a carry is generated at $i=2$ from $1+1$; at digit $i=5$ we get $1+1+0 = 2$, so $s_5 = 0$ and $c_6 = 1$; at $i=6$ we get $1+1+1 = 3$, so $s_6 = 1$ and $c_7 = 1$; at $i=7$ we get $0+0+1$, so $s_7 = 1$ and $c_8 = 0$. The result is $11001000_2$, which read as 8-bit two’s complement is $-56$. The test gives $c_8 \oplus c_7 = 0 \oplus 1 = 1$, correctly detecting the overflow.

In general, $c_n \oplus c_{n-1} = 1$ means that the carry into the most significant bit and the carry out of it disagree. If those two agree, the carry into the top position is correctly cancelled against the weight $-2^{n-1}$ of the sign bit, and the result stays within the representable range.

Exercise 9.3Standard

For a certain pipeline stage, take $t_{cq} = 35\ \mathrm{ps}$, $t_{ccq} = 20\ \mathrm{ps}$, $t_{su} = 30\ \mathrm{ps}$, $t_{h} = 40\ \mathrm{ps}$ and $t_{skew} = 15\ \mathrm{ps}$, with the delay of the combinational logic ranging from $t_{cd} = 10\ \mathrm{ps}$ to $t_{pd} = 420\ \mathrm{ps}$. (1) Find the maximum operating frequency. (2) Determine whether the hold constraint is satisfied, and if not, state what must be done about it. (3) If the combinational logic of this stage is split into two stages of equal delay, by what factor does the frequency increase?

Solution

(1) By the setup constraint of Proposition 5.2,

$$T \ge 35 + 420 + 30 + 15 = 500\ \mathrm{ps}$$

so $f \le 1/(500 \times 10^{-12}\ \mathrm{s}) = 2.0\ \mathrm{GHz}$.

(2) The hold constraint is $t_{ccq} + t_{cd} \ge t_h + t_{skew}$, that is, $20 + 10 = 30 \ge 40 + 15 = 55$. This is false, so the constraint is not satisfied. The shortfall is $25\ \mathrm{ps}$, so buffers of delay at least $25\ \mathrm{ps}$ must be inserted into the shortest path to make $t_{cd} \ge 35\ \mathrm{ps}$. As Proposition 5.2 states, $T$ does not appear in the hold constraint, so slowing the clock does not help.

(3) After splitting, $t_{pd} = 210\ \mathrm{ps}$, so

$$T \ge 35 + 210 + 30 + 15 = 290\ \mathrm{ps}, \qquad f \le 3.45\ \mathrm{GHz}$$

The factor is $500/290 \approx 1.72$, short of 2. The reason is that an overhead of $t_{cq} + t_{su} + t_{skew} = 80\ \mathrm{ps}$ is unavoidably added per stage, and this is exactly what lies behind $S(k) < k$ in Proposition 7.2.

Exercise 9.4Hard

An I-format RISC-V instruction consists, from the high bits down, of imm (12 bits, signed), rs1 (5 bits), funct3 (3 bits), rd (5 bits) and opcode (7 bits). For addi, opcode = 0010011 and funct3 = 000. (1) Encode addi x5, x6, -1 into 32 bits. (2) In RV32I the I-format immediate is limited to 12 bits. Explain how to place an arbitrary 32-bit constant into a register, using the U-format instruction lui (which places the upper 20 bits of the immediate into the upper 20 bits of the register and sets the lower 12 bits to $0$).

Solution

(1) The 12-bit two’s complement representation of $-1$ is 111111111111. Since rs1 = 6 is 00110 and rd = 5 is 00101, laying them out:

imm	rs1	funct3	rd	opcode
111111111111	00110	000	00101	0010011

Written out in a row this is 11111111111100110000001010010011. Grouping into nibbles gives 1111 1111 1111 0011 0000 0010 1001 0011, which in hexadecimal is 0xFFF30293.

(2) Let $C$ be the desired constant. Place the upper 20 bits with lui x5, hi and then add the lower 12 bits with addi x5, x5, lo. However, the immediate of addi is signed, so when the value of the low 12 bits, $\ell = C \bmod 2^{12}$, is at least $2^{11}$, the addi adds the negative value $\ell - 2^{12}$ instead. We therefore correct for this by carrying a $1$ into the upper part in advance:

$$\text{hi} = \left\lfloor \frac{C + 2^{11}}{2^{12}} \right\rfloor \bmod 2^{20}, \qquad \text{lo} = \bigl((C + 2^{11}) \bmod 2^{12}\bigr) - 2^{11}$$

For example, if $C = \mathtt{0x12345678}$ the low 12 bits are 0x678, which is below $2^{11} = \mathtt{0x800}$, so no correction is needed and the two instructions are lui x5, 0x12345 and addi x5, x5, 0x678. If on the other hand $C = \mathtt{0x12345FFF}$, the low 12 bits are 0xFFF ($-1$ as a signed value), so we use lui x5, 0x12346 and addi x5, x5, -1. The assembler’s pseudo-instruction li (load immediate) performs this test automatically.

References

• David A. Patterson, John L. Hennessy, Computer Organization and Design: The Hardware/Software Interface, RISC-V Edition, 2nd ed., Morgan Kaufmann, 2020 — Chapter 1 (performance), Chapter 2 (RISC-V instructions), Chapter 4 (datapath and pipelining), Chapter 5 (the memory hierarchy).
• Sarah L. Harris, David Money Harris, Digital Design and Computer Architecture, RISC-V Edition, Morgan Kaufmann, 2021 — Chapters 1–3 (Boolean algebra, CMOS, sequential circuits and timing), Chapter 5 (adders), Chapter 7 (microarchitecture).
• Noam Nisan, Shimon Schocken, The Elements of Computing Systems: Building a Modern Computer from First Principles, 2nd ed., MIT Press, 2021 — Chapters 1–5. A workbook that actually builds everything from NAND up to a CPU.
• John von Neumann, “First Draft of a Report on the EDVAC” (1945). Reprinted in IEEE Annals of the History of Computing 15(4) (1993), 27–75. DOI: 10.1109/85.238389
• John Backus, “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs”, Communications of the ACM 21(8) (1978), 613–641. DOI: 10.1145/359576.359579 — the source of the phrase “von Neumann bottleneck”.
• Andrew Waterman, Krste Asanović (eds.), The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA — published at riscv.org/technical/specifications/. The primary source for the instruction formats and their encoding.