The Art of Computer Programming を読む(6)

ひょんなことから、書店で "The Art of Computer Programming Volume 1, Fascicle 1: MMIX - A RISC Computer for the New Millennium" を見つけ、購入することができた。

TAOCP Vol.1 1.3 MIXには、次の記載がある。

MIXが現在ではすっかり時代遅れであることは認めなければならない。したがって、MIXは本書の次の版でMMIX, 2009型、という新しい機械にとって代わられるであろう。MMIXは、1ワードを64ビットで計算する、いわゆる縮小命令セットコンピュータ (RISC) になるであろう。それはMIXよりさらに魅力的であり、1990年代に広く使われるようになったコンピュータに似たものになるであろう。

まさに、TAOCP Vol.1のMMIX版が、本書 Fascicle 1 である。

本書が書店でほぼ定価で購入できたことは誠に僥倖であった。Amazonではそもそも在庫がなくマーケットプレイス新品は定価の9倍の値段、中古でも定価より高いものだけという状況である。神に感謝しよう。

Fascicle 1は、1.3のMMIX版である1.3'と、1.4のMMIX版である1.4'から成る。せっかくなので、MIXとMMIXを比較しながら読み進めていこうと思う。

今回は1.3.1'. MMIXの解説から。

ビットとバイト

(1)の記事も見比べるとよくわかる。

MIXではまずビットという概念が存在しなかった。バイトの大きさが決まっていなかったので、二進法を使えばbit、十進法を使えばdigit、三進法を使えばtrit(!?)というわけである。ただし、バイトは、少なくとも64通りの値を、多くても100通り以下の値までを区別することができる必要があった。

MMIXでは二進数を使うことが確定しており、ビットの概念が導入された。これに伴い、バイトは8個のビットの列となった。2^8 = 256であるから、256通りの値を区別できる。MIXの制限は超えていることになる。

あわせて、MMIXではワイド(=2バイト)、テトラバイト(=4バイト)、オクタバイト(=8バイト)という言葉も導入されている。

MMIXでは、整数は2の補数を使って表現することが定められている。今日のコンピュータで使われる方法と同じだ。MIXではバイトの実装方法が決まっていなかったので「何バイトで何桁の整数が表現できる」ということだけ利用してプログラムを書いていた。具体的な整数表現の話に入れたのは、2進数を使うと決めたからである。

とはいえ依然としてビットの概念なしにバイトを使ってプログラムするMIXを勉強したことは、抽象的にプログラムするということを強制し、自分にとっては抽象思考のための有益なトレーニングであると思う。

メモリとレジスタ

MIXでは、4000個のメモリセル、9個のレジスタ、オーバーフロートグル、比較表示器があった。

MMIXでは、2^64個のメモリセル、2^8=256個の汎用レジスタ、2^5=32個の専用レジスタが備わった。メモリのセル一つは1バイトを表すので、メモリは2^64バイトある。レジスタは一つでオクタバイト(8バイト)を保持する。
まず、汎用レジスタという概念に対応するものは、MIXにはなかったと思う(専用レジスタについては、MIXのレジスタ・オーバーフロートグル・比較表示器の果たしていた役割を、MMIXの専用レジスタの対応するものが果たしていると言える)。rA, rXが汎用レジスタだろうか。
そして、膨大になったメモリセル、レジスタが印象的だ。専用レジスタだけで32個もあるということは、命令セットも大きく変わっていることが予想される。そして実際その通りだ。

命令

MIXの命令は、メモリのセルの大きさと同じく5バイトと1符号で成っていた。

MMIXの命令は、テトラバイト、つまり4バイトからなる。
オペコード、第一オペラント、第二オペラント、第三オペラント、である。

ロードとストア命令

MIXの時は、ロードするのはワードと決まっており、1ワードは5バイトと1符号から成っていた。ロード命令は、ロード先のレジスタによって種類があった。LDAならrAへのロード、LDXならrXへのロード、といった具合である

LDA 1000      # メモリの1000番地のワードをrAにロード
LDX 2000,1(3:5) # メモリの2000番地をrI1で修飾した番地のワードの3バイト〜5バイトをrXにロード

しかし、MMIXは、まずロード命令の種類がロードする情報のサイズによって、つまりバイトかワイドかテトラかオクタかで分かれている(LDB, LDW, LDT, LDO)。これは、MIX命令でのFフィールドに相当する役割と考えて良いだろう。次に、ロード命令はオペラントを3つ取る。

LDB $1,$2,$3

であれば、$2で指定した番地を$3で修飾した番地を$1にロードする。明らかに$2はMIXの命令のAAフィールド、$3はMIXのインデックスレジスタに相当する役割だ。MIXと同様符号なしロード命令も存在する。

MIXでは、ロード命令はレジスタの右側にシフトして詰められるという仕様だった。MMIXでもこれは同じだが、MMIXではレジスタの左半分にテトラをロードする命令が存在する (LDHT)。

