コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで

0. この記事の要点

• コンピュータの本体は「スイッチの網」です。トランジスタ 2 個で NOT が、4 個で NAND ができ、NAND だけであらゆる論理関数を組み立てられます（系 2.4）。
• $n$ 変数のブール関数は $2^{2^n}$ 個しかなく、そのすべてが加法標準形で書けます（定理 2.3）。ハードウェアが「何を計算できるか」は、この有限性の上に乗っています。
• 加算器は具体的なブール関数の実装です。正しさは桁上げに関する帰納法で証明でき（定理 4.2）、速さは回路の深さで決まります（命題 4.4）。
• クロックとフリップフロップが「時間」を作ります。動作周波数の上限はセットアップ制約 $T \ge t_{cq} + t_{pd} + t_{su} + t_{skew}$ から出ます（命題 5.2）。
• フォン・ノイマン型アーキテクチャは「命令もデータも同じ記憶装置に、同じビット列として置く」という設計判断です。汎用性と引き換えに、記憶装置との細い通路がボトルネックになります。
• 命令セットアーキテクチャ（ISA）はハードウェアとソフトウェアの契約です。RISC-V はその契約を誰でも実装できる形で公開したもので、add x5, x6, x7 は 32 ビットの 0x007302B3 に符号化されます（例 8.2）。

1. 動機：配線を組み替える計算機から、プログラムを読む計算機へ

1946 年に公開された ENIAC は、当時としては桁違いに速い計算機でした。しかし、計算の内容を変えるには数千本のケーブルとスイッチを人手で差し替える必要があり、その作業に数日かかりました。計算そのものは秒で終わるのに、計算の指定に数日かかる。この非対称性が、次の設計の出発点になります。

1945 年、ジョン・フォン・ノイマンの名前で回覧された EDVAC の草稿は、この問題に一つの答えを与えました。命令もまた数である、だから命令をデータと同じ記憶装置に置き、計算機自身に読み出させればよい、という答えです。配線の組み替えは、記憶装置の書き換えに置き換わりました。これが記憶プログラム方式であり、今日のほぼすべてのコンピュータの基本設計です。

ここで素朴な疑問が立ちます。なぜ砂（シリコン）の塊が計算をするのでしょうか。 石は考えません。しかし石で作ったスイッチは、電圧の高低という 2 つの状態を区別できます。区別できる 2 状態があれば真偽が表せ、真偽が表せれば論理関数が表せ、論理関数が表せれば算術が表せます。そこに「前の値を覚える」仕組みと「今が何番目の手順か」を刻む時計を加えると、静的な回路が時間の中で動く計算過程になります。

この記事はその積み上げを、下から順に一段ずつ追います。

1. スイッチ（トランジスタ）から論理ゲートへ（定理 2.3、第 3 節）
2. 論理ゲートから算術（加算器）へ（第 4 節）
3. 組合せ回路から記憶とクロックへ（第 5 節）
4. 五大装置とフォン・ノイマン型アーキテクチャ（第 6 節）
5. CPU の内部構造と命令の実行（第 7 節）
6. ハードウェアとソフトウェアの契約としての ISA と RISC-V（第 8 節）

2. 準備：ブール関数とスイッチの言葉

回路の話をする前に、回路が実現しようとしている対象を数学の言葉で押さえます。

定義 2.1（ブール関数）

$\{0,1\}$ 上の $n$ 変数ブール関数とは、写像 $f : \{0,1\}^n \to \{0,1\}$ のことをいいます。$\{0,1\}$ 上の演算として

$$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、OR、NOT、XOR と呼びます。

回路の設計とは、実現したいブール関数を、これらの基本演算の合成として書き下すことにほかなりません。まず、対象がどれくらいあるのかを数えておきます。

命題 2.2（ブール関数の個数）

$n \ge 1$ とするとき、$n$ 変数ブール関数 $f : \{0,1\}^n \to \{0,1\}$ の総数はちょうど $2^{2^n}$ 個です。

証明（命題 2.2）

$f$ を決めることは、定義域 $\{0,1\}^n$ の各元に対して値 $0$ か $1$ を割り当てることと同じです。定義域の元の個数は、各成分が 2 通りで $n$ 成分あるので $2^n$ 個です。各元への値の割り当ては互いに独立で、それぞれ 2 通りあります。したがって割り当ての総数は $2$ を $2^n$ 回掛けたもの、すなわち $2^{2^n}$ です。

∎

具体的には $n=1$ で 4 個、$n=2$ で 16 個、$n=3$ で 256 個、$n=4$ で 65536 個、$n=5$ で約 43 億個です。$n$ について二重指数で増えるので、$n$ が大きい関数を真理値表で扱うことはできません。だからこそ、関数を式として構成する方法が要ります。次の定理がそれを与えます。

定理 2.3（加法標準形と AND・OR・NOT の完全性）

$n \ge 1$ とし、$f : \{0,1\}^n \to \{0,1\}$ を任意のブール関数とします。このとき $f$ は、変数 $x_1, \ldots, x_n$ と演算 $\land, \lor, \lnot$ のみを用いた式で表せます。具体的には、$a = (a_1,\ldots,a_n) \in \{0,1\}^n$ に対し

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

と定めると、$f$ が恒等的に $0$ でない場合には

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

が成り立ちます。$f$ が恒等的に $0$ の場合は $f = x_1 \land \lnot x_1$ と表せます。

証明（定理 2.3）

まず $m_a$ の性質を確かめます。

（i）$m_a(a) = 1$ であること。第 $i$ 因子は $a_i^{a_i}$ です。$a_i = 1$ なら因子は $a_i = 1$、$a_i = 0$ なら因子は $\lnot a_i = 1$ で、いずれの場合も $1$ です。すべての因子が $1$ なので AND も $1$ です。

（ii）$x \ne a$ ならば $m_a(x) = 0$ であること。$x \ne a$ なので $x_i \ne a_i$ となる添字 $i$ が存在します。$a_i = 1$ なら $x_i = 0$ で第 $i$ 因子は $x_i = 0$、$a_i = 0$ なら $x_i = 1$ で第 $i$ 因子は $\lnot x_i = 0$ です。因子が一つでも $0$ なら AND は $0$ です。

次に $f$ が恒等的に $0$ でないとし、右辺を $g(x) = \bigvee_{a \in f^{-1}(1)} m_a(x)$ とおきます（$f^{-1}(1) \ne \emptyset$ なので、これは空でない OR です）。任意の $x \in \{0,1\}^n$ について次が成り立ちます。

