コンピュータアーキテクチャの話 (45) 4004の設計を追体験する

　4ビット内部バスと各種レジスタ

　ブロックダイヤグラムに示すように、4004は背骨にあたる4ビット内部バスに各機能ユニットが接続された構造になっている。そして、内部バス制御表に示したように各ユニットからバスにデータを送り出し(SRC)たり、バスからデータを受け取ったり(DST)して処理を行っている。まず、この4004の中心となる4ビット内部バスとそれに繋がる各種レジスタを設計してみよう。

　次に示す図は4ビット内部バスに、外部との接続を行うデータバスバッファとTemp、OPR、OPAのようなレジスタの接続した構成の回路図である。アキュムレータACCの接続もほぼ同様であるが、ACCレジスタはバス以外にTempレジスタからの直接の入力があるので、D入力にマルチプレクサを必要とする点が若干異なっている。

　外部接続データバスバッファ、レジスタの4ビット内部バス接続

　FFはクロックが入ると必ずD入力からデータを取り込んで保持する回路であるが、論理設計をする場合、特定の条件だけでデータを取り込み、その他の場合には、以前の情報をそのまま保持したいという場合が多く存在する。このため、図の左上の灰色の箱に描いたように、エネーブル付きのFFを定義する。エネーブル付きのFFはD入力にマルチプレクサを持ち、 EN信号が"0"の場合はループバックのQを選択し、EN信号が"1"の場合にはD入力を選択して、クロックの立ち上がりでFFに保持する。この追体験設計では、オリジナルの4004とは異なり1相のクロックを用いるので、エネーブル付きのFFのクロックは常にΦ2であるので記載を省略する。

　レジスタは、このエネーブル付きFFと出力をバスに接続するトライステートバッファ 4組で構成されており、FFのエネーブルによりバスの情報を取り込むので、これがDST制御信号であり、バスをドライブするトライステートバッファのエネーブルがSRC制御信号で駆動される。

　外部ピンと接続するデータバスバッファは図の上側に描かれているように、両方向のトライステートバッファのペアで出来ている。外部ピンをドライブする側のトライステートバッファは論理回路図では同じ大きさで描かれているが、大きな負荷容量をドライブする必要があるので、物理的には大きなトランジスタが用いられている。

　データバスバッファがデータを受け取るのは外部ピンに出力するためであり、DST制御信号は外部ピンをドライブするトライステートバッファのエネーブルを行う。また、SRC制御信号は、外部ピンからの信号を 4ビット内部バスに載せるトライステートバッファのエネーブルを行う。

　コラムの第43回に掲載したバスの制御表を機能ユニット毎に整理すると、以下のようになる。ここでの記法は、:の左側にどのサイクルのDST信号、あるいはSRC信号かを示し、右側にその信号を"1"にする命令を書いている。

(1)データバスバッファ1stByte、2ndByte A1～A3 DST:全命令1stByte、2ndByte M1、M2 SRC:全命令1stByte X1 DST:全命令1stByte X2 SRC:IO read命令1stByte X2 DST:SRC、IO write命令1stByte X3 DST:SRC命令(2)Tempレジスタ1stByte X2 DST:JCN、JUN、JMS、INC、ISZ、ADD、SUB、LD、XCH、LDM、I/O read命令2ndByte X1 SRC:JUN、JMS命令(3)OPRレジスタ1stByte、2ndByte M1 DST:全命令2ndByte X3 SRC:全命令(4)OPAレジスタ1stByte、2ndByte M2 DST:全命令1stByte X1 SRC:全命令1stByte X2 SRC:JCN、JUN、JMS、BBL、LDM命令2ndByte X2 SRC:全命令(5)ACCレジスタ1stByte X2 DST:BBL命令1stByte X3 DST:ADD、SUB、LD、LDM、IO、ACC命令(6)インデックスレジスタ1stByte X2 SRC:INC、ISZ、ADD、SUB、LD、XCH命令1stByte X3 DST:INC、ISZ、XCH命令(7)Evenペアレジスタ1stByte X2 SRC:SRC、JIN命令2ndByte X2 DST:FIM、FIN命令(8)Oddペアレジスタ1stByte X3 SRC:SRC、JIN命令2ndByte X3 DST:FIM、FIN命令(9)PClow1stByte A1 SRC:全命令2ndByte A1 SRC:FIN命令以外の全命令1stByte X2 DST:JIN命令2ndByte X2 DST:JUN、JMS命令、条件成立の場合のJCN、ISZ命令(10)PCmid1stByte A2 SRC:全命令2ndByte A2 SRC:FIN命令以外の全命令1stByte X3 DST:JIN命令2ndByte X3 DST:JUN、JMS命令、条件成立の場合のJCN、ISZ命令(11)PChigh1stByte、2ndBye A3 SRC:全命令2ndByte X1 DST:JUN、JMS命令(12)RS1stByte X1 DST:全命令

