算術論理演算ユニットの設計 ( 教科書 4.5 節 )
yi = fi (x, x2, x3,..., xm) (for i n) 基本的な組合せ論理回路 : インバータ,AND ゲート,OR ゲート, y n 組合せ論理回路 ( 復習 ) 組合せ論理回路 : 出力値が入力値のみの関数となっている論理回路. 論理関数 f: {, } m {, } n を実現.( フィードバック ループや記憶回路を含まない ) x x 2 y y 2 x m XOR ゲートなど.
ANDゲート b y b y 組合せ論理回路 ( 復習 ) b OR ゲート y b y y NOTゲート ( インバータ ) y XORゲート b y b y b c b c y マルチプレクサ ( 選択回路 ) y
順序回路 ( 復習 ) 順序回路 : 出力値が, 入力値と回路の状態値の関数となっている論理回路. また, 次状態値も入力値と回路の現状態値の関数となっている. 順序機械 M=(I, O, S, δ, λ) を実現. x x 2 y y 2 x m 回路 記憶回路 y n 組合せ s s 2 sp I: 入力集合 O: 出力集合 S: 状態集合 δ: 状態遷移関数 λ: 出力関数 y i = f i (x, x 2,..., x m, s, s 2,..., s p ) (for i n) s j = g j (x, x 2,..., x m, s, s 2,..., s p ) (for j p)
同期式順序回路 ( 復習 ) 同期回路 : クロックに同期して動作する順序論理回路. クロックの立ち上がり時の入力と状態で, 次回クロックが立ち上がるまでの出力と状態を確定. 組合せ論理回路 記憶回路組合せ論理回路 記憶回路組合せ論理回路 記憶回路クロック 信号 代表的なクロック同期式記憶回路 :D フリップフロップ CLK D D CLK Q Q
算術演算や論理演算を実行する. プログラムの命令とデータを格納. デコーダ 算術論理演算ユニット ALU ALU プロセッサ 主記憶 データバス PC レジスタ アドレスバス *) 本講義では,XOR ならびにシフト演算は省略する ALU で計算されるデータを記憶する. データは主記憶から読み込まれ, 主記憶に書き戻される. ALU: Arithmetic Logic Unit 機能 (32 ビット演算 ) 論理演算 (AND,OR,XOR など ) 算術演算 ( 加算, 減算, 比較など ) シフト演算 基本構成部品 NOT ゲート ( インバータ ) AND/OR/XOR ゲート マルチプレクサ
ビット論理演算器を設計してみよう! 仕様 入力 :, b, ( 各 ビット ) 出力 :y( ビット ) 機能, b に対しる AND か OR の論理演算 により操作 (AND か OR か ) を決定 基本的な考え方 論理積 (AND) と論理和 (OR) の両方を並列に求める 信号の値に基づき何れか一方を選択してyへ出力する ( 操作 ) b y ( 出力 ) マルチプレクサ 真理値表 b y ( & b) ( & b) ( & b) ( & b) ( or b) ( or b) ( or b) ( or b)
32 ビット論理演算器の設計 () オペランドのビットごとに AND や OR をとる b y ( 出力 ) [3] [3] [2] [] [] ( 操作 ) 論理積の場合 ( 信号が )
32 ビット論理演算器の設計 (2) オペランドのビットごとに AND や OR をとる b y ( 出力 ) [3] [3] [2] [] [] ( 操作 ) 論理和の場合 ( 信号が )
仕様 ビット加算器を設計してみよう!() 入力 :, b, ( 各 ビット ) 出力 :s, ( 各 ビット ) 機能 入力,b, ならびに, 下の桁からの桁上がり () を加算 和 (s) と上の桁への桁上がり () を出力 出力 : 上位への桁上げ () キャリー アウト ) 出力 : 和 (s) 入力 : 下位からの桁上げ () b キャリー イン 入力 : 足される数 ( と b)
ビット加算器を設計してみよう!(2) b s ビット全加算器 s と の積和標準形 = b = b ( 和 ) s ( キャリー イン ) ( キャリー アウト ) b b 真理値表 b s b b b b
32 ビット加算器の設計 ビット加算器を使った 32 ビット加算器 3 b 3 s 3 b b 下位から上位へ桁上げが伝播 s 順次桁上げ加算器 (ripple crry dder) s
加算 /AND/OR 対応 ビット ALU の設計 仕様 入力 :, b, ( 各 ビット ) 入力 :(2ビット) 出力 :y, ( 各 ビット ) 機能 AND か OR か 加算 b 2 ( 操作 ) y により操作 ( 出力 ) を決定 = とbの論理積 (AND) = とbの論理和 (OR) = とbとの加算 s
加算 /AND/OR 対応 32 ビット ALU の設計 3 b 3 b b 2 y 3 y y b 2 ( 操作 ) 加算 /AND/OR 対応 bitalu y
減算器の設計 () 減算 (b を引く )= 負数の加算 ( b を足す ) 2 の補数表現の場合, 符号を気にすることなく, 符号なし整数の加算とまったく同じ方法で減算できる. キャリー ) 2 () 29 () 73 ()
減算器の設計 (2) 2の補数表現による負数のビット表現の簡単な求め方 : 2 進数の と を反転する. 2 で得られた 2 進数をひとつカウントアップする. b を求めるには : b の と を反転する. 2 の結果に を加算する. 3 と2の結果を加算する. -b の 2 の補数表現を求める (-b) を計算する
加算 / 減算 /AND/OR 対応 ビット ALU の設計 入力 :, b, ( 各 ビット ) 入力 :(2ビット),neg(ビット) 出力 :y, ( 各 ビット ) 2 ( 操作 ) 機能 AND か OR か 加算 か 減算 により操作を決定 y = 論理積 (AND) = 論理和 (OR) = 加算または減算 negにより入力 bを反転するか否か決定 neg= 反転なし (AND/OR/ 加算 ) neg= 反転 ( 減算 ) b neg ( ビット反転 )
加算 / 減算 /AND/OR 対応 32 ビット ALU の設計 3 b 3 b b 2 neg =, neg= の時 (-b) を出力 y 3 y y b neg neg= は neg= は( つまり) 加算 / 減算 /AND/OR 対応 bitalu ( ビット反転 ) 2 ( 操作 ) neg= b neg= b の反転 y
オーバーフロー () オーバーフロー : 算術演算の結果が表現可能な値の範囲を超えること. 4bit 加算の場合 : 2 3 4 正 (~) 正 (~) ~ (~7) (~7) で結果は ~ 4. オーバーフローの可能性あり. 結果が (8)~(4) のとき (= 負のとき ), オーバーフロー. 正 (~) 負 (~) ~ (~7) ( 8~ ) で結果は 8~6. オーバーフローはない. 負 (~) 正 (~) ~ ( 8~ ) (~7) で結果は 8~6. オーバーフローはない. 負 (~) 負 (~) ~ ( 8~ ) ( 8~ ) で結果は 6~ 2. オーバーフローの可能性あり. 結果が ~ のとき (= 正のとき ), オーバーフロー.
オーバーフロー (2) 4bit 減算の場合 : 5 6 7 8 正 (~) 正 (~) 正 (~) 負 (~) と同じ. オーバーフローなし. 正 (~) 負 (~) 正 (~) 正 (~) と同じ. 結果が負のとき, オーバーフロー. 負 (~) 正 (~) 負 (~) 負 (~) と同じ. 結果が正のとき, オーバーフロー. 負 (~) 負 (~) 負 (~) 正 (~) と同じ. オーバーフローなし.
3 b 3 b b 2 neg オーバーフロー (3) y 3 y y 符号ビット b 3 b neg 加算 / 減算 /AND/OR 対応 bitalu( 最上位ビット ) 3 正 正 = 負, 負 負 = 正のときオーバーフロー発生 ( ビット反転 ) 2 ( 操作 ) y 3
オーバーフロー (4) 3 b 3 y 3 備考 正 正 = 正 /5 正ー負 = 正 正 正 = 負 /5 正ー負 = 負 2 正 負 = 負 /6 正ー正 = 負 2 正 負 = 正 /6 正ー正 = 正 3 負 正 = 負 /7 負ー負 = 負 3 負 正 = 正 /7 負ー負 = 正 4 負 負 = 正 /8 負ー正 = 正 4 負 負 = 負 /8 負ー正 = 負 ならばオーバーフロー
3 b 3 b b neg ( 操作 ) ( ビット反転 ) オーバーフロー (5) 2 ovf y 3 y y 加算 / 減算 /AND/OR 対応 bitalu( 最上位ビット ) b neg ovf: オーバーフロー出力 2 ( 操作 ) y 3 ( ビット反転 ) ovf
比較器 (slt:set-on-less-thn) の設計 MIPS での比較命令の例 slt $s, $s, $s2 レジスタ $s の値と $s2 の値を比較して,$s<$s2 であれば $s に値 を, そうでなければ値 を格納 ( 分岐条件の設定に利用 ) Yes $s < $s2 No $s $s ALUに要求される機能 32ビット入力 とbを比較比較結果に依存するの -b< か否かを判定は最下位ビットのみ 2 比較結果に基づきかを出力 <bの場合:32ビットの >=bの場合:32ビットの
3 b 3 b b 2 neg (=) 減算に基づく大小比較 () MSB 用 ovf y 3 y y 符号ビット b 3 b neg 加算 / 減算 /AND/OR 対応 bitalu( 最上位ビット ) 3 2 ( 操作 ) y 3 ( ビット反転 ) ovf 減算結果の符号に基づき判定 (-bの結果が負 <b) 減算におけるオーバーフローに注意
減算に基づく大小比較 (2) 3 b 3 3 b 3 y 3 ovf 備考 5 正ー負 = 正 5 正ー負 = 負 6 正ー正 = 負 ( < b) 6 正ー正 = 正 7 負ー負 = 負 ( < b) 7 負ー負 = 正 8 負ー正 = 正 ( < b) 8 負ー正 = 負 ( < b) オーバーフローが生じなくて (ovf = ), 結果が負 (y 3 =) < b オーバーフローが生じて (ovf =), 結果が正 (y 3 =) < b つまり ovf と y 3 が不一致の場合は <b
3 b 3 b b 2 neg (=) < b 時に となる出力信号 setを生成 ovf MSB 用 大小比較 y 3 set y y b neg ( ビット反転 ) 2 ( 操作 ) y 3 set ovf
3 b 3 slt(=) slt b slt(=) b neg ( 操作 ) 比較器の設計 ( 出力の生成 ) slt slt MSB 用 2 ovf set y 3 y y ( ビット反転 ) LSB 以外 : を出力 LSB: 比較結果に基づき/を出力 neg b slt neg b slt 2 ( ビット反転 ) 完成版 MSB 用 ビット ALU 2 ( ビット反転 ) ( 操作 ) ( 操作 ) y y set ovf 完成版一般用 ビット ALU
3 b 3 完成版 MSB 用 slt(=) slt ビットALU b 完成版一般用 slt(=) slt ビットALU b 完成版一般用 slt ビットALU 2 neg ( 操作 ) ( ビット反転 ) 完成版 32 ビット ALU ovf set y 3 y y ゼロ判定回路 zero 命令 ALU 制御信号 (3 ビット ) ( 操作 ) neg ( ビット反転 ) AND OR ADD SUB SLT
加算器の高速化 () 順次桁上げ加算器 (Ripple Crry Adder) 3 b 3 b c 3 c y 3 ビット数に比例して遅延が大きくなる. y b c y
加算器の高速化 (2) 真理値表 b c y c c = c b c b = ( b ) c b
加算器の高速化 (3) 32 個の各加算器の回路は同じであるので, c = c b c b = ( b ) c b c 2 = c b c b = ( b ) c b c 3 = 3 c 3 b 3 c 3 3 b 3 = ( 3 b 3 ) c 3 3 b 3 c 2 の右辺の c,c 3 の右辺の c 2, を順次置換すると, c 2 = (( b ) c b ) ( b ) b c がわからなくても,c から c 2 が求められる. c 3 = ((( b ) c b ) ( b ) b ) ( 2 b 2 ) 2 b 2 c 2 がわからなくても,c から c 3 が求められる. ビット数が増えるほど, 指数関数的に式が長くなる (= 回路が大きくなる ).
加算器の高速化 (4) g i = i b i,p i = i b i とすると, c = g p c c 2 = g p g p p c c 3 = g 2 p 2 g p 2 p g p 2 p p c c 4 = g 3 p 3 g 2 p 3 p 2 g p 3 p 2 p g p 3 p 2 p p c 4bit 桁上げ先見加算器 (Crry Look Ahed Adder) 3 ~ 4bit c 4 4 b 3 ~b 桁上げ先見 y 3 ~y 4 4 c 加算器
4bit 桁上げ先見加算器 (Crry Look Ahed Adder) 3 b 3 2 b 2 b c 3 c c g 3 p 3 g 2 p 2 g p 桁上げ先見ユニット加算器の高速化 (5) y 3 c 4 y 2 y b c g p y
加算器の高速化 (6) 32bit 加算器 3 ~ 28 b 3 ~b 28 4 4 4bit 桁上げ先見加算器 4 y 3 ~y 28 c 28 7 ~ 4 b 7 ~b 4 4 4 4bit 桁上げ先見加算器 まだ長い! 4 y 7 ~y 4 c 4 3 ~ 4 b 3 ~b 4 y 3 ~y 4 c 4bit 桁上げ先見加算器
加算器の高速化 (7) 8 個の各 4bit 桁上げ先見加算器の回路は同じであるので, c 4 = g 3 p 3 g 2 p 3 p 2 g p 3 p 2 p g p 3 p 2 p p c c 8 = g 7 p 7 g 6 p 7 p 6 g 5 p 7 p 6 p 5 g 4 p 7 p 6 p 5 p 4 c 4 c 32 = g 3 p 3 g 3 p 3 p 3 g 29 p 3 p 3 p 29 g 28 p 3 p 3 p 29 p 28 c 28 P = p 3 p 2 p p,p = p 7 p 6 p 5 p 4,,G = g 3 p 3 g 2 p 3 p 2 g p 3 p 2 p g,g = g 7 p 7 g 6 p 7 p 6 g 5 p 7 p 6 p 5 g 4, として,c 8 の右辺の c 4,c 2 の右辺の c 8, を順次置換すると, c 4 = G P c c 8 = G P G P P c c 2 = G 2 P 2 G P 2 P G P 2 P P c
32bit 桁上げ先見加算器 (Crry Look Ahed Adder) 3 ~ 28 b 3 ~b 28 c 28 c 8 7 ~ 4 4 b 7 ~b 4 4 c 4 4 4 G 7 P 7 G P ト加算器の高速化 (8) 4 4 桁上げ先見ユニッy 3 ~y 28 c 32 3 ~ b 3 ~b c G P y3~y y 7 ~y 4 4 4 4