算術論理演算ユニットの設計 （教科書4.5節） Created by Tsuneo Nakanishi, 2002-2004 算術論理演算ユニットALU（１） 一般的なコンピュータの内部構造 算術演算や論理演算 を実行する． デコーダ アドレスバス PC レジスタ ALU データバス 主記憶 ・ ・ ・ Created by Tsuneo Nakanishi, 2002-2004 算術論理演算ユニットALU（２） 算術論理演算ユニット（ALU: Arithmetic Logic Unit） 算術演算命令の処理 加算命令 減算命令 比較命令 論理演算命令の処理 AND命令 OR命令 XOR命令（今回は省略） シフト命令の処理（今回は省略） 基本部品： インバータ，AND／ORゲート，マルチプレクサ Created by Tsuneo Nakanishi, 2002-2004 AND回路の設計 AND演算（&）： オペランドのビットごとに AND をとる． 1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 a y b １ビットのAND回路 Created by Tsuneo Nakanishi, 2002-2004 OR回路の設計 OR演算（|）： オペランドのビットごとに OR をとる． 1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 a y b １ビットのOR回路 Created by Tsuneo Nakanishi, 2002-2004 加算回路の設計（１） １ビットの加算回路 1 0 +) 0 出力：上位桁桁上げ 1 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 入力：下位桁桁上げ （cin） 入力：足される数（a） 入力：足される数（b） （cout） 出力：和（y） a b cout 1bit 加算器 y cin Created by Tsuneo Nakanishi, 2002-2004 加算回路の設計（２） 1ビットの加算回路を使った32ビット加算器 a31 b31 cout + y31 cin ・ ・ ・ a1 b1 cout + y1 cin a0 b0 cout + y0 0 Created by Tsuneo Nakanishi, 2002-2004 加算回路の設計（３） 真理値表 a b cin y cout 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 Created by Tsuneo Nakanishi, 2002-2004 加算回路の設計（４） a b cin y 演習問題①： この論理回路を簡単化せよ．（復習） Created by Tsuneo Nakanishi, 2002-2004 加算回路の設計（５） a b cin cout 演習問題②： この論理回路を簡単化せよ．（復習） Created by Tsuneo Nakanishi, 2002-2004 加算／AND／OR対応 1bit ALU a b cout + 00 01 10 11 y cin 操作 2 Created by Tsuneo Nakanishi, 2002-2004 加算／AND／OR対応 32bit ALU cout a31 b31 +/AND/OR 対応 1bit ALU y31 cin ・ ・ ・ cout a1 b1 +/AND/OR 対応 1bit ALU y1 cin cout a0 b0 操作 +/AND/OR 対応 1bit ALU y0 cin 2 0 Created by Tsuneo Nakanishi, 2002-2004 減算回路の設計（１） 減算（b を引く）＝負数の加算（–b を足す） 2の補数表現をした場合，符号を気にすることなく，符号なし整数 の加算とまったく同じ方法で減算できる． キャリー 1 1 0 +) 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 102(10) –29(10) 73(10) Created by Tsuneo Nakanishi, 2002-2004 減算回路の設計（２） 2の補数表現による負数のビット表現の簡単な求め方: ① 2進数の 0 と 1 を反転する． 0000 0000 0000 0101 → 1111 1111 1111 1010 ② ①で得られた2進数をひとつカウントアップする． 1111 1111 1111 1010 → 1111 1111 1111 1011 a – b を求めるには: ① b の 0 と 1 を反転する． ② a と①の結果を加算する． ③ ②の結果に 1 を加算する． Created by Tsuneo Nakanishi, 2002-2004 減算回路の設計（３） cout a31 b31 +/AND/OR 対応 1bit ALU 0 1 cin 反転=0 のとき b をそ のまま出力，反転=1 のとき反転出力． a1 b1 ・ ・ ・ cout +/AND/OR 対応 1bit ALU 0 1 +/AND/OR 対応 1bit ALU 0 1 操作 反転 y1 cin cout a0 b0 y31 cin 2 cyin y0 加算のときキャリーイ ン=0，減算のときキャ リーイン=1とする． Created by Tsuneo Nakanishi, 2002-2004 加減算／AND／OR対応 1bit ALU a b cout 0 1 + 00 01 10 11 y cin 反転 操作 2 Created by Tsuneo Nakanishi, 2002-2004 オーバーフロー（１） オーバーフロー: 算術演算の結果がレジスタに格納可能な範囲の 数を超えること． ４bit 加算の場合： ① 正（0000～0111） + 正（0000～0111） → 0000～1110 (0～7) + (0～7) で結果は 0 ～ 14．オーバーフローの可能性あり． 結果が 1000(8)～1110(14) のとき（＝負のとき），オーバーフロー． ② 正（0000～0111） + 負（1000～1111） → 1000～0110 (0～7) + (–8～–1) で結果は –8～6．オーバーフローはない． ③ 負（1000～1111） + 正（0000～0111） → 1000～0110 (–8～–1) + (0～7) で結果は –8～6．オーバーフローはない． ④ 負（1000～1111） + 負（1000～1111） → 0000～1110 (–8～–1) + (–8～–1) で結果は –16～–2．オーバーフローの可能性あり． 結果が 0000～0111 のとき（＝正のとき），オーバーフロー． Created by Tsuneo Nakanishi, 2002-2004 オーバーフロー（２） ４bit 減算の場合： ⑤ 正（0000～0111） – 正（0000～0111） 正（0000～0111） + 負（1000～1111） と同じ．オーバーフローなし． ⑥ 正（0000～0111） – 負（1000～1111） 正（0000～0111） + 正（0000～0111） と同じ． 結果が負のとき，オーバーフロー． ⑦ 負（1000～1111） – 正（0000～0111） 負（1000～1111） + 負（1000～1111） と同じ． 結果が正のとき，オーバーフロー． ⑧ 負（1000～1111） – 負（1000～1111） 負（1000～1111） + 正（0000～0111） と同じ．オーバーフローなし． Created by Tsuneo Nakanishi, 2002-2004 オーバーフロー（３） a31’ a31 b31 0 1 b31’ cout +／AND／OR 対応 1bit ALU cin ・ ・ ・ cout a1 b1 +／AND／OR 対応 1bit ALU 0 1 +／AND／OR 対応 1bit ALU 0 1 操作 反転 オーバーフローはここ で検査できる． y1 cin cout a0 b0 y31 y0 cin 2 cyin Created by Tsuneo Nakanishi, 2002-2004 オーバーフロー（４） a31’ b31’ cin y31 cout 備考 0 0 0 0 0 ①正＋正＝正／⑤正ー負＝正 0 0 1 1 0 ①正＋正＝負／⑤正ー負＝負 0 1 0 1 0 ②正＋負＝負／⑥正ー正＝負 0 1 1 0 1 ②正＋負＝正／⑥正ー正＝正 1 0 0 1 0 ③負＋正＝負／⑦負ー負＝負 1 0 1 0 1 ③負＋正＝正／⑦負ー負＝正 1 1 0 0 1 ④負＋負＝正／⑧負ー正＝正 1 1 1 1 1 ④負＋負＝負／⑧負ー正＝負 cin cout ならばオーバーフロー Created by Tsuneo Nakanishi, 2002-2004 オーバーフロー（５） a31’ a31 b31 0 1 b31’ ovf cout +／AND／OR 対応 1bit ALU y31 cin cout a1 b1 +／AND／OR 対応 1bit ALU 0 1 cin cout a0 +／AND／OR 対応 1bit ALU 0 b0 1 操作 反転 y1 y0 cin 2 cyin Created by Tsuneo Nakanishi, 2002-2004 最上位ビット専用 1bit ALU a b 0 1 + 00 01 10 11 y cin 反転 操作 yout 2 ovf Created by Tsuneo Nakanishi, 2002-2004 slt 回路の設計（１） a31’ a31 b31 0 1 b31’ +／AND／OR対応 1bit ALU （最上位用） cin ・ ・ ・ cout a1 b1 +／AND／OR 対応 1bit ALU 0 1 +／AND／OR 対応 1bit ALU 0 1 操作 反転 a < b ⇔ a – b < 0． ゆえに a – b の結果 の符号から，a < b が 検査できる． y1 cin cout a0 b0 ovf y31 yout y0 cin 2 cyin Created by Tsuneo Nakanishi, 2002-2004 slt 回路の設計（２） a31’ b31’ cin 0 0 0 0 0 ⑤正ー負＝正 0 0 1 1 0 ⑤正ー負＝負 0 1 0 1 0 ⑥正ー正＝負（a < b） 0 1 1 0 1 ⑥正ー正＝正 1 0 0 1 0 ⑦負ー負＝負（a < b） 1 0 1 0 1 ⑦負ー負＝正 1 1 0 0 1 ⑧負ー正＝正（a < b） 1 1 1 1 1 ⑧負ー正＝負（a < b） yout cout 備考 オーバーフローが生じなくて（ovf=0），結果が負（y31=1） → a < b（sltf = 1） オーバーフローが生じて（ovf =1），結果が正（y31=0） → a < b（sltf = 0） Created by Tsuneo Nakanishi, 2002-2004 slt 回路の設計（３） a31 b31 0 1 b31’ sltf ovf a31’ +／AND／OR対応 1bit ALU （最上位用） yout y31 cin cout a1 b1 +／AND／OR 対応 1bit ALU 0 1 cin cout a0 +／AND／OR 対応 1bit ALU 0 b0 1 操作 反転 y1 y0 cin 2 cyin Created by Tsuneo Nakanishi, 2002-2004 完全版最上位ビット専用 1bit ALU a b 0 1 + 00 01 10 11 y cin slt 反転 操作 sltf 2 ovf Created by Tsuneo Nakanishi, 2002-2004 完全版一般用 1bit ALU a b cout 0 1 + 00 01 10 11 y cin slt 反転 操作 2 Created by Tsuneo Nakanishi, 2002-2004 完全版 32bit ALU（１） sltf a31 b slt=0 31 完成版 最上位ビット専用 1bit ALU y31 命令 反転 操作 cyin cin ・ ・ ・ cout a1 b slt=0 1 完成版 一般ビット用 1bit ALU y1 cin cout a0 完成版 一般ビット用 1bit ALU b0 反転 操作 cyin ovf AND 0 00 * OR 0 01 * ＋ 0 10 0 ー 1 10 1 slt 1 10 1 y0 cin 2 Created by Tsuneo Nakanishi, 2002-2004 完全版 32bit ALU（２） sltf a31 b slt=0 31 完成版 最上位ビット専用 1bit ALU y31 命令 反転 操作 cyin cin ・ ・ ・ cout a1 b slt=0 1 完成版 一般ビット用 1bit ALU y1 cin cout a0 完成版 一般ビット用 1bit ALU b0 操作 反転 ovf AND 0 00 * OR 0 01 * ＋ 0 10 0 ー 1 10 1 slt 1 10 1 y0 cin 2 Created by Tsuneo Nakanishi, 2002-2004 完全版 32bit ALU（３） sltf a31 b slt=0 31 完成版 最上位ビット専用 1bit ALU y31 cin ・ ・ ・ cout a1 b slt=0 1 完成版 一般ビット用 1bit ALU y1 cin cout a0 完成版 一般ビット用 1bit ALU b0 2 ALU制御 cin y0 ovf 命令 ALU制御 AND 000 OR 001 ＋ 010 ー 110 slt 111 結果が 0 のときに 1．減算の結果に 適用して，等不等 の検査ができる． 3 Created by Tsuneo Nakanishi, 2002-2004 加算器の高速化（１） 順次桁上げ加算器（Ripple Carry Adder） a31 b31 cout cin c31 + y31 ビット数に比例して 遅延が大きくなる． ・ ・ ・ a1 b1 cout cin a0 b0 c1 + y1 cout c0 + y0 Created by Tsuneo Nakanishi, 2002-2004 加算器の高速化（２） 真理値表 a0 b0 c0 y c1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 c1 = a0・c0 + b0・c0 + a0・b0 = (a0 + b0)・c0 + a0・b0 Created by Tsuneo Nakanishi, 2002-2004 加算器の高速化（３） 32個の各加算器の回路は同じであるので， c1 = a0・c0 + b0・c0 + a0・b0 = (a0 + b0)・c0 + a0・b0 c2 = a1・c1 + b1・c1 + a1・b1 = (a1 + b1)・c1 + a1・b1 … c31 = a31・c31 + b31・c31 + a31・b31 = (a31 + b31)・c31 + a31・b31 c2 の右辺の c1，c3 の右辺の c2，…を順次置換すると， c2 = ((a0 + b0)・c0 + a0・b0)・(a1 + b1) + a1・b1 c1 がわからなくても，c0 から c2 が求められる． c3 = (((a0 + b0)・c1 + a0・b0)・(a1 + b1) + a1・b1)・(a2 + b2) + a2・b2 c2 がわからなくても，c0 から c3 が求められる． … ビット数が増えるほど，指数関数的に式が長くなる（＝回路が大きくなる）． Created by Tsuneo Nakanishi, 2002-2004 加算器の高速化（４） gi = ai・bi，pi = ai + bi とすると， c1 = g0 + p0・c0 c2 = g1 + p1・g0 + p1・p0・c0 c3 = g2 + p2・g1 + p2・p1・g0 + p2・p1・p0・c0 c4 = g3 + p3・g2 + p3・p2・g1 + p3・p2・p1・g0 + p3・p2・p1・p0・c0 4bit 桁上げ先見加算器（Carry Look Ahead Adder） a3～a0 4 b3～b0 4 c0 4bit 桁上げ先見 加算器 c4 4 y3～y0 Created by Tsuneo Nakanishi, 2002-2004 加算器の高速化（５） 4bit 桁上げ先見加算器（Carry Look Ahead Adder） a3 b3 a2 b2 a1 b1 a0 b0 c0 c3 c1 c1 + y3 c4 g3 p3 + g2 p2 + g1 p1 + g0 p0 桁 上 げ 先 見 ユ ニ ッ ト y2 y1 y0 Created by Tsuneo Nakanishi, 2002-2004 加算器の高速化（６） 32bit 加算器 a31～a28 b31～b28 4 4 4bit 桁上げ先見 加算器 4 y31～y28 c28 まだ長い！ ・ ・ ・ a7～a4 b7～b4 4 4 4bit 桁上げ先見 加算器 4 y7～y4 4 4 4bit 桁上げ先見 加算器 4 y3～y0 c4 a3～a0 b3～b0 c0 Created by Tsuneo Nakanishi, 2002-2004 加算器の高速化（７） 8個の各4bit桁上げ先見加算器の回路は同じであるので， c4 = g3 + p3・g2 + p3・p2・g1 + p3・p2・p1・g0 + p3・p2・p1・p0・c0 c8 = g7 + p7・g6 + p7・p6・g5 + p7・p6・p5・g4 + p7・p6・p5・p4・c4 … c32 = g31 + p31・g30 + p31・p30・g29 + p31・p30・p29・g28 + p31・p30・p29・p28・c28 P0 = p3・p2・p1・p0，P1 = p7・p6・p5・p4，…，G0 = g3 + p3・g2 + p3・p2・g1 + p3・ p2・p1・g0， G1 = g7 + p7・g6 + p7・p6・g5 + p7・p6・p5・g4，…として，c8 の右辺の c4，c12 の右辺の c8，…を順次置換すると， c4 = G0 + P0・c0 c8 = G1 + P1・G0 + P1・P0・c0 c12 = G2 + P2・G1 + P2・P1・G0 + P2・P1・P0・c0 … Created by Tsuneo Nakanishi, 2002-2004 加算器の高速化（８） 32bit 桁上げ先見加算器（Carry Look Ahead Adder） a31～a28 b31～b28 4 4 + 4 G7 P7 y31～y28 c32 c28 ・ ・ ・ c8 a7～a4 b7～b4 4 4 + G1 P1 + G0 P0 c4 a3～a0 b3～b0 c0 4 4 桁 上 げ 先 見 ユ ニ ッ ト 4 y7～y4 4 y3～y0 Created by Tsuneo Nakanishi, 2002-2004
© Copyright 2024 ExpyDoc