MMIXにもLDAという命令は存在するが、これはMIXのLDAとは全く異なる。第二・第三オペラントのアドレスを、メモリのコンテンツではなくアドレスそのものをロードする命令である (AはAddressのA)。MIXのアドレス転送命令ENTA, ENTX, ...が対応するように思う。

ストア命令は、ロード命令の逆。

数値演算命令

MIXの数値演算命令は、常にrAに対してメモリセル上のコンテンツを足す、引く、掛ける・割る、といった操作を行い、結果もrAに格納された (掛け算はrAとrX)。

MMIXは、レジスタとレジスタのコンテンツを演算する。ここはMIXと大きく異なる点である。MIXでは演算時間はほぼメモリセルの参照回数で決まっていたことを思い返すと、ましてやメモリのサイズが2^64になったのだから、数値演算の際のメモリの参照回数を減らすことは妥当だろう。

ADD $1,$2,$3

と書いた時、$2と$3の和を$1に代入する。もちろんオーバーフローが起きる可能性がある。オーバーフローが発生したときはオーバーフローシグナルが発生する。オーバーフローシグナルはシステムへの割り込みとして対処する。MIXではオーバーフロートグルの状態を確認してジャンプする JOV, JNOV を使っていたが、まったく異なる仕組みがMMIXには備わっている。

除算の剰余は剰余レジスタrRに入る。演算は、符号付演算と符号なし演算が別々に定義されている。符号なし乗算の上位8バイトは乗算上位レジスタrHに入る。符号なし除算の被除数の上位8バイトは被除数レジスタrDに配置してから演算する。

符号なし加算命令ADDUには特殊な亜種がある。2をかけてから符号なしで加算 (2ADDU), 4をかけてから符号なしで加算 (4ADDU) などである。これは、単純な乗算よりも高速に実行できるので、高速化のために準備された命令のようだ。

比較命令は、MIXでは比較結果を比較表示器にセットしていたのに対し、MMIXでは第一オペラントのレジスタにセットする。小さいか等しいか大きいかによって -1, 0, 1 を割り当てる。

条件命令

MIXにはなかった概念だ。

第二オペラントのレジスタの値が正か負か0かによって、第三オペラントのレジスタの値を第一オペラントのレジスタに代入するかどうかを変化する命令が定義されている。ジャンプを使わずに1命令で分岐ができるので便利だ。

ビット単位命令・バイト単位命令

これもMIXにはなかった概念。

ビット単位命令では、いわゆるブール代数の演算が用意されている。

バイト単位命令では、ビットの行列のようなもの(ブール行列)を考えて、ブール行列同士の演算を行うことに相当する。行列演算相当と考えると、これは数値計算上重要な役割を果たしそうだ。

浮動小数点演算命令

MIXにも浮動小数点演算命令は存在した。命令のFフィールドの値を6にすることで整数演算命令が浮動小数点演算命令になっていた。

MMIXは、IEEE/ANSI Standard 754で定義されている浮動小数点命令を全て実装している。

浮動小数点演算命令は、元のTAOCP Vol.1でもまだ触れられていない領域なので、Fascicle 1でも省略されている。

即値

プログラムで使う小さな値の定数を即座に取り出すための命令。これらの命令をうまく使うことで、メモリにまったくアクセスせずに任意の値をレジスタに設定できる。

MIXのENTやINCが相当するだろうか。

ジャンプと分岐

MMIXのジャンプは、JMPとGOの二つがある。
JMP命令は、現在実行している命令の番地からの相対番地でジャンプ先を指定する。
GO命令は、任意の絶対番地でジャンプ先を指定する。その際に、GOしなければ実行されたであろう番地を第一オペラントのレジスタに格納する。

MIXではジャンプ専用のレジスタがあったが、MMIXでは存在しない。ただし、サブルーティンコールや割り込みが発生した時にジャンプ元をrJにストアするという仕組みはあるようだ。

分岐命令は、MIXの条件付きジャンプ命令に等しい。ただし、見込み分岐命令というのがあり、これは分岐が起こる場合が半分以上ある時に使うとより高速に動作する、というものである。これはMIXにはなかった概念だ。

時間計測

MIXの命令実行時間は、ほぼメモリとレジスタの転送回数で決まっていた。

MMIXになると、レジスタ数も多くメモリに至っては途方もないセル数あるので、それぞれオーダーを区別する必要がありそうだ。CPUのクロックサイクル時間の単位のυとメモリ参照時間の単位のμの二つの単位時間から、命令の実行時間を算出している。


サブルーティンコール・システムへの配慮・割り込み、などオペレーティングシステムを考える上で大変興味深いトピックも残っているが、発展的な内容ということだったので今回はここまでとする。また1.4を読んだら戻ってくることにする。

1.3.2の続きから、本体のVol.1に戻りつつ、適宜Fascicleの記述も確認するというスタイルで読み進めていこうと思う。


この記事が気に入ったらサポートをしてみませんか?