パタヘネ3章の途中までです。算術演算はALUとシフト演算を使ってどのように実装されているのかが解説されています。
3.1
イントロのため割愛
3.2
ビット列で表される符号付き整数を2進数で加算できるALUという装置がある。この装置で加算と減算を行ったとき、コンピュータは有限の桁数しか保持できないので、オーバーフローが起こりうる。オーバーフローが起こったことを検知するにはどうすればいいだろうか？符号付き整数では最上位ビットが符号を表すため、大きな数同士を加算すると本来符号を表す最上位ビットにまで繰り上がりで値が入ってきてしまい、符号付きで数値を解釈すると負の値となる。負の数同士なら、絶対値として大きな数同士を足し合わせると正の値になる。加算においては、異符号の数値同士を足し合わせると必ず絶対値として小さくなるので、オーバーフローが起こらない。反対に、減算でオーバーフローが起こる場合は、絶対値の大きな異符号の数値同士を減算する場合となる。
オーバーフローが起こったとき、MIPSでは符号付き加算・減算では例外が発生する。符号なしの場合は例外は発生しない。C言語ではオーバーフローを無視するので、コンパイラは変数のタイプによらず符号なし演算の命令を選択する。
3.3
加減算は以上のように行われるが、乗算をALUとビットシフトで実装することを考える。乗算の計算方法は筆算を思い出すと分かる通り、乗数の低い桁から順に見ていき、0か1かに応じて被乗数を最終結果に加算していく。加算する際に、今乗数のi bit目を見ているなら被乗数をiビットシフトさせてから足す。乗数と被乗数が32ビット同士である場合、積は最大で64ビットとなるので、積を入れるレジスタは64ビット幅となる。以上より32ビットの乗数、被乗数、64ビットの積、制御判定部からなるシステムで乗算を実装できる。
上記より更にレジスタを節約する方法として、積の64ビットレジスタの下位32ビットを乗数で初期化し、上位32ビット目から積本体を入れる方法も存在する。この場合計算対象の桁を進めるごとに積レジスタを右にシフトしていく。最終的にもともと下位32ビットに入っていた乗数は消え去り、積レジスタには計算結果のみが残る。被乗数が左シフトされる代わりに積が右シフトされるので、概念的に前述の筆算ハードウェアと同じことを行っている。
更に高速化するためには、乗数をビットごとの和の形(0001+0010+0100+1000のような形)で書き、被乗数と各桁の積を0001×a+0010×a+…のように計算する。次に、各項を2個ずつの組とし、各組の2数の和を並列で計算する。計算された和を更に2個ずつの組とし、…と階層的に計算を行う。こうすることで32ビットなら5ステップで積を求める事ができる。
符号への対処に関しては、まず乗数・被乗数の符号を記憶しておき、次にそれぞれの符号を正に揃える。正の数同士の乗算を行ったあと、覚えておいた符号に応じて結果の符号を決定する。
3.4
除算でも筆算をベースとして計算を実装する。除数をまず32ビット左シフトしておき、被除数から除数を減算する。減算結果が正ならば商のビットを立てる。負であるなら減算した除数を被除数に足し戻す。次に除数を右に1ビットシフトし、商を左に1ビットシフトする。これを除数が0になるまで繰り返す。これを実装するためには除数、ALU、被除数がすべて64ビット必要となる。商は32ビットで足りる。
除算回路を最適化する方法として、剰余レジスタの上位32ビットを被除数で初期化し、下位32ビットを商に使うというものがある。
符号付き除算の場合、符号付き乗算の場合と同様、予め符号を覚えておいて絶対値の除算を行ったあと商の符号を決定するという方法で実装できる。ただし、数学的には剰余の符号の決め方に任意性があるので、被除数と剰余の符号が一致しなければならないという規則を導入して一意に結果が決まるようにする。
除算回路を更に高速化する方法としては、SRT除算という技法を使うことができる。この技法では参照表を利用して商の予測をおこない、間違っていたら後で訂正するという方法を使用する。
3.5
コンピュータで実数を表す場合、浮動小数点が用いられる。科学記数法のように、実数をx×2^yの形で表す。ただしxの部分は1.○○○の形式でなければならないという制約を設ける。このとき、xの部分とyの部分がわかれば実数を表現でき、浮動小数点では32ビットを区切ってxとyの部分を表現する。まずxの符号は最上位ビットで決定される。最上位ビットに引き続くのはyの部分に対応する指数部、残りの部分はxの絶対値を表す仮数部である。単精度浮動小数点数では指数部8ビット、仮数部23ビットである。倍精度浮動小数点数では指数部11ビット、仮数部52ビットである。また、仮数部の最上位のビットが必ず1になるのにそれを表すためにビットを使うのは無駄である。そのためIEEE754浮動小数点規格では、最上位の1ビットは暗黙的に存在するものとして仮数部はそれより下の桁だけを表現するようにしている。
また、浮動小数点数を整数と同じ比較回路で比較しようとした場合、指数部の符号の表現の仕方が問題となる。単精度浮動小数点数で考える。整数と同じように2の補数で符号を表現した場合、-1が11111111となり、単精度浮動小数点数全体を整数として解釈したら非常に大きな数に見えてしまう。そのため、指数部の大小が整数として解釈した場合と一致するよう、下駄履き表現という手法を使う。この手法では、指数部の8ビットを通常の整数として解釈した値から、127を引いた値が指数部の値であるとする。こうすることで整数と同じ大小比較ができる。なお、符号が最上位ビットであったり、指数部が仮数部より高いビットにあるのも、大小比較のためである。
浮動小数点数の加算の場合、桁が違っていることに対処しなければならない。そのために、小さい方の数値の指数を大きい方にあわせ、仮数部を右にシフトする。精度的に保持できない桁は捨てる。次に仮数部同士を整数の加算と同様にビットごとに足す。結果が精度的に保持できないなら丸めを行う。足した結果が1.○○○の正規化された形にならない事があるので、最後に正規化を行う。正規化の結果桁数が不足するようなら再度丸めを行う。
浮動小数点数の乗算では、指数部も関わってくる。指数法則から指数部同士の加算も必要となる。単純に整数として足し算すると下駄履き表現の下駄を2重に履かせている状態となるので、単純な整数としての加算後127を加える。次に仮数部をかけ合わせ、正規化する。桁があふれるぶんは丸める。計算結果の符号は元の数値の符号から決める。
MIPSでは浮動小数点数用のレジスタが存在しており、それらを扱う命令も存在する。また、倍精度浮動小数点数は2個の単精度浮動小数点数レジスタを結合したものとして表現される。そのため、倍精度浮動小数点数は偶数番の浮動小数レジスタでしか利用できない。
有限の桁数しか保持できないため、丸め方が計算精度に効いてくる。IEEE754では途中計算では2桁余分に保持するよう規定している。1桁目をガード桁、2桁目を丸め桁という。
コメント