[ 目次, 前節, 次節, 索引 ]

   レジスタと演算を記述して計算機のデータパスを定義する. レジスタを記述するには, 名前を与え, それへの代入を制御するボタンを指定する. これらのボタンのそれぞれに名前を与え, ボタンの制御でこのレジスタに入るデータの源を指定する. (源はレジスタか定数か演算である.) 演算を記述するには, それに名前を与え, その入力(レジスタか定数)を指定する.

   計算機の制御器は, 列への 入り口(entry points)を識別する ラベル(labels)と共に, 命令(instructions)の列として定義する. 命令は次のものの一つである:

• それを押すとレジスタへ値を代入するデータパスのボタンの名前 (制御図の箱に対応する)

• 指定したテストを実行するtest命令

• 直前のテストの結果に基づく, 制御器ラベルで指示した場所への条件つき分岐 (branch命令) (テストと分岐と合せて制御図の菱形に対応する.) テストが偽なら, 制御器は列での次の命令を続ける. そうでなければ, 制御器はラベルの後の命令から続ける.

• 制御器のラベルを名指した無条件分岐 (goto命令) そこから実行を続ける.

計算機は制御器命令列の先頭から出発し, 実行が列の終りに達した時, 停止する. 分岐が制御の流れを変えた時以外, 命令はリストした順に実行する.

(data-paths
 (registers
  ((name a)
   (buttons ((name a<-b) (source (register b)))))
  ((name b)
   (buttons ((name b<-t) (source (register t)))))
  ((name t)
   (buttons ((name t<-r) (source (operation rem))))))

 (operations
  ((name rem)
   (inputs (register a) (register b)))
  ((name =)
   (inputs (register b) (constant 0)))))

(controller
 test-b                           ; ラベル
   (test =)                       ; テスト
   (branch (label gcd-done))      ; 条件分岐
   (t<-r)                         ; ボタン押す
   (a<-b)                         ; ボタン押す
   (b<-t)                         ; ボタン押す
   (goto (label test-b))          ; 無条件分岐
 gcd-done)                        ; ラベル

   図5.3はこのように記述したGCD計算機を示す. GCD計算機は, 各レジスタは唯一つのボタンしかなく, 各ボタンとテストは制御器で唯一回だけ使われるという, 非常に単純な場合なので, この例はこれらの記述の一般性を示唆するに過ぎない.

   困ったことにこういう記述は読むのが難しい. 制御器の命令を理解するには, 常にボタンの名前, 演算の名前の定義を見直さなければならず, ボタンが何をするかを理解するには, 演算の名前の定義を見なければならない. そこで記法を変更し, データパスと制御器の情報を組み合せ, すべてが一度に見えるようにする.

   そういう形の記述を得るには, 任意のボタンと演算の名前を, その振舞いの定義で取り替える. つまり(制御器で)「ボタンt<-rを押せ」といい, 別に(データパスで) 「ボタンt<-rはrem演算の値をレジスタtに代入する」とか「rem演算の入力はレジスタaとbの内容である」という代りに, (制御器で)「レジスタaとbの内容のrem演算の値をレジスタt に代入するボタンを押せ」といおう. 同様に(制御器で)「=テストを実行せよ」といい, 別に(データパスで)「=テストはレジスタbの内容と定数0に操作する」という代りに, 「レジスタbの内容と定数0に=テストを実行せよ」といおう. データパスの記述をやめ, 制御器の列だけを残す. そこでGCD計算機は次のように記述する.

(controller
 test-b
   (test (op =) (reg b) (const 0))
   (branch (label gcd-done))
   (assign t (op rem) (reg a) (reg b))
   (assign a (reg b))
   (assign b (reg t))
   (goto (label test-b))
 gcd-done)

   この形の記述は図5.3に示したようなものより読みやすいが欠点もある:

• 大きい計算機では冗長である. データパスの要素が, 制御器の命令列に現れる時, その要素の完全な記述が繰り返される. (各演算とボタンは唯一回しか使われないので, これはGCD計算機の例では問題にならない.) その上, データパスの記述を繰り返すと, 計算機の実際のデータパス構造が不明瞭になる; 大きい計算機では, レジスタ, 演算やボタンがいくつあるか, それらがどう接続されているかがはっきりしない.

• 計算機定義での制御器の命令がLisp式のように見えるため, それが何かLisp の式ではないということを忘れそうになる. それらは, 正当な機械演算を表すだけである. 例えば演算は定数とレジスタの内容に対して直接操作出来るだけで, 他の演算の結果には操作出来ない.

これらの欠点にも拘らず, データパスの要素や接続を理解するより, 制御器の理解の方に関心があるので, このレジスタ計算機の言語を本章を通じて使うことにする. しかし実際の計算機の設計では, データパスの設計が重要なことを心に留めよう.

問題 5.2

レジスタ計算機言語を使い, 問題5.1の反復的な階乗計算機を記述せよ.

働き

   readはレジスタに格納し得る値を生じるという点で, われわれが使ってきた演算によく似ている. しかしreadは入力をレジスタからは取らない; その値は設計中の計算機の外で起きる何ものかに依存する. われわれの計算機の演算にそう振舞うことを許し, 従ってreadの使用を, 値を計算する他の演算に対するのと同じように描き記述するようにしよう.

   他方printは使ってきた演算と基本的に違っている: レジスタに格納すべき出力値は生じない. それは効果も持つが, この効果は設計している計算機の一部ではない. この種の演算を働き(action)と呼ぼう. データパス図では働きを, 値を計算する演算を表したのと同様に---働きの名前を含む台形として---表そう. 矢印は入力(レジスタか定数)から働きの箱を指す. また働きにボタンも対応させる. ボタンを押すと働きが起きる. 制御器に働きのボタンを押させるため, performという新しい種類の命令を使う. そこでレジスタa の内容を印字する働きは, 制御器の列では命令

(perform (op print) (reg a))

   図5.4は新しいGCD計算機のデータパスと制御器を示す. 答を印字した後で計算機を停止させる代りに, 繰り返し一対の整数を読み込み, そのGCDを計算し, 結果が印字出来るよう, もう一度出発させるようにした. この構造は, 4章の解釈系で使った駆動ループに似ている.

 (controller
  gcd-loop
    (assign a (op read))
    (assign b (op read))
  test-b
    (test (op =) (reg b) (const 0))
    (branch (label gcd-done))
    (assign t (op rem) (reg a) (reg b))
    (assign a (reg b))
    (assign b (reg t))
    (goto (label test-b))
  gcd-done
    (perform (op print) (reg a))
    (goto (label gcd-loop)))

1 この仮定は, 大量の複雑さをやり過す. 通常Lispシステムの実装のかなりの部分は, 読込みと印字の仕事に費やされる.

[ 目次, 前節, 次節, 索引 ]