　4ビット内部バスの制御は、以上の場合分けに従って、各ユニットのSRCとDST信号を作れば良い。

　なお、バス制御表のところで述べたように、インデックスレジスタを選択するためのRSレジスタへの書き込みが必要となるのはインデックスレジスタを使う命令だけである。しかし、インデックスレジスタを使わない命令では、どのインデックスレジスタが選択されていても問題ないので、制御信号の生成を簡単にするため、このように常にRSレジスタに書き込みを行う設計となっている。

　また、(7)、(8)にEvenレジスタペア、Oddペアレジスタという項がある。これはレジスタペアを扱うFIM、SRC、FIN、JIN命令では、レジスタ指定の最下位に相当するビットが命令種別の拡張に使われているので、 (7)の場合はRSレジスタの最下位ビットを強制的に"0"にし、(8)の場合はRSレジスタの最下位ビットを強制的に"1"にしてインデックスレジスタをアクセスすることを意味している。

　バスの制御信号は、次の図に示すように、命令の種別、命令の第一バイトの処理か第二バイトの処理か、そしてA1からX3のどのサイクルであるかの情報を生成し、それらを組み合わせてデータバスバッファやレジスタのSRC、DST信号を生成する。

　4ビット内部バス制御信号発生回路(一部分)デコーダとデータバスバッファのデータ受け取り(DST)信号の生成部分の回路を示す。

コンピュータアーキテクチャの話 (48) 4004の設計を追体験する

　

　FFを用いて設計したPCとスタックを次の図に示す。但し、これは4bit分であり、PClow、PCmid、PChighと、この回路を3個使ってPCとスタックを構成する。

　次の図において、一番上の行の4個のFFがPC、その下の行が順にスタック1、スタック2、スタック3となっており、スタックをプッシュすると、全ての行のFFは下の行にデータを転送する。そして、ポップの場合は、この逆で全ての行のFFは上の行にデータを転送するという構造により、スタックを実現している。

　4bit分のPCとスタック

　BUS0～3は4bit内部バスへの接続であり、PClow、PCmid、PChighともにBUS0はバスのBit-0、BUS1はバスのBit-1というように接続する。一方、PC0～3はインクリメンタへの出力であり、I-out0～3はインクリメンタの出力に接続する。そして、PClowのPC3～0とI-out3～0はインクリメンタの最下位4bit、PCmidは中位4bit、PChighは最上位4bitに接続する。

　またPC FFのQ出力はトライステートバッファを通して4bit内部バスに接続されており、このエネーブル信号は、PCがバスへの送り出し元となるSRC-PC信号に接続する。言わずもがなであるが、最下位の4bit分の制御信号はSRC-PClow信号、中位はSRC-PCmid信号、最上位はSRC-PChigh信号である。

　一番上のマルチプレクサを制御するPCF信号はPC FFへの入力の選択を行っており、"00"の場合にはマルチプレクサは右端のPCのQ出力の信号を選択するので、Φ2クロックが入っても同じ値が書き込まれ、結果として以前の状態を保持する。PCFが"01"の場合は右から2番目の信号を選択する。この信号はSTK1のQ出力であり、Φ2クロックが入るとスタックのPopとなる。

　PCFが"10"の場合はBUSが選択され、Φ2クロックが入るとバス上の情報がPCへ書き込まれる。また、PCFが"11"になるとI-outが選択され、インクリメンタの出力がPCに書き込まれ、結果としてPCが＋1されることになる。

