38 ー 2 章ブール算術 テップ 0 ) は、最下位ビットのペアが加算され、キャリービットが次の桁ビットの加 算器へと送られる。この処理は、れ一 1 回目のステップである最上位ビットまで続く。 こで、各ステップでは 3 つのビットの加算が行われることに注意してほしい。その ため、れ個の全加算器を並べて、キャリービットを上位の桁ビットの全加算器へ送る ようにすれば、れビットの加算器が実装できる。 インクリメンタ 〃ビットのインクリメンタは、 できる。 ALU れビットの加算器を用いれば簡単に実装することが 我々の ALU は入念に設計されたものである。必要とされる ALI_J の演算はすべて、 単純なプール演算を用いて論理的に導くことができる。そのため、 ALU の物理的な実 装も、図 2 - 5 の擬似コードで示した単純なプール演算を実装することで実現できる。 実装の最初のステップは、 zx と nx の制御ビットに従って、 16 ビット入力を変換する 論理回路を作成するのがよいだろう ( すなわち、 16 ビット入力を、場合に応じて、ゼ 口または反転させる回路を作成する ) 。この論理は、入力の x と y 、そして出力の〇 ut において用いられる。ビット単位の And 演算と加算は本章と前章で、すでに実装済み である。そのため、残る作業は、制御ビット f の値に応じて、 And 演算と加算を選ぶ 回路を構築することである。最後に、すべての回路を統合して全体として ALU を構 成する必要がある ( 「回路を構築する」とは、「 HDL コードを書く」ことを意味する ) 。 2.4 展望 本章で示した多ビット加算器の実装方法は標準的なものである。ただし、効率につ いては注意を払わなかった。実際、我々の実装はやや効率の悪いものである。その原 因は、キャリービットが最下位ビットから最上位ビットまで段階的に伝達するのに長 い時間を要するからである。この遅れを軽減するには、「キャリー先読み (carrylook ahead) 」と呼ばれる手法が用いられる。どのようなハードウェアプラットフォームで あれ、加算はいたることろで行われる操作であるから、そのような低水準における改 良は、コンピュータ全体のパフォーマンスを目覚ましく向上させる可能性がある。 コンピュータシステムを設計する場合、 ALU がどのような機能を提供すべきかとい う問題は、根本的には「コストとパフォーマンス」の問題に行き着く。一般的なルー

34 ー 2 章ブール算術 ある。次にその仕様を示す。 回路名 入力 出力 関数 コメント 2.2.2 工 nc16 in は 6 ] out は 6 ] in 十 1 out 2 の補数による加算。 オーパフローは検出されない。 ALU ( 算術論理演算器 ) これまで見てきた加算器回路の仕様は " 一般的 " なものであった。一般的とは、つ まり、どのようなコンピュータでも使われる、という意味である。それとは対照的に こで述べる ALU は、 Hack と呼ばれる特定のコンピュータブラットフォームだけ で使われる専用の回路である。その ALU は、これから先、コンピュータの中心的な 役割を担う回路となる。さらに、その ALU のアーキテクチャは、最小限の内部バー ツだけから構成されてはいるが、それにもかかわらす、非常に多くの機能を持つ。そ れゆえ、その論理設計は「効率さ」と「簡潔さ」を示す良い手本になるだろう。 Hack の ALU は、仕様で決められた関数である。厩 = い , のを計算するように 設計されている。こで、工と″は回路への 16 ビットの入力であり、 0 厩は 16 ビッ トの出力である。は算術演算または論理演算であり、全部で 18 種類の関数がある。 ALU に対して、どの関数を実行させるかを指定するには、制御ビット (control bits) と呼ばれる 6 ビットの入力ビットを用いる。実際の仕様については、擬似コードを用 いて示す ( 図 2 - 5 ) 。