• $f(x) = 1$ のとき、$x \in f^{-1}(1)$ なので $a = x$ が OR の項に現れ、（i）より $m_x(x) = 1$ です。OR は項が一つでも $1$ なら $1$ なので $g(x) = 1$ です。
• $f(x) = 0$ のとき、OR に現れるどの $a$ も $a \in f^{-1}(1)$ すなわち $a \ne x$ を満たすので、（ii）よりすべての項が $0$ です。よって $g(x) = 0$ です。

したがって $f$ と $g$ はすべての入力で一致し、$f = g$ です。$g$ は変数と $\land, \lor, \lnot$ だけで書かれています。

最後に $f$ が恒等的に $0$ の場合、$x_1 \land \lnot x_1$ は $x_1 = 0$ でも $x_1 = 1$ でも $0$ なので、これが $f$ を表します。

∎

この定理は「どんな入出力表も回路で実現できる」ことを保証します。しかも構成的なので、真理値表を書けば式が機械的に出ます。ただし実際のシリコン上では、AND・OR・NOT を直接作るより、次の系が示す一種類のゲートだけで済ませるほうが安上がりです。

系 2.4（NAND の関数完全性）

$x \barwedge y = \lnot(x \land y)$（NAND）と定めます。任意のブール関数 $f : \{0,1\}^n \to \{0,1\}$ は、変数と NAND のみを用いた式で表せます。

証明（系 2.4）

定理 2.3 により $f$ は $\land, \lor, \lnot$ の式で書けるので、この 3 つを NAND だけで作れば十分です。

• $\lnot x = \lnot(x \land x) = x \barwedge x$。実際 $x \land x = x$ なので両辺は一致します。
• $x \land y = \lnot(x \barwedge y) = (x \barwedge y) \barwedge (x \barwedge y)$。前の行の $\lnot$ の作り方を $x \barwedge y$ に適用しました。
• $x \lor y = (x \barwedge x) \barwedge (y \barwedge y)$。右辺は $\lnot(\lnot x \land \lnot y)$ であり、ド・モルガンの法則によりこれは $x \lor y$ に等しいです。

以上の 3 つの置き換えを $f$ の式に再帰的に適用すれば、NAND のみの式が得られます。

∎

例 2.5（3 変数多数決関数を式にする）

$x_1, x_2, x_3$ のうち $1$ が 2 個以上のとき $1$ を返す関数 $M$ を作ります。真理値表で $M = 1$ となる入力は $(0,1,1), (1,0,1), (1,1,0), (1,1,1)$ の 4 つです。定理 2.3 の構成をそのまま書くと

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

です。これは 3 入力 AND が 4 個、4 入力 OR が 1 個、NOT が 3 個で計 8 ゲートです。ここから簡約します。$a \lor a = a$ より最後の項 $x_1 \land x_2 \land x_3$ は 3 回使ってよいので、

$$\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}$$

と書き直せます。各行で $x \lor \lnot x = 1$ を使うと、1 行目は $(\lnot x_1 \lor x_1) \land x_2 \land x_3 = x_2 \land x_3$、2 行目は $x_1 \land x_3$、3 行目は $x_1 \land x_2$ になります。したがって

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

で、2 入力 AND が 3 個、3 入力 OR が 1 個の計 4 ゲートに減りました。同じ関数でも式の書き方でゲート数が倍半分変わります。これが論理合成という工程の仕事です。

3. トランジスタ：物理現象を論理にする

前節の $\land, \lor, \lnot$ を物理で実現します。現代の主役は MOSFET（金属酸化膜半導体電界効果トランジスタ）です。構造としては、シリコンの表面に薄い絶縁膜を挟んで金属（あるいは多結晶シリコン）の電極を載せた、要するに小さなコンデンサです。この電極（ゲート）に電圧をかけると、絶縁膜の下のシリコン表面に電荷が呼び寄せられ、両脇の 2 つの端子（ソースとドレイン）の間が導通します。電圧が導通を制御する。これがスイッチです。

論理設計では、この素子を理想化した次のモデルで扱えば足ります。

• nMOS：ゲート電圧が高い（論理 $1$）とき導通し、低い（論理 $0$）とき遮断する。
• pMOS：ゲート電圧が低いとき導通し、高いとき遮断する。振る舞いが nMOS と相補的です。

この 2 種類を組み合わせて、電源 $V_{DD}$ 側に pMOS の網（プルアップ網）、接地側に nMOS の網（プルダウン網）を置き、どんな入力に対してもどちらか一方だけが導通するように作るのが CMOS 論理です。最小の例が NOT ゲートです。

CMOS インバータ（NOT ゲート）。入力 A が 0 のとき上の pMOS だけが導通して出力 Y は電源電圧に、A が 1 のとき下の nMOS だけが導通して Y は接地電位になる。定常状態では電源から接地へ電流が流れる経路が存在しない。

入力 $A = 0$ なら pMOS が導通・nMOS が遮断で、出力 $Y$ は電源につながって $1$ になります。$A = 1$ なら逆で、$Y$ は接地につながって $0$ になります。すなわち $Y = \lnot A$ で、トランジスタ 2 個で NOT ができました。同じ考え方で、nMOS を 2 個直列・pMOS を 2 個並列にすると 4 個で NAND が、直並列を入れ替えると 4 個で NOR ができます。AND を作るには NAND の後ろに NOT を足して 6 個必要です。CMOS では出力が必ず反転する側が安上がりになるので、系 2.4 の NAND や NOR が実装の基本単位になります。

この構造から、消費電力についての基本則が導けます。

命題 3.1（CMOS の消費エネルギー）

出力に容量 $C$ がぶら下がった CMOS ゲートを考えます。プルアップ網とプルダウン網が同時に導通することはなく、トランジスタの漏れ電流は無視できるものとします。このとき、

1. 出力が変化していない定常状態では、電源から接地へ流れる電流は $0$ であり、消費電力も $0$ です。
2. 出力が $0 \to 1 \to 0$ と 1 往復するたびに、電源から取り出されて熱になるエネルギーはちょうど $C V_{DD}^2$ であり、その値は導通経路の抵抗値によりません。
3. クロック周波数 $f$ のもとで、1 クロックあたり平均 $\alpha$ 回の $0 \to 1$ 遷移が起きるなら、平均消費電力は $P = \alpha \, C \, V_{DD}^2 \, f$ です。

証明（命題 3.1）

（1）定常状態では、仮定によりプルアップ網とプルダウン網のどちらか一方だけが導通しています。したがって電源から接地までを結ぶ導通経路が存在せず、電流は流れません。電力は電圧と電流の積なので $0$ です。