　そして、STK1～3の各マルチプレクサを制御するSTKF制御信号が"00"の場合は、PCと同様に自分自身のQ出力が選択され、Φ2クロックが入っても以前の状態を保持する。STKF制御信号が"10"の状態でΦ2クロックが入ると、STK1はSTK2のQ出力、STK2はSTK3のQ出力が書き込まれ、結果としてスタックのPopを行い、STKF制御信号が"10"になると、STK1はPCのQ出力、STK2はSTK1のQ出力、STK3はSTK2のQ出力を書き込み、結果としてPushを行う。

　なお、この図ではSTK3のマルチプレクサのPopに対応する入力は"0"に接続しているので、Popを行うとSTK3にはゼロが入るという設計であるが、本物の4004では何が入るようになっているのかは不明である。

　ここまで作れば、残るのはPCFとSTKF信号を作り出す回路だけであるが、この回路は、次に示す簡単な回路で実現できる。

　PC、スタックの制御信号発生回路

　PCF1(上位ビット)はPCのインクリメントの場合と、バスからPCに内容を書き込む場合に"1"になれば良いので、PCをインクリメントするという信号とPCがバスのデスティネーションになるという信号のORを作れば良い。前に掲載した命令の動作を整理した表に示したように、PCはA3サイクルに＋1されるが、FIN命令の後半の8サイクルのケースだけが例外である。従って、これらの条件を2個の2入力NANDとインバータで生成しPC-Inc信号を作り、それとDST-PChigh信号をORすることによりPCF1high信号を作っている。また、PCF1mid、PCF1low信号も同様にDST-PCmid信号、DST-PClow信号とPC-Inc信号をORすることにより生成している。

　そしてPCF0(下位ビット)が"1"になるのはインクリメントのケースとPopのケースであるので、これらの信号のORで生成する。一方、STKFはPopとPushをそのまま使えば良いようにマルチプレクサの割り当てを行っているので、単純にこれらの信号を配線して使えばよい。PCF1信号はバスの信号の受け取りに関係するので、4ビット単位であり、high、mid、lowで異なる信号が必要になるが、PCF1とSTKF0、1信号はインクリメントやプッシュ、ポップのように12ビットを纏めて操作する場合に使われる信号であるので、high、mid、lowに共通に使用することができる。

コンピュータアーキテクチャの話 (47) 4004の設計を追体験する

　

　次にPCをインクリメント(+1)する回路を設計して見よう。

　PCの最下位のビットは元の値に"1"を加えるので、2進数の場合は、単純に値を反転すれば良い。そして、元の値が"1"であった場合は桁上がりを生じる。次のビットは桁上がりと元の値を加えるので、桁上がりが"0"なら何もせずそのままで、桁上がりが"1"の場合は値を反転し、かつ、元の値が"1"の場合は桁上がりを生じる。更に次のビットも同じである。

　まず、桁上がりが"1"の場合には値を反転するExclusive OR(排他的ORとも呼ぶが、以下ではXORと略記する)回路を作ろう。

　XOR回路

　この図のようにインバータ3個と2-2AND-OR-INV回路でXOR回路を構成する。XORは両方の入力が"1"あるいは"0"で一致している場合には"0"を出力し、その他の場合には"1"を出力する回路である。バイナリの加算では、0+0=0、桁上がりを無視すると1+1=0となり、その他は0+1=1、1+0=1であり、XOR回路は1ビットのバイナリの加算を行うことが出来る

　このXOR回路を用いて作った、簡単なリップルキャリー方式のインクリメンタの回路図を次の図に示す。

　リップルキャリー方式のPCインクリメンタ

　最下位ビットPC0は単純にインバータで値を反転して出力し、次のビットPC1はXOR回路を用いてPC0が"1"の場合は値を反転して出力する。また、PC0とPC1が共に"1"の場合には桁上げが生じるので、この桁上げ信号を2NANDとインバータで生成している。その次のPC2は、PC1の桁からの桁上げがある場合にはXOR回路で値を反転して出力し、次の桁への桁上げを2NANDとインバータで生成するというように、最上位ビットまで同じ回路を並べる。

