猫型エンジニアのブログ

プログラム/ネットワーク系の技術関連をまとめたページです 

コンピュータシステムの理論と実装(第1章〜第3章)

コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方

コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方

 まだSICPも2章の途中ですが、こちらを読み進めていきます。基本的なゲートを用いて、シュミレータ上でメモリ・CPU・コンパイラ・OS・高級言語まで作成するという、まさにコンピュータの真髄をたどっていく本です。今までコンパイラの作成などの本は聞いたことありますが、論理ゲートの作成から始めるというのは初めて聞きました。Amazonで注文してから届くまでが本当に待ち遠しかったです。

章末の演習問題の解答をGitHubに公開しました。

github.com

第1章 ブール論理

1.1.1 ブール代数
  • すべてのデジタル機器は論理ゲートからなる。
  • 抽象化...『機能』にのみ着目して、『実装』に関しては無視する。
  • 与えられた真理表を実現するブール式は一意にさだまらないが、少なくとも(3つのブール演算And,Or, Notからなる)一つの正準表現で表すことができる。正準表現は真理値表から機械的に導くことができる。
  • And,Or,Not演算はNAND(Not AND)演算であらわすことができる。つまりNAND演算ですべてのブール式を表現することができる。言わばNAND演算は、ブール代数の『原子』に相当する。
1.1.2 論理ゲート
1.2.2 基本論理ゲート
  • マルチプレクサ...複数の入力から一つの入力を選んで(セレクタ)出力するゲート。逆はデマルチプレクサ。If`文に対応する論理ゲート。
1.2.3 多ビットの基本ゲート
  • コンピュータのハードウェアは入出力にバス(複数ビット)を使用するのが一般的。
  • 基本論理ゲートを並列に並べることで多ビット基本ゲートができる。
  • 論理ゲートへの入力数自体は基本論理ゲートと変わらない(2入力)が、1入力あたりのビット数が増える(ex. 1bit->16bit)。
1.2.4 多入力の基本ゲート
  • 論理ゲートの入力数を拡張した論理ゲート。多ビットと多入力はそれぞれ独立しているため、多ビット・多入力の基本ゲートも用いられる。
  • 基本論理ゲートを直列に多段化に並べることで、多入力基本ゲートができる。

第2章 ブール算術

  • マイナスは2の補数で表す(最上位ビットは必ず1)。マイナスも足し算として表現される。
  • ALU(算術論理演算器)を基本ゲートと、その組み合わせの加算器から構築する。
  • このALUでは乗算・除算は未実装、それらにはOSで実装する。ALU(ハードウェア)/OS(ソフトウェア)のどちらで実装するかは、コストとパフォーマンスの問題。

第3章 順序回路

  • フィードバックループを利用することで、「状態を保つ」機能を持つ回路(順序回路)が可能になる。
  • フリップフロップ -> Bit -> Register -> PCの順に構成されている。
  • Bitでは現在のピンの条件が、次の状態の出力値を決める、タイムラグ(時間遅延)があることに注意。

第4章以降

  • 内容が多いため、分割しました。以下のリンク先です。

alexei-karamazov.hatenablog.com

参考 ハードウェアシュミレータ チップAPI

これがないとHDL書けません。せめてこのくらいは載せて欲しかったです。

  Add16(a= ,b= ,out= ); 
  ALU(x= ,y= ,zx= ,nx= ,zy= ,ny= ,f= ,no= ,out= ,zr= ,ng= ); 
  And16(a= ,b= ,out= ); 
  And(a= ,b= ,out= ); 
  ARegister(in= ,load= ,out= ); 
  Bit(in= ,load= ,out= ); 
  CPU(inM= ,instruction= ,reset= ,outM= ,writeM= ,addressM= ,pc= ); 
  DFF(in= ,out= ); 
  DMux4Way(in= ,sel= ,a= ,b= ,c= ,d= ); 
  DMux8Way(in= ,sel= ,a= ,b= ,c= ,d= ,e= ,f= ,g= ,h= ); 
  DMux(in= ,sel= ,a= ,b= ); 
  DRegister(in= ,load= ,out= ); 
  FullAdder(a= ,b= ,c= ,sum= ,carry= );  
  HalfAdder(a= ,b= ,sum= , carry= ); 
  Inc16(in= ,out= ); 
  Keyboard(out= ); 
  Memory(in= ,load= ,address= ,out= ); 
  Mux16(a= ,b= ,sel= ,out= ); 
  Mux4Way16(a= ,b= ,c= ,d= ,sel= ,out= ); 
  Mux8Way16(a= ,b= ,c= ,d= ,e= ,f= ,g= ,h= ,sel= ,out= ); 
  Mux(a= ,b= ,sel= ,out= ); 
  Nand(a= ,b= ,out= ); 
  Not16(in= ,out= ); 
  Not(in= ,out= ); 
  Or16(a= ,b= ,out= ); 
  Or8Way(in= ,out= ); 
  Or(a= ,b= ,out= ); 
  PC(in= ,load= ,inc= ,reset= ,out= ); 
  RAM16K(in= ,load= ,address= ,out= ); 
  RAM4K(in= ,load= ,address= ,out= ); 
  RAM512(in= ,load= ,address= ,out= ); 
  RAM64(in= ,load= ,address= ,out= ); 
  RAM8(in= ,load= ,address= ,out= ); 
  Register(in= ,load= ,out= ); 
  ROM32K(address= ,out= ); 
  Screen(in= ,load= ,address= ,out= ); 
  Xor(a= ,b= ,out= );