（2）まず $0 \to 1$ の充電を考えます。容量が $0$ から $V_{DD}$ まで充電されるとき、電源が送り出す電荷は $Q = C V_{DD}$ です。電源の電圧は一定 $V_{DD}$ なので、電源が供給するエネルギーは

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

です。一方、容量に蓄えられるエネルギーは

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

なので、差の $\tfrac{1}{2} C V_{DD}^2$ が pMOS の導通抵抗で熱になります。ここで抵抗値 $R$ はどこにも現れていないことに注意してください。次に $1 \to 0$ の放電では、容量に蓄えられていた $\tfrac{1}{2} C V_{DD}^2$ がすべて nMOS の導通抵抗で熱になり、電源はエネルギーを供給しません。往復の合計は $\tfrac{1}{2} C V_{DD}^2 + \tfrac{1}{2} C V_{DD}^2 = C V_{DD}^2$ です。

（3）1 秒あたりのクロック数は $f$、1 クロックあたりの $0 \to 1$ 遷移が平均 $\alpha$ 回なので、1 秒あたりの往復回数は $\alpha f$ です。（2）より 1 往復が $C V_{DD}^2$ なので、単位時間あたりのエネルギー、すなわち電力は $P = \alpha C V_{DD}^2 f$ です。

∎

$V_{DD}$ が二乗で効くという点が、この式のいちばん大事なところです。

例 3.2（電源電圧を下げると何が起きるか）

$10^9$ 個の信号線をもつチップを考えます。各線の容量を $C = 2\ \mathrm{fF} = 2 \times 10^{-15}\ \mathrm{F}$、動作周波数を $f = 3\ \mathrm{GHz}$、1 クロックあたりの平均遷移率を $\alpha = 0.01$、電源電圧を $V_{DD} = 1.0\ \mathrm{V}$ とします。命題 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}$$

です。ここで電源電圧だけを $1.8\ \mathrm{V}$ に上げると、$P$ は $(1.8/1.0)^2 = 3.24$ 倍になり $194\ \mathrm{W}$ になります。空冷で捨てられる熱の上限が 100 W 程度であることを考えると、この差は決定的です。半導体の微細化とともに電源電圧が 5 V から 1 V 付近まで下げられてきたのは、この二乗則が理由です。

注意 3.3（なぜ 2 進数なのか）

10 種類の電圧レベルを使えば 1 本の線で 1 桁の 10 進数が送れます。それでも 2 値を使うのは、雑音に対する余裕（ノイズマージン）のためです。電源電圧 $1\ \mathrm{V}$ で 10 レベルなら区別すべき間隔は約 $0.1\ \mathrm{V}$ ですが、2 値なら約 $1\ \mathrm{V}$ です。しかも 命題 3.1（1）が示すとおり、CMOS が電力をほとんど使わないのは出力が電源電圧か接地電位に振り切っているときだけで、中間電圧はそのままエネルギー損失になります。信頼性と電力の両面から、2 値が選ばれています。

注意 3.4（自作トランジスタ、自作チップ）

MOSFET が「絶縁膜を挟んだ電極でシリコン表面の導電性を制御する装置」であるという原理は素朴です。そのため、個人が自宅の設備で動くトランジスタを作った例がいくつもあります。ジェリー・エルスワース（Jeri Ellsworth）は自作の炉と真空装置で電界効果トランジスタを作って動作させ、サム・ゼルーフ（Sam Zeloof）は自宅のガレージにフォトリソグラフィの一式を組み上げて、複数のトランジスタを集積した自作チップを製造しています。反対方向の試みとして、ジェームズ・ニューマン（James Newman）の Megaprocessor は、市販の個別トランジスタ約 4 万個で 16 ビットのプロセッサを組み上げ、レジスタの各ビットを LED で光らせて動作を目に見えるようにしました。

これらは実用の装置ではありませんが、「計算は物理現象である」という事実を、抽象の階段を降りて確認させてくれます。今あなたが読んでいるこの文字も、どこかのシリコン表面で電荷が集まったり散ったりした結果です。

4. 組合せ回路から算術へ：加算器

論理ゲートが揃ったので、算術を作ります。2 進数の足し算は、桁ごとに「和の桁」と「上への桁上げ」を出す部品を並べれば実現できます。

定義 4.1（全加算器と桁上げ伝播加算器）

入力 $a, b, c \in \{0,1\}$ に対し

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

を出力する組合せ回路を全加算器といいます。$s$ を和ビット、$c'$ を桁上げ出力といいます。

$n$ 個の全加算器を、第 $i$ 番目の桁上げ出力 $c_{i+1}$ を第 $i+1$ 番目の桁上げ入力につなぐ形で連結し、$a_i, b_i$ を $i$ 桁目の入力、$c_0$ を最下位への桁上げ入力とした回路を、$n$ ビットの桁上げ伝播加算器（リップルキャリー加算器）といいます。

定理 4.2（桁上げ伝播加算器の正しさ）

$n \ge 1$ とし、$a_i, b_i \in \{0,1\}$（$0 \le i \le n-1$）と $c_0 \in \{0,1\}$ を任意に与えます。定義 4.1 の漸化式で $s_i, c_{i+1}$（$0 \le i \le n-1$）を定めるとき、整数の等式

$$\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$$

が成り立ちます。すなわち、$a$ と $b$ を $n$ ビット 2 進数と見た和に $c_0$ を加えた値が、$s$ を $n$ ビット 2 進数、$c_n$ を最上位ビットとする $n+1$ ビットの数に一致します。

証明（定理 4.2）

第 1 段：1 桁の等式。 各 $i$ について、整数として

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

が成り立つことを示します。左辺は $0$ 以上 $3$ 以下の整数です。$s_i = a_i \oplus b_i \oplus c_i$ は XOR が法 $2$ の加法（定義 2.1）であることから、左辺を $2$ で割った余りに等しいです。次に $c_{i+1}$ が左辺の $2$ による商、すなわち「3 つのうち少なくとも 2 つが $1$」に等しいことを場合分けで確かめます。

• $a_i = b_i = 1$ のとき：$a_i \land b_i = 1$ なので $c_{i+1} = 1$。左辺は $2 + c_i \ge 2$ で商は $1$。一致します。
• $a_i \ne b_i$ のとき：$a_i \land b_i = 0$、$a_i \oplus b_i = 1$ なので $c_{i+1} = c_i$。左辺は $1 + c_i$ で、商は $c_i$ に等しいです。一致します。
• $a_i = b_i = 0$ のとき：$a_i \land b_i = 0$、$a_i \oplus b_i = 0$ なので $c_{i+1} = 0$。左辺は $c_i \le 1$ で商は $0$。一致します。