2.5 プロジェクトー 39 ルとしては、算術演算と論理演算をハードウェアで実装するにはコストは高くつくが、 パフォーマンスは良くなる。このトレードオフの関係を考慮して、ハードウェアであ る ALU は設計される。本書で設計した ALU は、機能性を限定して、できるかぎり ソフトウェア側で他の操作を実装するような設計を採用した。たとえば、我々の ALU は、「乗算」も「除算」も「浮動小数点演算」の機能も提供していない。これらの操作 は、 OS レベルで実装される ( 詳細は 12 章で述べる ) 。このように、どのようなコン ピュータであれ、ハードウェアとソフトウェアの機能は、 ALU とオペレーティングシ ステム ( それは ALU の上で実行される ) がタッグを組んで提供するものである。 プール演算と ALU 設計の詳細については、「コンピュータアーキテクチャ」に関す る書籍などで論じられている。興味のある読者は、そのような書籍を参照してほしい。 2.5 プロジェクト 目標 本章で取り上げた回路をすべて実装する。使うことのできる構成要素は、前章まで に構築した回路である。本章で作った回路については、それ以降用いることができる。 本プロジェクトで読者が実装する HDL プログラムは、先のプロジェクトで構築し た回路を内部的に用いることだろう。その場合、自分で実装した回路を用いる代わり に、ビルトイン版の回路の使用を推奨する。ビルトイン版回路を用いれば、その回路 の動作は正しいことが保証でき、さらにハードウェアシミュレータの実行速度を最適 化できる。これを行うのは簡単である。あなたのプロジェクトのディレクトリに、そ のプロジェクトで取り組んでいる . hdl ファイルだけを含むようにすればよい。 手順については、前章のプロジェクトで示した「手順」と同じである。ただし、プ ロジェクトのディレクトリは、 pro j e ct s / 0 2 にある。

章術 数えることは、 この世の宗教である。この世の希望であり、救済である。 ガートルード・スタイン ( 1874 ー 1946 ) 本章では、数を表現し算術演算を行うための論理ゲートを作成する。我々の出発点 は 1 章で作成した論理ゲートであり、終着点は算術論理演算器 (ALU) である。コン ピュータで行われる算術演算と論理演算はすべて、この ALU 回路によって行われる。 そのため、 ALU の機能を理解することは、 CPU 、さらにはコンピュータ全体の仕組 みを理解する上で重要なステップとなる。 通常どおり、こでも段階的に話を進めていく。最初の「背景」の節では、符号付 き整数の表現について、また、その和を求めるために 2 進コードとプール算術がどの ように使われるかについて簡単に述べる。「仕様」の節では、加算器 (adder) につい て解説する。本章で登場する加算器は 3 つある。 2 ビット加算器、 3 ビット加算器、れ ビットバイナリをベアとした加算器の計 3 つである。また、この節では ALU の仕様 について明確な定義を与える。 ALU の仕様は複雑に見えるかもしれないが、シンプ ルな論理設計に基づいていることがわかるだろう。「実装」と「プロジェクト」の節で は、本書が提供するハードウェアシミュレータを用いて、各自のコンピュータ上で、 加算器と ALU を実装する方法について助言とガイドラインを与える。 2 進数の加算は単純な演算ではあるが、奥が深い。驚くべきことに、デジタルコン ピュータによって行われる命令の多くが「 2 進数の加算」へと還元することができる。 そのため、コンピュータの多種多様な命令を実装するにあたって、 2 進数の加算を理 解することが重要である。

ること、また、条件に応じてプログラム中の他の命令場所に移動することなどである。 CPU はこのようなタスクを次に挙げる 3 つのハードウェアを用いて実行する。それ は、 ALU 、レジスタ、制御ユニットである。 ALU ALU は下位レベルの算術演算と論理演算を行うように設計されており、その設計が そのコンピュータを特徴づける。たとえば、一般的な ALU が実行できる処理は、ふた つの数値の加算やワードのビット操作、与えられた数が正かどうかの判定などである。 レジスタ CPU は単純な計算を " 素早く " 行うように設計されている。パフォーマンスを向上 させるため、計算結果を遠く離れたメモリに出し入れするのではなく、近くの場所に 格納するのが望ましい。そのため、 CPU にはハイスピードなレジスタが少数ではあ るが備えられている。各レジスタは 1 ワードを保持することができる。 制御ユニット コンピュータの命令はバイナリコードによって表される。一般的には 16 、 32 、 64 ビット幅のバイナリコードが用いられる。そのような命令を実行するには、ます、その 命令をデコードしなければならない。そして、その命令に埋め込まれた情報は、特定 のハードウェア装置 (ALU 、レジスタ、メモリなど ) に信号を送るために利用する必 要がある。命令のデコードは制御ユニット (controlunit) によって行われる。また、 この制御ユニットは、次にどの命令をフェッチし実行するかという情報も保持する。 これで、 CPU の命令はループ処理のように記述することができる。このループ処 理は次のように続く。メモリから命令 ( ワード ) をフェッチする。その命令をデコー ドする。それを実行する。次の命令をフェッチする・・・・・・という流れである。命令の実 行には次に示すような小さな仕事を伴う。それは、 ALU に何らかの計算をさせるこ と、内部レジスタを操作すること、メモリからワードを読み込むこと、そしてメモリ にワードを書き込むことである。このようなタスクを実行する過程で、 CPU は次に フェッチし実行すべき命令がどこにあるかという情報も得る。 5.1.5 レジスタ 「メモリアドレスが j にあるデータを取得せよ」と CPU が命令すると、次の手続き

