パタヘネ３章 1~5 コンピュータにおける算術演算

#3.1 はじめに

###本章の目的

• 実数および少数の表し方
• 表せる最大値よりも演算結果が大きくなってしまった時の対処
• コンピュータハードウェアにおいての四則演算

この章でやること

• 加算、減算、乗算、除算、浮動小数点、SIMDを少し

#3.2 加算と減算

###加算

• コンピュータで行う自然な演算 : 足し算
• 数値の各ビットを右から左へ順に加えていき、繰り上げがあれば左隣へ加える

###減算

• 引き算
• 引く数を正負反転してから加算するという考え方もできる

$7_{10}$から$6_{10}$を引く演算

-6の2の歩数表現を使った加算

###オーバフローとは

• 用意されたハードウェアに演算の結果が収まらない場合に発生

#####オーバフローにならない加算減算

• 加算対象の２つの数値の符号が異なる場合にはオーバフローは起こりえない
• 減算対象の２つの数値の符号が同じ場合にはオーバフローは起こりえない

####オーバフローになる加算減算

• 2つの正の数を加算するとき/2つの負の数を加算した時
  • 符号ビットが不正な値になる

####符号なし整数のオーバフロー

• 符号なし整数は一般にメモリやアドレス用に使用される
• 状況に応じてオーバフローを認識したり、逆に無視したりできるような手段が必要
  • add, addi, subなどの命令ではオーバフロー時に例外が発生する
  • addu, addiu, subuなどの命令はオーバフローが起こっても例外は発生しない

####ハードウェアとソフトウェアのインタフェース

• コンピュータ設計者はオーバフローが発生した時の措置を決めなければならない
• MIPS: オーバフローを例外(exception)の形で提示する
  • オーバフローを引き起こした命令のアドレスをレジスタに待避
  • あらかじめ設定されているアドレスに制御を移す
  • 例外処理ルーチンが起動

MIPSのオーバフロー検出

• 符号あり加算
  • slt = set less than ( slt t3, t3, zero ) -> if t3 < zero, t3 = 1, otherwise t3 = 0
  • ３行目　足す数、足される数、２つの符号が不一致か判別
  • ７行目　３つの符号が不一致か判定
    • 足す数、足される数の符号が同じ場合、足す数、足される数、答え、３つの符号は一致していなければいけない
      • a + b = c において、a と b　が同じ符号の場合、cもそれと同じ符号でなくてはならない

• 符号なし加算

####まとめ

• コンピュータの語のサイズが有限であれば、算術演算結果がその語に収まらなくなる場合がある
• 今日のコンピュータはすべてオーバフローを検出する何らかの方法を持っている

3.3 乗算

乗算の演算

• 被乗数 x 乗数 = 積
• 被乗数 nビットと乗数 mビットを掛けると積の最大の長さは m+nビットとなる

乗算アルゴリズムとハードウェアの直列バージョン

• 32ビットの被乗数は最初は被乗数レジスタの右半分に置かれ、乗算ステップごとに１ビット左にシフトされる
• 乗算は乗算ステップごとに１ビット右にシフトされる
• 制御部: シフトのタイミングと積レジスタに書き込むタイミングをコントロール

第１の乗算アルゴリズム

2 x 3の計算

乗算ハードウェアの改善バージョン

• 被乗数、ALU、乗数レジスタは32bit
• 演算処理を並列に進めて高速化する
  • 乗算bitが1の場合に被乗算を積に加算 + 被乗数をシフトする

符号付きの乗算

• 乗数と被乗数を正の数に変換
• 両方の符号を記憶
• 処理サイクルを31回繰り返す
• 乗数と被乗数の符号が違う場合のみ、積の符号を負にする

乗算の高速化

• 右側の加算器の出力を左側の加算器の入力に接続
• 設計をパイプライン化し、多くの加算を同時に実行する　(4章)

MIPSにおける乗算