商と余りが一致したので、除法の一意性から 1 桁の等式が従います。

第 2 段：桁数についての帰納法。 $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$$

を示します。$k = 0$ のとき、両辺の和は空和なので左辺は $c_0$、右辺は $c_0 \cdot 2^0 = c_0$ で $P(0)$ は成り立ちます。

$P(k)$（$k \le n-1$）を仮定します。両辺に $(a_k + b_k) 2^k$ を加えると、左辺は $P(k+1)$ の左辺になります。右辺は

$$\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}$$

となります。2 行目で第 1 段の 1 桁の等式を使いました。これは $P(k+1)$ の右辺です。よって $P(k+1)$ が成り立ち、帰納法により $P(n)$ が得られます。

∎

例 4.3（4 ビット加算を最後まで追う）

$a = 1011_2$（$= 11$）、$b = 0110_2$（$= 6$）、$c_0 = 0$ として 定義 4.1 の漸化式を下位から回します。

$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

結果は $c_4 s_3 s_2 s_1 s_0 = 1\,0001_2 = 17$ で、たしかに $11 + 6 = 17$ です。定理 4.2 の等式が成り立っています。

同じ回路を符号付き（2 の補数）と見ると、$1011_2 = -5$、$0110_2 = 6$、下位 4 ビットの結果 $0001_2 = 1$ で $-5 + 6 = 1$ となり、これも正しいです。2 の補数表現では加算回路をそのまま使い回せるのが利点です。ただし正しさの判定は変わり、符号なしでは桁上げ出力 $c_4 = 1$ が「あふれ」ですが、符号付きでは $c_4 \oplus c_3 = 1 \oplus 1 = 0$ なのであふれていません。

桁上げ伝播加算器は、名前のとおり桁上げが下位から上位へ順に伝わります。全加算器 1 段の遅延を $d$ とすると $n$ ビットで遅延 $n d$、つまり $\Theta(n)$ です。64 ビットではこれが速度を決めてしまうので、実際の CPU は次の構造を使います。

命題 4.4（桁上げ先読みと接頭辞計算）

$g_i = a_i \land b_i$、$p_i = a_i \oplus b_i$ とおくと、定義 4.1 の桁上げは $c_{i+1} = g_i \lor (p_i \land c_i)$ と書けます。ここで $\{0,1\}^2$ 上の二項演算

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

を定めると、次が成り立ちます。

1. $\circ$ は結合的で、$(0,1)$ を単位元とするモノイドを与えます。
2. $(G_i, P_i) = (g_i, p_i) \circ (g_{i-1}, p_{i-1}) \circ \cdots \circ (g_0, p_0)$ とおくと、$c_{i+1} = G_i \lor (P_i \land c_0)$ が成り立ちます。
3. ファンイン 2 の AND・OR・XOR ゲートからなる回路で、すべての $c_{i+1}$（$0 \le i \le n-1$）を深さ $O(\log n)$、ゲート数 $O(n \log n)$ で計算できます。

証明（命題 4.4）

まず $c_{i+1} = g_i \lor (p_i \land c_i)$ を確かめます。定義 4.1 の定義式は $c_{i+1} = (a_i \land b_i) \lor (c_i \land (a_i \oplus b_i))$ で、$g_i, p_i$ の定義を代入すると $g_i \lor (c_i \land p_i)$ となり、AND の可換性から主張の形になります。

（1）結合律。 3 つの元について両側を計算します。

$$\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}$$

最後の式の第 1 成分は、AND が OR に分配することから $g_3 \lor (p_3 \land g_2) \lor (p_3 \land p_2 \land g_1)$ に等しく、上の式と一致します。単位元については $(g,p) \circ (0,1) = (g \lor (p \land 0), p \land 1) = (g,p)$、$(0,1) \circ (g,p) = (0 \lor (1 \land g), 1 \land p) = (g,p)$ です。

（2）$i$ についての帰納法。 $i = 0$ のとき $(G_0,P_0) = (g_0,p_0)$ で、$G_0 \lor (P_0 \land c_0) = g_0 \lor (p_0 \land c_0) = c_1$ です。$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}$$

となります。2 行目で分配律を、最後で $(G_i,P_i) = (g_i,p_i) \circ (G_{i-1},P_{i-1})$ を使いました。

（3）深さ。 $(G_i, P_i)$ は結合的演算の接頭辞（prefix）です。Kogge–Stone の構成では、$(G^{(0)}_i, P^{(0)}_i) = (g_i, p_i)$ から出発し、$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}})$$

と更新します（添字が負のときは単位元 $(0,1)$ とします）。結合律により、$(G^{(k)}_i, P^{(k)}_i)$ が区間 $[\max(0, i-2^k+1),\, i]$ 上の積に等しいことが $k$ についての帰納法で従います。$2^k \ge n$ となる $k = \lceil \log_2 n \rceil$ 段で全区間を覆うので、$(G_i,P_i)$ が得られます。$\circ$ 1 回は AND 2 個と OR 1 個（深さ 2）で実現でき、各段で $n$ 個並列に行うので、全体の深さは $O(\log n)$、ゲート数は $O(n \log n)$ です。最後に $s_i = p_i \oplus c_i$ を求める分は深さ 1 の追加で済みます。

∎

64 ビットで比較すると、桁上げ伝播が 64 段であるのに対し、$\lceil \log_2 64 \rceil = 6$ 段です。$\Theta(n)$ と $\Theta(\log n)$ の差が、そのままクロック周波数の差になります。

5. 記憶とクロック：順序回路

ここまでの回路には時間がありません。入力を与えれば、遅延の後に出力が決まるだけです。計算を「手順」にするには、値を覚える仕組みが要ります。それは回路に帰還を入れることで得られます。2 個の NOR ゲートの出力を互いの入力に戻すと SR ラッチになり、入力が両方 $0$ のあいだ直前の状態を保ちます。これを 2 段重ねて、クロック信号の立ち上がりの瞬間だけ入力を取り込むようにしたものが、エッジトリガ型 D フリップフロップです。CPU のレジスタは、この D フリップフロップを幅の分だけ並べたものです。

定義 5.1（同期式順序回路とタイミングパラメータ）