　このインクリメンタでは、桁上げ(キャリー)が下位のPC0から上位にさざなみ(リップル)のように伝搬して行くのでリップルキャリー方式と呼ばれる。この方式ではPC0入力からI-out11出力までの間には各段でNAND一段とインバータが入り、最後にXORがあるので、21段のゲートを通過する。このコラムの第26回で説明したCMOSを使う場合のロジカルエフォートの理論で言えば、NANDが3/2、インバータがファンアウト2であるので、中間の各段のエフォートは3.5である。これが10段あり、そして最後のI-out11を計算する段のXORのエフォートは3であるので、トータルエフォートは38となる。これはファンアウト4のインバータのエフォート(FO4INV)の約10倍であり、1サイクルで十分実行できる程度の遅延時間である。

コンピュータアーキテクチャの話 (103) Newton-Raphson法とGoldschmidt法(2)

　Goldschmidt法

　もう一つの方法として、1/bをマクローリン級数で展開し、展開した各項を順に計算していくGoldschmidt(ゴールドシュミット)のアルゴリズムと呼ばれる方法がある。

　Goldschmidt法では、a/bを求めるに当たり、被除数aをx(0)とし、除数bをy(0)とする。そして、その逆数の近似値の初期値をr(0)として、x(i+1)=x(i)*r(i)、y(i+1)=y(i)*R(i) とr(i+1)=2-y(i+1)の計算を繰り返す。この繰り返しでy(n)=1となれば、x(n)がa/bの商となる。Newton-Raphson法とは原理は違うのであるが、1回の繰り返しには2回の乗算と1回の2の補数化が必要であり、また、ビット精度も繰り返しごとに2倍になるので、Newton-Raphson法とほぼ同じ手間で割り算ができる。しかし、詳細にみると、実装の観点からは、Goldschmidt法はNewton-Raphson 法より優れている。2の補数化の処理をサボって否定で代用すると、Newton-Raphson 法ではb*X(i)を計算し、それを否定してからx(i)を掛けるという処理となる。一方、Goldschmidt法では、y(i)を否定してr(i)を掛けるのと同時にx(i)にr(i)を掛けることが可能である。

　図27:Newton-Raphson法とGoldschmidt法による割り算。Newton-Raphson法では、乗算が直前の結果に依存するので、全て直列に実行する必要がある。一方、Goldschmidt法ではxとyの計算は独立であり、並行して計算できる。

　これを図にすると図27のようになり、乗算に必要なサイクル数をNとすると、1回のループ当たり、Newton-Raphson法では2N+1サイクルを必要とするのに対して、パイプライン乗算器を使うと、Goldschmidt法ではN+1サイクルとほほ半分の時間で処理が完了する。Goldschmidt法の浮動小数点割り算器はIBMの初期の超大型機であるSystem360/91で採用された。それ以降も、Goldschmidt法はIBMのG4メインフレームプロセサや、SunのUltraSPARCの前世代のSuperSPARCなどで採用されている。

　このIBM System360/91は、浮動小数点の掛け算を毎秒5.53M回、割り算は1.385M回実行することができた。現在のマイクロプロセサと比較すると、おおよそ1/1000の性能であるが、40年あまり前(1966年の発売)のマシンとしては驚異的な高性能であった。

　前述のように、単精度の除算を考えると計算時間がLog2(N)に比例するGoldschmidt法は不利であるが、IEEE 754rで追加が予定されている4倍精度の浮動小数点除算の場合は、逆に、計算ステップ数が仮数の長さNに比例するSRT法に較べて反復法が有利になる。 113ビット精度の仮数(ガードビットとラウンドビットを入れると115ビット)をSRT割り算器で計算すると、Radix-4の割り算器では58サイクル、Radix-16の割り算器でも29サイクルを必要とする。一方、Goldschmidt法では、2回の掛け算からなる繰り返しをもう一度追加すれば良い。1回の乗算を4サイクルとすると4回の反復を17サイクルで実行でき、IEEE 754rの4倍精度の時代になると、Goldschmidt法が、再度、復権する可能性があると思われる。

反復法による平方根の計算

　Newton-Raphson法やGoldschmidt法により商を求めたように、これらの反復法を用いて平方根を計算することもできる。Newton-Raphson法の場合は、平方根の初期値をテーブルなどで生成し、