3.1 背引 組み合わせ回路 47 ( オプション ) comb. logic 順序回路 時間遅延 DFF gate(s) ( オプション ) comb. logic comb. logic out out = 工 (in) out out(t) = 工 (in(t-l), out(t-l)) 図 3 - 4 組み合わせ回路と順序回路 ( 「 in 」「 out 」はそれぞれひとつ以上の「入力」「出力」を、工は何 らかの関数を意味する ) 。順序回路は、必ず DFF 回路が組み合わせ回路に " 挟まれた " 構造になる。こ こで、組み合わせ回路はオプションであり、それを用いない構造もあり得る 組み合わせ回路については、入力値が変われば、その出力値は時間に関係なく直ち に変わることを思い出してほしい。それとは対照的に、順序回路アーキテクチャ内に DFF が組み込まれると、その出力値が変化するタイミングは、現在のクロック周期 から次のクロック周期に移行した時点であり、同じクロック周期においては変化しな い。実際のところ、我々が順序回路について求めることは、次のクロック周期の始ま りにおいてのみ正しい値を出力することだけである。クロック周期の間中は不安定な 状態であることを許容している。 この順序回路の出力が " 離散化 " される性質は、思わぬ結果を、そして重要な結果 をもたらす。それは、コンピュータアーキテクチャ全体を同期させることができる、 ということである。たとえば、 ALU にェ十″を計算するように指示したとする。 こで、ェは近くにあるレジスタに格納された値であり、リは遠く離れた場所にあるレ ジスタの値であると仮定する。さまざまな物理的制約 ( 距離、抵抗、干渉、ノイズな ど ) により、工とリの電気信号が ALU までに到着する時間は異なることになるだろ う。しかし、 ALU は組み合わせ回路であるから、時間という概念はない どのよう な信号であれ、その入力に入ってきたとしたら、即座にその加算が求められる。その ため、 ALU の出力が正しい朝十″」の値に落ち着くには、わすかな時間が必要であ る。その時間に達するまで ALU は " ゴミ " を出力していることになる。 この問題にどのように対応すればよいだろうか ? その答えは単純である。 ALU の 出力は順序回路 ( レジスタや RAM など ) を常に通過するため、この問題について考え る必要はまったくない。我々がやらなければならないことは、コンピュータのクロッ クを作成するとき、そのクロック周期の間隔を適切に決めることだけである。具体的 には、アーキテクチャ内で最も距離が長い回路間を移動するのに必要な時間を調べ、