すべての記憶素子が同一のクロック信号 $\mathrm{clk}$ の立ち上がりエッジで値を取り込む回路を同期式順序回路といいます。エッジトリガ型 D フリップフロップについて、次の量を定めます。

• $t_{cq}$（$t_{ccq}$）：クロックエッジから出力 Q が確定するまでの最大（最小）遅延。
• $t_{su}$（セットアップ時間）：入力 D がクロックエッジの何秒前までに確定していなければならないか。
• $t_{h}$（ホールド時間）：入力 D がクロックエッジの後、何秒間保たれていなければならないか。

また、フリップフロップ間の組合せ回路の最大遅延を $t_{pd}$、最小遅延を $t_{cd}$、クロックが各フリップフロップに届く時刻のばらつきの最大値を $t_{skew}$ と書きます。

命題 5.2（タイミング制約と最高動作周波数）

定義 5.1 の設定で、クロック周期を $T$ とします。すべてのフリップフロップが正しく値を取り込むためには、次の 2 つが必要十分です。

$$T \ge t_{cq} + t_{pd} + t_{su} + t_{skew} \qquad\text{（セットアップ制約）}$$$$t_{ccq} + t_{cd} \ge t_{h} + t_{skew} \qquad\text{（ホールド制約）}$$

特に動作周波数は $f = 1/T \le 1/(t_{cq} + t_{pd} + t_{su} + t_{skew})$ で頭打ちになります。ホールド制約には $T$ が現れないため、ホールド違反はクロックを遅くしても解消しません。

証明（命題 5.2）

送信側フリップフロップにクロックエッジが届く時刻を $0$ とします。

セットアップ制約。 送信側の出力 Q が確定するのは遅くとも時刻 $t_{cq}$ です。そこから組合せ回路を通るので、受信側の入力 D が確定するのは遅くとも $t_{cq} + t_{pd}$ です。一方、受信側に次のクロックエッジが届く時刻は、スキューの最悪の場合を考えると早くて $T - t_{skew}$ です。D はそのエッジの $t_{su}$ 以上前に確定していなければならないので

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

が必要で、移項すると第 1 式になります。逆に第 1 式が成り立てば上の不等式が成り立ち、条件は満たされます。

ホールド制約。 同じ時刻 $0$ のエッジで送信側は新しい値を出し始めます。それが受信側の D に届き始めるのは早くとも $t_{ccq} + t_{cd}$ です。受信側にとってこのエッジが届く時刻は、スキューの最悪の場合で遅くとも $t_{skew}$ です。受信側は自分のエッジから $t_{h}$ のあいだ D が変わらないことを要求するので

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

が必要で、これが第 2 式です。この式に $T$ は現れません。周期を長くしても、エッジ直後に新しい値が押し寄せるという事情は変わらないからです。ホールド違反は、経路にバッファを挿入して $t_{cd}$ を増やすことでしか直せません。

∎

例 5.3（周波数を数字で出す）

$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}$、組合せ回路は $t_{pd} = 310\ \mathrm{ps}$、$t_{cd} = 15\ \mathrm{ps}$ とします。命題 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}$$

です。ホールド制約は $25 + 15 = 40 \ge 30 + 20 = 50$ が偽なので満たされていません。この回路はクロックをいくら遅くしても動きません。最短経路にバッファを入れて $t_{cd}$ を $25\ \mathrm{ps}$ 以上にする必要があります。

さらに、この組合せ回路を遅延の等しい 2 段に分割してあいだにフリップフロップを挟むと、$t_{pd} = 155\ \mathrm{ps}$ となって

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

になります。周波数が 1.65 倍です。これがパイプライン化の原理で、命題 7.2 で改めて扱います。

6. 五大装置とフォン・ノイマン型アーキテクチャ

部品が揃いました。ここから計算機の全体像に移ります。古典的な分類では、コンピュータは次の五大装置からなります。

装置	役割	現代の実体
制御装置	命令を読み出して解読し、他の装置に制御信号を送る	命令デコーダ、制御ユニット
演算装置	算術演算・論理演算を行う	ALU、乗算器、浮動小数点演算器
記憶装置	命令とデータを保持する	レジスタ、キャッシュ、主記憶（DRAM）、SSD
入力装置	外界から情報を取り込む	キーボード、センサ、ネットワーク受信
出力装置	外界へ情報を送り出す	ディスプレイ、ネットワーク送信

このうち制御装置と演算装置をまとめたものが CPU（中央処理装置）です。第 3 節から第 5 節で作った部品との対応でいえば、演算装置は第 4 節の加算器などの組合せ回路、記憶装置のうち最速の層であるレジスタは第 5 節のフリップフロップの列です。

flowchart LR
IN["入力装置"] --> MEM["記憶装置"]
MEM --> OUT["出力装置"]
MEM <-->|"データ"| ALU["演算装置"]
MEM -->|"命令"| CU["制御装置"]
CU -.->|"制御信号"| ALU
CU -.->|"制御信号"| MEM

五大装置と情報の流れ。実線がデータと命令の流れ、破線が制御装置から出る制御信号を表す。

この図で決定的に重要なのは、記憶装置の箱が一つしかないことです。命令もデータも、同じ記憶装置に、同じビット列として置かれます。

定義 6.1（記憶プログラム方式（フォン・ノイマン型アーキテクチャ））

計算機が、実行すべき命令の列を、データと同じ書き換え可能な記憶装置の中にデータと同じ形式（ビット列）で保持し、次に実行する命令の番地を保持するレジスタ（プログラムカウンタ）に従って逐次読み出し、解読し、実行する方式を記憶プログラム方式といい、この方式に基づく構成をフォン・ノイマン型アーキテクチャといいます。

命令をデータと同じ場所に置くという一つの決定から、次の帰結がすべて出てきます。

• プログラムをデータとして扱える。 コンパイラ、リンカ、ローダ、仮想機械、JIT コンパイラはいずれも「プログラムを入力とし、プログラムを出力とするプログラム」です。この構図が成り立つのは、命令が記憶装置の中の単なるビット列だからです。言語処理系の側から見た同じ話は プログラミング言語論 で扱います（翻訳器と解釈器（定義 3.1）［プログラミング言語論］）。
• 命令とデータの区別は解釈の問題でしかない。 ある番地のビット列が命令なのかデータなのかは、CPU がそこをプログラムカウンタで指したか、ロード命令で読んだかの違いにすぎません。バッファオーバーフローによる攻撃は、データとして書き込んだビット列を命令として実行させる操作で、この設計の裏面です。現代の OS と CPU は、ページ単位（ページングによるアドレス変換（定義 5.1）［OS の役割］）に実行許可を与えないことでこれを防いでいます。詳しくは OS（オペレーティングシステム）の役割 を参照してください。
• 記憶装置との通路が細くなる。 命令もデータも同じ経路を通るため、CPU がどれだけ速くなっても、その経路の帯域が全体の速度を決めます。ジョン・バッカスは 1978 年のチューリング賞受賞講演でこれをフォン・ノイマンのボトルネックと呼びました。