　という計算を繰り返す。最終的にx(i)がaの平方根の逆数となると、x(i+1)はx(i)と同じになる。そうなると、最後にx(i+1)×aを計算すると、aの平方根が得られる。平方根の計算も割り算と同様に、繰り返しによりビット精度が倍増するので、8ビット精度の初期値からスタートすると、16ビット、32ビット、64ビットと3回の繰り返しで、IEEEの倍精度浮動小数点クラスの精度に到達する。しかし、割り算の場合はx(i+1)=x(i)×(2-b×x(i))であったので、各繰り返しステップの演算は、2回掛け算と1回の2の補数化で計算できたが、平方根の場合は3回の掛け算と1回の引き算が必要となるので、割り算よりも時間がかかる。

　Goldschmidt法では、x(0)=y(0)=aの初期状態から、z(i)=(3-y(i))/2、x(i+1)=x(i)×z(i)^2、y(i+1)=y(i)×z(i)を繰り返し計算する。ここでiの値にかかわらず、常にx(i)/y(i)^2=1/aであるので、繰り返しにより、x(i)が1.0になれば、y(i)はaの平方根となる。この計算も引き算が1回と3回の掛け算が必要であり、各ステップの計算量はNewton-Raphson法と同じであるが、最後の掛け算は不要である。

　また、 Newton-Raphson法では全ての計算が直前の計算結果をオペランドとするという依存関係があり全ての乗算をシリアルに実行する必要があるが、Goldschmidt法ではxとyの計算には依存関係が無いので、パイプライン乗算器を使う場合には、高速に計算できるというメリットがあるのは、割り算の場合と同様である。

コンピュータアーキテクチャの話 (50) 4004の設計を追体験する

　

　次の図に、ALUのブロックダイヤグラムを示す。ALUはバイナリの加減算を行うだけでなく、10進の加減算のアシスト、シフトやJCN命令の条件の成立、不成立の判定などを行う。ALUはこれらの動作を行うサブユニットの集合であり、要求された処理を行うサブユニットの出力をマルチプレクサMX-Oで選択してALUの出力とする。また、加減算を行うADDERは、命令によってオペランドとなるレジスタや定数が異なるので、その選択を行うためにMX-Y、MX-A、MX-Tの3つのマルチプレクサを設けている。

　ALUのブロックダイヤグラム

　CC Genサブユニットは、JCN命令の条件の成立、不成立を判定する特殊なユニットであり、詳細は後述する。

　NOTサブユニットは入力の論理否定値を出力するユニットであり、単純にインバータ 4個で構成することが出来る。Right Shift、Left ShiftはACCとYレジスタを繋いでリング状にシフトする処理を行うサブユニットであるが、単にビット位置を入れ替えて配線するだけで実現できる。

　バイナリエンコードは4ビットのワンホット信号("1"が1個だけの信号)をバイナリに変換するサブユニットであり、カルノーマップを書くと、次の図のようになる。元々の入力がワンホットで、1が2個以上ある組み合わせは存在ないと想定する。従ってカルノーマップの1が2個以上あるエントリは＊(Don’t Care:どちらの値が出力されても良い)として置く。そうすると、上位ビット(Bit2)のマップで"1"が出力されるのは、図において黄色で示した、ACCの下位2ビットが"00"のケースだけである。同様に緑で示した下位ビット(Bit1)の出力が"0"になるのは、ACCのビット3とビット1が"0"のケースだけである。従って、次のような簡単な回路で実現できる。

　キーボード信号のエンコードサブユニット

　ここではBit0出力は4個のいずれかのキーが押されているか否かを示すように、ACCの4ビットをANDしたものを出力する設計としている。このような仕様としたのは、複数のポートに分かれた多数のキーの押下をスキャンする場合には、ゼロでないポートがあれば、その中の一つのキーが押されたことを示し、押されたキーの番号はBit2、Bit1にバイナリエンコードされているので、右シフトすればバイナリ値が得られるという使い方を想定している。

　一方、キーが押されていない状態は、同様にゼロとして、ポートの中で押されたキー番号+1のバイナリ値を出力するという仕様も可能であり、この場合はキーの押されたポートの識別は同じであるが、バイナリへの変換は、右シフトの替わりに-1を行えば良い。

　4004のKBP命令がどのようなエンコードをするのかはデータシートには書かれていない。従って、どちらのエンコードが行われているか、あるいは全く異なる方式であるのかは不明であるが、ここに述べたエンコードは回路的に簡単であり、4004はこのようなエンコードを用いているのではなかろうか。