1 - 情報メディア学科演習室

本日の内容
コンピュータアーキテクチャと
機械語演習
加算器とその高速化
z 乗算器・除算器
z
3年次前期（第12回）
中島克人
情報メディア学科
[email protected]
1
1ビット加算器
z
z
1ビット加算器
半加算器（HA: Half Adder）
A
0
0
1
1
B
0
1
0
1
S
0
1
1
0
C
0
0
0
1
A
2進数1ビット
の加算
A
+ B
CS
B
HA
C S
S : 和（Sum）
C : 桁上げ
（Carry）
全加算器（FA: Full Adder）
A
0
0
1
1
B
0
1
0
1
Ci S
0 0
0 1
0 1
0 0
Co
0
0
0
1
2
A
0
0
1
1
B
0
1
0
1
Ci S
1 1
1 0
1 0
1 1
Co
0
1
1
1
2進数1ビット
（途中桁）
の加算
‥ Ai
+ ‥ Bi
Co Ci
‥ Si
z半加算器のAND／OR回路
Ai-1
Bi-1
‥
‥
A
0
0
1
1
Ci : Carry-in
S : 和（Sum）
Co : Carry-out
A
B
0
1
0
1
C
0
0
0
1
B
0
1
0
1
Ci S
0 0
0 1
0 1
0 0
Co
0
0
0
1
●
A
0
0
1
1
B
B
0
1
0
1
Ci S
1 1
1 0
1 0
1 1
Co
0
1
1
1
Ci
●
●
●
●
A
0
0
1
1
A
B
●
B Ci
FA
Co S
S
0
1
1
0
z全加算器のAND／OR回路
●
●
●
●
●
●
●
●
●
●
A
C
3
S
Co
S
4
Nビット加算器
Nビット加算器
z
全加算器（1ビット）をカスケード（＝縦つなぎ）接続して
構成した Nビット加算器が構成できる
z 4ビットの例（Ripple Carry Adder）
z
A 0 1 1 0
B 0 1 0 0
16bit 加算器（Ripple Carry Adder）
A(16bit)
16
Ci = 0
4
4
A
B
Ci
Co
Co
Co = 0
B
FA
S
1
Ci
A
Co
B
FA
Ci
S
A
B
FA
Co
Ci
A
S
0
B
Ci
FA
Co
4
S
1
4ビット加算器
4ビット加算器の改良
z
Ci
●
●
●
●
Co
Ci
A
4
B
●
●
Ci
4
A
B
Ci
4bit Adder
4bit Adder
4bit Adder
Co
Co
Co
S
4
S
4
S
4
16bit Ripple Carry Adder
z
クリティカル・パス（最大通過ゲート数）は AND・ORゲート換算で
何段か？
6
4ビット加算器の改良
●
●
●
B
4
問題点は？… Carryの伝播時間が大きい
●
z
桁上げ予見（Carry Look-ahead）
ci+1 = ai･bi + ai･ci + bi･ci
= ai･bi + (ai + bi)･ci
= gi + pi･ci
B
●
A
4
z
5
●
4
Co = 0
0
A
S
Ci = 0
16
4
4bit Adder
A
B(16bit)
4-bit CLA（Carry Look-ahead）
S
C4
= g3 + p3･g2 + p3･p2･g1 + p3･p2･p1･g0 + p3･p2･p1･c0
.... どれか 2つが 1だとCarryが上がる
ci+1
( ただし、 gi = ai･bi (Carry Generation),
pi = ai + bi (Carry Propagation) )
g3
ai
bi ci
FA
co s
C4
a2
b2
ci
a1
b1
= gi + pi･( gi-1 + pi-1･ci-1 )
= gi + pi･gi-1 + pi･pi-1･( gi-2 + pi-2･ci-2 )
= gi + pi･gi-1 + pi･pi-1･gi-2 + pi･pi-1･pi-2･gi-2 + …
4-bit CLA
7
P3
P2
P1
a3
b3
a3
b3
a2
b2
a1
b1
a0
b0
C0
8
Nビット減算器
16ビット加算器の改良
z
16bit 加算器（Carry Look Ahead Adder）
z 16bit減算器
桁上げ予見回路を付加することで大幅に動作速度向上
A12～15 B12～15
A8～11 B8～11
A4～7 B4～7
●
●
A15～0
●
●
－
A－B ＝ A＋（－B ）＝ A＋（B＋１）
A0～3 B0～3 C0
●
●
●
２の補数
B15～0
16
●
A B C12
4bit CLA
C16
A
B
A B C8
4bit CLA
C12
A B C4
4bit CLA
C8
A B C0
4bit CLA
C4
●
●
●
C12
A
B
C8
4bit Adder
4bit Adder
C16
C12
S
S
A
B
C4
4bit Adder
C8
C0 = 1
●
S
16
－
B
A
B
A
C0
S
Ci
16bit FA
S
4bit Adder
C4
B
Co
16
C16
S12～15
S8～11
S4～7
S0～3
9
加算器のまとめ
z
乗算器
加算器
z
– Ripple Carry Adder
全加算器（Full Adder／FA）をカスケード（＝縦つなぎ）接続すれば任意
のビット数の加算器が構成可能だが，最下位ビットのFAの桁上げ（C1）
が最上位ビット結果（Sn-1,Cn）に反映されるまで時間がかかる（多くのゲ
ートを通過）
– Carry Look Ahead Adder
原理
– 被乗数をシフトしながら加算する
– ただし、乗数の1の立っているビット位置だけ加算する
– 被乗数および乗数の桁数を nビットとすると積は 2nビット
1101
× 1001
1101
0000
0000
1101
1110101
4ビット程度ずつまとめて桁上げ予見器（Carry Look-ahead）で桁上が
り情報を上位ビットに伝える事で，最大通過ゲート数（クリティカル・パス）
を削減し，加算器の動作を高速化できる
z
10
減算器
– 2の補数は，ビット反転して最下位ビットに1を加えて作れる
– 加算器をベースに簡単に構成可
– B入力をビット反転し，最下位ビットのC0入力を1とする
正整数での例
11
被乗数
乗数
被乗数レジスタ（D）
２n ビット
初期値
0
step 1
左シフト
step 2
ゲート
n ビット
LSB
step 3
step 4
乗数レジスタ
（R）
右シフト
２n ビット加算器
コントロール
積
積レジスタ（P）
1
／
２n ビット
12
乗算器（高速乗算その1）
乗算器（高速乗算その1）
z
z
ブースの方法（Booth Recoding） ... 部分積加算回数の削減
– 連続する「1」を1回の加算と1回の減算に置き換える（Booth Recoding)
– bit(i+1) と bit(i) をまとめて bit(i) の位置で表現
– アルゴリズム: 連続する「1」を1回の加算と1回の減算に置き換える
bit位置 → i
j
i
j
i
j
乗数 011 .... 110 .... = ＋100 .... 000 .... = 100 .... 010 ...
－000 .... 010 ....
連続する「1」
例：乗数 00110111 = 5510
– 後ろのビット（i－1番目）を見つつ、コードし直す（ブースリコーディング）
– 2ビットずつリコーディングする（改良ブースリコーディング）と2ビット当り
高々1回の加減算で済むことが分かる
4進
乗数ビット
コード化後のビット
→ 部分積加算の回数が半分！ i+1 i i -1
i+1
i
表現
乗数ビットコード化後の
i i－1
ビット i
0
0
1
1
0
1
0
1
0
＋1
－1
0
2ビットずつ
リコーディング
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
ブースリコーディング
0
1
0
1
0
1
0
1
0
0
0
＋1
－1
0
0
0
0
＋1
＋1
0
0
－1
－1
0
= 01011001 = 6410－1610＋810－110
= 01010201
0
＋1
＋1
＋2
－2
－1
－1
0
改良ブースリコーディング
この2段階の操作を一度に行うに
は右表を使用
乗数 00110111 0
通常の乗算
01011
× 0 1 0 1 0 = （8－2）10
0
00000000
－1
1110101
0
000000
＋1
01011
01000010
Booth Recodingでの乗算
乗数ビット
i+1 i i -1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
コード化後のビット
i+1
i
0
0
0
＋1
－1
0
0
0
0
＋1
＋1
0
0
－1
－1
0
4進表現
i
0
＋1
＋1
＋2
－2
－1
－1
0
改良Booth Recoding変換表
14
乗算器（高速乗算その1）
１１10×610＝6610
01011
× 00110
00000000
0001011
001011
00000
01000010
= 01010201
13
乗算器（高速乗算その1）
z例：
改良Booth Recoding ... 部分積加算回数の半減
01011
× 0 2 2 = （8－2）10
1 1 1 0 1 0 1 0 －2
＋2
010110
0
0000
01000010
改良Booth Recoding（基数4）
での乗算
z演習：
6bitの2進数乗算 0011012×0011102 を下記の変換表を
用いて改良Booth Recording（基数4）で計算せよ
z解答：
変換表により
乗数 001110 0
= 010002
故に
0 0 1 1 0 1 = （13）10
× 1 0 2 = （16－2）10
1 1 1 1 1 1 1 0 0 1 1 0 ... －2
... 0
0000000000
... ＋1
00001101
•Booth Recodingでは加減算回数が増える可能性がある（010101→111111）
•改良Booth Recoding（2ビットずつ→基数4）では最大でも N／2（N:乗数桁数）
•部分積用加算回路で（0、＋1、－1、＋2、－2）倍の機能を
持たせるのは容易 ← どう構成する？
15
0 0 0 0 1 0 1 1 0 1 1 0 = （182）10
乗数ビット
i+1 i i -1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
コード化後のビット
i+1
i
0
0
0
＋1
－1
0
0
0
0
＋1
＋1
0
0
－1
－1
0
4進表現
i
0
＋1
＋1
＋2
－2
－1
－1
0
改良Booth Recoding変換表
16
乗算器（高速乗算その2）
乗算器（高速乗算その2）
z
部分積の加算を一度に行う
z
– 3入力1bitのCSA：1bit FA（Full Adder）と同じ
– 4入力CSA（Nbit）：1bit当り FAを2個使用（下図）
– 最終段だけ通常の加算器（Carry Look-ahead Adder等）が必要
加算の途中結果は2進表現でなくても良いので桁上げ
保存加算器（CSA：Carry Save Adder）を用いる
4入力加算器の改良例
4入力加算器の例
A
B
C
＋
D
B
C
CSA
＋
＋
A
桁上げ伝播
が2回
CSA
Carry
4入力 CSA
– 除数を右シフトしながら
被除数から減算する
– ただし、減算して負にな
ると加算して戻す（加え
戻し）
– 被除数は 2nビット、
除数および商は nビット
ai
ai
bi ci
co
CSAでは
桁上げは
斜め左に伝播
● ● ●
s
ai
bi ci
bi ci
FA
FA
co
bi ci
FA
co
s
ai
● ● ●
co
s
● ● ●
s
bi
ai
bi
CLA：Carry Look-ahead Adder
桁上げ伝播
が1回
s
Carry と Sum を別々に計算
し、最後に両者を加算
除算器
原理（加え戻し法）
A B C D
FA
Sum
第n+1ビット
17
z
A B C D
ai
＋
通常の加算器を積み
重ねると、桁上げ伝播
時間が多く必要
D
桁上げ保存加算器（CSA：Carry Save Adder）
s
Booth Recoding、
改良Booth
Recodingと組合せ
可能！！
第nビット
18
除算器
除数
0 1 0 1 ） 0 1 1 1 0 1 0 1 ... 被除数
... 1
－ 0101
0100101
－0101
11111101
... 0
＋0101
0100101
... 1
－ 0101
10001
... 1
－ 0101
0111
... 1
－ 0101
余り 0 0 1 0 商 1 0 1 1 1
z
原理（引き放し法）
0101）01110101
－ 0101
– 除数を右シフトしながら被
0 1 0 0 1 0 1 ... 1
除数から減算する
－0101
– ただし、減算して負になる
1 1 1 1 1 1 0 1 ... 0
と加え戻しは省略し、次の
＋ 0101
ステップで減算の代りに加
算する
10001
... 1
－ 0101
何故なら、
0111
... 1
＋除数×2k－除数×2k-1
－0101
＝＋除数×2k-1
0010
... 1
余り0 0 1 0 商1 0 1 1 1
（ただし、余りが負になれば
、加え戻しが必要）
正整数での例
19
20
乗算器と除算器のまとめ
除算器（引き放し法）
z
z
回路構成
レジスタＲ：
R≧0
n ビット
商0/1セット
＋
－
Rをテスト
Rを左シフトし、最下位を
1 に、Fを 0 にセット
＋／－指示
除数
n ビット
– 乗数のｎビット連続する１を、n+1ビット目の +1 と１ビット目の -1に置き
かえる（そのためのビットごとのコーディングが booth recoding）
– 改良booth recoding
– ２ビットずつ、 +2, +1, 0, -1, -2 のどれかにコーディングする
– これにより、部分積の加算回数が乗数のビット数の半分になる
R＜0
– 部分積の加算に必要な多入力加算器には、Carry Save
Adder が用いられる
Rを左シフトし、最下位を
0 に、Fを 1 にセット
z
コントロール
レジスタＤ
符号ビット
桁数回
終了？
除算器
– 加え戻し法
NO
– 被除数から除数を引いて余りの符号が反転したら、除数を加え戻す
YES
– 引き放し法
Rを右にシフトする
もしFが 1 なら Rに Dを加算
End
乗算器
– booth recoding
DをRの左半分から
減算（F=0）または加算（F=1）
左シフト
n ビット
z
Start：被除数をレジスタR にセット
除数をレジスタＤにセット
フラグF を 0 にセット
商（下位）
余り（上位）
初期値：被除数
アルゴリズム
– 被除数から除数を引いて余りの符号が反転したら、除数を加え戻す代
わりに、次の桁（1ビット右シフトした位置）で除数を加える
21
22

Download Report