三つ目への対策が、記憶階層とキャッシュです。命令用とデータ用のキャッシュを分ける構成（CPU の内側だけをハーバード型にする、と言われます）や、参照の局所性を利用した多段キャッシュが使われます。平均メモリアクセス時間 AMAT は

$$\text{AMAT} = t_{\text{hit}} + (\text{ミス率}) \times (\text{ミスペナルティ})$$

で見積もれます。ヒット時間 1 サイクル、ミス率 3 %、ミスペナルティ 100 サイクルなら $1 + 0.03 \times 100 = 4$ サイクルです。ミス率が 3 % から 6 % に上がるだけで 7 サイクル、つまり 1.75 倍になります。CPU の性能がしばしばアルゴリズムのメモリアクセスパターンで決まるのは、この式の第 2 項の係数が大きいからです。同じ形の見積もりは、アドレス変換を高速化するキャッシュ（TLB）についても使えます（TLB が効く理由を数値で見る（例 5.6）［OS の役割］）。

ヒント

「フォン・ノイマン型」という呼称は EDVAC 草稿の著者名に由来しますが、記憶プログラムの着想は J. プレスパー・エッカートとジョン・モークリーを含む EDVAC 計画の集団的な成果でもあり、帰属については歴史的な議論があります。用語としては定着しているので本記事でもそのまま使います。

7. CPU の中身：データパスと制御

CPU を開けると、大きく次の部品が入っています。

• レジスタファイル：数十本の高速な記憶。RV32I なら 32 ビットのレジスタが 32 本です。第 5 節のフリップフロップの列に、読み出し・書き込みのアドレスデコーダを付けたものです。
• ALU（算術論理演算装置）：加減算、AND・OR・XOR、シフト、比較を行う組合せ回路。中心にあるのは第 4 節の加算器です。
• プログラムカウンタ（PC）：次に実行する命令の番地を保持するレジスタ。
• 制御装置：命令のビット列を解読し、レジスタファイルの読み書き、ALU の演算種別、メモリアクセスの有無などを指示する信号を生成する回路。これも 定理 2.3 により、命令ビットを入力とするブール関数の組として実現できます。

これらをつなぐ経路をデータパスと呼び、経路上のスイッチ（マルチプレクサ）を切り替えるのが制御信号です。命令の実行は、次の 5 段階に分けて考えるのが標準です。

例 7.1（add 命令が 1 個実行されるまで）

PC が 0x00001000 を指し、そこに add x5, x6, x7 の機械語 0x007302B3 が置かれ、レジスタ x6 に 12、x7 に 30 が入っているとします。

1. 命令フェッチ（IF）：制御装置がアドレス 0x00001000 を命令メモリに出し、0x007302B3 を読み出します。同時に加算器が PC + 4 = 0x00001004 を計算します。
2. デコードとレジスタ読み出し（ID）：下位 7 ビットの 0110011 から R 形式の演算命令だと分かり、funct3 = 000、funct7 = 0000000 から演算は加算だと分かります。制御装置は「ALU は加算」「第 2 オペランドはレジスタ（即値ではない）」「レジスタ書き込みあり」「メモリアクセスなし」という信号を立てます。並行して、命令中の rs1 = 6、rs2 = 7 でレジスタファイルの 2 つの読み出しポートから 12 と 30 が出てきます。
3. 実行（EX）：ALU が $12 + 30 = 42$ を計算します。ここで動いているのが 定理 4.2 と 命題 4.4 の加算器です。
4. メモリアクセス（MEM）：この命令は何もしません。ロード命令やストア命令ならここでデータメモリを触ります。
5. 書き戻し（WB）：42 を rd = 5、すなわち x5 に書き込みます。同時に PC に 0x00001004 を書き込み、次のクロックエッジで次の命令へ進みます。

全体が 1 クロックで終わる設計を単一サイクル方式といいます。この場合、命題 5.2 の $t_{pd}$ は上の 5 段階すべてを通した遅延になるので、クロックが遅くなります。

命題 7.2（パイプライン化による速度向上）

1 命令の処理に必要な組合せ論理の総遅延を $T_{\text{logic}}$ とし、これを遅延の等しい $k \ge 2$ 段に分割してあいだにレジスタを挟むとします。レジスタ 1 段分のオーバーヘッド（命題 5.2 の $t_{cq} + t_{su} + t_{skew}$）を $t_r$ と書きます。データの依存関係や分岐による停止が一切ないと仮定するとき、$n$ 個の命令を処理する時間は

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

であり、速度向上比は $n \to \infty$ で

$$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$$

に収束します。特に $t_r > 0$ である限り、段数 $k$ を増やしても速度向上は $k$ 倍に達しません。

証明（命題 7.2）

分割しない場合、クロック周期は 命題 5.2 より $T_{\text{logic}} + t_r$ 以上必要で、1 命令に 1 サイクルかかるので $n$ 命令で $T_{\text{seq}}(n) = n(T_{\text{logic}} + t_r)$ です。

$k$ 段に分割すると、各段の論理遅延は $T_{\text{logic}}/k$ なので周期は $T_{\text{logic}}/k + t_r$ になります。第 1 命令が最終段を出るのは $k$ サイクル目、以降は停止がない仮定のもとで毎サイクル 1 命令ずつ完了するので、$n$ 命令には $k + (n-1) = n + k - 1$ サイクルかかります。よって $T_{\text{pipe}}(n)$ は主張の式です。

速度向上比は

$$\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}$$

で、$n \to \infty$ のとき第 1 因子は $1$ に収束します。第 2 因子の分母分子に $k$ を掛けると $S(k) = k(T_{\text{logic}} + t_r) / (T_{\text{logic}} + k t_r)$ です。$k$ 倍との比を取ると

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

で、$k \ge 2$ かつ $t_r > 0$ なら分母のほうが大きいので $S(k) < k$ です。

∎