36 ー 2 章ブー丿レ算術 制御ビットの各ビットは、 ALU に特定の基本演算を行わせるために用いられる。 れらの操作が合わさることで、さまざまな有用な関数の計算を行うことができる。全 体の操作は 6 つの制御ビットにより行われるので、可能性としては 26 = 64 通りの異 なる関数を操作できる。図 2 - 6 では、 18 種類の関数について、その仕様を示す。 このビットは これらのビットは このビットは出力前の。 ut 結果的に 入力 x に対しての 「 + 」か「 And 」をに対しての 生じる 操作を指定する 指定する操作を指定する ALU の出力 Z X n X out= これらのビットは 入力 y に対しての 操作を指定する z Y n 0 if f then out=x 十 y i f z y i f ny then then then e 1 S e then then out= ! out x 0 0 1 out x & y = 1 上 - 亠 1 ~ O - 亠 O 亠 O 「 1 0 1 亠 0 1 、 - 冂 - 0 - - Ⅱ ) 0 = 1 よ - 亠 1 ~ O O - 冂 ) - 冂一 1 亠 1 上「上 1 亠 - 亠 1 ~ 「亠 1 亠 1 亠 - Ⅱ ) 0 - い - 1 上 0 1 上 -0 - 亠 O 「亠 0 1 亠「亠 -1 - Ⅱ - - 冂一 - 冂 ) 当亠 - い ) 1 亠 0 1 上 1 亠 - 冂 ) 「亠 0 1 亠 O 「上“亠 1 亠 - 冂 ) 1 亠 O 「上 0 0 1 上 - 冂一 1 亠 - い - 冂 - - 冂 - - 上 1 亠 1 ~ 「亠 1 亠 1 亠 O O - - 「上 1 亠 - い ) 1 亠 x + 1 y + 1 x ー 1 x + y x ー Y Y¯x x & y 幻 Y 図 2 -6 ALU の真理値表。最初の 6 列に示すビットの値に対応して、右の列の関数を計算する ( 「 ! 」 「 & 」Ⅲという記号は、それぞれ「 Not 演算」「 And 演算」「 Or 演算」に対応する ) 。完全な ALU の真理 値表は 64 行からなるが、その中で我々が興味のある行は 1 8 行だけである この ALU は、 6 個の制御ビットの値によって、特定の関数 / ( ェ , のが実行されるよ うに設計されている。実際、図 2 - 5 で指定された ALU の内部論理 ( 擬似コードの「関 数」で示した論理 ) を適用することで、図 2-6 で指定された / は , のの値が出力され るようになっている。もちろん、それは偶然に起こったのではなく、そうなるように 注意深く設計したのである。 たとえば、図 2 - 6 の 12 行目を考えてほしい。その行で ALU の行う演算は x ー 1 で ある。 z x と nx のビットは 0 であるから、入力 x はゼロ化も反転もされない。 z y と

5.3 実装ー 103 叩令のデコード 命令をその基本領域へ、つまり、ビットの部分集合へ分割する ( パースする ) 。 次の命令のフェッチ とする回路へ送信する。 か」ということについて指示を与える。これを行うために、制御ビットを目的 命令を実行するために、コンピュータのさまざまな回路パーツに「何をすべき 命令の実行 我々はこれらのヒ、ツトを「制御ビット」と呼ぶことにする。 を指定する。 を実行するかが決定される。 d ビットは ALU の結果をレジスタに書き込むかどうか 力」のどちらを操作するかが決定される。また、 c ピットによって、 ALU がどの関数 が実行される。具体的には、 a ビットによって、 ALU が「 A レジスタ」か「メモリ入 結果として、機械語の仕様によって定義されている A 命令または C 命令のどちらか 一斉に送信される。その制御ビットによって各パーツでは決められた処理が行われ、 命令の各領域 ( i 、 a 、 c 、 d 、 j ビット ) はアーキテクチャ内のさまざまなパーツへ 命令の実行 域」を表す。 A 命令の場合、土ビットを除いた 15 ビットは定数値として解釈される。 ビットと c ビットは「 cornp 領域」、 d ビットは「靃領域」、 j ビットは第れ rn 〃領 トは命令の種類を表し、 0 が「 A 命令」、 1 が「 C 命令」に対応する。 C 命令の場合、 a 「土 xx a cccccc ddd j j j 」という領域へ分けて考えることができる。土ビッ らかによって表される。この 16 ビットが何を意味するかを知るためには、 CPU の命令は 16 ビットのワードであり、 A 命令または C 命令のどち 命令のデコード これより先、「 CPU の実装案」という用語は図 5 -7 を指すものとする。 発信されるふたつの制御ビットによって決定される。 次に実行する命令を把握する。これは命令のジャンプビットまたは ALU から

C. 4 使用方法ー 369 ・ : ◆テストが成功する場合 . \projects\02>HardwareSimu1ator A U. セ s セ comparison ended successfully End Of script ・ : ・テストが失敗する場合 . \projects\02 >HardwareSimu1ator ALU. セ s セ Comparison failure at line 24 : ◆ HDL にエラーがある場合 . \projects\02>HardwareSimu1ator ALU. セ s セ . \projects\02\ALU. hdl' Line 6 の out は 6 ] : 工 n HD L f 土 1 e C : \ . the specified sub bus is not in the bus range: load ALU. hd1 CPU 工ミュレータⅣ M 工ミュレータ これらのツールは、先のハードウェアシミュレー アセンブラ タと同様に用いる。 コマンド引数なしで実行すると、インタラクテイプモードで起動する。 「 Assembler xxx . asm 」として実行すれば、 xxx. asm が変換され、 xxx. hack が 生成される ( インタラクテイプモードでも、この変換作業を行うことができる ) 。 アセンブルが成功 . \projects\04\fi11>Assemb1er F土11. asm . \projects\04\fi11\Fi11. asm" Assemb1ing "c:\ . アセンブルが失敗 . \pr0jects\04\fi11>Assemb1er F土11. asm . \pE0jects\04\fiIl\Fi11. AssembIing い C : \ . 工 n line 15 ー Expression expected コンバイラ JackC 。 mpiler を引数なしで実行すると、現在のディレクトリにあるファイルを すべてコンパイルする。引数がファイルで与えられた場合、そのファイルをコンパイ ルする。引数がディレクトリの場合、ディレクトリに含まれるファイルをすべてコン パイルする。ワイルドカードい ) はサポートしていない。

5.2 Hack ハードウェアのプラットフォーム仕様ー 93 ーでは、参照しやすいように、 4 章 は ( 特に機械語については ) 、 4 章で提示した の内容を簡潔にまとめる。 Hack コンピュータは命令メモリに存在するプログラムを実行する。命令メモリは 読み込み専用のデバイスであるから、何らかの特別な方法を使ってプログラムをロー ドする必要がある。たとえば、必要とするプログラムがすでに書き込まれた ROM 回 路を用いることで、命令メモリの仕組みを実現することができる。新しいプログラム をロードするためには、新しい ROM 回路に差し替えればよい。この仕組みを模倣す るために、 Hack プラットフォームのハードウェアシミュレータは次の操作が行えるよ うになっている。それは、 Hack の機械語で書かれたプログラムを含むテキストファ イルを命令メモリに読み込むための操作である ( これ以降は、データメモリを RAM と呼び、命令メモリを ROM と呼ぶようにする ) 。 Hack の CPU は、 ALU と 3 つのレジスタから構成される ( ALU については 2 章で 説明を行った ) 。 3 つのレジスタは、「データレジスタ (D) 」「アドレスレジスタ (A) 」 「プログラムカウンタ (PC) 」と呼ばれる。 D レジスタと A レジスタは 16 ビットの 汎用的なレジスタであり、 A = D ー 1 や D = A のような算術演算や論理演算において用 いられる ( 4 章で示した Hack 機械語の仕様に従う ) 。 D レジスタはデータを保持する ためだけに用いられるが、 A レジスタの内容は、使われる命令に応じて次の 3 つの異 なる意味として解釈される。それは、データ値、 RAM アドレス、 ROM アドレスの 3 つである。 Hack 機械語は 2 種類の 16 ビット命令をベースとしている。アドレス命令は 「 ovvvvvvvvvvvvvvv 」というフォーマットに従う ( v は 0 または 1 を示す ) 。この . v という値を A レジスタに 命令を実行すれば、コンピュータは 15 ビットの vvv. 設定する。一方、計算命令は「 lllaccccccdddjjj 」というフォーマットに従う。 a ビットと c ビットは ALU に行うべき関数を指示し、 d ビットは ALU の出力を格 納する場所を指定する。 j ビットは ( オプションとして ) 移動条件を指定する。これ らはすべて Hack の機械語仕様に従って行われる。 この後すぐに見ていくことになるが、コンピュータアーキテクチャにおいて、プロ グラムカウンタ (PC) 回路の出力は ROM 回路のアドレス入力に接続されるように 配線されている。そのため、 ROM 回路からは常に ROM[PC] 、つまり、命令メモリ 中で PC が " 指さす " 場所のデータ値が出力される。この値は「現在命令 (current instruction) 」と呼ばれる。以上のことを踏まえると、各クロックサイクル中におけ るコンピュータ全体の操作は次のふたつの操作からなる。