• 64bitの積を保持するために２つ１組の32bitを当てている (レジスタ Hi, Lo)
• MIPSではオーバフローは無視される
  • ソフトウェアで検出する必要がある

まとめ

• 乗算はシフトと加算によって行われる
• 加算を並列に進めて、速度を速めることもできる

3.4 除算

除算の演算

• 被除数 = 商 x 除数 + 余剰

除算アルゴリズムとハードウェア

上のハードウェアを使用した、除算アルゴリズム

7/2 の計算

改善バージョンの除算ハードウェア

符号付き除算

• 除数と被除数の符号を記憶して、両者が異なる場合に商の符号を負にする

除算の高速化

• 乗算の場合は32個の部分的な積を即座に算出できる
• 除算の場合、計算の次のステップの前に減算結果の符号を知る必要がある
• SRT除算

MIPSにおける除算

• 乗算と似た設計
• Hiレジスタに剰余、Loレジスタに商が納められる

3.5 浮動小数点演算

• 実数: 実際にあると確かめた数量

• 科学記数法(scientific notation) : 小数点の左側には数字を一つしか書かない

  • $ 1.0_{10} \times 10^{-9} $ ($0.000000001_{10}$)

• 正規化数(normalized number) : 科学記数法で書いた数値で先頭に0が来ないもの

  • $3.15576_{10} \times 10^9$

• 浮動小数点形式

  • コンピュータ世界における少数
  • 計算で誤差が発生することを前提としている
  • 1.xxxx が仮数、2が基数、yyyyが指数
    
  • 利点
    • データの交換が単純になる
    • 浮動小数点演算アルゴリズムが単純化される
    • １語に格納できる数値の精度を上げることができる

####浮動小数点形式の数値の表現

• 式: $ (-1)^S \times 仮数 \times 2^{指数}$
• 範囲:

####アンダフロー

• 負の指数が大きすぎて指数部に収まりきらない

倍精度

• 範囲:
  • $ 2.0 \times 10^{308} $ ~ $2.0 \times 10^{-308} $

IEEE754浮動小数点規格

• 浮動小数点数の計算で最も広く採用されている標準規格
• 1980年以降に開発されたほぼすべてのコンピュータに導入されている
  • 正規化された２進数の先頭の１を仮数フィールドの中に持たない
    • 単精度の実際の長さ: 1(暗黙の１) + 23
    • 倍精度の実際の長さ: 1 + 52
    • 仮数が0の場合はハードウェアの設定で１を付与しないようにする
• 無効な演算操作 非数(NaN - Not a Number)
  • ０を０で割った場合や無限大から無限大を引いた場合
• 整数との共通性
  • 符号が最上位bitを占めている
    • ０より大きいか小さいか等しいかの判定が素早くできる

ゲタばき表現

• なぜこのような表現を使うのか

$ 1.0_{2} \times 2^{-1} $の表現 ～ 負の指数が大きな数字に見えてしまう

$ 1.0_{2} \times 2^{1} $の表現 ～ とても小さい数字に見えてしまう

• 最も小さい負の数を $00...00_{2}$, 最も大きな数を $11..11_{2}$と表したい

$ (-1)^S \times (1 +仮数) \times 2^{(指数-ゲタ)} $

• 単精度のゲタ: 127, 倍精度のゲタ: 1023
  • 範囲:
    • 最小値: $ - 1.0000 0000 0000 0000 0000 000_{2} \times 2^{-126 or -1022} $
    • 最大値: $ 1.1111 1111 1111 1111 1111 111_{2} \times 2^{127 or 1023} $

例: -0.75を単精度と倍精度で示せ

$3/4_{10} = -3/2_{10}$
$-11_{2}/2^2_{10} = -0.11_{2}$
$-1.1_{2} \times 2 ^{-1} $
$ (-1)^1 \times (1 + 1.0000 0000 0000 0000 0000 000_{2}) \times 2^{(126 - 127)}$