たとえば $T_{\text{logic}} = 800\ \mathrm{ps}$、$t_r = 50\ \mathrm{ps}$、$k = 5$ なら、周期は $850\ \mathrm{ps}$ から $160 + 50 = 210\ \mathrm{ps}$ になり、$S(5) = 850/210 \approx 4.05$ です。理想の 5 倍には届きません。しかも実際には、直前の命令の結果を次の命令が使う依存や、分岐先が確定するまで次の命令を決められない事情で停止が入ります。段数を増やすほどこの損失が大きくなるので、20 段を超えるような深いパイプラインは 2000 年代に見直されました。

8. 命令セットアーキテクチャと RISC-V

第 7 節では「機械語 0x007302B3 は add 命令である」と天下りに述べました。この対応表こそが、ハードウェアとソフトウェアの境界に置かれた契約です。

定義 8.1（命令セットアーキテクチャ（ISA））

プログラムから観測できる計算機の仕様の全体、すなわち （a）命令の集合とそのビット列への符号化、 （b）レジスタの本数・幅・役割、 （c）アドレス空間とメモリの見え方（アラインメント、バイト順、複数の実行主体から見た順序）、 （d）例外・割り込みの扱い、 （e）特権レベル を定めたものを命令セットアーキテクチャ（ISA）といいます。同じ ISA を、パイプライン段数もキャッシュ構成も異なる複数の回路で実装できます。その実装方式のほうをマイクロアーキテクチャといいます。

ISA が契約であるとは、次の意味です。コンパイラはこの契約だけを見てコードを出し、CPU 設計者はこの契約を守る限りどんな内部構造を採ってもよい。この分離があるので、20 年前に書かれたバイナリが今日の CPU で動きます。

RISC-V はこの契約を、誰でも自由に実装・拡張できる形で公開した ISA です。基本整数命令セット RV32I の骨格は次のとおりです。

• 32 ビットのレジスタが 32 本（x0 から x31）。x0 は常に $0$ に配線されているので、書き込んでも変化しません。
• 命令長は 32 ビット固定。命令形式は R・I・S・B・U・J の 6 種類だけです。
• メモリを触るのはロード命令とストア命令だけで、算術演算はレジスタとレジスタ（または即値）のあいだで行います（ロード・ストア方式）。
• 基本整数命令は 40 数個しかありません。乗除算は M 拡張、アトミック操作は A 拡張、単精度・倍精度浮動小数点は F・D 拡張、16 ビット長の圧縮命令は C 拡張として分離されています。

x0 が常に $0$ であるという一点が、命令数を減らすのに効いています。addi x5, x0, 7 は「x5 に 7 を入れる」命令になり、add x0, x0, x0 は何もしない命令（NOP）になり、beq x6, x0, L は「x6 が 0 なら分岐」になります。専用命令を用意せずに済むわけです。

例 8.2（add x5, x6, x7 を 32 ビットに符号化する）

R 形式の命令は、上位ビットから順に funct7（7 ビット）、rs2（5 ビット）、rs1（5 ビット）、funct3（3 ビット）、rd（5 ビット）、opcode（7 ビット）です。add は opcode = 0110011、funct3 = 000、funct7 = 0000000 と定められています。レジスタ番号は rd = 5、rs1 = 6、rs2 = 7 なので、それぞれ 00101、00110、00111 です。並べると

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

で、続けて書くと 00000000011100110000001010110011 です。4 ビットずつ区切ると 0000 0000 0111 0011 0000 0010 1011 0011、16 進で 0x007302B3 となります。例 7.1 で CPU が読んだのはこのビット列です。同じ手順を I 形式の addi について実行した計算は addi 命令の符号化（例 2.1）［プログラミング言語論］ にあります。

逆向きに読むこともできます。下位 7 ビットが 0110011 なら R 形式の整数演算、funct3 と funct7 の組で演算種別が決まる、という規則をハードウェアの側で見れば、それがそのまま制御装置の真理値表になります。

RISC-V が広く使われるようになった理由は、技術的な簡潔さだけではありません。仕様の使用にライセンス料も許諾も要らないため、大学の講義で学生が丸ごと 1 個 CPU を設計でき、研究者が独自拡張を試せ、企業が用途特化のプロセッサを起こせます。ISA が「契約」であるという性質は、契約書が公開されているときに最もよく働きます。

命令の上に載る層、すなわちこの契約をどう使ってプロセス（定義 3.1［OS の役割］）や仮想記憶や特権モード（定義 2.1［OS の役割］）を組み立てるかは OS（オペレーティングシステム）の役割 で、契約に向けて高級言語を翻訳する仕組みは プログラミング言語論 で扱います。

9. 演習

演習 9.1易

$x \downarrow y = \lnot(x \lor y)$（NOR）と定めます。NOR のみを用いて $\lnot x$、$x \lor y$、$x \land y$ を表し、NOR が関数完全であることを示してください。

解答

$\lnot x = x \downarrow x$ です。実際 $x \lor x = x$ なので $x \downarrow x = \lnot x$ となります。

$x \lor y = \lnot(x \downarrow y) = (x \downarrow y) \downarrow (x \downarrow y)$ です。1 つ目の等式は $\lnot\lnot(x \lor y) = x \lor y$ から、2 つ目は前段の $\lnot$ の構成を $x \downarrow y$ に適用したものです。

$x \land y = (x \downarrow x) \downarrow (y \downarrow y)$ です。右辺は $\lnot x \downarrow \lnot y = \lnot(\lnot x \lor \lnot y)$ で、ド・モルガンの法則によりこれは $x \land y$ に等しいです。

以上より $\land, \lor, \lnot$ がすべて NOR で書けるので、定理 2.3 と合わせて任意のブール関数が NOR のみで表せます。証明の流れは 系 2.4 と同じで、双対を取っただけです。

演習 9.2標準

8 ビット 2 の補数表現について答えてください。 （1）$-45$ のビット列を求めてください。 （2）$67 + (-45)$ を 8 ビットの加算器で計算し、定理 4.2 の記号で $c_8$ と $c_7$ を求めてください。 （3）符号付き加算のあふれ（オーバーフロー）が $c_n \oplus c_{n-1} = 1$ で判定できることを、この例と $100 + 100$ の例で確かめてください。

解答

（1）$45 = 00101101_2$ です。各ビットを反転して $11010010_2$、これに $1$ を加えて $11010011_2$（16 進で 0xD3）が $-45$ の表現です。検算すると、符号なしとして $211 = 256 - 45$ なので正しいです。

（2）$67 = 01000011_2$ です。下位から桁上げを追います。

$i$	$a_i$（67）	$b_i$（$-45$）	$c_i$	和	$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

結果は $s = 00010110_2 = 22$ で、$67 - 45 = 22$ と一致します。$c_8 = 1$、$c_7 = 1$ です。

（3）この例では $c_8 \oplus c_7 = 1 \oplus 1 = 0$ なのであふれなしと判定され、実際に答えは正しい値です。符号なしとして見れば $c_8 = 1$ は桁あふれですが、符号付きでは最上位への桁上げと最上位からの桁上げが打ち消し合っているので問題ありません。

次に $100 + 100$ です。$100 = 01100100_2$ なので、下位から追うと $i=2$ で $1+1$ の桁上げが立ち、$i=5$ の桁で $1+1+0 = 2$ となって $s_5 = 0$、$c_6 = 1$、$i=6$ では $1+1+1 = 3$ で $s_6 = 1$、$c_7 = 1$、$i=7$ では $0+0+1$ で $s_7 = 1$、$c_8 = 0$ です。結果は $11001000_2$ で、8 ビット 2 の補数として読むと $-56$ です。判定式は $c_8 \oplus c_7 = 0 \oplus 1 = 1$ となり、正しくあふれを検出しています。

一般に、$c_n \oplus c_{n-1} = 1$ は「最上位ビットへの桁上げと、最上位ビットからの桁上げが食い違う」ことを意味します。この 2 つが一致していれば、最上位への繰り上がりが符号ビットの重み $-2^{n-1}$ の分と正しく相殺され、結果は表現範囲に収まります。

演習 9.3標準

あるパイプライン段について、$t_{cq} = 35\ \mathrm{ps}$、$t_{ccq} = 20\ \mathrm{ps}$、$t_{su} = 30\ \mathrm{ps}$、$t_{h} = 40\ \mathrm{ps}$、$t_{skew} = 15\ \mathrm{ps}$ とし、組合せ回路の遅延は $t_{cd} = 10\ \mathrm{ps}$ から $t_{pd} = 420\ \mathrm{ps}$ の範囲とします。 （1）最高動作周波数を求めてください。 （2）ホールド制約が満たされているか判定し、満たされていなければ必要な対処を述べてください。 （3）この段の組合せ回路を遅延の等しい 2 段に分割したとき、周波数は何倍になりますか。

解答

（1）命題 5.2 のセットアップ制約より

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

なので $f \le 1/(500 \times 10^{-12}\ \mathrm{s}) = 2.0\ \mathrm{GHz}$ です。

（2）ホールド制約は $t_{ccq} + t_{cd} \ge t_h + t_{skew}$、すなわち $20 + 10 = 30 \ge 40 + 15 = 55$ です。これは偽なので満たされていません。差は $25\ \mathrm{ps}$ なので、最短経路に遅延 $25\ \mathrm{ps}$ 以上のバッファを挿入して $t_{cd} \ge 35\ \mathrm{ps}$ とする必要があります。命題 5.2 のとおり、ホールド制約に $T$ は現れないため、クロックを遅くしても解消しません。

（3）分割後は $t_{pd} = 210\ \mathrm{ps}$ なので

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

です。倍率は $500/290 \approx 1.72$ 倍で、2 倍には届きません。1 段あたり $t_{cq} + t_{su} + t_{skew} = 80\ \mathrm{ps}$ のオーバーヘッドが必ず乗るからで、これが 命題 7.2 の $S(k) < k$ の正体です。

演習 9.4難

RISC-V の I 形式命令は、上位ビットから imm（12 ビット、符号付き）、rs1（5 ビット）、funct3（3 ビット）、rd（5 ビット）、opcode（7 ビット）の順に並びます。addi は opcode = 0010011、funct3 = 000 です。 （1）addi x5, x6, -1 を 32 ビットに符号化してください。 （2）RV32I の I 形式では即値が 12 ビットに制限されます。32 ビットの任意定数をレジスタに置くにはどうすればよいか、U 形式命令 lui（即値の上位 20 ビットをレジスタの上位 20 ビットに置き、下位 12 ビットを $0$ にする）を使って説明してください。

解答

（1）$-1$ の 12 ビット 2 の補数表現は 111111111111 です。rs1 = 6 は 00110、rd = 5 は 00101 なので、並べると

imm	rs1	funct3	rd	opcode
111111111111	00110	000	00101	0010011

続けて書くと 11111111111100110000001010010011 です。4 ビットずつ区切ると 1111 1111 1111 0011 0000 0010 1001 0011、16 進で 0xFFF30293 です。

（2）目的の定数を $C$ とします。lui x5, hi で上位 20 ビットを置き、続けて addi x5, x5, lo で下位 12 ビットを足します。ただし addi の即値は符号付きなので、下位 12 ビットの値 $\ell = C \bmod 2^{12}$ が $2^{11}$ 以上のとき、addi は $\ell - 2^{12}$ という負の値を足してしまいます。そこで

$$\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}$$

のように、上位側にあらかじめ $1$ を繰り上げておく補正をします。たとえば $C = \mathtt{0x12345678}$ なら下位 12 ビットは 0x678 で $2^{11} = \mathtt{0x800}$ 未満なので補正は不要で、lui x5, 0x12345 と addi x5, x5, 0x678 の 2 命令になります。一方 $C = \mathtt{0x12345FFF}$ なら下位 12 ビットは 0xFFF（符号付きで $-1$）なので、lui x5, 0x12346 と addi x5, x5, -1 とします。アセンブラの疑似命令 li（load immediate）は、この判定を自動で行っています。

参考文献

• David A. Patterson, John L. Hennessy, Computer Organization and Design: The Hardware/Software Interface, RISC-V Edition, 2nd ed., Morgan Kaufmann, 2020 — 第 1 章（性能）、第 2 章（RISC-V 命令）、第 4 章（データパスとパイプライン）、第 5 章（記憶階層）。
• Sarah L. Harris, David Money Harris, Digital Design and Computer Architecture, RISC-V Edition, Morgan Kaufmann, 2021 — 第 1〜3 章（ブール代数、CMOS、順序回路とタイミング）、第 5 章（加算器）、第 7 章（マイクロアーキテクチャ）。
• Noam Nisan, Shimon Schocken, The Elements of Computing Systems: Building a Modern Computer from First Principles, 2nd ed., MIT Press, 2021 — 第 1〜5 章。NAND から CPU までを実際に組み上げる演習書です。
• John von Neumann, “First Draft of a Report on the EDVAC” (1945). 再録: 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 — 「フォン・ノイマンのボトルネック」の出典。
• Andrew Waterman, Krste Asanović (eds.), The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA — riscv.org/technical/specifications/ で公開されています。命令形式と符号化の一次資料です。